Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
\у\ = 2 [у]+-у. (3.5.26)
Пользуясь рис. 3.5.1, можно также заметить, что для у ^ 0
у log е
[log у]+<
Из (3.5.26) и (3.5.27) следует, что
. 2 log е
log
Qm (UL)
Р(Ч)
Qm (UL)
РЫ
Qm (ul)
-log
P(UL)
Для выражения, стоящего в правой части в (3.5.28), имеем
Qm (ul)
Р(Ч)
UL
ры
1,
(3.5.27)
(3.5.28)
(3.5.29)
- log = т Нт (U) + (L -m) Н (Um+1 \ Um• • • Ux)~LHl (U).
р (ul)
Подставляя выражения (3.5.28)—(3.5.30) в (3.5.24), получим
(3.5.30)
Рг
у-log Qm К)-----i-l0gP(UL)
>е
<
*> См. (5.4.5) для вывода неравенства Чебышева.
79
Заметим, наконец, что из теоремы 3.5.1 следует, что выражение, стоящее в квадратных скобках в правой части (3.5.31), при L> m стремится к нулю при возрастании пг равномерно по L> пг. Таким образом, для любого фиксированного е правая часть°неравенства будет меньше, чем 8 для достаточно больших пг. |
Доказательство теоремы. Для заданных е> 0, б> О выберем т достаточно большим так, чтобы правая часть (3.5.31) была меньше, чем б для всех L > т, и
| Н (Um+1 \ит... их)~Нх (и) I < е. (3.5.32)
Выберем затем достаточно большое L0>- т так, чтобы для всех L ^ L0
Рг
-logQm(uI) + H(U,n+1\Um...U1)
> е
<6. (3.5.33)
Это возможно сделать на основании леммы 1. Из неравенств (3.5.31)— (3.5.33) для L0 имеем
Рг Г log P(UL)+ #«,(?/) >3ej<2S. (3.5.34)
Для того чтобы увидеть это, следует заметить, что, если не имеют места ни событие в левой части (3.5.31), ни событие в левой части (3.5.33), то тогда не может произойти событие в (3.5.34). Следовательно, вероятность события в (3.5.34) не больше, чем сумма вероятностей событий в (3.5.31) и (3.5.33). В силу произвольности е> 0 и 6> О это эквивалентно (3.5.16), что завершает доказательство теоремы. | Теорема 3.1.1 с заменой Н (U) на Нх (U) доказывается теперь, как и раньше при Н (U), если использовать теорему 3.5.3 вместо (3.1.7).
3.6. МАРКОВСКИЕ источники
Некоторые идеи последнего параграфа могут быть выявлены с особой ясностью, если рассмотреть частный класс источников, называемых марковскими источниками. Эти источники задаются множеством состояний, обозначаемых целыми числами 1, ..., J и алфавитом букв источника, обозначаемым, как обычно, ах, ..., ац. В каждую единицу времени источник производит букву и переходит в новое состояние. Последовательность букв источника обозначается через и = (их, и2, ...), а последовательность состояний — через s = (slt s2, ...).
Пусть Qji обозначает условную вероятность перехода в состояние
i при условии, что задано предыдущее состояние j:
Qn =--= Pr (st = i | sw = /). (3.6.1)
Предположим, что вероятность перехода в состояние зависит только от предыдущего состояния
80
Pr (s, I s,_lt s,_2, ...) = Pr (s, | s^i). (3.6.2)
Случайная последовательность состояний, для которой выполнены
(3.6.1) и (3.6.2), называется конечной однородной цепью Маркова.
Пусть Pj (ah) обозначает вероятность того, что производится буква ak, когда источник находится в состоянии /, и предположим, что эта вероятность зависит только от текущего состояния
рЛак) = Рг [“< = ak I = Л, (3.6.3)
Pr {lit | S;) = Pr (lli | S;, Ы,_!, S,_(3.6.4)
Предположим, наконец, что состояние источника однозначно определяется предыдущим состоянием и предыдущей буквой.
Рис. 3.6.1 иллюстрирует работу марковского источника. Узлы соответствуют состояниям, а направленные ребра соответствуют буквам
а2-//г
Рис. 3.6.1. Марковский источник; на ребрах указаны выход ah и вероятность
Pj(ah).
источника и переходам между состояниями. Каждое ребро, направленное от данного узла, должно соответствовать различным буквам для того, чтобы новое состояние однозначно определялось по предыдущему состоянию и букве.
Состояние марковского источника можно представить себе как тот объект, который определяет влияние истории источника на следующую букву. Так, например, стационарный источник, для которого каждая выходная буква статистически зависит лишь от I предыдущих выходных букв, является марковским источником, состояниями которого являются всевозможные последовательности из I букв. Из этого примера становится ясным, что большинство хороших стационарных источников может быть по крайней мере аппроксимировано марковскими источниками.
Поучительно рассмотреть моделирование английского текста с помощью марковского источника. Шеннон (1948) привел примеры последовательностей, порождаемых такими моделями; в первой из них буквы зависят от одной или двух предыдущих букв, а во второй — слова зависят от предыдущего слова с соответствующим выбором вероятностей.