Содержание
Примеры решений
Задача 1. Для заданной матрицы переходных вероятностей Р найти вероятности перехода за 2 шага и стационарные вероятности, если они существуют.
Задача 2. Задана матрица $P_1$ вероятностей перехода дискретной цепи Маркова из состояния $i (i=1,2)$ в состояние $j (j=1,2)$ за один шаг. Распределение вероятностей по состояниям в момент $t=0$ определяется вектором $ar$. Найти:
1) матрицу $P_2$ перехода из состояния $i$ в состояние $j$ за два шага;
2) распределение вероятностей по состояниям в момент $t=2$;
3) вероятность того, что в момент $t=1$ состоянием цепи будет $i=2$;
4) стационарное распределение.
Задача 3. В заданной матрице $L$ элемент $lambda_
А) построить граф переходов между состояниями, ребра которого помечены соответствующими интенсивностями переходов.
Б) написать систему уравнений для определения предельных вероятностей различных состояний.
В) решить эту систему уравнений, найти предельную вероятность каждого состояния.
Задача 4. Найти стационарные вероятности и математическое ожидание для марковского процесса N, заданного графом переходов состояний.
Задача 5. Дан размеченный граф состояний системы. 
Найти:
А) матрицы перехода за один и два шага,
Б) вероятности состояний системы после первого, второго, третьего шага, если в начальный момент система находилась в состоянии $S_1$,
В) финальные вероятности.
Задача 6. Система имеет три состояния. Построить граф состояний системы, написать уравнения Колмогорова и найти стационарное распределение.
Маркова цепь (Markov Chain) — марковский процесс с дискретным временем, заданный в измеримом пространстве.
Введение
Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей".
В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений, особое внимание марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений.
Простой пример: бросание монеты
Прежде чем дать описание общей схемы, обратимся к простому примеру. Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, . и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, .
При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные значения j = k ± 1 c одинаковой вероятностью 1/2.
Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
Формулы и определения
Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, . случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов
ξ(0) — ξ(1) — . — ξ(t) — . . (1)
Формально обозначим все возможные состояния целыми i = 0, ±1, . Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:
P(ξ(t+1) = j|ξ(0) = i, . ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j . (3) — марковское свойство.
Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний — ее однородность состоит в том, что определенные в (2) переходные вероятности pkj, ∑j pkj = 1, k = 0, ±1, . не зависят от времени, т.е. P(ξ(t+1) = j|ξ(t) = k) = Pij — матрица вероятностей перехода за один шаг не зависит от n.
Ясно, что Pij — квадратная матрица с неотрицательными элементами и единичными суммами по строкам.
Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.
На практике: доставка оборудования по округам
Предположим, что некая фирма осуществляет доставку оборудования по Москве: в северный округ (обозначим А), южный (В) и центральный (С). Фирма имеет группу курьеров, которая обслуживает эти районы. Понятно, что для осуществления следующей доставки курьер едет в тот район, который на данный момент ему ближе. Статистически было определено следующее:
1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях — в В и в 40 случаях — в С;
2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях — в В и в 20 случаях — в С;
3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях — в В и в 20 случаях — в С.
Таким образом, район следующей доставки определяется только предыдущей доставкой.
Матрица вероятностей перехода будет выглядеть следующим образом:
Например, р12 = 0.4 — это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А.
Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% — в С.
Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0 B и B—>B;
Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:
P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)
Подставляя числовые значения:
P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33
Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки.
Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок — это может занять довольно много времени.
Покажем более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу P в квадрат:
Тогда элемент (2, 3) — это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P 2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.
Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:
1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) — вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2 ).
2 способ. Вычислить матрицу P 3 :
Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:
Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С.
Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).
Цепь Маркова – череда событий, в которой каждое последующее событие зависит от предыдущего. В статье мы подробнее разберём это понятие.
Цепь Маркова – это распространенный и довольно простой способ моделирования случайных событий. Используется в самых разных областях, начиная генерацией текста и заканчивая финансовым моделированием. Самым известным примером является 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, если вы знакомы с линейной алгеброй, более эффективным способом возведения матрицы в степень будет сначала диагонализировать эту матрицу.
Теперь, зная, что из себя представляет цепь Маркова, вы можете легко реализовать её на одном из языков программирования. Простые цепи Маркова являются фундаментом для изучения более сложных методов моделирования.
