Рассмотрим задачу об осле, стоящем точно между двумя копнами: соломы ржи и соломы пшеницы (рис. 10.5).

Осел стоит между двумя копнами: "Рожь" и "Пшеница" (рис. 10.5). Каждую минуту он либо передвигается на десять метров в сторону первой копны (с вероятностью ), либо в сторону второй копны (с вероятностью ), либо остается там, где стоял (с вероятностью ); такое поведение называется одномерным случайным блужданием. Будем предполагать, что обе копны являются "поглощающими" в том смысле, что если осел подойдет к одной из копен, то он там и останется. Зная расстояние между двумя копнами и начальное положение осла, можно поставить несколько вопросов, например: у какой копны он очутится с большей вероятностью и какое наиболее вероятное время ему понадобится, чтобы попасть туда?

Чтобы исследовать эту задачу подробнее, предположим, что расстояние между копнами равно пятидесяти метрам и что наш осел находится в двадцати метрах от копны "Пшеницы". Если места, где можно остановиться, обозначить через ( - сами копны), то его начальное положение можно задать вектором -я компонента которого равна вероятности того, что он первоначально находится в . Далее, по прошествии одной минуты вероятности его местоположения описываются вектором , а через две минуты - вектором . Ясно, что непосредственное вычисление вероятности его нахождения в заданном месте по прошествии минут становится затруднительным. Оказалось, что удобнее всего ввести для этого матрицу перехода .

Пусть - вероятность того, что он переместится из в за одну минуту. Например, и . Эти вероятности называются вероятностями перехода , а -матрицу называют матрицей перехода . Заметим, что каждый элемент матрицы неотрицателен и что сумма элементов любой из строк равна единице. Из всего этого следует, что - начальный вектор -строка, определенный выше, местоположение осла по прошествии одной минуты описывается вектором-строкой , а после минут - вектором . Другими словами, -я компонента вектора определяет вероятность того, что по истечении минут осел оказался в .

Можно обобщить эти понятия. Назовем вектором вероятностей вектор -строку, все компоненты которого неотрицательны и дают в сумме единицу. Тогда матрица перехода определяется как квадратная матрица , в которой каждая строка является вектором вероятностей. Теперь можно определить цепь Маркова (или просто цепь) как пару , где есть - матрица перехода , а есть - вектор -строка. Если каждый элемент из рассматривать как вероятность перехода из позиции в позицию , а - как начальный вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова , которое можно найти в книгах по теории вероятностей (см. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир. 1967) Позиция обычно называется состоянием цепи . Опишем различные способы их классификации.

Нас будет интересовать следующее: можно ли попасть из одного данного состояния в другое, и если да, то за какое наименьшее время. Например, в задаче об осле из в можно попасть за три минуты и вообще нельзя попасть из в . Следовательно, в основном мы будем интересоваться не самими вероятностями , а тем, положительны они или нет. Тогда появляется надежда, что все эти данные удастся представить в виде орграфа , вершины которого соответствуют состояниям, а дуги указывают на то, можно ли перейти из одного состояния в другое за одну минуту. Более точно, если каждое состояние представлено соответствующей ему вершиной).

Определение. Однородной называют цепь Маркова, если условная вероятность (переход из состояния в состоянии) не зависит от номера испытания. Поэтому вместо пишут просто.

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

Таким образом, случайное блуждание? пример однородной цепи Маркова с дискретным временем.

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

Таким образом, в обозначении первый индекс указывает номер предшествующего, а второй? номер последующего состояния. Например, - вероятность перехода из второго состояния в третье.

Пусть число состояний конечно и равно.

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

Так как в каждой строке матрицы помещены вероятности событий (перехода из одного и того же состояния в любое возможное состояние), которые образуют полную группу, то сумма вероятностей этих событий равна единице. Другими словами, сумма переходных вероятностей каждой строки матрицы перехода равна единице:

