Тема 2. Марковские случайные процессы

2.1. Понятие о марковском процессе

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

Пусть имеется некоторая физическая система Тема 2. Марковские случайные процессы - student2.ru , которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Пусть в настоящий момент Тема 2. Марковские случайные процессы - student2.ru (рис.) система находится в определенном состоянии Тема 2. Марковские случайные процессы - student2.ru . Мы наблюдаем процесс со стороны и в момент Тема 2. Марковские случайные процессы - student2.ru знаем состояние системы Тема 2. Марковские случайные процессы - student2.ru и всю предысторию процесса, все, что было при Тема 2. Марковские случайные процессы - student2.ru . Нас, естественно, интересует будущее Тема 2. Марковские случайные процессы - student2.ru . Можем ли мы его предсказать? В точности – нет, наш процесс случайный, значит – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы можем найти. Например, вероятность того, что через некоторое время Тема 2. Марковские случайные процессы - student2.ru система Тема 2. Марковские случайные процессы - student2.ru окажется в состоянии Тема 2. Марковские случайные процессы - student2.ru или сохранит состояние Тема 2. Марковские случайные процессы - student2.ru . Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы Тема 2. Марковские случайные процессы - student2.ru и забыв о его предыстории (поведение системы при Тема 2. Марковские случайные процессы - student2.ru ). Само состояние Тема 2. Марковские случайные процессы - student2.ru , разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Иначе формулируя, в марковском процессе будущее зависит от прошлого только через настоящее.

Итак, дадим определение марковского случайного процесса. Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени Тема 2. Марковские случайные процессы - student2.ru вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент Тема 2. Марковские случайные процессы - student2.ru и не зависят от того, когда и как система пришла в это состояние.

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

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

Пример такого процесса: техническое устройство Тема 2. Марковские случайные процессы - student2.ru состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможные состояния можно перечислить:

Тема 2. Марковские случайные процессы - student2.ru оба узла исправны,

Тема 2. Марковские случайные процессы - student2.ru первый узел ремонтируется, второй исправен,

Тема 2. Марковские случайные процессы - student2.ru второй узел ремонтируется, первый исправен,

Тема 2. Марковские случайные процессы - student2.ru оба узла ремонтируются.

Переходы системы Тема 2. Марковские случайные процессы - student2.ru из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или другого узла или окончания ремонта.

При анализе случайных процессов с дискретными состояниями обычно используют так называемый граф состояний. Построим граф состояний для рассмотренного примера (рис.).

Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем, является марковским, то для его описания можно построить довольно простую математическую модель. Но перед этим познакомимся с важным понятием теории вероятностей – понятием «потока событий».

2.2. Потоки событий

Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени. Например: поток вызовов на телефонной станции; поток отказов (сбоев) ЭВМ; поток железнодорожных составов, поступающих на сортировочную станцию.

Важной характеристикой потока событий является его интенсивность Тема 2. Марковские случайные процессы - student2.ru - среднее число событий, приходящееся на единицу времени. Интенсивность потока может быть как постоянной ( Тема 2. Марковские случайные процессы - student2.ru ), так и переменной, зависящей от времени Тема 2. Марковские случайные процессы - student2.ru . Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик – интенсивнее, чем в другие часы.

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

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность Тема 2. Марковские случайные процессы - student2.ru стационарного потока должна быть постоянной. На практике часто встречаются потоки событий, которые (по крайней мере на ограниченном участке времени) могут считаться стационарными. Например, поток вызовов, поступающих на АТС между 13 и 14 часами, практически стационарен; но тот же поток в течение суток уже не стационарен.

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени Тема 2. Марковские случайные процессы - student2.ru и Тема 2. Марковские случайные процессы - student2.ru число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Это означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от друга, вызванные каждое своими собственными причинами. Например, поток пассажиров входящих в метро, практически не имеет последействия. А вот поток пассажиров выходящих из метро, уже имеет последействие.

Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по несколько сразу. Например, поток клиентов, направляющихся в парикмахерскую или к зубному врачу, обычно ординарен, чего нельзя сказать о потоке клиентов, направляющихся в загс для регистрации браков. Если поток событий ординарен, то вероятностью попадания на малый участок времени Тема 2. Марковские случайные процессы - student2.ru двух или более событий можно пренебречь.

Поток событий называется простейшим, если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия.

В расчетах, связанных с потоками событий, очень удобно пользоваться понятием «элемента вероятности». Рассмотрим на оси Тема 2. Марковские случайные процессы - student2.ru простейший поток с интенсивностью Тема 2. Марковские случайные процессы - student2.ru и произвольно расположенный элементарный (очень маленький) участок времени Тема 2. Марковские случайные процессы - student2.ru . Элементом вероятности называется вероятность попадания на этот участок хотя бы одного события потока. Для простейшего потока элемент вероятности равен интенсивности потока, умноженной на длину элементарного участка.

Тема 2. Марковские случайные процессы - student2.ru (6)

Элемент вероятности, в силу отсутствия последействия, совершенно не зависит от того, сколько событий и когда появлялись ранее.

