Примеры цепей Маркова

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

Все примеры находятся в счетном пространстве состояний . Для обзора цепей Маркова в общем пространстве состояний см. Цепи Маркова в измеримом пространстве состояний .

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

Рассмотрим случайное блуждание по числовой прямой, где на каждом шаге позиция (назовем ее x ) может измениться на +1 (вправо) или −1 (влево) с вероятностями:

${\displaystyle P_{\mathrm {переместить~влево} }={\dfrac {1}{2}}+{\dfrac {1}{2}}\left({\dfrac {x}{c+|x|}}\right)}$

${\displaystyle P_{\mathrm {перемещение~вправо} }=1-P_{\mathrm {перемещение~влево} }}$

(где c — константа больше 0)

Например, если константа c равна 1, вероятности перемещения влево в позициях x = −2,−1,0,1,2 определяются соответственно. Случайное блуждание имеет эффект центрирования, который ослабевает с увеличением c .${\displaystyle {\dfrac {1}{6}},{\dfrac {1}{4}},{\dfrac {1}{2}},{\dfrac {3}{4}},{\dfrac {5}{6}}}$

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

Предположим, что кто-то начинает с $10 и ставит $1 на бесконечное, честное, подбрасывание монеты до бесконечности или до тех пор, пока все деньги не будут проиграны. Если представляет собой количество долларов, которые у него есть после n подбрасываний, причем , то последовательность является марковским процессом. Если кто-то знает, что у него сейчас $12, то можно ожидать, что при равных шансах у него будет либо $11, либо $13 после следующего подбрасывания. Это предположение не улучшается дополнительным знанием о том, что человек начал с $10, затем поднялся до $11, снизился до $10, поднялся до $11, а затем до $12. Тот факт, что предположение не улучшается знанием более ранних подбрасываний, демонстрирует свойство Маркова , свойство без памяти стохастического процесса. ^[1]${\displaystyle X_{n}}$${\displaystyle X_{0}=10}$${\displaystyle \{X_{n}:n\in \mathbb {N} \}}$

Этот пример взят у самого Маркова. ^{[2] Марков выбрал 20 000 букв из} «Евгения Онегина» Пушкина , классифицировал их на гласные и согласные и подсчитал вероятности перехода. Стационарное распределение составляет 43,2 процента гласных и 56,8 процента согласных, что близко к фактическому количеству в книге. ^[3]$${\displaystyle {\begin{array}{lll}&{\text{гласная}}&{\text{согласная}}\\{\text{гласная}}&.128&.872\\{\text{согласная}}&.663&.337\end{array}}}$$

Вероятности погодных условий (моделируемых как дождливые или солнечные) с учетом погоды предыдущего дня можно представить с помощью матрицы перехода : ^[4]

${\displaystyle P={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}}$

Матрица P представляет собой погодную модель, в которой за солнечным днем ​​с вероятностью 90% последует еще один солнечный день, а за дождливым днем ​​с вероятностью 50% последует еще один дождливый день. ^[4] Столбцы можно обозначить как «солнечно» и «дождливо», а строки можно обозначить в том же порядке.

( P ) _ij — вероятность того, что если данный день относится к типу i , то за ним последует день типа j .

Обратите внимание, что сумма строк матрицы P равна 1: это потому, что P — стохастическая матрица . ^[4]

Известно, что погода в день 0 (сегодня) солнечная. Это представлено начальным вектором состояния, в котором запись «солнечно» составляет 100%, а запись «дождливо» составляет 0%:

${\displaystyle \mathbf {x} ^{(0)}={\begin{bmatrix}1&0\end{bmatrix}}}$

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

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {x} ^{(0)}P={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.9&0.1\end{bmatrix}}}$

Таким образом, вероятность того, что первый день также будет солнечным, составляет 90%.

Погоду на второй день (послезавтра) можно предсказать таким же образом, используя вектор состояния, который мы вычислили для первого дня:

${\displaystyle \mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P=\mathbf {x} ^{(0)}P^{2}={\begin{bmatrix}1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}^{2}={\begin{bmatrix}0.86&0.14\end{bmatrix}}}$

или

${\displaystyle \mathbf {x} ^{(2)}=\mathbf {x} ^{(1)}P={\begin{bmatrix}0.9&0.1\end{bmatrix}}{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}={\begin{bmatrix}0.86&0.14\end{bmatrix}}}$

Общие правила для дня n :

${\displaystyle \mathbf {x} ^{(n)}=\mathbf {x} ^{(n-1)}P}$

${\displaystyle \mathbf {x} ^{(n)}=\mathbf {x} ^{(0)}P^{n}}$

В этом примере прогнозы погоды на более отдаленные дни меняются все меньше и меньше с каждым последующим днем ​​и стремятся к вектору устойчивого состояния. ^[5] Этот вектор представляет вероятности солнечной и дождливой погоды во все дни и не зависит от начальной погоды. ^[5]

Вектор устойчивого состояния определяется как:

${\displaystyle \mathbf {q} =\lim _{n\to \infty }\mathbf {x} ^{(n)}}$

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