Приведем пример матрицы перехода системы, которая может находиться в трех состояниях; переход из состояния в состояние происходит по схеме однородной цепи Маркова; вероятности перехода задаются матрицей:

Здесь видим, что если система находилось в состоянии, то после изменения состояния за один шаг она с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,2 перейдет в состояние, то после перехода она может оказаться в состояниях; перейти же из состояния в она не может. Последняя строка матрицы показывает нам, что из состояния перейти в любое из возможных состояний с одной и той же вероятностью 0,1.

На основе матрицы перехода системы можно построить так называемый граф состояний системы, его еще называют размеченный граф состояний. Это удобно для наглядного представления цепи. Порядок построения граф рассмотрим на примере.

Пример 2. По заданной матрице перехода построить граф состояний.

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

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

Цепь Маркова – череда событий, в которой каждое последующее событие зависит от предыдущего. В статье мы подробнее разберём это понятие.

Цепь Маркова – это распространенный и довольно простой способ моделирования случайных событий. Используется в самых разных областях, начиная генерацией текста и заканчивая финансовым моделированием. Самым известным примером является SubredditSimulator . В данном случае Цепь Маркова используется для автоматизации создания контента во всем subreddit.

Цепь Маркова понятна и проста в использовании, т. к. она может быть реализована без использования каких-либо статистических или математических концепций. Цепь Маркова идеально подходит для изучения вероятностного моделирования и Data Science.

Сценарий

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

Теперь вам захотелось научиться предсказывать погоду на завтрашний день. Интуитивно вы понимаете, что погода не может кардинально поменяться за один день. На это влияет множество факторов. Завтрашняя погода напрямую зависит от текущей и т. д. Таким образом, для того чтобы предсказывать погоду, вы на протяжении нескольких лет собираете данные и приходите к выводу, что после пасмурного дня вероятность солнечного равна 0,25. Логично предположить, что вероятность двух пасмурных дней подряд равна 0,75, так как мы имеем всего два возможных погодных условия.

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

Этот пример показывает ключевые понятия цепи Маркова. Цепь Маркова состоит из набора переходов, которые определяются распределением вероятностей, которые в свою очередь удовлетворяют Марковскому свойству.

Обратите внимание, что в примере распределение вероятностей зависит только от переходов с текущего дня на следующий. Это уникальное свойство Марковского процесса – он делает это без использования памяти. Как правило, такой подход не способен создать последовательность, в которой бы наблюдалась какая-либо тенденция. Например, в то время как цепь Маркова способна сымитировать стиль письма, основанный на частоте использования какого-то слова, она не способна создать тексты с глубоким смыслом, так как она может работать только с большими текстами. Именно поэтому цепь Маркова не может производить контент, зависящий от контекста.

Модель

Формально, цепь Маркова – это вероятностный автомат. Распределение вероятностей переходов обычно представляется в виде матрицы. Если цепь Маркова имеет N возможных состояний, то матрица будет иметь вид N x N, в которой запись (I, J) будет являться вероятностью перехода из состояния I в состояние J. Кроме того, такая матрица должна быть стохастической, то есть строки или столбцы в сумме должны давать единицу. В такой матрице каждая строка будет иметь собственное распределение вероятностей.

Общий вид цепи Маркова с состояниями в виде окружностей и ребрами в виде переходов.

Примерная матрица перехода с тремя возможными состояниями.

Цепь Маркова имеет начальный вектор состояния, представленный в виде матрицы N x 1. Он описывает распределения вероятностей начала в каждом из N возможных состояний. Запись I описывает вероятность начала цепи в состоянии I.

Этих двух структур вполне хватит для представления цепи Маркова.

Мы уже обсудили, как получить вероятность перехода из одного состояния в другое, но что насчет получения этой вероятности за несколько шагов? Для этого нам необходимо определить вероятность перехода из состояния I в состояние J за M шагов. На самом деле это очень просто. Матрицу перехода P можно определить вычислением (I, J) с помощью возведения P в степень M. Для малых значений M это можно делать вручную, с помощью повторного умножения. Но для больших значений M, если вы знакомы с линейной алгеброй, более эффективным способом возведения матрицы в степень будет сначала диагонализировать эту матрицу.

