Марковские процессы

 

Рассмотрим процесс с множеством состояний М и со следующим правилом перехода из состояния в состояние: когда процесс находится в состоянии i Î М, делается случайное испытание, которое определяет, в какое состояние на следующем такте процесс должен перейти. Зависимость результата испытания от состояния i спрятана в распределении вероятностей его исходов: каждому i сопоставляется набор вероятностей pi(j), с которыми процесс попадет в состояния j Î М. При этом, разумеется,

 

 

Если рассматривать процесс в последовательные моменты времени, начиная с момента 0, и задать начальное распределение вероятностей р(0), где р(0)(i) — вероятность находиться в начальный момент в состоянии i, мы сможем определить вероятность появления траектории процесса i0, i1,..., it, как произведение

 

 

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

 

 

Используя это выражение для вероятности траектории, можно сосчитать и всевозможные вероятности более сложных событий. Например как подсчитать вероятность p(t)(i) того, что на шаге t процесс будет находиться в состоянии i? Подсчитаем ее сначала для t = 1. Имеем:

 

 

Осознав, что набор вероятностей pj(i) образует просто матрицу, в которой j может считаться индексом строки, a i — индексом столбца (она i называется матрицей переходных вероятностей марковского процесса), мы сможем сказать, что вектор р(1) получается умножением вектора р(0)  на матрицу переходных вероятностей Р. Для вычисления р(2) мы получим аналогичную формулу

 

 

(причем в последнем случае 2 обозначает уже квадрат матрицы Р). Теперь уже ясно, что мы можем ожидать для шага i формулу

 

 

Проверьте ее справедливость сами.

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

 

Теорема. Если все элементы матрицы переходных вероятностей Р положительны, то при t, стремящемся к бесконечности, вектор р(t) стремится к вектору p(t)=p(0)×Pt , являющемуся единственным решением системы

 

     p×P=p,              

 

Доказательство. Обозначим через d минимальный элемент ма­трицы Р. По предположению d > 0. Введем для удобства функцию f переводящую вероятностный вектор в другой: f(p) = р × Р. Пока­жем прежде всего, что отображение f сжимающее, т.е., что отношение «расстояния» между векторами f(p) и f(q) к расстоянию между векторами р и q не превосходит некоторого значения r, где r < 1. Расстояние в данном случае — это просто некоторая числовая мере отклонения одного вектора от другого. Нужно только хорошо выбрать эту меру, мы предлагаем попробовать

 

 

и посмотрим сейчас, чем такая мера хороша. Введем матрицу D, элементы которой на d меньше, чем у Р. Учитывая, что у вероятностных векторов сумма компонент равна 1, и используя определение d, полу­чаем для любого вектора р

 

 

(напомним, что 1 — это вектор из единиц). Таким образом,

 

f(p)-f(q)=(p-q)×D

 

и далее

 

 

 

Здесь мы можем принять р = 1 — md < 1 (подумайте, почему так опре­деленное р не будет отрицательным). Из получившегося неравенства

 

 

следует для любого п

 


 

 

отсюда легко получается сходимость последовательности  p(0)Pn  при любом начальном векторе  p(0). Переходя в формуле   p(n)=p(n-1)P к пределу, мы получаем для предельного вектора  p(t)=p(0)×Pt уравнение =P.

Единственность решения этого уравнения легко следует из того же неравенства. Действительно, если р1  и  р2 — два решения, то

 

P)≤ρ×

 

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

 

Следствие. Если при каком-нибудь п > О все элементы матрицы Рn положительны, то утверждение теоремы остается в силе.

Доказательство. Матрицу Р в доказательстве сходимости мож­но заменить матрицей Рn, и доказать сходимость в последовательно­стях {pkn+s}k Для любого s Î 0 : п — 1. Далее, воспользовавшись тем, что матрица Рn+1 также положительна, мы увидим сходимость и в по­следовательностях {pk(n+1)+s}k, а отсюда уже и сходимость всей {pk}k.

Много информации о поведении марковской цепи дает граф переходов, который строится по матрице переходных вероятностей. Вершины графа — состояния цепи, а дуги соответствуют положительным элементам матрицы: если P[i, j] > 0, то паре (i, j) соответствует дуга ведущая из i в j. Можно сказать, что марковская цепь — это случайное блуждание по ее графу переходов.

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

 

 

A

B

C

D

E

F

G

H

I

J

K

L

A

0.0

0.7

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.3

0.0

0.0

B

0.0

1.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

C

0.2

0.2

0.0

0.0

0.1

0.0

0.0

0.0

0.5

0.0

0.0

0.0

D

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

1.0

0.0

0.0

0.0

E

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

1.0

F

1.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

G

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

1.0

0.0

0.0

H

0.5

0.0

0.0

0.0

0.0

0.2

0.0

0.3

0.0

0.0

0.0

0.0

I

0.0

0.0

0.5

0.0

0.5

0.0

0.0

0.0

0.0

0.0

0.0

0.0

J

0.0

0.0

0.0

0.0

0.0

0.0

