4.8. Марковские источники

Марковский источник характеризуется «состояниями», в которых он может находиться, и правилами, управляющими его переходом из одного данного состояния в какое-либо другое.

Рис. 4.1 Марковский источник.

Буквы порождаются источником с вероятностями, зависящими только от состояния, в котором находится источник, и источник изменяет свое состояние, вообще говоря, каждый раз, когда порождается буква. После порождения некоторой буквы новое состояние однозначно определяется старым состоянием и этой буквой, в то время как эти два состояния не могут однозначно определить порожденную букву.

Действие источника графически можно иллюстрировать схемами, подобными показанной на рис. 4.1. Каждый узел схемы

представляет собой состояние а каждая ветвь указывает (в направление стрелки) изменение состояния, происшедшее в результате порождения некоторой буквы Состояние является начальным, имеющим место при порождении первой буквы.

Если для каждого состояния источника заданы условные вероятности букв то каждая переходная вероятность может быть вычислена суммированием вероятностей букв, приводящих к переходу из состояния Например, в случае рис. 4.1 мы имеем

Матрица условных вероятностей полностью описывает источник, а потому, следовательно, и ансамбль сообщений, образованный порожденными им последовательностями букв.

Рис. 4.2. Периодический марковский источник.

Важнейшей характеристикой последовательности состояний, допускаемых источником, является то, что каждое состояние этой последовательности зависит только от непосредственно предшествующего ему состояния. Последовательности такого типа, известные в математике как цепи Маркова, широко исследованы. Краткий обзор (без доказательств) некоторых свойств цепей Маркова с конечным числом состояний дан здесь и в следующих двух разделах (см. [1]).

Состояние называется «возвратным», если вероятность возможного возвращения в равна единице, в противном случае состояние называют «невозвратным». В случае рис. 4.1 все состояния, кроме возвратны.

Состояние называется «периодическим», с периодом если возвращение в возможно только после шагов, где любое натуральное число. Например, все состояния на рис. 4.2 периодические, с периодом, равным 2. Все состояния на рис. 4.1 непериодические.

Множество состояний называется «замкнутым», если переходы за один шаг из любого состояния этого множества могут вести только в состояние этого же множества. Цепь называется «неразложимой», если никакое подмножество ее состояний,

отличное от множества всех состояний, не замкнуто; в противном случае цепь называется «разложимой».

Цепь, показанная на рис. 4.1, разложимая, так как подмножество, образованное всеми состояниями, кроме замкнуто. Однако если исключить то оставшиеся состояния будут образовывать неразложимую цепь. Вообще, если некоторое подмножество состояний образует неразложимую подцепь, то эта подцепь может изучаться независимо от всех других состояний. В самом деле, после того как источник попадает в одно из состояний этого подмножества, все состояния, не принадлежащие этому подмножеству, становятся недоступными и, следовательно, могут не рассматриваться.

Теорема. Не существует цепи с конечным числом состояний, состоящей только из невозвратных состояний; возвратные состояния, имеющиеся в цепи, можно разбить на замкнутые множества, соответствующие неразложимым подцепям. В эти замкнутые множества можно попасть из невозвратных состояний, но не наоборот, как, например, в случае рис. 4.1.

Теорема. Неразложимая цепь (или подцепь) с конечным числом состояний может содержать только возвратные состояния. Если одно из ее состояний периодическое, то все состояния должны быть периодическими с тем же самым периодом.