The length of the interval of indeterminacy for the estimate of multiple change-points
This article considers the problem of estimating the length of the interval of indeterminacy during construction of change-points' estimates using dynamical programming. It was proved that mathematical expectation of the length of the interval has asymptotically linear dependency on the penalty...
Saved in:
| Date: | 2007 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/4494 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | The length of the interval of indeterminacy for the estimate of multiple change-points / G. Shurenkov // Theory of Stochastic Processes. — 2007. — Т. 13 (29), № 1-2. — С. 251-266. — Бібліогр.: 8 назв.— англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859493379021209600 |
|---|---|
| author | Shurenkov, G. |
| author_facet | Shurenkov, G. |
| citation_txt | The length of the interval of indeterminacy for the estimate of multiple change-points / G. Shurenkov // Theory of Stochastic Processes. — 2007. — Т. 13 (29), № 1-2. — С. 251-266. — Бібліогр.: 8 назв.— англ. |
| collection | DSpace DC |
| description | This article considers the problem of estimating the length of the interval of indeterminacy during construction of change-points' estimates using dynamical programming. It was proved that mathematical expectation of the length of the interval has asymptotically linear dependency on the penalty for a change of distribution when the number of estimations tends to infinity.
|
| first_indexed | 2025-11-24T21:03:13Z |
| format | Article |
| fulltext |
ΞN =
{
ξN
1 , . . . , ξN
N
}
N ≥ 1
{ξN
1 , . . . , ξN
N } = {ξ1, . . . , ξN}
{F1, . . . , FK} P(ξj ∈
A) = Fh0
j
(A) h0 = {h0
j , j = 1, . . . , N}
h0
j ∈ {1, . . . , K} h0
j = const
kj = [θiN ] < j ≤ [θi+1N ] 0 = θ0 < θ1 < . . . < θR < θR+1 = 1
kj
h
h0 {ξ1, . . . , ξN}
Γ = {1, . . . , K}
φ(·, j):R �→ R, j ∈ Γ.
φ
HN = {(h1, ..., hN) | hj ∈ Γ, j = 1, ..., N} , H =
⋃
N
HN .
J :H �→ R
h ∈ Hn
J(h) =
n∑
i=1
(φ(ξi, hi) − πN(hi, hi−1)), πN(g, l) = πN 1g �=l,
πN > 0
ĥ = argmax
h∈HN
J(h).
h0
ĥ
k̂1 = k1(ĥ) = min
{
l | ĥl �= ĥj, 1 ≤ j < l
}
k̂i = ki(ĥ) = min
{
l | ĥl �= ĥj , ki−1(ĥ) ≤ j < l
}
i ĥ
ĥ i
g h J(h) = J(g)
ĥ
θ̄ = mini�=j |θi − θj |,
φki(x) = φ(x, k) − φ(x, i).
ĥ
gj(l) = argmax
h={h0,...,hj−1,hj},hj=l
J(h), l ∈ Γ
gj+1
j (l) = argmax
i∈Γ
(
J(gj(i)) + φ(ξj+1, l) − πN(i, l)
)
,
ĥ = argmax
h=hN(l),l∈Γ
J(h).
ĥu = argmax
h=gu(l),l∈Γ
J(h)
gj(l)
s
χ(s) = min
{
t > s | gt
s(i) = gt
s(1), i ∈ Γ
}
.
χ(s)
s Δχ(s) = χ(s)−s
χ(s, k) = min{t > s | gt
s(i) = k, i ∈ Γ}, k ∈ Γ,
χ(s) = min
k∈Γ
χ(s, k).
i t
gt+1(i)
h g
J(h) > J(g)
i t J(gt(i)) >
J(gt(j)), j ∈ Γ, j �= i i
t J(gt(i)) ≥ J(gt(j)), j ∈ Γ
t
ĥt
α ∈ R i α
t
J(gt(i)) > J(gt(j)) − α, j ∈ Γ, j �= i.
i α t
J(gt(i)) ≥ J(gt(j)) − α, j ∈ Γ, j �= i.
α t Ot
α
Pk(·) ξ1, . . . ξN
Fk Ek
κ = mini�=j Eφji(ζj) > 0, ζj
Fj
φji(ζj) ≤ C < ∞, i, j ∈ Γ
Dφji(ζj) < σ2 < ∞, i, j ∈ Γ
φ(x, j) ξ1, . . . ξN
wki
0 = wki
0 (t0) = t0, w
ki
1 (t0) = min
{
t > t0 | max
t0<u≤t
∑u
j=t0+1 φki(ξj) > πN
}
wk
0 = wk
0(t0) = t0, wki
l (t0) = wki
l (t0) = wki
1 (wk
l−1(t0))
wk
l = wk
l (t0) = wk
l (t0) = maxi�=k wki
l (t0)
vk
l = vk
l (t0) = vk
l (t0) = wk
3l(t0)
E = {E(t1, t2) | t1 < t2} ,
E(t1, t2) =
{
min
i�=k
min
t1<l1≤l2≤t2
l2∑
j=l1
φki (ξj) > −πN
2
}
, t1 < t2
vk
E = vk
E(t0) = vk
E(t0, φ) = min{vk
1(t) | E(s, vk
1(s)) , t ≥ t0}
ṽk
E = ṽk
E(t0) = ṽk
E(t0, φ) = min{vk
l (t0)|E(vk
l−1, v
k
l ) }
vk
E(t0) ≤ ṽk
E(t0)
t0
χ(s) ≤ min
k∈Γ
vk
E(t0), t0 ≥ s.
EΔχ(t) ≤ 6(πN + C)(K − 1)(1 + θ−1)
C1κ
,
C1 = 1 − 48σ2(K − 1)2
πN
πN + C
πNκ
.
∃u 0 ≤ u ≤ t gt(k) =
{
ĥu
1 , . . . ĥ
u
u, k, . . . , k
}
{k, . . . , k}
u + 1 gt(k)
h′ = {gt
1(k), . . . , gt
u(k)}
h′′ =
{
ĥu
1 , . . . ĥ
u
u, k, . . . , k
}
gt(k)
J(gt(k)) = J(h′) − πN +
t∑
j=u+1
φ(ξj, k) < J(ĥu) − πN +
t∑
j=u+1
φ(ξj, k) = J(h′′).
k gt(k)
t
t
k t J(ĥt
t) = J(gt(k))
gt+1(k)
g̃t(k) =
{
gt+1
1 (k), ..., gt+1
t (k)
}
, g̃t+1(k) =
{
gt
1(k), ..., gt
t(k), k
}
.
gt+1(k) g̃t+1(k) gt+1(k) g̃t+1(k)
J(gt+1(k)) ≥ J(g̃t+1(k)) = J(gt(k)) + φ(ξt+1, k).
J(gt+1(k)) = J(g̃t(k)) − πN + φ(ξt+1, k).
gt+1(k) k
t
J(gt(k)) ≥ J(g̃t(k)).
0 ≥ J(g̃t(k)) − J(gt(k)) = J(gt+1(k)) − J(g̃t+1(k)) + πN ≥ πN .
i t
J
(
ĥt
)
− J
(
gt(i)
)
> πN
i t
gt(i) �= ĥt J(gt(i)) < J(ĥt)
gt+1(i) {gt
1(i), . . . , g
t
t(i), i}
J(gt+1(i)) = J(ĥt) − πN + φ(ξt+1, i) > J(gt(i)) + φ(ξt+1, i)
J(ĥt) − J(gt(i)) > πN .
gt+1(i)
g̃t+1(i) =
{
ĥt
1, ..., ĥ
t
t, i
}
.
gt+1(i)
J(g̃t+1(i))− J(gt+1(i)) = J(ĥt)− πN + φ(ξt+1, i)− J(gt(i)) − φ(ξt+1, i) > 0.
gt+1(i) t
i i t
t
πN
i, k ∈ Γ, i �= k, t > t0, t0 ≤ u < t, x ∈ R α, αu ∈ [0, πN ]
Ctu
ki (x, α) =
{∑t
j=u+1 φki(ξj) > α − πN + x, k ∈ Ou
α
}
,
Dtu
ki(x) =
{∑t
j=u+1 φki(ξj) > x
}
.
⋂
t0≤u<t
(
Ctu
ki (x, αu) ∪ Dtu
ki(x)
) ∩ Dtt0
ki (πN + x)
J
(
gt(k)
)− J
(
gt(i)
)
> x
gt(i) t0 t
u gt(i)
k α u − 1
t∑
j=u
φki (ξj) > x − πN + α.
gu(i)
J(gu(i)) ≤ J(gu−1(k)) − πN + α + φ(ξu, i)
u − 1 i k α
α ≥ 0
J(gu−1(k)) +
t∑
j=u
φ(ξj, k) − J(gu(i)) −
t∑
j=u+1
φ (ξj, i) > x.
J(gt(k)) ≥ J(gu−1(k)) +
∑t
j=u φ(ξj, k)
J
(
gt(k)
)− J (gu(i)) −
t∑
j=u+1
φ (ξj, i) > x.
t∑
j=u
φki (ξj) > x.
J(gu(k)) ≥ J(ĥu−1) − πN + φ(ξu, k), J(gu(i)) = J(ĥu−1) − πN + φ(ξu, i).
J (gu(k)) +
t∑
j=u+1
φ (ξj , k) − J(gu(i)) −
t∑
j=u+1
φ(ξj, i) > x
J(gt(k)) − J(gu(i)) −
t∑
j=u+1
φ(ξj, i) > x
gt(i) [t0, t]
t∑
j=t0+1
φki (ξj) > πN + x
J(gt(k)) ≥ J(gt0(i)) +
∑t
j=t0+1 φ(ξj, k) − πN
J(gt(k)) − J(gu(i)) −
t∑
j=u+1
φ(ξj, i) > x.
k [t0, w
k
1(t0)]
gwk
1 (t0)(i) k i
k t0 J(gt0(k)) −
J(gt0(i)) > 0 i �= k
wki
1 (t0)∑
j=t0+1
φki(ξj) > πN .
(t0, w
k
1(t0)]
g̃(i) =
{
gt0
1 (k), . . . gt0
t0 (k), k, . . . , k, i, . . . i
}
,
k i wk
1(t0)
ḡ(i) =
{
gt0
1 (i), . . . gt0
t0 (i), i, . . . i
}
.
J(g̃(i)) − J(ḡ(i)) = J(gt0(k)) − J(gt0(i)) +
wki
1 (t0)∑
j=t0+1
φki(ζj) − πN > 0.
gwk
1 (t0)(i) i
(t0, w
k
1(t0)]
gwk
1 (t0)(i)
k i
t0
χ(s, k) ≤ vk
E(t0), t0 ≥ s.
E(vk
l−1(t0), v
k
l (t0)) wl =
wk
l (t0). [w3l−2, w3l) k πN
2
⋂
i�=k
⋂
w3l−3<u≤t
Dtu
ki
(
−πN
2
)
∩ D
tw3l−3
ki
(πN
2
)
w3l−2 ≤ t < w3l k πN
2
Dtu
ki
(
−πN
2
)
=
{
t∑
j=u+1
φki(ξj) > −πN
2
}
E(vk
l−1, v
k
l ) =
{
min
i�=k
min
vk
l−1<l1≤l2≤vk
l
l2∑
j=l1
φki (ξj) > −πN
2
}
wki
l
t∑
j=w3l−3+1
φki (ξj) =
wki
3l−2∑
j=w3l−3+1
φki (ξj) +
t∑
j=wki
3l−2+1
φki (ξj) > πN − πN
2
=
πN
2
.
D
tw3l−3
ki
(
πN
2
)
k πN
2
[w3l−1, w3l) k
⋂
i�=k
⋂
w3l−3<u≤w3l−2
Dtu
ki (0) ∩
⋂
w3l−2<u≤t
Ctu
ki
(
0,−πN
2
)
∩ D
tw3l−3
ki (πN ) .
w3l−1 ≤ t < w3l
u ∈ [w3l−3, w3l−2) Dtu
ki (0)
t∑
j=w3l−2+1
φki (ξj) >
πN
2
w3l−2∑
j=u
φki (ξj) > −πN
2
.
u ∈ [w3l−2, w3l−1) Ctu
ki
(
0,−πN
2
)
E(vk
l−1, v
k
l ) k πN
2
[w3l−2, w3l−1)
D
tw3l−3
ki (πN )
w3l−2∑
j=w3l−3+1
φki (ξj) +
wki
3l−1∑
j=w3l−2+1
φki (ξj) +
t∑
j=wki
3l−1+1
φki (ξj) >
πN
2
+ πN − πN
2
=
= πN , t ∈ [w3l−1, w3l).
k [w3l−1, w3l)
gvl(i) w3l−1
χ(s, k) ≤ vk
E(t0).
Ej = E(vk
j−1, v
k
j )
ξj Fk
Ek ṽk
E ≤ Ek vk
1
Pk(E(0, vk
1))
E(ξ | A) =
∫
ξ(ω)P(dω | A)
ξ1, ...ξN ξN+1, . . .
Fk ṽk
E
Ek ṽk
E ≤
∞∑
l=1
Ek(v
k
l | ∩l−1
j=1Ej ∩ El)Pk
(∩l−1
j=1Ej ∩ El
)
=
∞∑
l=1
l∑
j=1
Ek(Δvk
j | ∩l−1
j=1Ej ∩ El)Pk
(∩l−1
j=1Ej ∩ El
)
= Ek(v
k
1 | E)Pk(E)
∞∑
l=0
l(1 − Pk(E)l + Ek(v
k
1 | E) =
Ek(v
k
1 | E)Pk(E)Pk(E)−1 + Ek(v
k
1 | E) =
Ek(v
k
1 )
Pk(E)
ξj
Fk
Ek wk
1(t0) − t0 ≤ (K − 1)(πN + C)
κ
.
ξ1, . . . ξN
Ewk
1(t0) − t0 = Ewk
1(0).
wk
1(0) = maxi�=k wki
1 (0) ≤∑i�=k wki
1 (0)
Ewk
1(0) ≥
∑
i�=k
Ewki.
Ewki
E
wki∑
j=1
φki (ξj) ≤ πN + C
κ
,
Ewk
1(0) ≤ (K − 1)(πN + C)
κ
.
ξ1, . . . ξN Δwj(t0)
Ek vk
1(t0) − t0 ≤ 3(K − 1)(πN + C)
κ
.
ξ1, . . . ξN Fk
P
(
min
i�=k
min
1≤l1≤l2≤vk
1
l2∑
j=l1
φki (ξj) > −πN
2
)
≥ 1 − 48σ2(K − 1)2
πN
πN + C
κπN
P
⎛
⎝min
i�=k
min
1≤l1≤l2≤vk
1
l2∑
j=l1
φki (ξj) ≤ −πN
2
⎞
⎠ ≤
∑
i�=k
P
⎛
⎝ min
1≤l1≤l2≤vk
1
l2∑
j=l1
φki (ξj) ≤ −πN
2
⎞
⎠
P
(
min
1≤l1≤l2≤vk
1
l2∑
j=l1
φki (ξj) ≤ −πN
2
)
≤
P
(
min
1≤l1≤l2≤vk
1
l2∑
j=l1
(
φki (ξj) − Eφki (ξj)
) ≤ −πN
2
)
≤
P
(
max
1≤l1≤l2≤vk
1
∣∣∣∣∣
l2∑
j=l1
(
φki (ξj) − Eφki (ξj)
)∣∣∣∣∣ ≥ πN
2
)
≤
P
(
max
1≤l1≤vk
1
∣∣∣∣∣
l1∑
j=1
(
φki (ξj) − Eφki (ξj)
)∣∣∣∣∣ ≥ πN
4
)
P
(
max
1≤l1≤vk
1
∣∣∣∣∣
l1∑
j=1
(
φki (ξj) − Eφki (ξj)
)∣∣∣∣∣ ≥ πN
4
)
≤ 16
π2
N
D
vk
1∑
j=1
φki (ξj) ≤
16σ2Evk
1
π2
N
≤ 48σ2(K − 1)(πN + C)
κπ2
N
P
(
min
i�=k
min
1≤l1≤l2≤vk
1
l2∑
j=l1
φki (ξj) > −πN
2
)
≥ 1 − 48σ2(K − 1)2(πN + C)
κπ2
N
.
t0 ≥ t
χ(t) ≤ min
k∈Γ
vk
E(t0),
EΔχ(t) ≤ 2(1 + θ̄−1) max
k∈Γ
Ek vk
E
v(s) = vk
E(s), k = h0
s
ρ(s) s v(s)
ks s ks
n n s
EΔχ(t) = EΔχ(t) 1ρ(t)=0 +EΔχ(t) 1ρ(t)=1 +EΔχ(t) 1ρ(t)>1 = a1 + a2 + a3
a2
EΔχ(t) 1ρ(t)=1 = E
(
χ(t) − kt
)
1ρ(t)=1 +E
(
kt − t
)
1ρ(t)=1 ≤
E max(χ(t) − kt, 0) 1ρ(t)=1 +E(kt − t) 1ρ(t)=1 = a21 + a22
a1 + a22 kt > t χ(t) ≤ v(t)
EΔχ(t) 1ρ(t)=0 +E(kt − t) 1ρ(t)=1 ≤ EΔχ(t) 1ρ(t)=0 +E(kt − t) 1ρ(t)≥1 ≤
E
(
Δχ(t) 1v(t)<kt +(kt − t) 1v(t)≥kt
) ≤ E min
(
Δv(t), kt − t
)
ξj (t, kt]
E min(Δv(t), kt − t) = Eh0
t
min(Δv(t), kt − t) ≤ Eh0
t
v(t) ≤ max
k∈Γ
Ek vk
E(0),
a21
Emax
(
χ(t) − kt, 0
)
1ρ(t)=1 ≤ E min
(
max(χ(t) − kt, 0), kt
2 − kt
)
≤ E min
(
max(v(kt) − kt, 0), kt
2 − kt
)
= Emin
(
Δv(kt), kt
2 − kt
)
E min(Δv(kt), kt
2 − kt) ≤ max
k∈Γ
Ek Δvk
E(0)
a3 E(Δχ(t) 1ρ(t)>1) ≤ (N + 1)P (Δv(kt) > θN) .
P
(
Δv(kt) > θ̄N
) ≤ E Δv(kt)
θ̄N
E(Δχ(t) 1ρ(t)>1) ≤ 2 maxk Ek v(0)
θ̄
χ(s) ≤ min
k∈Γ
vk
E(t0),
t0 ≥ s ξj Fk
Ek vk
E(t0) ≤ Ek ṽk
E(t0) ≤ Ek vk
1(0)
Pk(E(0, vk
1))
.
Pk(E(0, vk
1)) ≥ 1 − 48σ2(K − 1)2
πN
πN + C
πNκ
.
Ek vk
E(t0) ≤ Ek vk
1(0)
C1
.
Ek vk
1 ≤ 3(K − 1)(πN + C)
κ
.
Ek vk
E(t0) ≤
3(K − 1)(πN + C)
C1κ
.
E χ(s) ≤ 2(1 + θ̄−1) max
k∈Γ
Ek vk
E ≤ 6(1 + θ̄−1)(K − 1)(πN + C)
C1κ
.
E φki(ζj) = ∞
φ(ζj, j)−φ(ζj, i)
E φji(ζj) > 0, i �= j, ζj
Fj E φji(ζj) = +∞
E φji(ζj) 1φji(ζj)<0 > −∞, i, j ∈ Γ
D φji(ζj) 1φji(ζj)<0 < σ2 < ∞, i, j ∈ Γ
φki
y (x) =
{
φki(x), y < x,
y, y ≥ x.
κ > 0, C ∈ R
EΔχ(t) ≤ 6(πN + C)(K − 1)(1 + θ̄−1)
C2κ
,
C2 = 1 − 48(σ2 + C2)(K − 1)2
πN
πN + C
πNκ
.
E χ(s) − s ≤ 2(1 + θ̄−1)
Ek vk
1 (0)
Pk(E(0, vk
1))
.
Ek vk
1(0) = 3 Ek wk
1(0).
Ek wk
1(0) ≤∑i�=k Ek wki
1 (0).∑t
j=1 φki
y (ξj) ≤
∑t
j=1 φki(ξj), wki
1 (0, φ) ≤ wki
1 (0, φy).
E φki
y (ζj) → E φki(ζj), y → ∞,
∃κ > 0 ∃C ∈ R : E φki
C (ζj) > κ.
Ek wki
1 (0, φC) ≤ πN + C
κ
.
Ek vk
1(0, φC) = 3 Ek wk
1(0, φC) ≤ 3(K − 1)(πN + C)
κ
.
Pk(E(0, vk
1))
Pk(E(0, vk
1)) ≥ Pk
(
min
i�=k
min
0<l1≤l2≤vk
1
l2∑
j=l1
φki
C (ξj) > −πN
2
)
D φki
C (ζk) ≤ D φki(ζk)φki(ζk)<0 + E
(
φki
C (ζk)φki(ζk)≥0
)2 ≤ σ2 + C2
Pk(E(0, vk
1)) ≤ C2.
E Δχ(s) ≤ 6(πN + C)(K − 1)(1 + θ̄−1)
C2κ
|
| id | nasplib_isofts_kiev_ua-123456789-4494 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0321-3900 |
| language | English |
| last_indexed | 2025-11-24T21:03:13Z |
| publishDate | 2007 |
| publisher | Інститут математики НАН України |
| record_format | dspace |
| spelling | Shurenkov, G. 2009-11-19T10:25:42Z 2009-11-19T10:25:42Z 2007 The length of the interval of indeterminacy for the estimate of multiple change-points / G. Shurenkov // Theory of Stochastic Processes. — 2007. — Т. 13 (29), № 1-2. — С. 251-266. — Бібліогр.: 8 назв.— англ. 0321-3900 https://nasplib.isofts.kiev.ua/handle/123456789/4494 This article considers the problem of estimating the length of the interval of indeterminacy during construction of change-points' estimates using dynamical programming. It was proved that mathematical expectation of the length of the interval has asymptotically linear dependency on the penalty for a change of distribution when the number of estimations tends to infinity. en Інститут математики НАН України The length of the interval of indeterminacy for the estimate of multiple change-points Article published earlier |
| spellingShingle | The length of the interval of indeterminacy for the estimate of multiple change-points Shurenkov, G. |
| title | The length of the interval of indeterminacy for the estimate of multiple change-points |
| title_full | The length of the interval of indeterminacy for the estimate of multiple change-points |
| title_fullStr | The length of the interval of indeterminacy for the estimate of multiple change-points |
| title_full_unstemmed | The length of the interval of indeterminacy for the estimate of multiple change-points |
| title_short | The length of the interval of indeterminacy for the estimate of multiple change-points |
| title_sort | length of the interval of indeterminacy for the estimate of multiple change-points |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/4494 |
| work_keys_str_mv | AT shurenkovg thelengthoftheintervalofindeterminacyfortheestimateofmultiplechangepoints AT shurenkovg lengthoftheintervalofindeterminacyfortheestimateofmultiplechangepoints |