Примеры цепей Маркова
В этой статье приведены примеры цепей Маркова и марковских процессов в действии.
Все примеры находятся в счетном пространстве состояний . Обзор цепей Маркова в общем пространстве состояний см. в разделе Цепи Маркова в измеримом пространстве состояний .
Дискретное время
[ редактировать ]Настольные игры с кубиками
[ редактировать ]Игра в змеи и лестницы или любая другая игра, ходы которой полностью определяются игральными костями, представляет собой цепь Маркова, действительно, поглощающую цепь Маркова . В этом отличие от карточных игр, таких как блэкджек , где карты представляют собой «память» о прошлых ходах. Чтобы увидеть разницу, рассмотрим вероятность определенного события в игре. В вышеупомянутых играх в кости единственное, что имеет значение, — это текущее состояние доски. Следующее состояние доски зависит от текущего состояния и следующего броска кубиков. Это не зависит от того, как все дошло до нынешнего состояния. В такой игре, как блэкджек, игрок может получить преимущество, помня, какие карты уже были показаны (и, следовательно, каких карт больше нет в колоде), поэтому следующее состояние (или рука) игры не зависит от прошлые состояния.
Случайное блуждание цепей Маркова
[ редактировать ]Случайное блуждание со смещением по центру
[ редактировать ]Рассмотрим случайное блуждание по числовой прямой, где на каждом шаге позиция (назовем ее x ) может измениться на +1 (вправо) или -1 (влево) с вероятностями:
(где c — константа больше 0)
Например, если константа c равна 1, вероятности движения влево в позициях x = −2,−1,0,1,2 определяются выражением соответственно. Случайное блуждание имеет эффект центрирования, который ослабевает по мере увеличения c .
Поскольку вероятности зависят только от текущей позиции (значения x ), а не от каких-либо предыдущих позиций, это смещенное случайное блуждание удовлетворяет определению цепи Маркова.
Играть в азартные игры
[ редактировать ]Предположим, что вы начинаете с 10 долларов и ставите 1 доллар на бесконечное, честное подбрасывание монеты на неопределенный срок или до тех пор, пока все деньги не будут проиграны. Если представляет собой количество долларов, которые человек получает после n бросков, причем , то последовательность является марковским процессом. Если кто-то знает, что у него сейчас 12 долларов, то можно было бы ожидать, что при равных шансах после следующего броска у него будет либо 11, либо 13 долларов. Это предположение не усиливается дополнительными знаниями о том, что человек начал с 10 долларов, затем поднялся до 11 долларов, снизился до 10 долларов, поднялся до 11 долларов, а затем до 12 долларов. Тот факт, что предположение не улучшается благодаря знанию предыдущих бросков, демонстрирует марковское свойство — свойство случайного процесса без памяти. [1]
Модель языка
[ редактировать ]Этот пример исходил от самого Маркова. [2] Марков выбрал 20 000 букв из пушкинского «Евгения Онегина» , классифицировал их на гласные и согласные и подсчитал вероятности перехода. Стационарное распределение составляет 43,2 процента гласных и 56,8 процента согласных, что близко к фактическому подсчету в книге. [3]
Простая модель погоды
[ редактировать ]Вероятности погодных условий (смоделированных как дождливые или солнечные) с учетом погоды в предыдущий день:может быть представлена матрицей перехода : [4]
Матрица P представляет модель погоды, в которой за солнечным днем с вероятностью 90% последует еще один солнечный день, а за дождливым днем с вероятностью 50% последует еще один дождливый день. [4] Столбцы могут быть помечены как «солнечно» и «дождливо», а строки могут быть помечены в том же порядке.

