6.12. Смежная система

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

Как можно оценить энтропию марковского процесса? Рассмотрим для простоты марковский процесс первого порядка; при переходе к системе порядка изменяется лишь обозначение.

Поскольку основным является фундаментальное неравенство для двух распределений, попробуем использовать его для распределений Символ обозначает вероятность пары символов; аналогично, Как отмечалось,

Таким образом, используя (6.4.2), имеем

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

получаем

Разлагая логарифм и перенося члены, имеем

Снова используем условную вероятность. Тогда

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

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

Равенство имеет место только в случае, когда Поэтому доказано, что ограничения могут только уменьшить энтропию.

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

Однако процесс является процессом первого порядка, так что

Используя несколько раз исходное распределение вероятностей получаем

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

Поэтому как и следовало ожидать.