<< Предыдущая

стр. 8
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

\

откуда следует нижняя оценка 2.
3. Из (5.5) прежде всего следует разложение

(5.7)
HUX) = ^-Н,^(Х) + jH(XL\X1,X2, ...,XL-X).
Li
LJ


Используя уже известное соотношение (5.5), получаем неравенство
(5.8)
L.HUX)<(L-l)-HL-l(X)+HL(X).
После подстановки получаем утверждение 3.
. (5.9)
HL(X) < HL^{X).
4. Утверждения 1., 2. и ограничение Н\{Х) < оо устанавливают
существование предела. Используя далее «правило цепочки», полу-
чаем

/V"\ Г LT/ V V V \|
тт
/> -" 7
f

+ ff(Xi,|Xi, X 2 ,..., X b -i) + Я ( Х ь + 1 | ^ 1 , Jf2, • • •, XL)+
(5.10)
+ •••+ H(XL+J\XUX2,..., XL+i.i)\.
Согласно утверждению 1., условная энтропия в правой части .ра-
венства не возрастает, поэтому справедлива оценка
1
HL+j(X) <
˜^
(5.11)
l±lH{XL/\X1,Xi,...,XL-1).
L j
Устремляя j к бесконечности, получим

lira HL+j{X)< lim —"— H(XUX2,.. • ,XL.-i)+
j-»oo j->oa L+J
(5.12)
i±±H(XL\X1,X2,...,XL.l),
+
L +J
что дает для каждого натурального L,
Яоо<Я(Хь|А-1,Х 2 ,... 1 Х 1 ,_1), (5.13)
но, т.к. для любого натурального L выполняется так же и 2., то 5.13
превращается в равенство при L — оо. •
»
Глава 5. Стационарные дискретные источники с памятью I

5.2. Теорема кодирования источников 2 /
Теперь мы можем дополнить теорию информации еще одной теоре-
мой. Окалывается, что объединяя события источника в блоки длимы
L и кодируя эти блоки, средняя длина кодового слова на событие
может достигнуть энтропию источника Нх(х) при L—>оо как угодно
близко. При этом память источника полностью учитывается.

Теорема 5.2.1. Теорема кодирования стационарного дискретного ис-
точника с энтропией Hi(X).
Для блока длины L существует .D-ичный префиксный код, в кото-
ром средняя длина кодового слова на одно событие п удовлетворяет
неравенству
(5.14)
М§^§ 1
Теорема (5.14) не нуждается в специальном доказательстве. Если
мы рассматриваем блоки длины L как новые независимые события
с энтропией, равной L • HL{X) И применяем теорему кодирования
источников 1, то мы имеем

(5.15)
^ 1 1.

Разделив все члены неравенства на L, получаем среднюю длину ко-
дового слова на событие

)^ШЛ. (5.16)
При L — оо, Hi(x) — Нос(х) = Н(х) мы имеем
» »

LHL(X) LHL{X)
(517)




(5Л8)
+ 6
-
Таким образом, для любого сколь угодно малого S, существует
метод кодирования блоков, содержащих L > 1/6 событий, при кото-
ром для средней длины кодового слова на событие п выполняется
неравенство (5.18). Теорема кодирования источников 2 показывает,
что увеличивая длину блока L, мы можем как угодно близко подойти
к энтропии Н(х) = Ноо(х). Однако, на практике существуют неко-
торые ограничения. Для того, чтобы блок из L событий мог быть
5.3. Конечные цепи Маркова

I
' продекодирован, он должен быть полностью принят, что может при-
вести к недопустимым задержкам декодирования и недопустимому
Объему буфера памяти.


5.3. Конечные цепи Маркова
В этом и последующих параграфах будет рассматриваться специ-
альная форма дискретных источников с памятью марковские ис-
точники. Их описание сходно с марковскими цепями, которые на-
шли разнообразное применение в других областях науки и техники.
Гак, на основе марковских цепей строятся модели распознавания ре-
чи, модели передачи по телефонным коммутируемым каналам. Це-
ни Маркова1 используются при исследовании моделей сетей связи
(каналы Гильберта-Элиота) и в теории управления транспортными
потоками. Значение цепей Маркова основывается не только на их
полном математическом описании, но также на том факте, что с их
помощью можно составить математическую модель многих процес-
сов, наиболее близкую к практике.