Поток событий называется рекуррентным, если он стационарен, ординарен, а интервалы времени между событиями Тема 2. Марковские случайные процессы - student2.ru представляют собой независимые случайные величины с одинаковым произвольным распределением. Пример: технический элемент (радиолампа) работает непрерывно до своего отказа (выхода из строя); отказавший элемент мгновенно заменяется новым. Если отдельные экземпляры элемента выходят из строя независимо друг от друга, то поток отказов будет рекуррентным.

2.3. Уравнения Колмогорова для вероятностей состояний.

Финальные вероятности состояний.

Рассматривая марковские процессы с дискретным состоянием и непрерывным временем удобно представлять, что все переходы системы Тема 2. Марковские случайные процессы - student2.ru из состояния в состояние происходят под действием каких-то потоков событий (поток вызовов, поток отказов, поток восстановлений и т.д.). Если все потоки событий, переводящие систему Тема 2. Марковские случайные процессы - student2.ru из состояния в состояние – простейшие, то процесс протекающий в системе, будет марковким (это достаточное, но не необходимое условие). Это и естественно, так как простейший поток не обладает последействием: в нем «будущее» не зависит от «прошлого».

Если система Тема 2. Марковские случайные процессы - student2.ru находится в каком-то состоянии Тема 2. Марковские случайные процессы - student2.ru , из которого есть непосредственный переход в другое состояние Тема 2. Марковские случайные процессы - student2.ru , то это можно представить так, как будто на систему, пока она находится в состоянии Тема 2. Марковские случайные процессы - student2.ru , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из Тема 2. Марковские случайные процессы - student2.ru в Тема 2. Марковские случайные процессы - student2.ru .

Для наглядности проставим на графе состояний интенсивности потоков событий. Обозначим через Тема 2. Марковские случайные процессы - student2.ru интенсивность потока событий переводящего систему из состояния Тема 2. Марковские случайные процессы - student2.ru в Тема 2. Марковские случайные процессы - student2.ru . Граф состояний с проставленными интенсивностями называется размеченным.

Построим такой граф. Интенсивность потоков событий, переводящих систему из состояния в состояние, будем вычислять, предполагая, что среднее время ремонта узла не зависит от того, ремонтируется ли один узел или оба сразу. Это будет именно так, если ремонтом каждого узла занят отдельный специалист. Найдем все интенсивности потоков событий, переводящих систему из состояния в состояние. Пусть система находится в состоянии Тема 2. Марковские случайные процессы - student2.ru . Какой поток событий переводит ее в состояние Тема 2. Марковские случайные процессы - student2.ru ? Очевидно, поток отказов первого узла. Его интенсивность Тема 2. Марковские случайные процессы - student2.ru равна единице, деленной на среднее время безотказной работы первого узла. Какой поток событий переводит систему обратно из Тема 2. Марковские случайные процессы - student2.ru в Тема 2. Марковские случайные процессы - student2.ru ? Очевидно, поток «окончания ремонтов» первого узла. Его интенсивность Тема 2. Марковские случайные процессы - student2.ru равна единице, деленной на среднее время ремонта первого узла. Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем стрелкам графа (рис).

Пусть рассматривается система Тема 2. Марковские случайные процессы - student2.ru , имеющая Тема 2. Марковские случайные процессы - student2.ru возможных состояний Тема 2. Марковские случайные процессы - student2.ru . Назовем вероятностью Тема 2. Марковские случайные процессы - student2.ru го состояния вероятность Тема 2. Марковские случайные процессы - student2.ru того, что в момент Тема 2. Марковские случайные процессы - student2.ru система будет находиться в состоянии Тема 2. Марковские случайные процессы - student2.ru . Очевидно, что для любого момента сумма всех вероятностей состояний равна 1: Тема 2. Марковские случайные процессы - student2.ru .

Имея в своем распоряжении размеченный граф состояний, можно найти все вероятности состояний Тема 2. Марковские случайные процессы - student2.ru как функции времени. Для этого составляются и решаются так называемые уравнения Колмогорова – особого вида дифференциальные уравнения, в которых неизвестными функциями являются вероятности состояний.

Рассмотрим на конкретном примере, как эти уравнения составляются.

….

Это система 4 линейных дифференциальных уравнений с 4-мя неизвестными функциями Тема 2. Марковские случайные процессы - student2.ru . Одно из них любое можно отбросить, заменив его условием нормировки Тема 2. Марковские случайные процессы - student2.ru .

Сформулируем теперь общее правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности какого-то ( Тема 2. Марковские случайные процессы - student2.ru го) состояния. В правой части – сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния умноженная на вероятность данного ( Тема 2. Марковские случайные процессы - student2.ru го) состояния.

Чтобы решить уравнения Колмогорова и найти вероятности состояний необходимо, прежде всего, задать начальные условия.

Полученную таким образом систему дифференциальных уравнений можно решить с использованием преобразования Лапласа.

Однако исследователя часто интересует вопрос, что будет происходить с вероятностями состояний при Тема 2. Марковские случайные процессы - student2.ru . Будут ли вероятности состояний стремится к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют.

Предположим, что это условие выполнено, и финальные вероятности существуют:

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

Если вероятности Тема 2. Марковские случайные процессы - student2.ru постоянны, то их производные равны нулю. Значит, все левые части уравнений Колмогорова будут равны нулю. И мы имеем уже систему не дифференциальных, а линейных алгебраических уравнений.

Наши рекомендации