Цепь Маркова: заключение

Теперь, зная, что из себя представляет цепь Маркова, вы можете легко реализовать её на одном из языков программирования. Простые цепи Маркова являются фундаментом для изучения более сложных методов моделирования.

Способы математических описаний марковских случайных процессов в системе с дискретными состояниями (ДС) зависят от того, в какие моменты времени (заранее известные или случайные) могут происходить переходы системы из состояния в состояние.
Если переход системы из состояния в состояние возможен в заранее фиксированные моменты времени, имеем дело со случайным марковским процессом с дискретным временем. Если переход возможен в любой случайный момент времени, то имеем дело со случайным марковским процессом с непрерывным временем.
Пусть имеется физическая система S , которая может находиться в n состояниях S 1 , S 2 , …, S n . Переходы из состояния в состояние возможны только в моменты времени t 1 , t 2 , …, t k , назовём эти моменты времени шагами. Будем рассматривать СП в системе S как функцию целочисленного аргумента 1, 2, …, k , где аргументом является номер шага.
Пример: S 1 → S 2 → S 3 → S 2 .
Условимся обозначать S i ( k ) – событие, состоящее в том, что после k шагов система находится в состоянии S i .
При любом k события S 1 ( k ) , S 2 ( k ) ,…, S n ( k ) образуют полную группу событий и являются несовместными.

Процесс в системе можно представить как цепочку событий.
Пример:S 1 (0) , S 2 (1) , S 3 (2) , S 5 (3) ,….
Такая последовательность называется марковской цепью , если для каждого шага вероятность перехода из любого состояния S i в любое состояние S j не зависит от того, когда и как система пришла в состояние S i .
Пусть в любой момент времени после любого k -го шага система S может находиться в одном из состояний S 1 , S 2 , …, S n , т. е. может произойти одно событие из полной группы событий: S 1 ( k ) , S 2 ( k ) , …, S n ( k ) . Обозначим вероятности этих событий:
P 1 (1) = P (S 1 (1)); P 2 (1) = P (S 2 (1)); …; P n (1) = P (S n ( k ));
P 1 (2) = P (S 1 (2)); P 2 (2) = P (S 2 (2)); …; P n (2) = P (S n (2));
P 1 (k ) = P (S 1 (k )); P 2 (k ) = P (S 2 (k )); …; P n (k ) = P (S n (k )).
Легко заметить, что для каждого номера шага выполняется условие
P 1 (k ) + P 2 (k ) +…+ P n (k ) = 1.
Назовём эти вероятности вероятностями состояний .следовательно, задача будет звучать следующим образом: найти вероятности состояний системы для любого k .
Пример. Пусть имеется какая-то система, которая может находиться в любом из шести состояний. тогда процессы, происходящие в ней, можно изобразить либо в виде графика изменения состояния системы (рис. 7.9, а ), либо в виде графа состояний системы (рис. 7.9, б ).

а)

Рис. 7.9
Также процессы в системе можно изобразить в виде последовательности состояний: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Вероятность состояния на (k + 1)-м шаге зависит только от состояния на k- м шаге.
Для любого шага k существуют какие-то вероятности перехода системы из любого состояния в любое другое состояние, назовем эти вероятности переходными вероятностями марковской цепи.
Некоторые из этих вероятностей будут равны 0, если переход из одного состояния в другое невозможен за один шаг.
Марковская цепь называется однородной , если переходные состояния не зависят от номера шага, в противном случае она называется неоднородной .
Пусть имеется однородная марковская цепь и пусть система S имеет n возможных состояний: S 1 , …, S n . Пусть для каждого состояния известна вероятность перехода в другое состояние за один шаг, т. е. P ij (из S i в S j за один шаг), тогда мы можем записать переходные вероятности в виде матрицы.

