32
Теорема 2 (К.Шеннон). Для любого ε >0
lim log2 βn (ε) = H.
n→∞ n
Д о к з а т е л ь с т в о. Пусть Q n (ε) - множество наиболее вероятных последовательностей таких, что P( Q n (ε))≥ 1-ε, а исключение любой последовательности из Q n (ε) образует множество, вероятность которого
меньше 1-ε. Возьмем малое δ>0 и рассмотрим множество В из предыдущей теоремы. Тогда для x В
H - δ < −log2 P(x) < H + δ n
или
- n(H-δ) > log 2 P(x) > - n(H+δ).
Отсюда
2−n(H +δ ) < P(x) < 2−n(H −δ ) .
Рассмотрим оценки для Q n (ε). По определению Q n (ε) P(Q Поскольку
Q n (ε) = (Q n (ε) IB ) U( Q n (ε) IB ),
(6)
n (ε))≥ 1-ε.
тогда |
|
|
|
|
|
|
||
P(Q n (ε)) = ∑P(x) = |
∑P(x) + |
∑P(x) . |
||||||
|
x Qn ( x) |
|
x Qn ( x)IB |
x Qn ( x)I |
B |
|
||
Для второй суммы справедлива оценка |
|
|
|
|||||
P (Q n (ε) I |
|
) ≤ P( |
|
)<ε. |
|
|
|
|
|
B |
|
|
|
|
|||
B |
|
|
|
|
||||
P(Q n (ε) IB )) = |
|
∑P(x) < ∑2−n(H −δ ) = |
||||||
|
|
x Qn ( x)IB |
x Qn ( x)IB |
|||||
= Q n (ε) IB ) 2−n(H −δ ) |
≤ Q n (ε) 2−n(H −δ ) = |
|||||||
= βn (ε) 2−n(H −δ ) .
Следовательно,
1-ε. ≤ P(Q n (ε)) < βn (ε) 2−n(H −δ ) +ε.
Отсюда получаем
βn (ε) > 2n(H −δ ) (1- 2ε).
Докажем, что множество Q n (ε) содержит минимальное число после-
довательностей среди всех множеств С, таких что P(C) ≥ 1-ε. Доказательство будем вести от противного. x Q n (ε) , x C и y C,
y Q n (ε), такие последовательности, что P(x) ≥ P(y), так как в Q n (ε) со-
держатся наиболее вероятные последовательности. Предположим, что
C \ Q n (ε) < Q n (ε)\ C
33
(т.е. Q n (ε) - не минимальное множество). Тогда
∑P(x) < ∑P(x) ,
x C\Qn (ε) x Qn (ε)\C
так как справа слагаемых хотя бы на 1 больше и все они не меньше слагаемых в левой сумме. Пусть y 0 имеет наименьшую вероятность среди всех y
Q n (ε)\ C. Следовательно,
∑P(x) ≤ |
∑P(x) . |
x C\Qn (ε) x (Qn (ε)\C)\{y0}
Поскольку
Q n (ε)\{y 0 } = (Q n (ε)IC ) U(( Q n (ε)\C)\{y 0 }),
то, учитывая, что по определению множества Q n (ε)
P(Q n (ε)\{y 0 }) < 1 - ε,
получим
P(C) = P(Q n (ε)IC ) + P(C\ Q n (ε)) ≤ P(Q n (ε) IC ) +
+ P(Q n (ε)\C\{y 0 }) = P(Q n (ε)\{y 0 }).
Тогда
P(C) <1 - ε,
что противоречит предположению. Следовательно, Q n (ε) - минимальное
множество векторов, имеющих максимальную вероятность. Отсюда и из (6)
Q n (ε)≤ В = ∑1 < ∑ |
|
p(x) |
≤ 2n(H +δ ) . |
||
|
−n(H +δ ) |
||||
Таким образом, |
x B x B2 |
|
|||
|
|
|
|
||
2n(H −δ ) < Q n (ε) < 2n(H +δ ) |
|
|
|||
или |
|
|
|
|
|
H-δ < |
log 2 βn (ε ) |
< H +δ. |
|
|
|
n |
|
|
|||
|
|
|
|
|
|
Следовательно,
lim log2 βn (ε) = H,
n→∞ n
что и требовалось доказать.
Множество открытых текстов можно представить как объединение В
и B . Множество B имеет маленькую вероятность, множество В оценивается по теореме 2.
Х≈ 2nH (x) .
Следовательно,