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

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

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

Дискретное время

Настольные игры с кубиками

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

Случайное блуждание цепей Маркова

Случайное блуждание со смещением по центру

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

P_{\mathrm {move~left} }={\dfrac {1}{2}}+{\dfrac {1}{2}}\left({\dfrac {x}{c+|x|}}\right)

P_{\mathrm {move~right} }=1-P_{\mathrm {move~left} }

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

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

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

Играть в азартные игры

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

Модель языка

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

Простая модель погоды

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

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%:

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

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

\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%.

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

\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}}

или

\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 таковы:

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

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

Устойчивое состояние погоды

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

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

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

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

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

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

{\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}}

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

q_{1}+q_{2}=1.

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

{\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 = застойное}, матрица перехода для этого примера будет следующей:

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 (п + 1) = х (н) П.$ Итак, если в момент времени $n$ система находится в состоянии $x (н)$ , затем через три периода времени, в момент времени $n + 3,$ распределение будет

{\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$ распределение будет

{\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% недель будут находиться в стагнации, поскольку:

\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 зависит только от текущего состояния.

Непрерывное время

Процесс рождения-смерти

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

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

См. также

Ссылки

^ Оксендал, Б.К. (Бернт Карстен), 1945- (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Шпрингер. ISBN 3540047581 . OCLC 52203046 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )
^ Марков А.А. "Пример статистического анализа текста Евгения Онегина, иллюстрирующий объединение испытаний в Цепочку". Вестник Императорской академии наук Санкт-Петербурга, серия 6 (1913): 153162.
^ Введение Гринстеда и Снелла в вероятность , стр. 465
^ Jump up to: ^а ^б ^с Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии . НЛ: Северная Голландия Elsevier. стр. 73–95 . ISBN 978-0-444-52965-7 .
^ Jump up to: ^а ^б ^с ^д Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии . НЛ: Северная Голландия Elsevier. стр. 73–95 . ISBN 978-0-444-52965-7 .
^ «Установившееся (состояние) марковских процессов» . Репетиторы Блумингтона.
^ С. П. Мейн и Р. Л. Твиди, 2005. Цепи Маркова и стохастическая стабильность. Архивировано 3 сентября 2013 г. в Wayback Machine.

Внешние ссылки

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

[:3-1] Оксендал, Б.К. (Бернт Карстен), 1945- (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Шпрингер. ISBN 3540047581 . OCLC 52203046 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

[2] Марков А.А. "Пример статистического анализа текста Евгения Онегина, иллюстрирующий объединение испытаний в Цепочку". Вестник Императорской академии наук Санкт-Петербурга, серия 6 (1913): 153162.

[3] Введение Гринстеда и Снелла в вероятность , стр. 465

[:0-4] Jump up to: ^а ^б ^с Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии . НЛ: Северная Голландия Elsevier. стр. 73–95 . ISBN 978-0-444-52965-7 .

[:1-5] Jump up to: ^а ^б ^с ^д Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии . НЛ: Северная Голландия Elsevier. стр. 73–95 . ISBN 978-0-444-52965-7 .

[6] «Установившееся (состояние) марковских процессов» . Репетиторы Блумингтона.

[MCSS-7] С. П. Мейн и Р. Л. Твиди, 2005. Цепи Маркова и стохастическая стабильность. Архивировано 3 сентября 2013 г. в Wayback Machine.

[1]

[2]

[3]

[4]

[5]

[6]

[7]