Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
L-±x L 1 = 1
lim-J- S fn(Tlu)^in{u)
(3.5.13)
1, если u-i_~ui, U2 = U2, ..., ип = и'п, 0 во всех остальных случаях.
(3.5.14)
76
кодовых букв на букву источника равно
j— 1
В задаче 3.21 приведен пример эргодического источника, в котором это среднее, рассматриваемое как случайная величина, принимает различные значения с ненулевыми вероятностями. Трудность состоит в том, что (3.5.15) представляет собой среднее по времени в ином смысле, чем (3.5.13), так как оно определено с помощью сдвигов на L букв сразу, а не сдвигов на одну букву.
К счастью, теорема 3.1.1 остается справедливой для произвольных эргодических источников. Главная трудность в доказательстве теоремы состоит в установлении справедливости закона больших чисел для собственной информации, т. е. в доказательстве того, что с большой вероятностью / (ul)/L близко к Нх (U) для больших L. Этот закон больших чисел представляет значительный математический и теоретико-информационный интерес, и он будет сформулирован в виде теоремы.
Теорема 3.5.3. [Макмиллан (1953).] Пусть для дискретного стационарного эргодического источника Нг (U) < оо.
Для произвольных е> О, б > 0 существует целое число L0 (е, б) (которое зависит от источника), такое, что при всех L ^ L0 (е, б)
До того как доказать теорему, введем некоторые необходимые обозначения и докажем две леммы. Заметим, что
Отметим, что правая часть (3.5.17) очень похожа на среднее по времени, задаваемое (3.5.13). Отличие состоит в том, что каждое слагаемое в (3.5.17), являющееся собственной информацией, зависит от разного числа предыдущих букв источника. Центральным месуом доказательства является установление того, что эта зависимость убывает достаточно быстро, когда / стремится к бесконечности. Пусть Р (uL) = = Р («1, ..., иь) обозначает вероятность последовательности L букв источника; определим для любого целого числа 1 т < L величину Qm (иь) как
Другими словами, Qm (иь) является приближением вероятностной меры источника, которое учитывает статистические зависимости лишь т прошлых букв. Отметим, что
(3.5.16)
(3.5.17)
L
2 Qm (UL) = 1 •
UL
77
Это можно показать суммированием вначале по аь, затем по Uz,_ 1 и так далее и, наконец, по u2.
Лемма 1. Для дискретного стационарного эргодического источника с Н1 (U) < оо и для произвольного т ^ 1
lim — log Qm (uL) — —H (Um+11 Um...U1)
(3.5.19)
с вероятностью 1.
Доказательство. Из (3.5.18) следует, что
l°g Qm (Ч/.) -
I I Ul~ 1 >
I = m -f-1
Щ-т)-
(3.5.20)
Так как log P (um) не зависит от L и принимает конечные значения с вероятностью 1, то
lim — log P(u,J = 0
L-> оо L,
(3.5.21)
с вероятностью 1. Аналогично, так как log Р (нг| «;_ь ..., «;_т) является функцией последовательности т букв и имеет конечное математическое ожидание —Н (Um+i\Um ... UJ, а также в силу того, что источник является эргодическим, (3.5.13) приводит к равенству
lim
.1
V log Р(«гК-1> ••• - ui-m)-L^oo L—m
l =m+ 1
(3.5.22)
с вероятностью 1. И, наконец, так как т фиксировано, то предел в (3.5.22) не меняется при замене 1 /(L—т) на ML. Теперь на основании равенств (3.5.20)—(3.5.22) получаем (3.5.19). |
Лемма 2. Для дискретного стационарного эргодического источника с Н1 (U) < оо, для произвольных е > 0, б > 0, для достаточно большого т и для любого L > т
Рг.
logQmK) —>e}<6. (3.5.23)
Доказательство. Имеем: 1
Рг = Рг
L
log Qm (uL)---logP(uL)
>e =
log
(ul) p (ul)
>Le <¦
Le
log
Q™ (uz,) 4ul)
(3.5.24)
78
где было использовано неравенство Чебышева*' для неотрицательной случайной величины
р ы
Пусть теперь для любого числа у выражение [у]+ обозначет «положительную часть» у, т. е.
[у, О,
[У]+ =
О, у< 0.
(3.5.25)
Рис. 3.5.1.
Рассматривая раздельно положительные и отрицательные значения у, легко проверить, что
