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

Цепи Маркова

Введение

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение. Обозначим через вероятность того, что в результате шагов (испытаний) система перейдет из состояния в состояние . Например, – вероятность перехода за 10 шагов из второго состояния в пятое.

Подчеркнем, что при получим переходные вероятности

Поставим перед собой задачу: зная переходные вероятности найти вероятности перехода системы из состояния в состояние за шагов.

С этой целью введем в рассмотрение промежуточное (между и ) состояние . Другими словами, будeм считать, что из первоначального состояния за шагов система перейдет в промежуточное состояние с вероятностью , после чего за оставшиеся шагов из промежуточного состояния она перейдет в конечное состояние с вероятностью .

По формуле полной вероятности, получим

. (1)

Эту формулу называют равенством Маркова.

Пояснение. Введем обозначения:

– интересующее нас событие (за шагов система перейдет из начального состояния в конечное ), следовательно, ; − гипотезы(за шагов система перейдет из первоначального состояния в промежуточное состояние ), следовательно, − условная вероятность наступления при условии, что имела место гипотеза (за шагов система перейдет из промежуточного состояния в конечное ), следовательно,

По формуле полной вероятности,

()

Или в принятых нами обозначениях

что совпадает с формулой Маркова (1).

Зная все переходные вероятности т.е зная матрицу перехода из состояния в состояние за один шаг, можно найти вероятности перехода из состояния в состояние за два шага, следовательно, и саму матрицу перехода ; по известной матрице можно найти матрицу перехода из состояния в состояние за три шага, и т.д.

Действительно, положив в равенстве Маркова

,

цепь марков случайный вероятность

,

(2)

Таким образом, по формуле (2) можно найти все вероятности следовательно, и саму матрицу . Поскольку непосредственное использование формулы (2) оказывается утомительным, а матричное исчисление ведет к цели быстрее, напишу вытекающие из (2) соотношение в матричной форме:

Положив в (1), аналогично получим

В общем случае

Теорема 1. При любых s, t

(3)

Доказательство. Вычислим вероятность по формуле полной вероятности (), положив

Из равенств

Отсюда из равенств (4) и

получим утверждение теоремы.

Определим матрицу В матричной записи (3) имеет вид

Так как то где − матрица вероятности перехода. Из (5) следует

(6)

Результаты, полученной в теории матриц, позволяют по формуле (6) вычислить и исследовать их поведение при

Пример 1. Задана матрица перехода Найти матрицу перехода

Решение. Воспользуемся формулой

Перемножив матрицы, окончательно получим:

.

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

Распределение вероятностей в произвольной момент времени можно найти, воспользовавшись формулой полной вероятности

(7)

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

где вероятности перехода.

Если в цепи Маркова то при любом

Это утверждение следует по индукции из (7) и (8).

Приведем формулировку теоремы о предельных вероятностях для одного важного класса цепей Маркова.

Теорема 1. Если при некотором >0 все элементы матрица положительны, то для любых , при

, (9)

где стационарное распределение с а некоторая постоянная, удовлетворяющая неравенством 0< h <1.

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

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

Рассмотрим несколько примеров цепи Маркова, которых условия теоремы 1, не выполнены. Нетрудно проверить, что такими примерами является примеры. В примере вероятности перехода имеют приделы, но эти приделы зависят от начального состояния. В частности, при

В других примеров приделы вероятностей при очевидно, не существуют.

Найдем стационарное распределение в примере 1. Нужно найти вектор удовлетворяющий условиям (8):

,

;

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

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

(10)

где , если , и в противном случае. Так как

,

то, воспользовавшись свойством математического ожидания и формулой (9), получим

.

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

Поскольку

Из формулы (11), в частности, следует, что

при

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

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

Докажем сначала две леммы. Положим

Лемма 1. При любых существуют пределы

Доказательство. Используя уравнение (3) с получим

Таким образом, последовательности и монотонны и ограничены. Отсюда следует утверждение леммы 1.

Лемма 2. Если выполнены условия теоремы 2, то существуют постоянные , такие, что

Для любых

где , означает суммирование по всем , при которых положительно, а суммирование по остальным . Отсюда

. (12)

Так как в условиях теоремы 1 вероятности перехода при всех , то при любых

И в силу конечности числа состояний

Оценим теперь разность . Используя уравнение (3) с , , получим