0.4

0.0

0.0

0.0

0.6

0.0

K

0.0

0.0

0.0

0.0

0.0

0.2

0.0

0.0

0.0

0.8

0.0

0.0

L

0.0

0.0

0.0

0.0

0.5

0.0

0.0

0.0

0.0

0.0

0.0

0.5

 

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

Пример. Пусть S = {А, В, С, D, Е, F, G, Н, I, J, К, L} и матрица переходных вероятностей P[S, S] задана приведенной таблицей. В этих нулях трудно разбираться, а нам сейчас нужны только места положительных элементов, поэтому построим таблицу переходов, а по ней граф переходов и диаграмму порядка.

 

 

A

B

C

D

E

F

G

H

I

J

K

L

A

 

+

 

 

 

 

 

 

 

+

 

 

B

 

+

 

 

 

 

 

 

 

 

 

 

C

+

+

 

 

+

 

 

 

+

 

 

 

D

 

 

 

 

 

 

 

 

+

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

+

F

+

 

 

 

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

 

 

+

 

 

H

+

 

 

 

 

+

 

+

 

 

 

 

I

 

 

+

 

+

 

 

 

 

 

 

 

J

 

 

 

 

 

 

+

 

 

 

+

 

K

 

 

 

 

 

+

 

 

 

+

 

 

L

 

 

 

 

+

 

 

 

 

 

 

+

 

Граф переходов и диаграмма порядка.

 

Из диаграммы порядка ясно видны три эргодических класса: S1 = {Е, L}, S2 = {В},    S3 = {A,G, К, F, J} (последний обозначен буквой W). Состояния, вроде В, образующие одноэлементные эргодические классы, называются поглощающими состояниями.

Множество S3 разбито на такие два подмножества: S31 = {А,G,К} и S32 = {F, J}, что переходы из состояния в состояние всегда вызывают пе­реход из одного подмножества в другое. Говорят, что это эргодический класс с периодом 2. В общем случае, при периоде (числе подмножеств) d получаем циклическое движение S1® S2® …®Sd®S1 .

Разбиение S3 на два подмножества будет видно лучше, если выписать подматрицу p[S3, S3], переставив в ней строки и столбцы

 

 

A

G

K

F

J

A

 

 

+

J

 

+

K

+

+

F

+

 

 

 

J

 

+

+

 

Отметим, что в матрице Р2[S3, S3] все ненулевые элементы будут сосредоточены в диагональных блоках P2[S31, S31] и P2[S32, S32], а у матрицы P2[S3, S3] все элементы диагональных блоков положительны.

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

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

При периоде d, большем 1, когда эргодический класс Si разбиваем на d «фазовых» подклассов Sis, s Î 0 : (d - 1), нужно рассматривать матрицу . Ее подматрица  при любом фиксированном s будет стохастической матрицей цепи с единственным эргодическим классом с периодом 1. Следовательно, вероятностное распределение будет сходиться в каждом фазовом подклассе отдельно.

Рассмотрим теперь пару примеров, где полезно использовать технику марковских цепей.

Пример 1. Схема обслуживания с отказами. Рассмотрим систему, обслуживающую поступающие запросы, например сервер. Система состоит из 4 одинаковых блоков, например модемов, к которым поступают звонки от пользователей — поток запросов на обслуживание. Если все четыре блока заняты, запрос теряется. Если же есть свободные блоки, то один из них принимает запрос и становится занятым до завершения выполнения запроса.

Моделируя эту систему как марковскую цепь, мы принимаем в качестве ее состояния количество занятых блоков. Будем считать время дискретным и шаг по времени выберем достаточно маленьким, так, чтобы можно было пренебречь вероятностью поступления двух запросов за один шаг. Теперь обозначив через a вероятность поступления одного запроса, вероятность непоступления запросов будет, очевидно, равна 1-a.

Может показаться странным, но время обслуживания также удобно считать случайным и состоящим из независимых продолжений. Более точно мы считаем, что запрос с вероятностью b обслуживается за один шаг, а с вероятностью 1-b обслуживается после этого шага как новый запрос. Это дает вероятность (1-b)b для обслуживания за два шага, (1-b)2b - для обслуживания за три шага, и т. д.

Теперь нетрудно написать матрицу переходных вероятностей

 

 

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

 

 

или после несложных преобразований

 

 

откуда, полагая , получаем

 

 

и, следовательно,

 

 

и из условия нормировки

 

 

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

Полученные здесь формулы легко переносятся на случай произвольного числа блоков, и мы можем провести экономический анализ системы: сопоста­вить затраты на дополнительные блоки и даваемый ими прирост работоспо­собности системы.

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

 

 

 Граф переходов для алгоритма Краскала.

 

Например, в алгоритме Краскала мы можем выделить вершины:

start — s, начало работы, возможен переход к состоянию а;

arc — а, получение новой дуги, возможен переход к е или к с;

check — с, анализ дуги, возможен переход к i или к a;

include — i, вставка дуги, возможен переход к а или к е;

end — е, завершение работы.

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