Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.3. Эргодические марковские процессы

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

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

Рис. 5.3.1. Неэргодический граф

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

Даже если имеется такое множество состояний, что из любого одного можно попасть в любое другое, вероятности не обязательно стабилизируются. Рассмотрим, например, шахматную доску, в которой разрешены переходы на одну клетку влево, вправо, вверх или вниз, но не по диагонали. Начиная с белой клетки, после четного числа переходов мы оказываемся на белой клетке, а после нечетного — на черной клетке. Следовательно, вероятности зависят от цвета клетки, на которой мы находимся в данный момент. Таким образом, теория всех возможных марковских процессов, в принципе, является достаточно запутанной. Однако марковские процессы, которыми интересуются в теории информационных систем, являются эргодическими и не обладают такими странными свойствами. В конце концов в длинной последовательности вероятности символов сообщения устанавливаются равными некоторым фиксированным числам. Как уже отмечалось, наличие предельного распределения вероятностей не означает фактического смешивания символов. Легко, например, понять, что значат слова предельное состояние или множество предельных состояний. Столь же легко увидеть, что если множество предельных состояний не совпадает с множеством всех состояний системы, то система неэргодична, так как имеются состояния, из которых нельзя попасть в другие состояния. Кроме того, следует избегать любого периодического чередования состояний. Предполагается, что любой источник, который в дальнейшем придется кодировать, является эргодическим. Однако появление незргодических источников не является абсолютно невозможным. Возникающие сложности нетрудно преодолеть. В дальнейшем предполагается, что все наши системы эргодичны.

Задача

5.3.1. Изобразите графы для марковских процессов с символами и 1 и памятью первого, второго и третьего порядков.

<< Предыдущий параграф Следующий параграф >>
Оглавление