Цепи Маркова: от переходной матрицы до стационарного распределения

Задача: синоптик-минималист. Погода бывает солнечной или дождливой, и завтрашняя зависит только от сегодняшней: за солнечным днём солнце повторяется с вероятностью $0,7$, за дождливым дожди продолжаются с вероятностью $0,6$. Вопрос, который страшно задать: какая доля дней в длинном прогнозе будет дождливой? Перебирать недели вручную безнадёжно. Ответ прячется в одной матрице и одном уравнении — и попутно объясняет, почему Google ранжирует страницы, а супермаркеты планируют запасы.

Цепь Маркова: состояния и переходные вероятности#

Система в каждый момент находится в одном из состояний — у нас их два: «Солнечно» и «Дождь». Числа $0,7$ и $0,6$ — переходные вероятности: шанс перейти из состояния в состояние за один шаг. Ключевое требование — марковское свойство: следующий шаг зависит только от текущего состояния, а не от истории. Погода «без памяти»: если сегодня солнечно, шанс завтрашнего дождя один и тот же — было ли солнечно неделю подряд или вчера прорвался единственный ливень.

Все переходные вероятности укладываются в матрицу перехода $P$. Наша погода:

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

Один шаг = одно умножение на матрицу#

Распределение по состояниям — строка вероятностей, например старт ${\pi }_0=(1,0)$: сто процентов солнечных прогулок. Один день прогноза — умножение строки на матрицу:

Компоненты считаются по правилу «строка на столбец», то есть обычным умножением матриц. Через два дня: ${\pi }_2={\pi }_0{P}^2$, и матрицу $P^2$ можно посчитать целиком — её элементы читаются как вероятности перехода за два шага:

Смотрите, что происходит по мере возведения в степень: строки матрицы сближаются. $P$ начинается с $0,7$ и $0,4$ в первом столбце, $P^2$ даёт уже $0,61$ и $0,52$, ещё несколько умножений — и обе строки почти совпадут. Это не совпадение, а признак того, что стартовая погода забывается: к пятому-шестому дню прогноз перестаёт зависеть от того, с чего начали.

Стационарное распределение: уравнение πP = π#

Предельное распределение, которое больше не меняется при умножении на $P$, называется стационарным. Формально: $\pi P=\pi$ плюс условие нормировки ${\pi }_1+{\pi }_2=1$. Для нашей погоды выпишем уравнения покомпонентно:

Стационарное распределение отвечает на вопрос «какая доля времени» — это следствие закона больших чисел: доля дождливых дней в длинной серии сходится к ${\pi }_2$, хотя соседние дни остаются зависимыми. Заметьте, что $43\%$ дождя больше, чем «шанс дождя после солнца» $30\%$, и меньше, чем $60\%$ самоподдержания дождя: стационарное значение — средневзвешенное двух режимов, а не какое-то одно переходное число.

Скорость сходимости — отдельная красота. Разность $P^n-$ предельной матрицы затухает как $|p+q-1{|}^n$; для нашей погоды $|0,7+0,6-1|=0,3$ — за пять шагов поправка сжимается почти в двести раз. А теперь уберите память у погоды до предела: поставьте оба ползунка на $0,95$. Стационарное распределение то же — $(0,5;0,5)$, ведь ${\pi }_1=\frac{1-q}{2-p-q}=\frac{0,05}{0,1}=\frac{1}{2}$, — но затухание идёт как $0,9^n$: в самозамкнутых состояниях система держится за старт надолго.

Взгляд линейной алгебры#

Уравнение $\pi P=\pi$ переписывается как $(P^{\top }-E){\pi }^{\top }=\vec{0}$ — то есть стационарное распределение это собственный вектор матрицы $P^{\top }$ с собственным значением $1$. У всякой стохастической матрицы единица — максимальное собственное значение, поэтому равновесие существует и устойчиво; почему так и как такое решать систематически — в уроке про собственные значения. Из этой же картины достаётся скорость сходимости: второе по модулю собственное значение равно $p+q-1$ — ровно то число, которое мы вычислили выше.

Ошибки, которые дают неверное равновесие#

• Столбцы вместо строк: записали матрицу так, что суммы по столбцам равны единице, а умножаете строку справа — получите другое распределение. Проверка: сумма строк $P$ обязана быть единицами.
• Забыта нормировка: из $\pi P=\pi$ находится направление, а не масштаб — бесконечно много кратных решений. Всегда добавляйте ${\pi }_1+{\pi }_2+\cdots =1$.
• Подстановка начального распределения в ответ: при стартовой погоде $(1,0)$ первый день уже даёт $70\%$ солнца, но это не стационарная доля — она появится лишь после нескольких умножений.
• Дроби без приведения: при проверке $0,3{\pi }_1=\frac{6}{35}$ нужно сравнивать с $0,4{\pi }_2$ в том же знаменателе $35$, иначе «несовпадение» на пустом месте. Приводите все сравнения к одному знаменателю.

Быстрый счёт стационарного распределения: для матрицы $\left(\begin{array}{cc}0,7& 0,3\\ 0,4& 0,6\end{array}\right)$ ищем $\pi P=\pi$. Уравнения: $0,7{\pi }_1+0,4{\pi }_2={\pi }_1$ и нормировка ${\pi }_1+{\pi }_2=1$. Из первого $0,3{\pi }_1=0,4{\pi }_2$, то есть ${\pi }_1=\frac{4}{7}$, ${\pi }_2=\frac{3}{7}$. Интерпретация: несмотря на асимметрию переходов, в долгом пределе примерно 57% времени система проведёт в первом состоянии. Проверка одной строкой: подстановка обеих компонент во второе уравнение сходится — $0,7\cdot \frac{4}{7}+0,4\cdot \frac{3}{7}=\frac{4}{7}$.

Следующий урок — случайные процессы: пуассоновский поток и времена ожидания: события во времени вместо состояний по дням. Для повторения матричной части держите под рукой умножение матриц и шпаргалку по терверу; прикладной статистический взгляд на модели связи — в корреляции и регрессии.