. (7.1)
По диагонали этой матрицы расположены вероятности того, что система переходит из состояния S i в то же состояние S i .
Пользуясь введенными ранее событиями , можно переходные вероятности записать как условные вероятности:
.
Очевидно, что сумма членов в каждой строке матрицы (1) равна единице, поскольку события образуют полную группу несовместных событий.

При рассмотрении марковских цепей, так же как и при анализе марковского случайного процесса, используются различные графы состояний (рис. 7.10).

Рис. 7.10

Данная система может находиться в любом из шести состояний, при этом P ij – вероятность перехода системы из состояния S i в состояние S j . Для данной системы запишем уравнения, что система находилась в каком-либо состоянии и из него за время t не вышла:

В общем случае марковская цепь является неоднородной, т. е. вероятность P ij меняется от шага к шагу. Предположим, что задана матрица вероятностей перехода на каждом шаге, тогда вероятность того, что система S на k -м шаге будет находиться в состоянии S i , можно найти по формуле

Зная матрицу переходных вероятностей и начальное состояние системы, можно найти вероятности состояний после любого k -го шага. Пусть в начальный момент времени система находится в состоянии S m . Тогда для t = 0
.
Найдем вероятности после первого шага. Из состояния S m система перейдет в состояния S 1 , S 2 и т. д. с вероятностями P m 1 , P m 2 , …, P mm , …, P mn . Тогда после первого шага вероятности будут равны

. (7.2)
Найдем вероятности состояния после второго шага: . Будем вычислять эти вероятности по формуле полной вероятности с гипотезами:
.
Гипотезами будут следующие утверждения:

• после первого шага система была в состоянии S 1 -H 1 ;
• после второго шага система была в состоянии S 2 -H 2 ;
• после n -го шага система была в состоянии S n -H n .

Вероятность любого состояния после второго шага:

(7.3)
В формуле (7.3) суммируются все переходные вероятности P ij , но учитываются только отличные от нуля. Вероятность любого состояния после k -го шага:

(7.4)
Таким образом, вероятность состояния после k -го шага определяется по рекуррентной формуле (7.4) через вероятности (k – 1)-го шага.

Задача 6. Задана матрица вероятностей перехода для цепи Маркова за один шаг. Найти матрицу перехода данной цепи за три шага.
Решение. Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

В каждой строке матрицы помещены вероятности событий (перехода из состояния i в состояние j ), которые образуют полную группу, поэтому сумма вероятностей этих событий равна единице:

Обозначим через p ij (n) вероятность того, что в результате n шагов (испытаний) система перейдет из состояния i в состояние j . Например p 25 (10) - вероятность перехода из второго состояния в пятое за десять шагов. Отметим, что при n=1 получаем переходные вероятности p ij (1)=p ij .
Перед нами поставлена задача: зная переходные вероятности p ij , найти вероятности p ij (n) перехода системы из состояния i в состояние j заn шагов. Для этого введем промежуточное (между i и j ) состояние r . Другими словами, будем считать, что из первоначального состояния i за m шагов система перейдет в промежуточное состояние r с вероятностью p ij (n-m) , после чего, за оставшиеся n-m шагов из промежуточного состояния r она перейдет в конечное состояние j с вероятностью p ij (n-m) . По формуле полной вероятности получаем:
.
Эту формулу называют равенством Маркова. С помощью этой формулы можно найти все вероятности p ij (n) , а, следовательно, и саму матрицу P n . Так как матричное исчисление ведет к цели быстрее, запишем вытекающее из полученной формулы матричное соотношение в общем виде.
Вычислим матрицу перехода цепи Маркова за три шага, используя полученную формулу:

Ответ: .

Задача №1 . Матрица вероятностей перехода цепи Маркова имеет вид:
.
Распределение по состояниям в момент времени t=0 определяется вектором:
π 0 =(0.5; 0.2; 0.3)
Найти: а) распределение по состояниям в моменты t=1,2,3,4 .
в) стационарное распределение.

