Введение в теорию марковских цепей
Цепью Маркова называют такую последовательность случайных событий, в которой вероятность каждого события зависит только от состояния, в котором процесс находится в текущий момент и не зависит от более ранних состояний. Конечная дискретная цепь определяется:
множеством состояний S = {s1, …, sn}, событием является переход из одного состояния в другое в результате случайного испытания
вектором начальных вероятностей (начальным распределением) p(0) = {p(0)(1),…, p(0)(n)}, определяющим вероятности p(0)(i) того, что в начальный момент времени t = 0 процесс находился в состоянии si
матрицей переходных вероятностей P = {pij}, характеризующей вероятность перехода процесса с текущим состоянием si в следующее состояние sj, при этом сумма вероятностей переходов из одного состояния равна 1:
∑j=1…n pij = 1
Пример матрицы переходных вероятностей с множеством состояний S = {S1, …, S5}, вектором начальных вероятностей 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) все-равно будет стабилизироваться.
Доказательство этих утверждений есть в [1] в подробном виде.
Классификация состояний марковских цепей
При рассмотрении цепей Маркова нас может интересовать поведение системы на коротком отрезке времени. В таком случае абсолютные вероятности вычисляются с помощью формул из предыдущего раздела. Однако более важно изучить поведение системы на большом интервале времени, когда число переходов стремится к бесконечности. Далее вводятся определения состояний марковских цепей, которые необходимы для изучения поведения системы в долгосрочной перспективе.
Марковские цепи классифицируются в зависимости от возможности перехода из одних состояний в другие.
Группы состояний марковской цепи (подмножества вершин графа переходов), которым соответствуют тупиковые вершины диаграммы порядка графа переходов, называются эргодическими классами цепи. Если рассмотреть граф, изображенный выше, то видно, что в нем 1 эргодический класс M1 = {S5}, достижимый из компоненты сильной связности, соответствующей подмножеству вершин M2 = {S1, S2, S3, S4}. Состояния, которые находятся в эргодических классах, называются существенными, а остальные — несущественными (хотя такие названия плохо согласуются со здравым смыслом). Поглощающее состояние si является частным случаем эргодического класса. Тогда попав в такое состояние, процесс прекратится. Для Si будет верно pii = 1, т.е. в графе переходов из него будет исходить только одно ребро — петля.
Поглощающие марковские цепи используются в качестве временных моделей программ и вычислительных процессов. При моделировании программы состояния цепи отождествляются с блоками программы, а матрица переходных вероятностей определяет порядок переходов между блоками, зависящий от структуры программы и распределения исходных данных, значения которых влияют на развитие вычислительного процесса. В результате представления программы поглощающей цепью удается вычислить число обращений к блокам программы и время выполнения программы, оцениваемое средними значениями, дисперсиями и при необходимости — распределениями. Используя в дальнейшем эту статистику, можно оптимизировать код программы — применять низкоуровневые методы для ускорения критических частей программы. Подобный метод называется профилированием кода.
Например, в алгоритме Дейкстры присутствуют следующие состояния цепи:
vertex (v), извлечение новой вершины из очереди с приоритетами, переход только в состояние b;
begin (b), начало цикла перебора исходящих дуг для процедуры ослабления;
analysis (a), анализ следующей дуги, возможен переход к a, d, или e;
decrease (d), уменьшение оценки для некоторой вершины графа, переход к a;
end (e), завершение работы цикла, переход к следующей вершине.
Остается задать вероятности переходом между вершинами, и можно изучать продолжительности переходов между вершинами, вероятности попадания в различные состояния и другие средние характеристики процесса.
Аналогично, вычислительный процесс, который сводится к обращениям за ресурсами системы в порядке, определяемом программой, можно представить поглощающей марковской цепью, состояния которой соответствуют использованию ресурсов системы – процессора, памяти и периферийных устройств, переходные вероятности отображают порядок обращения к различным ресурсам. Благодаря этому вычислительный процесс представляется в форме, удобной для анализа его характеристик.
Цепь Маркова называется неприводимой, если любое состояние Sj может быть достигнуто из любого другого состояния Si за конечное число переходов. В этом случае все состояния цепи называются сообщающимися, а граф переходов является компонентой сильной связности. Процесс, порождаемый эргодической цепью, начавшись в некотором состоянии, никогда не завершается, а последовательно переходит из одного состояния в другое, попадая в различные состояния с разной частотой, зависящей от переходных вероятностей. Поэтому основная характеристика эргодической цепи –
вероятности пребывания процесса в состояниях Sj, j = 1,…, n, доля времени, которую процесс проводит в каждом из состояний. Неприводимые цепи используются в качестве моделей надежности систем. Действительно, при отказе ресурса, который процесс использует очень часто, работоспособность всей системы окажется под угрозой. В таком случае дублирование такого критического ресурса может помочь избежать отказов. При этом состояния системы, различающиеся составом исправного и отказавшего оборудования, трактуются как состояния цепи, переходы между которыми связаны с отказами и восстановлением устройств и изменением связей между ними, проводимой для сохранения работоспособности системы. Оценки характеристик неприводимой цепи дают представление о надежности поведения системы в целом. Также такие цепи могут быть моделями взаимодействия устройств с задачами, поступающими на обработку.
