Лабораторная работа №6 Марковские случаные процессы Теоретические положения
Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага. В противном случае марковская цепь называется неоднородной.
Рассмотрим
сначала однородную марковскую цепь.
Пусть система S
имеет п возможных
состояний 
.
Предположим, что для каждого состояния
нам известна вероятность перехода в
любое другое состояние за один шаг (в
том числе и вероятность задержки в
данном состоянии). Обозначим 
вероятность перехода
за один шаг из состояния 
в состояние 
;
будет вероятность
задержки системы в состоянии 
.
Запишем переходные вероятности
в виде прямоугольной таблицы (матрицы):
Некоторые
из переходных вероятностей 
могут быть равны нулю: это означает, что
за один шаг переход системы из i-го
состояния в j-е
невозможен. По главной диагонали матрицы
переходных вероятностей стоят вероятности
того, что система не
выйдет из состояния 
,
а останется в нём.
Пользуясь
введенными выше событиями 
переходные вероятности
можно записать как
условные вероятности:
.
Отсюда
следует, что сумма членов, стоящих в
каждой строке матрицы ,
должна быть равна единице, так как, в
каком бы состоянии система ни была перед
k-м шагом, события 
несовместны и образуют
полную группу.
При
рассмотрении марковских цепей часто
бывает удобно пользоваться «размеченным
графом состояний», на котором проставлены
не все переходные вероятности, а только
те из них, которые не равны нулю и меняют
состояние системы, т. е. 
при 
;
«вероятности задержки» 
проставлять на графе излишне, так как
каждая из них дополняет до единицы сумму
переходных вероятностей, соответствующих
всем стрелкам, исходящим из данного
состояния.
Если
из состояния 
не исходит ни одной стрелки (переход из
него ни в какое другое состояние
невозможен), соответствующая вероятность
задержки 
равна единице.
Имея в распоряжении размеченный граф состояний (или, что равносильно, матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний
после любого (k-го) шага.
Покажем, как это делается.
Предположим,
что в начальный момент (перед первым
шагом) система находится в каком-то
определенном состоянии, например, 
.
Тогда, для начального момента (0) будем
иметь:
,
т.
е. вероятности всех состояний равны
нулю, кроме вероятности
начального состояния 
,
которая равна единице.
Найдем
вероятности состояний после первого
шага. Мы знаем, что перед первым шагом
система заведомо находится в состоянии
.
Значит, за первый шаг она перейдет в
состояния 
с вероятностями
,
записанными в m-й строке матрицы переходных вероятностей. Таким образом, вероятности состояний после первого шага будут:
Найдем вероятности состояний после второго шага
.
Будем вычислять их по формуле полной вероятности, с гипотезами:
—
после первого шага система
была в состоянии 
;
—
после первого шага бистема
была в состоянии
;
— . . . . . .
—
после первого шага система
была в состоянии 
;
— . . . . . .
—
после первого шага система
была в состоянии 
.
Вероятности
гипотез известны (см. );
условные вероятности перехода в состояние
,
при каждой гипотезе тоже известны и
записаны в матрице переходных вероятностей.
По формуле полной вероятности получим:
.
Пример
1. По некоторой цели
ведется стрельба четырьмя выстрелами
в моменты времени 
.
Возможные состояния цели (системы 5):
—цел,ь невредима;
—цель незначительно
повреждена;
—цель получила существенные
повреждения,
—цель полностью поражена
(не может функционировать),
Размеченный граф состояний системы показан на рис. 4.9.
В
начальный момент цель находится в
состоянии 
(не повреждена). Определить вероятности
состояний цели после четырех выстрелов.
Рис. 4.9
Решение. Из графа состояний имеем:
Аналогично находим:
Таким образом, матрица переходных вероятностей имеет вид:
В формуле (2.6) суммирование распространяется формально на все состояния 5],.., 5П; фактически учитывать надо только те из них, для которых переходные вероятности Р;-г отличны от нуля, то есть те состояния, из которых может совершиться переход в состояние 5г (или задержка в нем).
Таким образом, вероятности состояний после второго шага известны. Очевидно, после третьего шага они определяются аналогично:
Так как в начальный момент цель 5 находится в состоянии 5Ь то
Вероятности состояний после первого шага (выстрела) берутся из первой строки матрицы:
и вообще после &-го шага:
Вероятности состояний после второго шага:
Итак, вероятности состояний рг(К) после &-го шага определяются рекуррентной формулой (2.8) через вероятности состояний после (^ — 1).го шага; те, в свою очередь—через вероятности состояний после (Ь — 2)-го шага, и т. д.
Вероятности состояний после третьего шага
Вероятности состояний после четвертого шага
Таким образом, нами получены вероятности всех исходов обстрела цели (четырех выстрелов):
цель не повреждена: рх(4) -х, 0,008;
цель получила незначительные повреждения: р3(4) •х. 0,070;
цель получила существенные повреждения: ра(4) ~0,129,
цель поражена полностью: р4(4) ж 0,793
Мы рассмотрели однородную марковскую цепь, для которой вероятности перехода от шага к шагу не меняются.
Рассмотрим теперь общий случай — неоднородную марковскую цепь, для которой вероятности перехода Рг] меняются от шага к шагу. Обозначим Р(® —вероятность перехода системы из состояния 5 г в состояние 5, на &-м шаге, то есть условную вероятность
Предположим, что нам заданы матрицы вероятностей перехода на каждом шаге Тогда вероятность тогог что система 5 после & шагов будет находиться в состоянии 5Г, выразится формулой:
которая отличается от аналогичной формулы (2 8) для однородной цепи Маркова только тем, что в ней фигурируют вероятности перехода, за-* висящие от номера шаги и. Вычисления по формуле (2.9) ничуть не сложнее, чем в случае однородной цепи.
Пример 2. Производится три выстрела по цели, которая может быть в тех же четырех состояниях 3^ 5г, 83, 54, что и в предыдущем примере, но вероятности перехода для трех последовательных выстрелов различны и заданы тремя матрицами.
В начальный момент цель находится в состоянии Й1 Найти вероятности со стояний аосле трех выстрелов Решение, Имеем