5.2. Энтропия марковской цепи

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

функций которые называются вероятностями перехода. В (5.2.1) вероятности соответствуют однократному распределению случайной величины

Вероятность перехода равняясь условным вероятностям обладает свойством неотрицательности и нормировки

Дискретный марковский процесс называют также марковской цепью.

Переходя от вероятностей (5.2.1) к условным вероятностям, легко получить, что в случае марковского процесса

и, следовательно,

Поэтому

Благодаря (5.2.3) иерархическая формула (1.3.6) принимает вид

Аналогичным образом для средних энтропий имеем

Дискретный марковский процесс является стационарным, если вероятности перехода не зависят от значения параметра и если все однократные распределения одинаковы (равны Образуя многократные распределения по формуле (5.2.1),

легко доказать, что они также удовлетворяют условию стационарности (5.1.1).

Стационарность однократного распределения означает, что выполняется уравнение

Последнее легко вывести, записывая согласно (5.2.1.) двукратное распределение и суммируя его по что дает

Учитывая (5.2.3), легко видеть, что для стационарного марковского процесса удельная энтропия (5.1.3) совпадает с энтропией, соответствующей вероятностям перехода при стационарном распределении вероятностей:

В самом деле, усредняя (5.2.3) со стационарными вероятностями убеждаемся, что всем значениям соответствует одна и та же условная энтропия равная (5.2.8).

Усредним далее формулу (5.2.4) со стационарными вероятностями. Это даст равенство

Сравнивая его с (5.1.13), видим, что в стационарном марковском случае

т. е. формула

выполняется точно. К результату (5.2.10) можно прийти также при помощи формулы (5.1.12). В самом деле, поскольку, как отмечалось, то в сумме в правой части (5.1.14) остается лишь единственный ненулевой член: что совпадает с (5.2.10).

2. Итак, для вычисления энтропии, если задана матрица вероятностей перехода

следует найти стационарное распределение и воспользоваться формулами (5.2.8), (5.2.9). Уравнение (5.2.7) вполне однозначно определяет стационарное распределение если марковский процесс является эргодическим, т. е. если собственное значение является невырожденным собственным значением матрицы

(5.2.12). Согласно теореме о разложении определителей, из уравнения будет вытекать (5.2 7), если положить

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

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

Как известно [Дуб, 1], состояния дискретного марковского процесса можно расположить в таком порядке, чтобы переходная матрица имела следующий «ящичный» вид:

где

Здесь означает матрицу, имеющую размерность и описывающую переход из подмножества содержащего состояний, в подмножество состояниями. На прочих местах стоят нули. Множества образуют эргодические классы. Из множества происходят переходы в эргодические классы Из каждого такого класса нет выхода. Поэтому внутри каждого класса устанавливается свое стационарное распределение. Оно может быть найдено по формуле типа (5.2.13)

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

стационарное распределение есть линейная комбинация

частных распределений (5.2.15), которые, как легко видеть, являются ортогональными

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

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

Учитывая (5.2.16), (5.2.14), получаем, что удельную энтропию (5.2.8) удобно представить суммой

где частные энтропии

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

Суммирование в (5.2.17), (5.2.18) проводится только по эргодическим классам Подпространство же имеет нулевую стационарную вероятность. Соединение всех эргодических классов на котором концентрируется стационарная вероятность, можно назвать «активным» подпространством. На удельную энтропию распределения и переходы в «пассивном» пространстве оказывают влияние лишь постольку, поскольку они влияют на вероятности Если процесс эргодический, т. е. имеется, кроме лишь один эргодический класс тогда и пассивное пространство вообще не оказывает никакого влияния на удельную энтропию. В этом случае удельная энтропия

марковского процесса в пространстве совпадает с удельной энтропией марковского процесса, протекающего в подпространстве и имеющего матрицу перехода

3. Чтобы проиллюстрировать применение формул, полученных в этом параграфе, рассмотрим несколько несложных примеров.

Пример 1. Рассмотрим сначала простейший дискретный марковский процесс — процесс с двумя состояниями. Матрица (5.2.12) является при этом 2 -матрицей. Вследствие условия нормировки (5.2.2) ее элементы не являются независимыми. Имеются лишь два независимых параметра определяющих матрицу я:

Поскольку в данном случае

то согласно (5.2.13) имеем стационарное распределение

и кроме того

Применяя формулу (5.2.8), находим удельную энтропию

где

Далее по формуле (5.2.10) нетрудно получить граничную энтропию

Пример 2. Пусть теперь имеется процесс с тремя состояниями, имеющий переходную матрицу

При этом, очевидно,

По формуле (5.2.13) находим стационарное распределение

где

Удельная энтропия (5.2.8) оказывается равной

где обозначено

Данный процесс с тремя состояниями будет неэргодическим, если, например, так что матрица перехода имеет «ящичный» вид

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

Первое из них совпадает с (5.2.19). Указанные функции являются ортогональными. Задаваясь начальным распределением по формуле (5.2.16) находим результирующее стационарное распределение

Теперь согласно (5.2.17) нетрудно записать удельную энтропию