Отсюда, используя (8)-(10), найдем

=.

Объединяя это соотношение с неравенством (14) , получим утверждение леммы.

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

0<. (15)

Отсюда и из леммы 1 находим

Следовательно, при получи и

Положительность следует из неравенства (15). Переходя к пределу при и в уравнении (3), получим, что удовлетворяет уравнению (12). Теорема доказана.

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

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

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

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

Стационарные процессы. Самая старая из известных эргодических теорем, как отмечалось выше, может быть интерпретирована как результат, описывающий предельное поведение стационарного случайного процесса. Такой процесс обладает тем свойством, что все вероятностные законы, которым он удовлетворяет, остаются инвариантными относительно сдвигов по времени. Эргодическую теорему, впервые сформулированную физиками в качестве гипотезы, можно представить как утверждение о том, что при определенных условиях среднее по ансамблю совпадает со средним по времени. Это означает, что одну и ту же информацию можно получить из долговременного наблюдения за системой и из одновременного (и одномоментного) наблюдения многих независимых копий той же самой системы. Закон больших чисел есть не что иное, как частный случай эргодической теоремы Биркгофа. Интерполяция и предсказание поведения стационарных гауссовских процессов, понимаемых в широком смысле, служат важным обобщением классической теории наименьших квадратов. Теория стационарных процессов - необходимое орудие исследования во многих областях, например, в теории связи, которая занимается изучением и созданием систем, передающих сообщения при наличии шума или случайных помех.

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

Также цепь Маркова можно использовать для генерации текстов. На вход подается несколько текстов, затем строится цепь Маркова с вероятностями следования одних слов за другими и на основе данной цепи создается результирующий текст. Игрушка получается весьма занятной!

Заключение

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

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

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

1. Чистяков В.П. Курс теории вероятностей. 6-е изд., испр. − СПб.: Издательство «Лань», 2003. − 272 с. − (Учебник для вузов. Специальная литература).

2. Гнеденко Б.В. Курс теории вероятностей.

3. Гмурман В.Е. Теория вероятностей и математическая статистика.

4. Вентцель Е.С. Теория вероятностей и ее инженерные приложения.

5. Колмогоров А.Н., Журбенко И.Г., Прохоров А.В. Введение в теорию вероятностей. − Москва-Ижевск: Институт компьютерных исследований, 2003, 188 стр.

6. Кац М. Вероятность и смежные вопросы в физике.

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

Примером однородной цепи Маркова могут служить случайные блуждания. Пусть на прямой Oxв точке с целочисленной координатойx=nнаходится материальная частица. В определенные моменты времени
частица скачкообразно меняет свое положение (например, с вероятностьюpможет сместиться вправо и с вероятностью 1 –p– влево). Очевидно, координата частицы после скачка зависит от того, где находилась частица после непосредственно предшествующего скачка, и не зависит от того, как она двигалась в предшествующие моменты времени.

В дальнейшем ограничимся рассмотрением конечных однородных цепей Маркова.

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

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

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

, где представляют вероятности перехода за один шаг.

Отметим некоторые особенности матрицы перехода.

Равенство Маркова

Обозначим через
вероятность того, что в результатеnшагов (испытаний) система перейдет из состоянияв состояние. Например,
- вероятность перехода за 10 шагов из третьего состояния в шестое. Отметим, что приn= 1 эта вероятность сводится просто к переходной вероятности
.

Возникает вопрос, как, зная переходные вероятности
, найти вероятности перехода состоянияв состояниезаnшагов. С этой целью вводится в рассмотрение промежуточное (междуи) состояниеr. Другими словами, полагают, что из первоначального состояниязаmшагов система перейдет в промежуточное состояниеrс вероятностью
, после чего за оставшиесяn–mшагов из промежуточного состоянияrона перейдет в конечное состояниес вероятностью
. Используя формулу полной вероятности, можно показать, что справедлива формула

Эту формулу называют равенством Маркова .

Зная все переходные вероятности
, т.е. зная матрицу переходаиз состояния в состояние за один шаг, можно найти вероятности
перехода из состояние в состояние за два шага, а значит, и саму матрицу перехода, далее – по известной матрице- найтии т.д.

Действительно, полагая в равенстве Маркова n= 2,m= 1 получим

или
. В матричном виде это можно записать как
.

