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

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

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

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

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

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

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

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

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

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

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

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

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

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

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью . Для такого процесса моменты t 1 , t 2 , когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t , а номер шага 1, 2, k , Случайный процесс в этом случае характеризуется последовательностью состояний S(0) , S(1) , S(2) , S(k) , где S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы после первого шага; S(k) - состояние системы после k -го шага...

Событие {S(k) = S i }, состоящее в том, что сразу после k -го шага система находится в состоянии S i (i = 1, 2,), является случайным событием. Последовательность состояний S(0) , S(1) , S(k) , можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью , если для каждого шага вероятность перехода из любого состояния S i в любое S j не зависит от того, когда и как система пришла в состояние S i . Начальное состояние S(0) может быть заданным заранее или случайным.

Вероятностями состояний цепи Маркова называются вероятности P i (k) того, что после k -го шага (и до (k + 1)-го) система S будет находиться в состоянии S i (i = 1, 2, n ). Очевидно, для любою k .

Начальным распределением вероятностей Марковской цепи называется распределение вероятностей состояний в начале процесса:

P 1 (0), P 2 (0), P i (0), P n (0).

В частном случае, если начальное состояние системы S в точности известно S(0) = S i , то начальная вероятность Р i (0) = 1, а все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на k -м шаге из состояния S i в состояние S j называется условная вероятность того, что система S после k -го шага окажется в состоянии S j при условии, что непосредственно перед этим (после k - 1 шага) она находилась в состоянии S i .

Поскольку система может пребывать в одном из n состояний, то для каждого момента времени t необходимо задать n 2 вероятностей перехода P ij , которые удобно представить в виде следующей матрицы:

где Р ij - вероятность перехода за один шаг из состояния S i в состояние S j ;

Р ii - вероятность задержки системы в состоянии S i .

Такая матрица называется переходной или матрицей переходных вероятностей.

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

Переходные вероятности однородной Марковской цепи Р ij образуют квадратную матрицу размера n m .

Отметим некоторые ее особенности:

1. Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного (из i -го) состояния, в том числе и переход в самое себя.

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

3. Сумма вероятностей каждой строки равна единице, так как переходы образуют полную группу несовместных событий:

4. По главной диагонали матрицы переходных вероятностей стоят вероятности Р ii того, что система не выйдет из состояния S i , а останется в нем.

Если для однородной Марковской цепи заданы начальное распределение вероятностей и матрица переходных вероятностей , то вероятности состояний системы P i (k) (i, j = 1, 2, n ) определяются по рекуррентной формуле:

, (3.1)

Пример 1. Рассмотрим процесс функционирования системы - автомобиль. Пусть автомобиль (система) в течение одной смены (суток) может находиться в одном из двух состояний: исправном (S 1 ) и неисправном (S 2 ). Граф состояний системы представлен на рис. 3.2.

Рис. 3.2.Граф состояний автомобиля

В результате проведения массовых наблюдений за работой автомобиля составлена следующая матрица вероятностей перехода:

где P 11 = 0,8 - вероятность того, что автомобиль останется в исправном состоянии;

P 12 = 0,2 - вероятность перехода автомобиля из состояния «исправен» в состояние «неисправен»;

P 21 = 0,9 - вероятность перехода автомобиля из состояния «неисправен» в состояние «исправен»;

P 22 = 0,1 - вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан , т.е. Р 1 (0) = 0 и Р 2 (0) =1.

Требуется определить вероятности состояний автомобиля через трое суток.

Используя матрицу переходных вероятностей и формулу (3.1), определим вероятности состояний P i (k) после первого шага (после первых суток):

P 1 (1) = P 1 (0)×P 11 + P 2 (0)×P 21 = 0?0,8 + 1?0,9 = 0,9;

P 2 (1) = P 1 (0)×P 12 + P 2 (0)×P 22 = 0?0,2 + 1?0,1 = 0,2.

Вероятности состояний после второго шага (после вторых суток) таковы:

P 1 (2) = P 1 (1)×P 11 + P 2 (1)×P 21 = 0,9×0,8 + 0,1×0,9 = 0,81;

= 0,9×0,2 + 0,1×0,1 = 0,19.

Вероятности состояний после третьего шага (после третьих суток) равны:

P 1 (3) = P 1 (2)×P 11 + P 2 (2)×P 21 = 0,81×0,8 + 0,19×0,9 = 0,819;

= 0,81×0,2 + 0,19×0,1 = 0,181.

Таким образом, после третьих суток автомобиль будет находиться в исправном состоянии с вероятностью 0,819 и в состоянии «неисправен» с вероятностью 0,181.

Пример 2. В процессе эксплуатации ЭВМ может рассматриваться как физическая система S , которая в результате проверки может оказаться в одном из следующих состояний: S 1 - ЭВМ полностью исправна; S 2 - ЭВМ имеет неисправности в оперативной памяти, при которых она может решать задачи; S 3 - ЭВМ имеет существенные неисправности и может решать ограниченный класс задач; S 4 - ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (состояние S 1 ). Проверка ЭВМ производится в фиксированные моменты времени t 1 , t 2 , t 3 . Процесс, протекающий в системе S , может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных вероятностей имеет вид

