|
Марковские процессы
Рассмотрим процесс с множеством состояний М и со следующим правилом перехода из состояния в состояние: когда процесс находится в состоянии 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) стремится к вектору 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 уравнение Единственность решения этого уравнения легко следует из того же неравенства. Действительно, если р1 и р2 — два решения, то
что возможно только при совпадении этих решений.
Следствие. Если при каком-нибудь п > О все элементы матрицы Р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. Можно сказать, что марковская цепь — это случайное блуждание по ее графу переходов. Построим диаграмму порядка графа переходов. Как мы помним она представляет собой ациклический граф, вершины которого суть элементы некоторого разбиения множества М. Так как в диаграмме порядка нет циклов, то в ней существуют тупиковые вершины, т.е. вершины, из которых дуги не выходят.
Подмножества М, соответствующие тупиковым вершинам диаграммы порядка, называются эргодическими классами марковской цепи. Пример. Пусть S = {А, В, С, D, Е, F, G, Н, I, J, К, L} и матрица переходных вероятностей P[S, S] задана приведенной таблицей. В этих нулях трудно разбираться, а нам сейчас нужны только места положительных элементов, поэтому построим таблицу переходов, а по ней граф переходов и диаграмму порядка.
Граф переходов и диаграмма порядка.
Из диаграммы порядка ясно видны три эргодических класса: 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], переставив в ней строки и столбцы
Отметим, что в матрице Р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), нужно рассматривать матрицу Рассмотрим теперь пару примеров, где полезно использовать технику марковских цепей. Пример 1. Схема обслуживания с отказами. Рассмотрим систему, обслуживающую поступающие запросы, например сервер. Система состоит из 4 одинаковых блоков, например модемов, к которым поступают звонки от пользователей — поток запросов на обслуживание. Если все четыре блока заняты, запрос теряется. Если же есть свободные блоки, то один из них принимает запрос и становится занятым до завершения выполнения запроса. Моделируя эту систему как марковскую цепь, мы принимаем в качестве ее состояния количество занятых блоков. Будем считать время дискретным и шаг по времени выберем достаточно маленьким, так, чтобы можно было пренебречь вероятностью поступления двух запросов за один шаг. Теперь обозначив через a вероятность поступления одного запроса, вероятность непоступления запросов будет, очевидно, равна 1-a. Может показаться странным, но время обслуживания также удобно считать случайным и состоящим из независимых продолжений. Более точно мы считаем, что запрос с вероятностью b обслуживается за один шаг, а с вероятностью 1-b обслуживается после этого шага как новый запрос. Это дает вероятность (1-b)b для обслуживания за два шага, (1-b)2b - для обслуживания за три шага, и т. д. Теперь нетрудно написать матрицу переходных вероятностей
и увидеть, что она имеет
единственный эргодический класс, и, следовательно, система
или после несложных преобразований
откуда,
полагая
и, следовательно,
и из условия нормировки
Итак, мы
нашли набор Полученные здесь формулы легко переносятся на случай произвольного числа блоков, и мы можем провести экономический анализ системы: сопоставить затраты на дополнительные блоки и даваемый ими прирост работоспособности системы. Пример 2. Марковская модель работы программы. Это пример того, как в трудной ситуации приходится идти на заведомо неправильные, неадекватные реальности, модели для того, чтобы получить хоть какой-то результат. Предположим, что мы анализируем какую-то программу и хотим оценить временные параметры ее работы — среднее время исполнения программы, частоту выполнения отдельных блоков и т.д. Составим граф переходов этой программы, в котором вершинами будут точки ветвления алгоритма (условные переходы), а дугами — пути вычислений между этими вершинами. Теперь сделаем переходы случайными, для чего припишем дугам, выходящим из каждой вершины, какие-либо вероятности (это вероятности выбора дуг при условии, что процесс находится в данной вершине, так что сумма вероятностей дуг, выходящих из каждой вершины, равна единице).
Граф переходов для алгоритма Краскала.
Например, в алгоритме Краскала мы можем выделить вершины: start — s, начало работы, возможен переход к состоянию а; arc — а, получение новой дуги, возможен переход к е или к с; check — с, анализ дуги, возможен переход к i или к a; include — i, вставка дуги, возможен переход к а или к е; end — е, завершение работы. и получим граф, изображенный на рис. 4.3. Осталось только задать (с очевидными обозначениями) вероятности переходов рас, pci и pie, и тогда можно будет изучать, хотя бы грубо, продолжительности переходов между вершинами, вероятности попадания в различные состояния и другие средние характеристики процесса. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||