Поскольку q не зависит от начальных условий, он должен оставаться неизменным при преобразовании P. [ ^5] Это делает его собственным вектором (с собственным значением 1) и означает , что его можно вывести из P. ^[5]

Проще говоря, стационарный вектор — это вектор, который при умножении на P возвращает нам тот же самый вектор. ^[6] Для примера с погодой мы можем использовать это для составления матричное уравнение:

${\displaystyle {\begin{aligned}P&={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}\\\mathbf {q} P&=\mathbf {q} &&{\text{(}}\mathbf {q} {\text{ is unchanged by }}P{\text{.)}}\\&=\mathbf {q} I\\\mathbf {q} (P-I)&=\mathbf {0} \\\mathbf {q} \left({\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}-{\begin{bmatrix}1&0\\0&1\end{bmatrix}}\right)&=\mathbf {0} \\\mathbf {q} {\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}&=\mathbf {0} \\{\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}{\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}&={\begin{bmatrix}0&0\end{bmatrix}}\\-0.1q_{1}+0.5q_{2}&=0\end{aligned}}}$

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

${\displaystyle q_{1}+q_{2}=1.}$

Решение этой пары одновременных уравнений дает вектор стационарного состояния:

${\displaystyle {\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}={\begin{bmatrix}0.833&0.167\end{bmatrix}}}$

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

Диаграмма состояний для простого примера показана на рисунке справа, с использованием направленного графа для изображения переходов состояний . Состояния представляют, демонстрирует ли гипотетический фондовый рынок бычий рынок , медвежий рынок или застойный рыночный тренд в течение данной недели. Согласно рисунку, за бычьей неделей следует еще одна бычья неделя в 90% случаев, за медвежьей неделей в 7,5% случаев и застойная неделя в оставшиеся 2,5% случаев. Обозначая пространство состояний {1 = бык, 2 = медведь, 3 = застой}, матрица перехода для этого примера выглядит следующим образом:

${\displaystyle P={\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}.}$

Распределение по состояниям можно записать как стохастический вектор-строку x с отношением x ^{( n  + 1)}  =  x ^{( n )} P . Таким образом, если в момент времени n система находится в состоянии x ^{( n )} , то через три периода времени, в момент времени n  + 3, распределение будет

${\displaystyle {\begin{aligned}x^{(n+3)}&=x^{(n+2)}P=\left(x^{(n+1)}P\right)P\\\\&=x^{(n+1)}P^{2}=\left(x^{(n)}P\right)P^{2}\\&=x^{(n)}P^{3}\\\end{aligned}}}$

В частности, если в момент времени n система находится в состоянии 2 (медведь), то в момент времени n  + 3 распределение будет

${\displaystyle {\begin{aligned}x^{(n+3)}&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}^{3}\\[5pt]&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.7745&0.17875&0.04675\\0.3575&0.56825&0.07425\\0.4675&0.37125&0.16125\\\end{bmatrix}}\\[5pt]&={\begin{bmatrix}0.3575&0.56825&0.07425\end{bmatrix}}.\end{aligned}}}$

Используя матрицу перехода, можно рассчитать, например, долгосрочную долю недель, в течение которых рынок находится в состоянии стагнации, или среднее количество недель, которое потребуется, чтобы перейти от стагнации к бычьему рынку. Используя вероятности перехода, вероятности устойчивого состояния указывают, что 62,5% недель будут на бычьем рынке, 31,25% недель будут на медвежьем рынке и 6,25% недель будут в состоянии стагнации, поскольку:

${\displaystyle \lim _{N\to \infty }\,P^{N}={\begin{bmatrix}0.625&0.3125&0.0625\\0.625&0.3125&0.0625\\0.625&0.3125&0.0625\end{bmatrix}}}$

Подробную разработку и множество примеров можно найти в онлайн-монографии Meyn & Tweedie 2005. ^[7]

Конечный автомат может быть использован в качестве представления цепи Маркова. Предполагая последовательность независимых и одинаково распределенных входных сигналов (например, символы из двоичного алфавита, выбранные путем подбрасывания монеты), если автомат находится в состоянии y в момент времени n , то вероятность того, что он перейдет в состояние x в момент времени n  + 1, зависит только от текущего состояния.

Если кто-то поджигает сто зерен попкорна в духовке, причем каждое зернышко поджигается в независимый экспоненциально распределенный момент времени, то это будет непрерывный во времени марковский процесс . Если обозначает количество зерен, поджигаемых до момента времени t , то задачу можно определить как нахождение количества зерен, поджигаемых в более позднее время. Единственное, что нужно знать, это количество зерен, поджигаемых до момента времени «t». Не обязательно знать, когда они поджигались, поэтому знание предыдущих моментов времени «t» не имеет значения.${\displaystyle X_{t}}$${\displaystyle X_{t}}$

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

• Марк В. Шейни
• Система взаимодействующих частиц
• Стохастические клеточные автоматы

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Examples of Markov chains" – news · newspapers · books · scholar · JSTOR (June 2016) (Learn how and when to remove this message)

• Монополия как цепь Маркова