5.3.1. Дискретные во времени цепи Маркова
В этом разделе шаг за шагом вводится понятие конечных дискрет-
ных во времени марковских цепей. Мы наглядно поясним это поня-
тие на простейшем примере «случайных блужданий».
Пример: Случайные блуждания студента.
Нас интересует вопрос о том, доберется ли пьяный студент от
дверей пивной до дверей студенческого общежития. Поставим во-,
прос но другому (рис. 5.2): какова вероятность того, что случайные
блуждания на 7 временном шаге приведут студента в пространствен-
ное состояние Si? или
Р («случайные блуждения» приведут к состоянию Si в момент
времени п = 7).
Ситуация, изображенная на рис. 5.2 уже содержит в себе важ-
нейшие признаки цени Маркова. Под марковской цепью понимается
дискретный во времени и по состоянию марковский процесс S(n).
Его реализацией является множество путей, ведущих из состояний
5i в состояние S;.
'А. А. Марков (1856 1922) - выдающийся русский математик. Прим. перев.
50 Глава 5. Стационарные дискретные источники с памятью


ШАГИ 0 1 2 3 4 5 6 7 8 л

5
ГЧЖ*˜˜
ПИВНАЯ Щ -
* ч
ЯГ 7
I TV Щ"7 * '
5
А.
If N,
J *)
#м 3» ч
* -


1«Li s

^ .
***** Студенческое общежитие


Р и с . 5.2. Случайные блуждания студента.

Исходным пунктом для описания марковской цепи является мно-
жество состояний
(5.19)

где /V натуральные и стохастический вектор распределения ве-
роятностей состояний в момент времени п
г
Рп = (Рп(1),Рп(2),...,Рп(Л )). (5.20)

Для того, чтобы полностью определить цепь Маркова, нам оста-
ется задать метод подсчета вероятностей р„(г) для любого момента
времени п. Из определения вероятности имеем


(5.21)
г=1

Особое значение имеет распределение вероятностей в начале на-
блюдения, т.е. начальные условия

Ро = (Ро(1),Ро(2),...,Ро(Л0). (5-22)

Смена состояний описывается переходными вероятностями

Тад,», 0 7 * ) = P(a[m] (5.23)
= stn s[n2] = Sj).

Эти переходные вероятности обладают следующими свойствами:
1. Одно из состояний в момент времени п всегда достигается при
любом Si в момент п\


(5.24)
г) = 1-
51
5.3. Конечные цепи Маркова

2. Граничное распределение, т.е. вероятности j'-ro состояния в
момент времени п2
N
5Z я'па.щО'Л) = Pmti)- (5-25)

3. Рекурсивная формула для переходных вероятностей (частный
случай уравнения Колмогорова - Чэнмена.)
N
7r
тпз.шО'А) = X! "3,n2070Tn 2 ,ni(/A)- (5.26)

Дискретное равенство Колмогорова - Чэпмена получается транс-
формацией «правила цепочки» для вероятностей

(5.27)
p{xi,x2)=p(x2/xi)p(xi),

р(х ь а;2,хз) = p(x3/xi,x 2 )p(x2/xi)p(xi). (5.28)
Умножая обе части равенства на \/р(х{), получим

(5.29)
р{х2,х3/х3) =р(хз/х1,х2)р(х2/х1).

Суммируя по всем х2, приходим к дискретной форме уравнения Кол-
могорова - Чэпмена

p(x3/xi) = ^2P(X3'/XI,X2)P(X2/XI). (5.30)
х2
При преобразовании (5.30) в (5.26), мы предполагаем

р(хз/хьх 2 ) =р(х 3 /хг). (5.31)

Последнее равенство характеризует марковский процесс.

Определение 5.3.1. Марковским процессом называется процесс, в
котором прошлое не оказывает влияния на будущее, если настоящее
известно.
Замечание. В рассмотренном примере известное прошлое это
стохастическая переменная Х\, известное настоящее - Х2, неиз-
вестное будующее - Х3.

Применение цепей Маркова сильно упрощается, когда они гомо-
генны, стационарны и регулярны. Рассмотрим эти три понятия.
Глава 5. Стационарные дискретные источники с памятью

Определение 5.3.2. Цепь Маркова гомогенна, если переходные ве- /
роятности между состояниями не зависят от выбора временной точ-е
ки отсчета. /

Таким образом, переходные вероятности зависят только от раз(-
ности времен отсчетов I.
Tr{j/i) = p(s[n] = Si U a[n + I] = Sj) n = 0,1,2,3,... . (5.32)
В этом случае для I = ri2 - n\ и т = пз — пг равенство Колмого-
рова - Чэпмена (5.26) можно записать в виде

(5.33)
n+m{Jli) =

Это равенство может быть представлено в виде суммы покомпонент-
ных произведений векторов-строк на векторы-столбцы. Записав пе-
реходные вероятности в виде матрицы, получим уравнение (5.33) в
матричной форме
тг 1 + т (1/1) т+т{2/1) • • • TTl+m(N/l) \
7г(+т(1/2) тг,+т(2/2) ••• m+m(N/2)
(5.34)

\jrJ+ra(l/JV) •••
n+m(2/N) 7rl+m(N/N)J

<< Предыдущая

стр. 8
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>