Определить вероятности состояний ЭВМ после трех проверок.

Решение . Граф состояний имеет вид, показанный на рис. 3.3. Против каждой стрелки проставлена соответствующая вероятность перехода. Начальные вероятности состояний P 1 (0) = 1, P 2 (0) = P 3 (0) = P 4 (0) = 0.

Рис. 3.3. Граф состояний ЭВМ

По формуле (3.1), учитывая в сумме вероятностей только те состояния, из которых возможен непосредственный переход в данное состояние, находим:

P 1 (1) = P 1 (0)×P 11 = 1×0,3 = 0,3;

P 2 (1) = P 1 (0)×P 12 = 1×0,4 = 0,4;

P 3 (1) = P 1 (0)×P 13 = 1×0,1 = 0,1;

P 4 (1) = P 1 (0)×P 14 = 1×0,2 = 0,2;

P 1 (2) = P 1 (1)×P 11 = 0,3×0,3 = 0,09;

P 2 (2) = P 1 (1)×P 12 + P 2 (1)×P 22 = 0,3×0,4 + 0,4×0,2 = 0,20;

P 3 (2) = P 1 (1)×P 13 + P 2 (1)×P 23 + P 3 (1)×P 33 = 0,27;

P 4 (2) = P 1 (1)×P 14 + P 2 (1)×P 24 + P 3 (1)×P 34 + P 4 (1)×P 44 = 0,44;

P 1 (3) = P 1 (2)×P 11 = 0,09×0,3 = 0,027;

P 2 (3) = P 1 (2)×P 12 + P 2 (2)×P 22 = 0,09×0,4 + 0,20×0,2 = 0,076;

P 3 (3) = P 1 (2)×P 13 + P 2 (2)×P 23 + P 3 (2)×P 33 = 0,217;

P 4 (3) = P 1 (2)×P 14 + P 2 (2)×P 24 + P 3 (2)×P 34 + P 4 (2)×P 44 = 0,680.

Итак, вероятности состояний ЭВМ после трех проверок следующие: P 1 (3) = 0,027; P 2 (3) = 0,076; P 3 (3) = 0,217; P 4 (3) = 0,680.

Задача 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени t 1 , t 2 , t 3 , t 4 .

Возможные состояния системы: S 1 - цель невредима; S 2 - цель незначительно повреждена; S 3 - цель получила значительные повреждения; S 4 - цель полностью поражена. В начальный момент времени цель находится в состоянии S 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, если вы знакомы с линейной алгеброй, более эффективным способом возведения матрицы в степень будет сначала диагонализировать эту матрицу.

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

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

Цепи Маркова

Введение

§ 1. Цепь Маркова

§ 2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

§3. Равенство Маркова

§4. Стационарное распределение. Теорема о предельных вероятностях

§5. Доказательство теоремы о предельных вероятностях в цепи Маркова

§6. Области применения цепей Маркова

Заключение

Список использованной литературы

Введение

Тема нашей курсовой работы цепи Маркова. Цепи Маркова названы так в честь выдающегося русского математика, Андрея Андреевича Маркова, который много занимался случайными процессами и внес большой вклад в развитие этой области. В последнее время можно услышать о применении цепей Маркова в самых разных областях: современных веб-технологиях, при анализе литературных текстов или даже при разработке тактики игры футбольной команды. У тех, кто не знает что такое цепи Маркова, может возникнуть ощущение, что это что-то очень сложное и почти недоступное для понимания.

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

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

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

§1. Цепь Маркова

Представим, что производится последовательность испытаний.

Определение. Цепью Маркова называют последовательность испытаний, в каждом из которых появляется одно и только одно из

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

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

, причем известно, что в шестом испытании появилось событие , то условная вероятность того, что в седьмом испытании наступит событие , не зависит от того, какие события появились в первом, втором, …, пятом испытаниях.

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

Часто при изложении теории цепей Маркова придерживаются иной терминология и говорят о некоторой физической системе

, которая в каждый момент времени находится в одном из состояний: , и меняет свое состояние только в отдельные моменты времени то есть система переходит из одного состояния в другое (например из в ). Для цепей Маркова вероятность перейти в какое-либо состояние в момент зависит только от того, в каком состоянии система находилась в момент , и не изменяется от того, что становятся известными ее состояния в более ранние моменты. Так же в частности, после испытания система может остаться в том же состоянии («перейти» из состояния в состояние ).

Для иллюстрации рассмотрим пример.

Пример 1. Представим, что частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты

. Частица может находиться в точках с целочисленными координатами: ; в точках и находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью и влево с вероятностью , если только частица не находится у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка между стенками. Здесь мы видим, что этот пример блуждания частицы представляет собой типичную цепь Маркова.

Таким образом, события называют состояниями системы, а испытания – изменениями ее состояний.

Дадим теперь определение цепи Маркова, используя новую терминологию.

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

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

§2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

Определение. Однородной называют цепь Маркова, если условная вероятность