Полагая n=3,m=2, получим
. В общем случае справедливо соотношение
.

Пример . Пусть матрица переходаравна

Требуется найти матрицу перехода
.

Умножая матрицу саму на себя, получим
.

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

Здесь через
обозначена вероятность нахождения системы в состояниив начальный момент времени. В частном случае, если начальное состояние системы в точности известно (например
), то начальная вероятность
, а все остальные равны нулю.

Если для однородной цепи Маркова заданы начальное распределение вероятностей и матрица перехода, то вероятности состояний системы на n-м шаге
вычисляются по рекуррентной формуле

.

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

где - вероятность того, что прибор останется в исправном состоянии;

- вероятность перехода прибора из исправного в неисправное состояние;

- вероятность перехода прибора из неисправного в исправное состояние;

- вероятность того, что прибор останется в состоянии "неисправен".

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

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

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

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

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

Таким образом, вероятность того, что прибор будет находиться в исправном состоянии равна 0,819, и того, что в неисправном – соответственно 0,181.

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

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

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

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

Теория

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

Если говорить простыми словами, то Цепь Маркова - это взвешенный граф. В его вершинах находятся события, а в качестве веса ребра, соединяющего вершины A и B - вероятность того, что после события A последует событие B.

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

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

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

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

Обозначения

В вершинах у нас находятся события (от A, B, C, D, E...). На ребрах вероятность того, что после i-го события будет событие j > i. Для условности и удобства я пронумеровал вершины (№1, №2 и т.д).

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

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

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

Напомню:

Матрица смежности графа 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

Идея

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

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

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

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

1) инициализируем начальную позицию k нулевой вершиной.
2) Если вершина не конечная, то генерируем число m от 0...n-1 на основе распределения вероятности в строке k матрицы, где n - число вершин, а m - номер следующего события (!). Иначе выходим
3) Номер текующей позиции k приравниваем к номеру сгенерированной вершине
4) На шаг 2

Замечание: вершина конечная если распределение вероятностей нулевое (см. 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; }

Пример вывода, который генерирует программа:

Голосование: 41, 23

Настоящая статья носит реферативный характер, написана на основе приведенных в конце источников, которые местами цитируются.

Введение в теорию марковских цепей

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

1. множеством состояний S = { s 1 , …, s n }, событием является переход из одного состояния в другое в результате случайного испытания
2. вектором начальных вероятностей (начальным распределением) p (0) = { p (0) (1),…, p (0) (n)}, определяющим вероятности p (0) (i) того, что в начальный момент времени t = 0 процесс находился в состоянии s i
3. матрицей переходных вероятностей P = { p i j }, характеризующей вероятность перехода процесса с текущим состоянием s i в следующее состояние s j , при этом сумма вероятностей переходов из одного состояния равна 1:

∑ j =1… n p i j = 1

Пример матрицы переходных вероятностей с множеством состояний S = { S 1 , …, S 5 }, вектором начальных вероятностей p (0) = {1, 0, 0, 0, 0}:

С помощью вектора начальных вероятностей и матрицы переходов можно вычислить стохастический вектор p (n) — вектор, составленный из вероятностей p (n) (i) того, что процесс окажется в состоянии i в момент времени n . Получить p (n) можно с помощью формулы:

P (n) = p (0) × P n

Векторы p (n) при росте n в некоторых случаях стабилизируются — сходятся к некоторому вероятностному вектору ρ , который можно назвать стационарным распределением цепи. Стационарность проявляется в том, что взяв p (0) = ρ, мы получим p (n) = ρ для любого n .
Простейший критерий, который гарантирует сходимость к стационарному распределению, выглядит следующим образом: если все элементы матрицы переходных вероятностей P положительны, то при n , стремящемуся к бесконечности, вектор p (n) стремится к вектору ρ , являющемуся единственным решением системы вида
p × P = p .
Также можно показать, что если при каком-нибудь положительном значении n все элементы матрицы P n положительны, тогда вектор p (n) все-равно будет стабилизироваться.
Доказательство этих утверждений есть в в подробном виде.

Марковская цепь изображается в виде графа переходов, вершины которого соответствуют состояниям цепи, а дуги — переходам между ними. Вес дуги (i , j), связывающей вершины s i и s j будет равен вероятности p i (j) перехода из первого состояния во второе. Граф, соответствующий матрице, изображенной выше:

