Марковские цепи с конечным числом состоянии и непрерывным временем
Определение. Случайный процесс с дискретным временем называется марковским, если на любом шаге S вероятность P (S) перехода системы из состояния i , в состояние jзависитлишь от состояния А в которое попала система на (S—1) шаге, и не зависит от того, как и когда она в это состояние попала. Кратко это свойство формулируют так: при заданном настоящем будущее не зависит от прошлого. В силу этого марковский процесс еще называют процессомбез последействияили однородным.
Определение. Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s –ом испытании наступит событие Aj при условии, что в (s – 1) – ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний.
Независимые испытания являются частным случаем цепи Маркова. События называются состояниями системы, а испытания – изменениями состояний системы.
По характеру изменений состояний цепи Маркова можно разделить на две группы.
Определение. Цепью Маркова с дискретным временемназывается цепь, изменение состояний которой происходит в определенные фиксированные моменты времени. Цепью Маркова с непрерывным временемназывается цепь, изменение состояний которой возможно в любые случайные моменты времени.
Определение. Однороднойназывается цепь Маркова, если условная вероятность pij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность pij называется переходной вероятностью.
Пусть, число состояний конечно и равно k.
Тогда матрица, составленная из условных вероятностей перехода будет иметь вид:
Эта матрица называется матрицей перехода системы.
Т.к. в каждой строке содержаться вероятности событий, которые образуют полную группу, то сумма элементов каждой строки матрицы равна единице.
На основе матрицы перехода системы можно построить граф состояний системы,или размеченный граф состояний.
Пример. По заданной матрице перехода построить граф состояний.
Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.
S1
0,2 0,7
S2 0,4 S4
0,6 0,5
0,1 0,5
S3
На графе не отмечаются вероятности перехода системы из одного состояния в то же самое.
Пусть Pij(n) – вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r – некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое pij(1) = pij.
Тогда вероятность Pij(n) может быть найдена по формуле, называемой равенством Маркова:
Здесь т – число шагов (испытаний), за которое система перешла из состояния i в состояние r.
Равенство Маркова можно трактовать как видоизмененную формулу полной вероятности.
Используя матрицу перехода Р1, можно найти вероятности Pij(2) перехода из состояния i в состояние j за два шага , т.е. матрицу Р2:
так как при n=2 равенство Маркова – формула умножения матрицы P1 на P1 , следовательно, можно получить:
Пример. Задана матрица переходов Р1. Найти матрицу Р2.
Определение. Матрицы, суммы элементов всех строк которых равны единице, называются стохастическими.
Если при некотором п все элементы матрицы Рп не равны нулю, то такая матрица переходов называется регулярной.
Регулярные матрицы переходов задают цепь Маркова, в которой каждое состояние может быть достигнуто через п шагов из любого состояния. Такие цепи Маркова также называются регулярными.
Теорема. (теорема о предельных вероятностях) Пусть дана регулярная цепь Маркова с п состояниями и Р – ее матрица вероятностей перехода. Тогда существует предел и матрица Р(¥) имеет вид:
Т.о. матрица Р(¥) состоит из одинаковых строк. Числа u1, u2, …, un называются предельными вероятностями.Эти вероятности не зависят от исходного состояния системы и являются компонентами собственного вектора матрицы РТ (транспонированной к матрице Р).
Собственный вектор полностью определяется из условий:
Пример. Найдем предельные вероятности для рассмотренного выше примера.
C учетом того, что u1 + u2 = 1, получаем:
Итак:
Возможные состояния системы в момент t=m можно охарактеризовать векторами (m)=(q1(m), q2(m), ..., qk(m)),
где qi(m) – это вероятность того, что в момент t=m система находится в состоянии Аi.
Используя формулу полной вероятности, нетрудно показать, что имеет место равенство:
(m+1)= (m)×Р.
Применяя эту формулу последовательно при m=0, 1, 2,... , можно получить выражение для вектора (m) через вектор начальных состояний (0) и матрицу вероятностей переходов Р, а именно:
(m)= (0)×Рm.
Предельным распределением вероятностей цепи Маркова называется вектор qp={q1, q2, ..., qk} такой, что
Стационарным распределением называется вектор q={q1, q2, ..., qk}, который удовлетворяет условиям:
Вектор определяет распределение вероятностей, которое с течением времени не меняется, т.е. стационарное распределение является также предельным распределением. В развернутом виде система для нахождения координат вектора , т.е. имеет следующий вид:
(*)
Первые n уравнений этой системы являются линейно зависимыми, поэтому любое одно из них можно отбросить. В результате получится система n линейных уравнений, которая почти всегда имеет единственное решение.
По теореме о предельных вероятностях регулярная цепь Маркова имеет предельное распределение вероятностей, которое может быть найдено из системы (*).
Задача 1. Задана матрица P1 вероятностей перехода дискретной цепи Маркова из i-ro в j-oe состояние за один шаг (i, j = 1, 2). Распределение вероятностей по состояниям в начальный момент t = 0 определяется вектором .
Найти:
1) матрицу P2 перехода цепи из состояния i в состояние j за два шага;
2) распределение вероятностей по состояниям в момент t = 2;
3) вероятность того, что в момент t = 1 состоянием будет i = 2;
4) стационарное распределение.
Дано:
Решение: Для дискретной цепи Маркова в случае её однородности справедливо соотношение ,
где P1 – матрица переходных вероятностей за один шаг
Pn – матрица переходных вероятностей за n шагов;
1) Найдем матрицу P2 перехода за 2 шага.
Пусть распределение вероятностей по состояниям на S-ом шаге определяется вектором
Зная матрицу Pn перехода за n шагов можно определить распределение вероятностей по состоянием на (s+n)-ом шаге.
(4) |
,
2) Найдем распределение вероятностей по состоянием системы в момент t=2. Положим (4) S=0 и n=2. Тогда .
Получим
3) Найдем распределение вероятностей по состояниям системы в момент t=1. Положим в (4) S(0) и n=1, тогда
Откуда видно, что вероятность того, что в момент t=1 состоянием цепи будет A2, равна p2(1)=0,87.
Распределением вероятностей по состояниям называется стационарным, если оно не меняется от шага к шагу, то есть
(5) |
Тогда из соотношения (4) при n=1 получим или
4) Найдем стационарное распределение. Так как k=2 имеем . Запишем систему линейных уравнений (5) в координатной форме:
; ; ; ; .
Следовательно, .
Ответ:
1) матрица перехода за два шага для данной цепи Маркова имеет вид ;
2) распределение вероятностей по состояниям в момент t=2 равно ;
3) вероятность того, что в момент t=1 состоянием цепи будет A2, равна p2(1)=0,87;
4) Стационарное распределение имеет вид .
Задача 2. Ремонтная мастерская располагает двумя диагностическими приборами. Известно, что если в какой-то день оба прибора были незаняты, то на следующий день с вероятностью 0,6 они снова окажутся незанятыми и с одинаковыми вероятностями будет занят один или два прибора. Если был занят один прибор, то назавтра с вероятностью 0,2 оба будут свободны и с вероятностью 0,5 – оба заняты. Наконец, если оба прибора были заняты, то назавтра с вероятностью 0,6 оба опять будут заняты и с вероятностью, вдвое меньшей, будет занят только один прибор. Предполагая, что в начале недели (в понедельник) нет никакой информации о занятости приборов, найти вероятность того, что в среду оба прибора будут заняты. Кроме того, найти предельное распределение вероятностей.
Решение. Рассмотрим следующие состояния:
Е0 – не занят ни один прибор;
Е1 – занят один прибор;
Е2 – заняты оба прибора.
Исходя из условия задачи матрица вероятностей переходов имеет вид:
Отсутствие информации в понедельник фактически означает, что вероятности начальных состояний одинаковые, т.е.:
=(1/3; 1/3; 1/3).
Вероятности состояний в среду определяются вектором q(2).
Имеем:
Таким образом, вероятность занятости сразу двух приборов будет равна 136/300.
Предельные вероятности найдем как решение системы:
Решая эту систему методом Гаусса, найдем:
q1=13/51;
q2=14/51;
q3=24/51.
Марковские цепи с конечным числом состоянии и непрерывным временем
Пусть физическая система, возможные состояния которой А1,А2, .... , Аk может переходить из состояния в состояние не в определенные моменты времени, а в любой момент времени случайным образом. При этом возникает случайный процесс (цепь) с непрерывным временем.
Если процесс с непрерывным временем обладает отсутствием последействия, то его называют марковским случайным процессом с непрерывным временем или непрерывной цепью Маркова.
Для непрерывной цепи Маркова. вероятность перехода из состояния Аi в состояние Аj в любой момент времени равна нулю. Поэтому вместо вероятности перехода Рij рассматривают плотность вероятности перехода lij которая определяется как предел отношения вероятности перехода Рij{Dt} за время Dt из состояния Ai в состояние Aj; к длине промежутка Dt при Dt 0, т. е.
lij = . (1)
Плотность вероятности lij может быть как постоянной величиной, так и величиной, зависящей от момента времени t, с которого начинается промежуток Dt.
Если плотность вероятности перехода lij не зависит от t, марковский процесс(цепь) называетсяоднородным.
В дальнейшем будем предполагать, что рассматриваемые процессы удовлетворяют условиюординарности: в один и тот же момент времени t система не может изменить свое состояние более чем один раз.
Из курса дифференциального исчисления известно, что соотношение (1) можно записать в виде Рij(Dt)=lijDt + aij(Dt), где aij(Dt)— бесконечно малая высшего порядка по сравнению с Dt. Тогда с точностью до бесконечно малой имеем:
Pij(Dt) = lijDt, i j (2)
т. е. вероятность перехода Рij(Dt) за малое время Dt равна произведению плотности вероятности перехода lij на Dt. Поэтому lij еще называютинтенсивностью перехода системы из Аi в Aj.
Из величин lij составим квадратнуюматрицу интенсивностей переходов:
L = (3)
обладающую свойствами:
1) lij 0, i j, это следует из (2), так как Pij(Dt) 0;
2) lij 0, i=j, так как lii = (Pii(Dt) – 1);
3) = 0 действительно, (li1 + li2 + … lii + … lik)Dt = Pi1(Dt) + Pi2(Dt) +…+( Pii(Dt) – 1) + …+ Pik(Dt)) = 0.
Интенсивности переходов lij удобно задавать на графе состояний. На графе указывают обычно интенсивности lij >0.
Зная матрицу интенсивностей переходов или размеченный граф состояний, можно определить вероятности состояний:
p1 (t), p2 (t), …, pk(t), = 1, (4)
т. е. вероятности нахождения системы в состоянии А1, А2, … , Аk в момент времени t. Вероятности pi(t) как функции t удовлетворяютсистеме дифференциальных уравнении Колмогорова, которая в матричной форме имеет вид
p’(t) = p(t) L (5)
где p’(t) = ( p1’(t), p2’(t),…, pk’(t)); p(t) = ( p1(t), p2(t),…, pk(t)), L —
матрица интенсивностей переходов (З).
Распределение вероятностей состояний системы называетсястационарным, если оно не меняется с течением времени, т. е. если
p(t) = p, (6)
где p = ( p1, p2, …, pk) = const, j = 1, 2, ..., k. Дифференцируя равенство (6) по t, получим: p’(t) = 0.
С учетом уравнения (5) приходим к выводу, что стационарное распределение удовлетворяет соотношению
p L = 0, (7)
т. е. для получения стационарного распределения достаточно в системе дифференциальных уравнений Колмогорова положить p'j =0; j =1, 2,.., k.
Уравнения системы (7) не в матричной форме удобно выписывать непосредственно по размеченному графику состояний в соответствии со следующим правилом:
сумма произведений ljipi, j i для стрелок, выходящих из i-го состояния, равна сумме произведений lijpj, j iдля стрелок, входящих в i-е состояние.
Задача 2. Задана матрица
интенсивностей переходов непрерывной цепи Маркова. Составить размеченный граф состояний, соответствующий матрице L; выписать систему дифференциальных уравнений Колмогорова для вероятностей состояний; найти стационарное распределение вероятностей.
Решение. Размеченный граф должен иметь 3 состояния А1, А2, А3. Из матрицы L находим интенсивности переходов lij>0, i j и отмечаем их над соответствующими стрелками (рис. 2). Имеем l12=5, соединяем состояния А1 и А2 стрелкой, направленной от А1 к А2, отмечая интенсивность перехода над стрелкой; l13=0, следовательно, состояния А1 и А3 стрелкой не соединяем и т. д. Составляем
уравнения Колмогорова: положим в уравнении (5); p(t) = (p1(t), p2(t), p3(t)); p’(t) = (p1’(t), p2’(t), p3’(t)),
тогда
(p1’(t), p2’(t), p3’(t)) = (p1(t), p2(t), p3(t))
умножая вектор p(t) на матрицу L будем иметь:
p1’(t) = - 5 p1(t) + p2(t) + p3(t);
p2’(t ) = 5p1(t) - p2(t) + p3(t);
p3’(t ) = -2 p3(t).
Для нахождения стационарного распределения достаточно в последней системе дифференциальных уравнений положить все производные pi’(t ) = 0, i = 1, 2, 3. Пусть p = (p1, p2, p3)есть стационарное распределение, тогда:
0 = - 5 p1 + p2 + p3;
0 = 5p1 - p2 + p3; (8)
0 = -2 p3.
Решая систему, получим p3 = 0, p2= 5p1. В силу уравнения (4) p1 + p2 + p3 = 1,следовательно, p = ( 1/6; 5/6; 0).
Заметим, что для определения стационарного распределения мы получили бы такую же систему, если бы воспользовались правилом, приведенным выше. Действительно, для состояния А1 имеем 5 p1 = 1 p2 + 1 p3 , для состояния А2: 1 p2 = 5p1 + 1 p3, для состояния A3: 1 p3 + 1p3 = 0. Составляя из этих уравнений систему, убедимся, что она эквивалентна системе(8).
Для многих практических случаев важно знать, как ведут себя вероятности pi(t}, i=l, 2,..., k при большом времени работы системы, т. е. при t . Если при определенных условиях существуютпредельные вероятности состояний
pi = pi(t), i = 1, 2, …, k, (9)
не зависящие от того, в каком состоянии система находилась в начальный момент, то это означает, что с течением времени в системе устанавливаетсяпредельный стационарный режим.
Система, для которой существуют предельные вероятности, называетсяэргодической, а возникающий в ней случайный процессэргодическим.
Выясним условия, при которых существуют предельные вероятности состояний. Введем ряд понятий.
Состояние Аi называетсянесущественным, если найдется такое состояние Аj что из Ai в Аj, перейти можно, а из Aj в Ai — нельзя. Состояние Ai называетсясущественным,если оно не является несущественным. Например, для системы, граф состояний которой дан на рис. 2, состояние А3 несущественно (так как из него можно перейти в состояние А1или А2 но обратно вернуться нельзя), состояния А1 и A2 — существенны. Два существенных состояния Ai и Aj называютсясообщающимися, если из Ai можно попасть в Aj и из Aj в Ai. На рис. 2 представлены сообщающиеся состояния A1 и А2.
Теорема 1. Если Ai — несущественное состояние, то
pi(t) = 0. (10)
Смысл этой теоремы состоит в том, что в конечном итоге система выйдет из несущественного состояния Ai и больше в него не вернется.
Теорема 2. Чтобы цепь (процесс) с конечным числом состояний имела единственное стационарное распределение вероятностей, совпадающее с предельным, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой.
Пример. В условиях задачи 2 найти предельные вероятности состояний.
Решение. В рассматриваемой цепи состояния A1 и A2 являются существенными сообщающимися состояниями, A3 — несущественно. Следовательно, по теореме 2 предельное распределение совпадает со стационарным и имеет вид p = ( 1/6; 5/6; 0). Заметим, что результат p3(t) = 0 можно было получить непосредственно из теоремы 1, так как состояние A3 несущественно.
Пример. Задана матрица интенсивностей переходов непрерывной цепи Маркова. Составить размеченный граф состояний, соответствующий матрице ; составить систему дифференциальных уравнений Колмогорова для вероятностей состояний; найти предельное распределение вероятностей.
Дано:
Решение: Однородная цепь Маркова с конечным числом состояний A1,A2,…,Ak характеризуется матрицей интенсивностей переходов
,
где - интенсивность перехода цепи Маркова из состояния Ai в состояние Aj;
- вероятность перехода Ai Aj за интервал времени .
Переходы системы из состояния в состояние удобно задавать с помощью размеченного графа состояний, на котором отмечаются дуги, соответствующие интенсивностям .
Составим размеченный граф состояний для заданной матрицы интенсивностей переходов.
Пусть - вектор вероятностей , нахождения системы в состоянии Aj в момент t. Очевидно, что и . Тогда по правилу дифференцирования векторной функции скалярного аргумента получим . Вероятности удовлетворяют системе дифференциальных уравнений Колмогорова (СДУК), которая в матричной форме имеет вид
(6) |
,
Если в начальный момент система находилась в состоянии Aj, то СДУК следует решать при начальных условиях
(7) |
Совокупность СДУК (6) и начальных условий (7) однозначно описывает однородную цепь Маркова непрерывным временем и конечным числом состояний.
Составим СДУК для заданной цепи Маркова. Поскольку k=3, то j=1,2,3. Из соотношения (6) получим
Отсюда будем иметь:
Последнее условие называется нормировочным.
Распределение вероятностей по состояниям называется стационарным, если оно не меняется с течением времени, то есть , где pj=const, j=1,2,…,k.
Отсюда . Тогда из СДУК (6) получаем систему для нахождения стационарного распределения , где .
Для данной задачи из СДУК будет иметь
Из нормировочного условия получим
Ответ: предельное распределение имеет вид .
Пример. Определить, существует ли стационарный режим для марковского случайного процесса, размеченный граф состояний которого изображен на рисунке. Если стационарный режим существует, то найти стационарное распределение вероятностей.
Указание.Проведите классификацию состояний системы и примените следствия из теоремы Маркова.
а) Состояние 6 - существенное. Остальные - несущественные состояния. Поэтому единственное стационарное распределение совпадает с предельным.
Для несущественных состояний предельные вероятности равны нулю. Учитывая, что сумма всех вероятностей = 1 получим искомое стационарное распределение:
б) Несущественные состояния 1, 2, 6. Состояния 3, 4, 5 - существенные сообщающиеся поэтому единственное стационарное распределение совпадает с предельным.
Приравнивая к каждую из строк-уравнений к 0 и учитывая, что сумма вероятностей = 1 получим: