Подождите немного. Документ загружается.
x
n
x
1
, ..., x
n−1
x
n
H(X
n
|X
1
, ..., X
n−1
)
H(X
n
|X
1
, . . . , X
n−1
) = H(X|X
n−1
).
H
n
(X) H(X|X
n−1
)
H(X|X
n
) n
H
n
(X) n
H
n
(X) ≥ H(X/X
n−1
)
lim
n→∞
H
n
(X) = lim
n→∞
H(X|X
n
)
H(X
n
) = H(X) + H(X|X
1
) + ... + H(X|X
n−1
).
n
n
H(X
n+1
)
(a)
= H(X
1
...X
n
X
n+1
) =
(b)
= H(X
1
...X
n
) + H(X
n+1
|X
1
, ..., X
n
) =
(c)
= H(X
n
) + H(X|X
n
) ≤
(d)
≤ H(X
n
) + H(X|X
n−1
) ≤
(e)
≤ H(X
n
) + H
n
(X) =
(f)
= (n + 1)H
n
(X).
H
n
(X)
(n+1)
H
n
(X) H(X|X
n
)
lim
n→∞
H
n
(X) ≥ lim
n→∞
H(X|X
n
).
m < n
H(X
n
) = H(X
1
. . . X
n
) =
(a)
= H(X
1
. . . X
m
) + H(X
m+1
. . . X
n
|X
1
, . . . , X
m
) =
(b)
= mH
m
(X) + H(X
m+1
|X
1
, . . . , X
m
) + . . .
+H(X
n
|X
1
, . . . , X
n−1
) ≤
(c)
≤ mH
m
(X) + (n − m)H(X|X
m
).
H(X|X
m
)
m
n n → ∞.
lim
n→∞
H
n
(X) ≤ H(X|X
m
),
m. m
lim
n→∞
H
n
(X) ≤ lim
m→∞
H(X|X
m
).
¤
H
∞
(X) = lim
n→∞
H
n
(X), H(X|X
∞
) = lim
n→∞
H(X|X
n
).
H
∞
(X) = H(X|X
∞
)
H(X
1
...X
n
) = H(X
1
) + ... + H(X
n
).
H(X
n
) = nH(X).
n n
H
n
(X) = H(X),
H
∞
(X) = H(X).
H(X|X
n
) = H(X
n+1
|X
1
, ..., X
n
) = H(X),
H(X|X
∞
) = H(X).
s
H(X|X
n
) = H(X
n+1
|X
1
, ..., X
n
) =
= H(X
n+1
|X
n−s+1
, ..., X
n
) = H(X|X
s
).
n
H(X|X
∞
) = H(X|X
s
).
H(X
n
) = H(X
1
. . . X
s
X
s+1
. . . X
n
) =
= H(X
1
. . . X
s
) + H(X
s+1
. . . X
n
|X
1
, . . . , X
s
).
H(X
s+1
. . . X
n
|X
1
, . . . , X
s
) = H(X
s+1
|X
1
, . . . , X
s
) +
+ H(X
s+2
|X
1
, . . . , X
s+1
) + . . .
+ H(X
n
|X
1
, . . . , X
n−1
),
H(X
s+1
...X
n
|X
1
, ..., X
s
) = (n − s)H(X|X
s
).
H(X
n
) = sH
s
(X) + (n − s)H(X|X
s
).
n n
H
∞
(X) = H(X|X
s
).
H
n
(X) = H(X|X
s
) +
s
n
(H
s
(X) − H(X|X
s
)) =
= H(X|X
n
) +
s
n
(H
s
(X) − H(X|X
s
)).
H
n
(X)
H(X|X
n
) n
H(X|X
s
)
s
X = {x, p(x)}
n T
n
(δ)
H(X)
T
n
(δ) =
½
x :
¯
¯
¯
¯
1
n
I(x) − H(X)
¯
¯
¯
¯
≤ δ
¾
,
δ
T
n
(δ)
δ > 0
lim
n→∞
P (T
n
(δ)) = 1.
n
|T
n
(δ)| ≤ 2
n(H(X)+δ)
.
ε > 0 n
0
n ≥ n
0
|T
n
(δ)| ≥ (1 − ε)2
n(H(X)−δ)
.
x ∈ T
n
(δ)
2
−n(H(X)+δ)
≤ p(x) ≤ 2
−n(H(X)−δ)
.
n ξ
i
, i =
1, ..., n m σ
2
P
Ã
¯
¯
¯
¯
¯
1
n
n
X
i=1
ξ
i
− m
¯
¯
¯
¯
¯
≥ ε
!
≤
σ
2
nε
2
.
n
T
1 ≥ P (T
n
(δ)) =
X
x∈T
n
(δ)
p(x) ≥ |T
n
(δ)| min
x∈T
n
(δ)
p(x) ≥ |T
n
(δ)|2
−n(H+δ
0
)
.
ε > 0 n
0
n > n
0
P (T
n
(δ)) ≥ 1 − ε.
T
n
(δ)
P (T
n
(δ)) ≤ |T
n
(δ)| max
x∈T
n
(δ)
p(x) ≤ |T
n
(δ)|2
−n(H(X)−δ)
.
¤
T
n
(δ)
2
nH(X)
nH(X)
H(X)
H(X)
M
T
n
(δ) M2
−nH(X)
1 − M2
−nH(X)
M 2
nH(X)
H(X)) M2
−nH(X)
τ
x
(x) x
x τ (x) = {τ
x
(x), x ∈ X}
x
x = (x
1
, ..., x
n
)
p(x) =
n
Y
i=1
p(x
i
) =
Y
x∈X
p(x)
τ
x
(x)
.
1
n
I(x) = −
X
x∈X
τ
x
(x)
n
log p(x).
H(X)
τ
x
(x)
n
≈ p(x)
x x
X
{p(x), x ∈ X}
A = {a}
A = {0, 1}
C = {c} |C| = M
A
A
A
X = {0, 1, 2, 3}
C
1
= {00, 01, 10, 11}
C
2
= {1, 01, 001, 000}
C
3
= {1, 10, 100, 000}
C
4
= {0, 1, 10, 01}
C
2
C
3
C
3
C
2
C
3
C
2
C
2