Классификация состояний марковских цепей

При рассмотрении цепей Маркова нас может интересовать поведение системы на коротком отрезке времени. В таком случае абсолютные вероятности вычисляются с помощью формул из предыдущего раздела. Однако более важно изучить поведение системы на большом интервале времени, когда число переходов стремится к бесконечности. Далее вводятся определения состояний марковских цепей, которые необходимы для изучения поведения системы в долгосрочной перспективе.
Марковские цепи классифицируются в зависимости от возможности перехода из одних состояний в другие.
Группы состояний марковской цепи (подмножества вершин графа переходов), которым соответствуют тупиковые вершины диаграммы порядка графа переходов, называются эргодическими классами цепи. Если рассмотреть граф, изображенный выше, то видно, что в нем 1 эргодический класс M 1 = { S 5 }, достижимый из компоненты сильной связности, соответствующей подмножеству вершин M 2 = { S 1 , S 2 , S 3 , S 4 }. Состояния, которые находятся в эргодических классах, называются существенными, а остальные — несущественными (хотя такие названия плохо согласуются со здравым смыслом). Поглощающее состояние s i является частным случаем эргодического класса. Тогда попав в такое состояние, процесс прекратится. Для S i будет верно p ii = 1, т.е. в графе переходов из него будет исходить только одно ребро — петля.

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

Например, в алгоритме Дейкстры присутствуют следующие состояния цепи:

• vertex (v), извлечение новой вершины из очереди с приоритетами, переход только в состояние b ;
• begin (b), начало цикла перебора исходящих дуг для процедуры ослабления;
• analysis (a), анализ следующей дуги, возможен переход к a , d , или e ;
• decrease (d), уменьшение оценки для некоторой вершины графа, переход к a ;
• end (e), завершение работы цикла, переход к следующей вершине.

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

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

Цепь Маркова называется неприводимой, если любое состояние S j может быть достигнуто из любого другого состояния S i за конечное число переходов. В этом случае все состояния цепи называются сообщающимися, а граф переходов является компонентой сильной связности. Процесс, порождаемый эргодической цепью, начавшись в некотором состоянии, никогда не завершается, а последовательно переходит из одного состояния в другое, попадая в различные состояния с разной частотой, зависящей от переходных вероятностей. Поэтому основная характеристика эргодической цепи –
вероятности пребывания процесса в состояниях S j , j = 1,…, n , доля времени, которую процесс проводит в каждом из состояний. Неприводимые цепи используются в качестве моделей надежности систем. Действительно, при отказе ресурса, который процесс использует очень часто, работоспособность всей системы окажется под угрозой. В таком случае дублирование такого критического ресурса может помочь избежать отказов. При этом состояния системы, различающиеся составом исправного и отказавшего оборудования, трактуются как состояния цепи, переходы между которыми связаны с отказами и восстановлением устройств и изменением связей между ними, проводимой для сохранения работоспособности системы. Оценки характеристик неприводимой цепи дают представление о надежности поведения системы в целом. Также такие цепи могут быть моделями взаимодействия устройств с задачами, поступающими на обработку.

Примеры использования

Система обслуживания с отказами

Сервер, состоит из нескольких блоков, например модемов или сетевых карт, к которым поступают запросы от пользователей на обслуживание. Если все блоки заняты, то запрос теряется. Если один из блоков принимает запрос, то он становится занятым до конца его обработки. В качестве состояний возьмем количество незанятых блоков. Время будет дискретно. Обозначим за α вероятность поступления запроса. Также мы считаем, что время обслуживания также является случайным и состоящим из независимых продолжений, т.е. запрос с вероятностью β обслуживается за один шаг, а с вероятностью (1 - β) обслуживается после этого шага как новый запрос. Это дает вероятность (1 - β) β для обслуживания за два шага, (1 - β) 2 β для обслуживания за три шага и т.д. Рассмотрим пример с 4 устройствами, работающими параллельно. Составим матрицу переходных вероятностей для выбранных состояний:

1 - α	α	0	0	0
β	1 - α - β	α	0	0
0	2 β	1 - α - 2 β	α	0
0	0	3 β	1 - α - 3 β	α
0	0	0	4β	1 - 4 β

