Цепи Маркова

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

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

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

РЕФЕРАТ

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

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

Содержание:

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

Рассмотрим состояния цепи Маркова более конкретно. Их можно классифицировать следующим образом:

- Возвратное состояние;

- Достижимое состояние;

- Неразложимая цепь Маркова;

- Периодическое состояние;

- Периодическая цепь Маркова;

- Поглощающее состояние;

- Эргодическое состояние.

Рассмотрим некоторые из них.

Возвратное состояние – это состояние Марковской цепи, посещаемое ею бесконечное число раз.

Определение.

Пусть дана однородная цепь Маркова с дискретным временем . Пусть - вероятность, выйдя из состояния i, вернуться в него ровно за n шагов. Тогда - вероятность, выйдя из состояния i, вернуться в него за конечное время.

Состояние i называется возвратным (рекуррентным), если fii = 1. В противном случае состояние называется невозвратным (транзиентным).

Достижимое состояние

Определение

Пусть - однородная цепь Маркова с дискретным временем. Состояние j называется достижимым из состояния i, если существует           n = n(i,j) такое, что  .

Пишут .

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

Период состояния

Пусть дана однородная цепь Маркова с дискретным временем с матрицей переходных вероятностей P. В частности, для любого , матрица является матрицей переходных вероятностей за n шагов. Рассмотрим последовательность . Число , где gcd обозначает наибольший общий делитель, называется периодом состояния j.

Замечание: таким образом, период состояния j равен d(j), если из того что следует, что n делится на d(j).

Периодические состояния и цепи

- Если d(j) > 1, то состояние j называется периодическим.

- Если d(j) = 1, то состояние j называется апериодическим.

- Периоды сообщающихся состояний совпадают:

.

Таким образом период любого неразложимого класса цепи Маркова определён и равен периоду любого своего представителя. Соответственно, классы делятся на периодические и апериодические.

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

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

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

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

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

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

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

p0 (1 - α) + p1 β = p0,

p0 α + p1 (1 - α - β) + p2 2β = p1,

p1 α + p2 (1 - α - 2β) + p3 3β = p2,

p2 α + p3 (1 - α - 3β) + p4 4β = p3,

p3 α + p4 (1 - 4β) = p4.

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

p1 = γ p0,

p2 = γ2 p0 / 2,

p3 = γ3 p0 / 3,

p4 = γ4 p0 / 4,

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

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

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

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

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

Логично, что продуктивность почвы со временем ухудшается. Например, если в прошлом году состояние почвы было удовлетворительное, то в этом году оно может только остаться таким же или стать плохим, а хорошим никак не станет. Однако садовник может повлиять на состояние почвы и изменить переходные вероятности в матрице P1 на соответствующие им из матрицы P2:

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