Сегодня я хотел бы поведать вам о написании класса для упрощения работы с цепями Маркова.

Прошу под кат.

Начальные знания:

Представление графов в форме матрицы смежности, знание основных понятий о графах. Знание C++ для практической части.

Теория

Це́пь Ма́ркова - последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего).

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

Приведу пример цепи Маркова:

В дальнейшем мы будем рассматривать в качестве примера эту схему.

Очевидно, что если из вершины A есть только одно исходящее ребро, то его вес будет равен 1.

Обозначения

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

Матричное представление цепи Маркова

Напомню:

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) - это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

В нашем случае матрица будет иметь размер 10x10, напишем ее:

0 50 0 0 0 0 50 0 0 0
0 0 80 20 0 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 0 100 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 70 30 0
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 100 0 0 0 0

Идея

Таким образом, мы имеем значения вероятности наступления события с номером, равным номеру столбца после события с номером, равным строки .

Те кто знают теорию вероятностей могли догадаться, что каждая строка - это функция распределения вероятностей.

Алгоритм обхода цепи Маркова

Замечание: вершина конечная если распределение вероятностей нулевое (см. 6-ю строку в матрице).

Довольно изящный алгоритм, так ведь?

Реализация

Реализация алгоритма обхода

template Element *Markov::Next(int StartElement = -1) { if (Markov::Initiated) // если матрица смежности создана { if (StartElement == -1) // если стартовый элемент по умолчанию StartElement = Markov::Current; // то продолжаем (в конструкторе Current = 0) std::random_device rd; std::mt19937 gen(rd()); std::discrete_distribution<> dicr_distr(Markov::AdjacencyMatrix.at(Current).begin(), Markov::AdjacencyMatrix.at(Current).end()); // инициализируем контейнер для генерации числа на основе распределения вероятности int next = dicr_distr(gen); // генерируем следующую вершину if (next == Markov::size()) // тонкости работы генератора, если распределение вероятностей нулевое, то он возвращает количество элементов return NULL; Markov::Current = next; // меняем текущую вершину return &(Markov::elems.at(next)); // возвращаем значение в вершине } return NULL; }

Данный алгоритм выглядит особенно просто благодаря особенностям контейнера discrete_distribution . На словах описать, как работает этот контейнер довольно сложно, поэтому возьмем в пример 0-ю строку нашей матрицы:

0 50 0 0 0 0 50 0 0 0

В результате работы генератора он вернет либо 1, либо 6 с вероятностями в 0.5 для каждой. То есть возвращает номер столбца (что эквивалентно номеру вершины в цепи) куда следует продолжить движение дальше.

Пример программы, которая использует класс:

Реализация программы, которая делает обход цепи Маркова из примера

#include #include "Markov.h" #include #include using namespace std; int main() { Markov chain; ofstream outs; outs.open("out.txt"); ifstream ins; ins.open("matrix.txt"); int num; double Prob = 0; (ins >> num).get(); // количество вершин string str; for (int i = 0; i < num; i++) { getline(ins, str); chain.AddElement(str); // добавляем вершину } if (chain.InitAdjacency()) // инициализируем матрицу нулями { for (int i = 0; i < chain.size(); i++) { for (int j = 0; j < chain.size(); j++) { (ins >> Prob).get(); if (!chain.PushAdjacency(i, j, Prob)) // вводим матрицу { cerr << "Adjacency matrix write error" << endl; } } } outs << chain.At(0) << " "; // выводим 0-ю вершину for (int i = 0; i < 20 * chain.size() - 1; i++) // генерируем 20 цепочек { string *str = chain.Next(); if (str != NULL) // если предыдущая не конечная outs << (*str).c_str() << " "; // выводим значение вершины else { outs << std::endl; // если конечная, то начинаем с начала chain.Current = 0; outs << chain.At(0) << " "; } } chain.UninitAdjacency(); // понятно } else cerr << "Can not initialize Adjacency matrix" << endl;; ins.close(); outs.close(); cin.get(); return 0; }