( P ) ij — вероятность того, что, если данный день относится к типу i , он будетза которым следует день типа j .
Обратите внимание, что сумма строк P равна 1: это потому, что P — стохастическая матрица . [4]
Предсказание погоды
[ редактировать ]Погода в день 0 (сегодня) известна как солнечная. Это представлено вектором начального состояния, в котором «солнечная» запись равна 100%, а «дождливая» запись равна 0%:
Погоду в день 1 (завтра) можно предсказать, умножив вектор состояния из дня 0 на матрицу перехода:
Таким образом, вероятность того, что первый день тоже будет солнечным, составляет 90%.
Погоду на второй день (послезавтра) можно предсказать таким же образом, исходя из вектора состояния, который мы вычислили для первого дня:
или
Общие правила для дня n таковы:
Устойчивое состояние погоды
[ редактировать ]В этом примере прогнозы погоды на более отдаленные дни меняются все меньше и меньше в каждый последующий день и стремятся к вектору устойчивого состояния . [5] Этот вектор представляет вероятность солнечной и дождливой погоды во все дни и не зависит от начальной погоды. [5]
Вектор устойчивого состояния определяется как:
но сходится к строго положительному вектору только в том случае, если P — регулярная матрица перехода (т. е. существуетесть хотя бы один P н со всеми ненулевыми записями).
Поскольку q не зависит от начальных условий, оно должно оставаться неизменным при преобразовании с помощью P . [5] Это делает его собственным вектором (с собственным значением 1) и означает, что его можно получить из P . [5]
С точки зрения непрофессионала, вектор устойчивого состояния — это вектор, который, когда мы умножаем его на P , мы получаем обратно тот же самый вектор. [6] В примере с погодой мы можем использовать это для создания матричного уравнения:
и поскольку они являются вектором вероятности, мы знаем, что
Решение этой пары одновременных уравнений дает вектор устойчивого состояния:
В заключение, в долгосрочной перспективе около 83,3% дней будут солнечными. Не все марковские процессы имеют вектор установившегося состояния. В частности, матрица перехода должна быть регулярной . В противном случае векторы состояния будут колебаться во времени, не сходясь.
Фондовый рынок
[ редактировать ]
Диаграмма состояний для простого примера показана на рисунке справа, где для изображения переходов состояний используется ориентированный граф . Состояния показывают, демонстрирует ли гипотетический фондовый рынок бычий рынок , медвежий рынок или застойную рыночную тенденцию в течение данной недели. Согласно диаграмме, за бычьей неделей следует еще одна бычья неделя в 90% случаев, за медвежьей неделей - в 7,5% случаев, а за застойной неделей - в остальных 2,5% случаев. Обозначая пространство состояний {1 = бычье, 2 = медвежье, 3 = застойное}, матрица перехода для этого примера будет следующей:
Распределение по состояниям можно записать как стохастический вектор-строку x с соотношением x ( п + 1) = х ( н ) П. Итак, если в момент времени n система находится в состоянии x ( н ) , затем через три периода времени, в момент времени n + 3, распределение будет
В частности, если в момент времени n система находится в состоянии 2 (медвежий), то в момент n + 3 распределение будет
Используя матрицу перехода, можно рассчитать, например, долгосрочную долю недель, в течение которых рынок находится в стагнации, или среднее количество недель, которое потребуется, чтобы перейти от застойного рынка к бычьему. Используя вероятности перехода, вероятности устойчивого состояния показывают, что 62,5% недель будут находиться на бычьем рынке, 31,25% недель будут на медвежьем рынке и 6,25% недель будут находиться в стагнации, поскольку:
Подробное развитие и множество примеров можно найти в онлайн-монографии Meyn & Tweedie 2005. [7]
Конечный автомат можно использовать как представление цепи Маркова. Предполагая последовательность независимых и одинаково распределенных входных сигналов (например, символов из двоичного алфавита, выбранных путем подбрасывания монеты), если машина находится в состоянии y в момент времени n , то вероятность того, что она перейдет в состояние x в момент времени n + 1 зависит только от текущего состояния.
Непрерывное время
[ редактировать ]Процесс рождения-смерти
[ редактировать ]Если кто-то лопнет в духовке сто зерен попкорна, причем каждое зерно лопнет в независимое, экспоненциально распределенное время, то это будет марковский процесс с непрерывным временем . Если обозначает количество ядер, появившихся к моменту времени t , задачу можно определить как нахождение количества ядер, которые появятся через какое-то более позднее время. Единственное, что нужно знать, это количество ядер, которые лопнули до момента «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.
Эта статья нуждается в дополнительных цитатах для проверки . ( июнь 2016 г. ) |