Можно заметить, что она имеет единственный эргодический класс, и, следовательно, система p × P = p в классе вероятностных векторов имеет единственное решение. Выпишем уравнения системы, позволяющей находить это решение:

P 0 (1 - α) + p 1 β = p 0 ,
p 0 α + p 1 (1 - α - β) + p 2 2 β = p 1 ,
p 1 α + p 2 (1 - α - 2 β) + p 3 3 β = p 2 ,
p 2 α + p 3 (1 - α - 3 β) + p 4 4 β = p 3 ,
p 3 α + p 4 (1 - 4 β) = p 4 .

Отсюда получаем (при γ = α / β):

P 1 = γ p 0 ,
p 2 = γ 2 p 0 /2,
p 3 = γ 3 p 0 /3,
p 4 = γ 4 p 0 /4,

из условия нормировки следует:

P 0 = С = (1 + γ + γ 2 /2 + γ 3 /3 + γ 4 /4) -1 .

Теперь известен набор вероятностей π i того, что в стационарном режиме в системе будет занято i блоков. Тогда долю времени p 4 = С γ 4 /4 в системе заняты все блоки, система не отвечает на запросы. Полученные результаты распространяются на любое число блоков. Теперь можно воспользоваться ими: можно сопоставить затраты на дополнительные устройства и уменьшение времени полной занятости системы.
Подробнее можно ознакомиться с этим примером в .

Процессы принятия решений с конечным и бесконечным числом этапов

Рассмотрим процесс, в котором есть несколько матриц переходных вероятностей. Для каждого момента времени выбор той или иной матрицы зависит от принятого нами решения. Понять вышесказанное можно на следующем примере. Садовник в результате анализа почвы оценивает ее состояние одним из трех чисел: (1) - хорошее, (2) - удовлетворительное или (3) - плохое. При этом садовник заметил, что продуктивность почвы в текущем году зависит только от ее состояния в предыдущем году. Поэтому вероятности перехода почвы без внешних воздействий из одного состояния в другое можно представить следующей цепью Маркова с матрицей P1:

Теперь можно сопоставить каждому переходу из одного состояния в другое некоторую функцию дохода, которая определяется как прибыль или убыток за одногодичный период. Садовник может выбирать использовать или не использовать удобрения, именно от этого будет зависеть его конечный доход или убыток. Введем матрицы R1 и R2, определяющие функции дохода в зависимости от затрат на удобрения и качества почвы:

R1
7.00	6.00	3.00
0.00	5.00	1.00
0.00	0.00	-1.00

R2
6.00	5.00	-1.00
7.00	4.00	0.00
6.00	3.00	-2.00

Наконец перед садовником стоит задача, какую стратегию нужно выбрать для максимизации среднего ожидаемого дохода. Может рассматриваться два типа задач: с конечным и бесконечным количеством этапов. В данном случае когда-нибудь деятельность садовника обязательно закончится. Кроме того, визуализаторы решают задачу принятия решений для конечного числа этапов. Пусть садовник намеревается прекратить свое занятие через N лет. Наша задача теперь состоит в том, чтобы определить оптимальную стратегию поведения садовника, то есть стратегию, при которой его доход будет максимальным. Конечность числа этапов в нашей задаче проявляется в том, что садовнику не важно, что будет с его сельскохозяйственным угодьем на N +1 год (ему важны все года до N включительно). Теперь видно, что в этом случае задача поиска стратегии превращается в задачу динамического программирования. Если через f n (i) обозначить максимальный средний ожидаемый доход, который можно получить за этапы от n до N включительно, начиная из состояния с номером i , то несложно вывести рекуррентное соотношение, связывающее f n (i) с числами f n +1 (j)

F n (i) = max k {∑ j =1 m p ij k [ r ij k + f n +1 (j)]}, n = 1, 2, …, N

Здесь k - номер используемой стратегии. Это уравнение основывается на том, что суммарный доход r ij k + f n +1 (j) получается в результате перехода из состояния i на этапе n в состояние j на этапе n +1 с вероятностью p ij k .
Теперь оптимальное решение можно найти, вычисляя последовательно f n (i) в нисходящем направлении (n = N …1). При этом введение вектора начальных вероятностей в условие задачи не усложнит ее решение.
Данный пример также рассмотрен в .

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

