Jump to content

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

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

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

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

[ редактировать ]

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

[ редактировать ]

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

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

[ редактировать ]

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

[ редактировать ]

Рассмотрим случайное блуждание по числовой прямой, где на каждом шаге позиция (назовем ее 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» не имеет значения.

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

См. также

[ редактировать ]
  1. ^ Оксендал, Б.К. (Бернт Карстен), 1945- (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Шпрингер. ISBN  3540047581 . OCLC   52203046 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )
  2. ^ Марков А.А. "Пример статистического анализа текста Евгения Онегина, иллюстрирующий объединение испытаний в Цепочку". Вестник Императорской академии наук Санкт-Петербурга, серия 6 (1913): 153162.
  3. ^ Введение Гринстеда и Снелла в вероятность , стр. 465
  4. ^ Jump up to: а б с Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии . НЛ: ​​Северная Голландия Elsevier. стр. 73–95 . ISBN  978-0-444-52965-7 .
  5. ^ Jump up to: а б с д Ван Кампен, Н.Г. (2007). Случайные процессы в физике и химии . НЛ: ​​Северная Голландия Elsevier. стр. 73–95 . ISBN  978-0-444-52965-7 .
  6. ^ «Установившееся (состояние) марковских процессов» . Репетиторы Блумингтона.
  7. ^ С. П. Мейн и Р. Л. Твиди, 2005. Цепи Маркова и стохастическая стабильность. Архивировано 3 сентября 2013 г. в Wayback Machine.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c07ad4ae335b7d3634a877ff8014ee7f__1720461660
URL1:https://arc.ask3.ru/arc/aa/c0/7f/c07ad4ae335b7d3634a877ff8014ee7f.html
Заголовок, (Title) документа по адресу, URL1:
Examples of Markov chains - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)