4.9. Свойства непериодического марковского источника с конечным числом состояний

Рассмотрим непериодический, неразложимый марковский источник (цепь) с конечным числом состояний, и пусть вероятность того, что источник попадет в состояние из состояния точно за шагов.

Теорема. Для всех пар состояний

Распределение вероятностей удовлетворяет системе уравнений

где суммирование ведется по всем состояниям источника.

Определитель системы линейных однородных уравнений (4.105) обращается в нуль, поскольку

Таким образом, определяется из равенства (4.105) с точностью до постоянного множителя. Значение этого постоянного множителя должно быть таким, чтобы

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

Два важных свойства становятся очевидными из выражения (4.104). Первое — вероятность того, что источник будет находиться в каком-либо частном состоянии стремится к пределу, когда число последовательных переходов между состояниями неограниченно возрастает. Второе — предел единствен и, в частности, не зависит от начального состояния источника. Эти два свойства вместе означают, что последовательности символов, порождаемых источником, попадают в пределе в условия статистического равновесия. Кроме того, если вероятность нахождения в каком-либо начальном состоянии равна значению удовлетворяющему равенству (4.105), то эти условия статистического равновесия существуют с самого начала.

Тот факт, что эти свойства различны, а не являются двумя аспектами одного и того же свойства, становится ясным, если мы рассмотрим разложимый марковский источник, состоящий, например, из двух неразложимых подцепей Тогда выражение (4.104) применимо к двум любым состояниям, принадлежащим к одной и той же неразложимой цепи, но неприменимо к состояниям, принадлежащим различным цепям. Очевидно, что если принадлежит одной цепи, другой, то

поскольку из состояний одной цепи нельзя перейти в состояние другой. Следовательно, равенство (4.104) можно переписать в виде

где равно нулю, если принадлежит равно нулю, если принадлежит Соответственно суммирование в выражении (4.105) должно вестись только по состояниям цепи, к которой принадлежит Тогда, если и

- вероятности того, что начальное состояние принадлежит к соответственно, то вероятность нахождения источника в состоянии равна в пределе при

Кроме того, если задаваемые равенством (4.110) вероятности равны вероятностям начальных состояний, то вероятность нахождения источника в каком-либо состоянии не зависит от времени. В этом случае все статистические характеристики ансамбля порождаемых источником последовательностей не зависят от времени и источник с самого начала находится в стационарном режиме работы.

Этот простой пример иллюстрирует, каким образом в ансамбле последовательностей, порождаемых марковским источником, может проявляться статистическая однородность во времени, даже в том случае, когда влияние начального состояния не исчезает с возрастанием времени. Исчезновение влияния начального состояния, характеризующее неразложимые, непериодические источники с конечным числом состояний, придает им дополнительную однородность ансамбля, которую мы в разд. 4.5 назвали эргодичностью. Таким образом, грубо говоря, эргодичность означает, что почти каждая порождаемая источником последовательность является представителем всего ансамбля последовательностей. Точнее, среднее по последовательности любой случайной величины, связанной с состоянием (или конечным числом последовательных состояний) эргодического источника, равно с вероятностью 1 среднему по ансамблю той же случайной величины. То есть последовательность значений, принимаемых такими случайными величинами, подчиняется усиленному закону больших чисел, сформулированному в разд. 4.4. Ясно, что это несправедливо для источника, состоящего из двух отдельных подцепей, так как при этом состояния только одной из подцепей окажутся в какой-либо последовательности состояний.

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

Теорема. Источник, находящийся в невозвратном состоянии, с вероятностью 1 окажется в конце концов в возвратном состоянии, если только общее число состояний конечно. Если

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

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

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

Далее, для непериодического разложимого источника асимптотическое значение энтропии на букву, когда длина последовав тельности букв стремится к равна

где суммирование ведется по всем состояниям цепи.

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

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

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