Рассмотрим текст, состоящий из слов w . Представим процесс, в котором состояниями являются слова, так что когда он находится в состоянии (S i) система переходит в состояние (s j) согласно матрице переходных вероятностей. Прежде всего, надо «обучить» систему: подать на вход достаточно большой текст для оценки переходных вероятностей. А затем можно строить траектории марковской цепи. Увеличение смысловой нагрузки текста, построенного при помощи алгоритма цепей Маркова возможно только при увеличении порядка, где состоянием является не одно слово, а множества с большей мощностью — пары (u , v), тройки (u , v , w) и т.д. Причем что в цепях первого, что пятого порядка, смысла будет еще немного. Смысл начнет появляться при увеличении размерности порядка как минимум до среднего количества слов в типовой фразе исходного текста. Но таким путем двигаться нельзя, потому, что рост смысловой нагрузки текста в цепях Маркова высоких порядков происходит значительно медленнее, чем падение уникальности текста. А текст, построенный на марковских цепях, к примеру, тридцатого порядка, все еще будет не настолько осмысленным, чтобы представлять интерес для человека, но уже достаточно схожим с оригинальным текстом, к тому же число состояний в такой цепи будет потрясающим.
Эта технология сейчас очень широко применяется (к сожалению) в Интернете для создания контента веб-страниц. Люди, желающие увеличить трафик на свой сайт и повысить его рейтинг в поисковых системах, стремятся поместить на свои страницы как можно больше ключевых слов для поиска. Но поисковики используют алгоритмы, которые умеют отличать реальный текст от бессвязного нагромождения ключевых слов. Тогда, чтобы обмануть поисковики используют тексты, созданные генератором на основе марковской цепи. Есть, конечно, и положительные примеры использования цепей Маркова для работы с текстом, их применяют при определении авторства, анализе подлинности текстов.

Цепи Маркова и лотереи

В некоторых случаях вероятностная модель используется в прогнозе номеров в различных лотереях. По-видимому, использовать цепи Маркова для моделирования последовательности различных тиражей нет смысла. То, что происходило с шариками в тираже, никак не повлияет на результаты следующего тиража, поскольку после тиража шары собирают, а в следующем тираже их укладывают в лоток лототрона в фиксированном порядке. Связь с прошедшим тиражом при этом теряется. Другое дело последовательность выпадения шаров в пределах одного тиража. В этом случае выпадение очередного шара определяется состоянием лототрона на момент выпадения предыдущего шара. Таким образом, последовательность выпадений шаров в одном тираже является цепью Маркова, и можно использовать такую модель. При анализе числовых лотерей здесь имеется большая трудность. Состояние лототрона после выпадения очередного шара определяет дальнейшие события, но проблема в том, что это состояние нам неизвестно. Все что нам известно, что выпал некоторый шар. Но при выпадении этого шара, остальные шары могут быть расположены различным образом, так что имеется группа из очень большого числа состояний, соответствующая одному и тому же наблюдаемому событию. Поэтому мы можем построить лишь матрицу вероятностей переходов между такими группами состояний. Эти вероятности являются усреднением вероятностей переходов между различными отдельными состояниями, что конечно, снижает эффективность применения модели марковской цепи к числовым лотереям.
Аналогично этому случаю, такая модель нейронной сети может быть использована для предсказания погоды, котировок валют и в связи с другими системами, где есть исторические данные, и в будущем может быть использована вновь поступающая информация. Хорошим применением в данном случае, когда известны только проявления системы, но не внутренние (скрытые) состояния, могут быть применены скрытые марковские модели, которые подробно рассмотрены в Викиучебнике (скрытые марковские модели).

Литература

1. Романовский И.В. Дискретный анализ: Учебное пособие для студентов, 3-е изд. - СПб: Невский Диалект; БХВ Петербург, 2003.
2. Таха, Хэмди А. Введение в исследование операций, 6-е изд. — М.: Издательский дом «Вильямс», 2001.
3. Вернер М. Основы кодирования. Учебник для ВУЗов. — М.: Техносфера, 2004.
4. Беляев А., Гаврилов М., Масальских А., Медвинский М. Марковские процессы , 2004.

Визуализаторы

1. Алексеев В. Марковские процессы принятия решений , 2002.
2. Беляев А. Марковские цепи , 2002.

Задача 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 -ое состояние. Действительно,

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