(переход из состояния в состоянии ) не зависит от номера испытания. Поэтому вместо пишут просто .

Пример 1. Случайное блуждание. Пусть на прямой

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

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

Задача 1. Задана матрица вероятностей перехода дискретной цепи Маркова из i -го состояния в j -ое за один шаг (i , j =1, 2). Распределение вероятностей по состояниям в начальный момент t =0 определяется вектором =(0,1; 0,9). Найти:

1. матрицу Р2 перехода цепи из состояния i в состояние j за два
шага;

2. распределение вероятностей по состояниям в момент t =2;

3. вероятность того, что в момент t =1 состоянием цепи будет А2 ;

4. стационарное распределение.

Решение. Для дискретной цепи Маркова в случае ее однородности справедливо соотношение

где Р1 – матрица переходных вероятностей за один шаг;
Рn - матрица переходных вероятностей за n шагов;

1. Найдем матрицу Р2 перехода за два шага

Пусть распределение вероятностей по состояниям на S -ом шаге определяется вектором
.
Зная матрицу Pn перехода за n шагов, можно определить распределение вероятностей по состояниям на (S+ n) –ом шаге . (5)

2. Найдем распределение вероятностей по состояниям системы в момент t =2. Положим в (5) S =0 и n =2. Тогда .

Получим .

3. Найдем распределение вероятностей по состояниям системы в момент t =1.

Положим в (5) s =0 и n =1, тогда .
Откуда видно, что вероятность того, что в момент t =1 состоянием цепи будет А2 ,равна р2(1) =0,69.
Распределение вероятностей по состояниям называется стационарным, если оно не меняется от шага к шагу, то есть
Тогда из соотношения (5) при n =1 получим

4. Найдем стационарное распределение. Так как =2 имеем =(р1; р2). Запишем систему линейных уравнений (6) в координатной форме

Последнее условие называется нормировочным. В системе (6) всегда одно уравнение является линейной комбинацией других. Следовательно, его можно вычеркнуть. Решим совместно первое уравнение системы и нормировочное. Имеем 0,6р1 =0,3р2 , то есть р2 =2р1 . Тогда р1 +2 р1 =1 или , то есть . Следовательно, .
Ответ:
1) матрица перехода за два шага для данной цепи Маркова имеет вид ;
2) распределение вероятностей по состояниям в момент t =2 равно ;
3) вероятность того, что в момент t =1 состоянием цепи будет А2 , равна р2(t) =0,69;
4) стационарное распределение имеет вид

Задана матрица интенсивностей переходов непрерывной цепи Маркова. Составить размеченный граф состояний, соответствующий матрице Λ; составить систему дифференциальных уравнений Колмогорова для вероятностей состояний; найти предельное распределение вероятностей. Решение. Однородная цепь Маркова с конечным числом состояний А1 , А2 ,…А характеризуется матрицей интенсивностей переходов ,

где - интенсивность перехода цепи Маркова из состояния Аi в состояние Аj ; рij(Δt) -вероятность перехода Ai→ Aj за интервал времени Δ t .

Переходы системы из состояния в состояние удобно задавать с помощью размеченного графа состояний, на котором отмечаются дуги, соответствующие интенсивностям λ ij >0. Составим размеченный граф состояний для заданной матрицы интенсивностей переходов

Пусть - вектор вероятностей р j(t) ,
j =1, 2,…,, нахождения системы в состоянии А j в момент t .

Очевидно, что 0≤р j(t) ≤1 и . Тогда по правилу дифференцирования векторной функции скалярного аргумента получим . Вероятности р j(t) удовлетворяют системе дифференциальных уравнений Колмогорова (СДУК), которая в матричной форме имеет вид . (7)

Если в начальный момент система находилась в состоянии Аj , то СДУК следует решать при начальных условиях
р i (0)=1, рj(0)=0, j≠i, j=1, 2,…, . (8)
Совокупность СДУК (7) и начальных условий (8) однозначно описывает однородную цепь Маркова с непрерывным временем и конечным числом состояний.
Составим СДУК для заданной цепи Маркова. Поскольку =3, то j =1, 2, 3.

Из соотношения (7) получим

.
Отсюда будем иметь

Последнее условие называется нормировочным.
Распределение вероятностей по состояниям называется стационарным , если оно не меняется с течением времени, то есть , где р j= const , j =1,2,…,. Отсюда .

Тогда из СДУК (7) получаем систему для нахождения стационарного распределения
(9)
Для данной задачи из СДУК будем иметь

Из нормировочного условия получим 3р2+р2+р2=1 или . Следовательно, предельное распределение имеет вид .
Заметим, что этот результат можно получить непосредственно по размеченному графу состояний, если воспользоваться правилом: для стационарного распределения сумма произведений λ ji pi , j≠ i , для стрелок, выходящих из i -го состояния, равна сумме произведений λ ji pi , j≠ i , для стрелок, входящих в i -ое состояние. Действительно,

Очевидно, что полученная система эквивалентна той, которая составлена по СДУК. Следовательно, она имеет то же решение.
Ответ: стационарное распределение имеет вид .