Примеры цепей Маркова - Examples of Markov chains

Эта страница содержит примеры Цепи Маркова и марковские процессы в действии.

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

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

Настольные игры в кости

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

Цепи Маркова случайного блуждания

Смотрите также: Случайная прогулка

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

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

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

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

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

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

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

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

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

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

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

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

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

Приведенная выше матрица в виде графика.

(п)_{я j} это вероятность того, что если данный день относится к типу я, за ним последует день типа j.

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

Предсказание погоды

Погода в день 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%.

Погоду на 2 день (послезавтра) можно предсказать точно так же:

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

Общие правила дня п находятся:

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

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

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

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

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

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

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

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

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

Распределение по состояниям можно записать как стохастический вектор строки Икс с отношением Икс^(п + 1) = Икс^(п)п. Так что если вовремя п система в состоянии Икс^(п), затем через три периода времени п + 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}}}$

Прогнозирование цепей Маркова на 3 дискретных шагах на основе матрицы перехода из примера слева.^[5]

В частности, если вовремя п система находится в состоянии 2 (медведь), то в момент времени п + 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}}}$

Прогнозирование цепей Маркова на 50 дискретных шагах. Опять же, используется матрица перехода слева.^[5]

Используя матрицу перехода, можно рассчитать, например, долгосрочную долю недель, в течение которых рынок находится в состоянии стагнации, или среднее количество недель, которое потребуется для перехода от стагнационного к бычьему рынку. Используя вероятности перехода, вероятности устойчивого состояния показывают, что 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.^[6]

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

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

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

Смотрите также: Процесс рождения-смерти и Точечный процесс Пуассона

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

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

Смотрите также

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

Рекомендации

1. Эксендал, Б. К. (Бернт Карстен), 1945- (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Springer. ISBN  3540047581. OCLC  52203046.
2. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 1–235. ISBN  978-1-119-38755-8.
3. Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии. NL: Северная Голландия, Эльзевир. стр.73 –95. ISBN  978-0-444-52965-7.
4. Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии. NL: Северная Голландия, Эльзевир. стр.73 –95. ISBN  978-0-444-52965-7.
5. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. Хобокен, Нью-Джерси: Джон Уайли и сыновья. С. 131–163. ISBN  9781119387572. OCLC  982373850.
6. С.П. Мейн и Р.Л. Твиди, 2005. Марковские цепи и стохастическая устойчивость В архиве 2013-09-03 на Wayback Machine

внешняя ссылка

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