5.2. Что такое марковский процесс?

До сих пор в книге использовались лишь вероятности появления различных символов алфавита источника.Знакомство с естественными языками показывает, что

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

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

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

Считается, что система всегда находится в каком-то состоянии. Для источника с памятью первого порядка имеется состояний, по одному для каждого из символов алфавита источника. Примером предсказания с памятью первого порядка является предсказание погоды типа: «Погода завтра будет такой же, как сегодня». Для источника памятью второго порядка имеется состояний, по одному для каждой нары символов источника. Линейное предсказание является источником с (памятью второго порядка; следующее значение оценивается по двум предыдущим — . В общем случае для источника с памятью порядка у марковского процесса имеется состояний.

Рассматривая простой пример источника с памятью первого порядка, предположим, что имеется алфавит из трех символов — Пусть вероятность того, что за буквой а следует любая из трех букв, равна 1/3. Пусть вероятность тою, что за буквой снова следует буква равна 1/2, а вероятность того, что за буквой следует буква а или с, равна 1/4. Наконец, пусть вероятность того, что за буквой с следует другая буква с, равна 1/2, а вероятность того, что за с следует равна 1/4. Тогда имеем

Для марковского процесса такого же типа полезно, рассматривать граф переходов. В этом случае, конечно, имеется три состояния (рис. 5.2.1), помеченных буквами с и обозначенных кружками. Каждая стрелка соответствует переходу из одного состояния в другое; вероятность перехода равна числу, стоящему у этой стрелки Например, соответствует стрелке, идущей из в и равна 1/4. В нашем примере у каждого состояния имеется три входящих и три выходящих стрелки.

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

Граф можно представить в виде матрицы

причем текущее состояние обозначается буквой слева от матрицы, а следующее состояние — буквой над матрицей. Элементы матрицы называются переходными вероятностями. Сумма всех элементов любой матрицы переходных вероятностей должна равняться 1, поскольку текущее состояние должно обязательно перейти в какое-то состояние.

Рис. 5.2.1. Граф переходов

Предположим теперь, что вместо текущего состояния имеется лишь распределение вероятностей для текущего состояния, где Может случиться, что одна из вероятностей равна 1, а остальные две равны 0; это означает, что текущее состояние точно определено. Если умножить этот вектор-строку справа на матрицу переходных вероятностей (5.2.1), получим распределение вероятностей завтрашней погоды:

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

Записывая матрицу в виде

сразу видим, что элементы квадрата матрицы переходных вероятностей меняются не так сильно, как элементы первоначальной матрицы (5.2.1). Если возвести в квадрат матрицу (5.2.2), получим матрицу для предсказания погоды на 4 дня вперед. В этом частном случае несложно доказать, что

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

Сохраняется ли для последовательных матриц переходных вероятностей равенство 1 суммы элементов любой строки? Для доказательства того, что это свойство сохраняется, образуем из двух Общих матриц элементы третьей матрицы

Предположение о суммах элементов в строках имеют вид Поэтому

что и требовалось.

Какой вид имеет распределение вероятностей состояний с для предельной матрицы? Ясно, что это распределение не должно меняться при переходе к следующему дню; иначе говоря, для частного случая матрицы (15.2.1) должно, выполняться следующее равенство:

Это эквивалентно системе из трех уравнений:

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

Таким образом, независимо от первоначального распределения вероятностей для матрицы переходных вероятностей (5.2.1) получаем одно и то же распределяв вероятностей (3/11, 4/11, 4/11).

Задачи

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

5.2.2. Вычислите стационарное распределение вероятностей состояний, используя матрицу переходных вероятностей (5.2.2).