Цепи Маркова

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Кафедра «Высшая математика»

РЕФЕРАТ

По дисциплине: «Высшая математика»

На тему: "Цепи Маркова"

Содержание:

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

Основные понятия теории Марковских цепей...................................................5

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

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

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

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

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

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

Список используемой литературы....................................................................22

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

Для начала введем определение: процесс, протекающий в физической системе, называется марковским, если  в любой момент времени вероятность любого состояния системы в будущем зависит только от состояния системы в текущий момент и не зависит от того, каким образом система пришла в это состояние.

Также цепью Маркова можно определить как последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s–ом испытании наступит событие Aj при условии, что в (s–1)–ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний.

Эти цепи, названные в честь своего изобретателя - Маркова Андрея Андреевича (1856-1922), который был выдающимся русским математиком, внёсшим большой вклад в теорию вероятности, математический анализ и теорию чисел.

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

1. множеством состояний S = {s1, …, sn}, событием является переход из одного состояния в другое в результате случайного испытания

2. вектором начальных вероятностей (начальным распределением) p(0) = {p(0)(1),…, p(0)(n)}, определяющим вероятности p(0)(i) того, что в начальный момент времени t=0 процесс находился в состоянии si

3. матрицей переходных вероятностей P = {pij}, характеризующей вероятность перехода процесса с текущим состоянием si в следующее состояние sj, при этом сумма вероятностей переходов из одного состояния равна одному:

∑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) × Pn

Векторы p(n) при росте n в некоторых случаях стабилизируются - сходятся к некоторому вероятностному вектору ρ, который можно назвать стационарным распределением цепи. Стационарность проявляется в том, что взяв p(0) = ρ, мы получим p(n) = ρ для любого n.

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

Также можно показать, что если при каком-нибудь положительном значении n все элементы матрицы P n положительны, тогда вектор p(n) все-равно будет стабилизироваться.

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

Основные понятия теории Марковских цепей.

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

        Для описания эволюции этой системы введем последовательность дискретных случайных величин , ,..., ,... Индекс n играет роль времени. Если в момент времени n система находилась в состоянии , то мы будем считать, что = j. Таким образом, случайные величины являются номерами состояний системы.

Последовательность , ,..., ,... образует цепь Маркова, если для любого n и любых , , ..., ,...

P(=j / = , ..., =i)=P(=j / =i).

  Для цепей Маркова вероятность в момент времени n попасть в состояние , если известна вся предыдущая история изучаемого процесса, зависит только от того, в каком состоянии находился процесс в момент n-1. То есть при фиксированном "настоящем" "будущее" не зависит от "прошлого". Свойство независимости "будущего" от "прошлого" при фиксированном "настоящем" называется  марковским  свойством.

Вероятности   (=j / =i), i, j=1,2,..., r называются вероятностями перехода из состояния в состояние за один шаг.

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

Вероятности перехода удобно располагать в виде квадратной матрицы

Матрица P называется матрицей вероятностей перехода однородной цепи Маркова за один шаг. Она обладает следующими свойствами:

              а) ;

              б) для всех i: 

Квадратные матрицы, для которых выполняются условия а) и б), называются стохастическими.

Вектор , где =P(), i=1,2...,r  называется вектором начальных вероятностей.

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

Приведем пример: Завод выпускает телевизоры определенного типа. В зависимости от того, находит ли данный тип телевизора спрос у населения, завод в конце каждого года может находиться в одном из состояний: состояние 1 – спрос есть, состояние 2 – спроса нет. Пусть вероятность сохранить состояние 1 в в следующем году с учетом возможного изменения спроса равна , а вероятность изменить состояние 2 с учетом мероприятий по улучшению выпускаемой модели равна . Тогда процесс производства на данном заводе можно описать цепью Маркова с матрицей переходов:

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

Можно показать, что матрица вероятностей перехода цепи Маркова за n шагов равняется n-ой степени матрицы P вероятностей перехода за один шаг. Для однородной цепи Маркова при любом m выполняется равенство

P()=P().

Но последняя вероятность есть вероятность перехода из состояния в состояние за n шагов.

Теорема о предельных вероятностях.

Цепь Маркова, для которой существуют пределы , называется эргодической. Решение (,,...,) написанной выше системы (1) называется стационарным распределением вероятностей для марковской цепи с матрицей перехода P = [].

Если из состояния система может перейти в состояние с положительной вероятностью за конечное число шагов, то говорят, что достижимо из .

Состояние называется существенным, если для каждого состояния , достижимого из , достижимо из . Если же для хотя бы одного j достижимо из , а не достижимо из , то - несущественное состояние.

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

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

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

Группы состояний марковской цепи (подмножества вершин графа переходов), которым соответствуют тупиковые вершины диаграммы порядка графа переходов, называются эргодическими классами цепи. Если рассмотреть граф, изображенный выше, то видно, что в нем 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, доля времени, которую процесс проводит в каждом из состояний. Неприводимые цепи используются в качестве моделей надежности систем. Действительно, при отказе ресурса, который процесс использует очень часто, работоспособность всей системы окажется под угрозой. В таком случае дублирование такого критического ресурса может помочь избежать отказов. При этом состояния системы, различающиеся составом исправного и отказавшего оборудования, трактуются как состояния цепи, переходы между которыми связаны с отказами и восстановлением устройств и изменением связей между ними, проводимой для сохранения работоспособности системы. Оценки характеристик неприводимой цепи дают представление о надежности поведения системы в целом. Также такие цепи могут быть моделями взаимодействия устройств с задачами, поступающими на обработку.