5.4. Эффективное кодирование эргодического марковского процесса
Ясно, что марковскую структуру источника можно использовать для улучшения кодирования. Для каждого состояния марковской системы, можно применить соответствующий код Хаффмена построенный по вероятностям выхода из зтого состояния. В зависимости от того, насколько сильно меняются вероятности в каждом состоянии, выигрыш в кодировании может быть большим или меньшим. Однако при увеличении памяти марковского процесса выигрыш уменьшается, а число состояний быстро растет.
Построим такие коды Хаффмена для матрицы, описывающей погоду (см. разд. 5.2). Для состояния а (сегодня) имеем (завтра) двоичное кодирование: 
Для состояния 
Для состояния 
Для стационарного распределения получим [используя стационарные; вероятности (5.2.3)] среднюю длину кода: 
Одновременно выполним кодирование в соответствии со средними частотами; букв 
Эти частоты совпадают, очевидно, со стационарными вероятностями 
Код имеет вид: 
Таким образом,
Следовательно, средняя длина кода им для кодирования в отдельных состояниях меньше, чем для кодирования, основанного на средних частотах 
Как и следовало ожидать, в системах марковского типа средняя длина кода уменьшается.
Задача
5.4.1. Пусть вероятности для хорошей погоды а равны 
а остальные вероятности такие же, как в этом разделе. Покажите, что 
