2.2. Марковские цепи

Событие {5(?) = 5/}, состоящее в том, что сразу после к-го шага система находится в состоянии 5,(/ = 1, 2, ...), является случайным событием. Последовательность состояний 5(0), 5(1), ..., S(k), ... можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью, если для каждого шага вероятность перехода из любого состояния 5/ в любое Sj не зависит от того, когда и как система пришла в состояние 5/. Начальное-состояние 5(0) может быть заданным заранее или случайным.

Вероятностями состояний цепи Маркова называются вероятности Pj(k) того, что после к-го шага (и до (к + 1)-го) система 5 будет находиться в состоянии 5,(/ =1,2, ..., п). Очевидно, для любого к

ІРі(к) = 1. (2.1)

Начальным распределением вероятностей марковской цепи называется распределение вероятностей состояний в начале процесса:

Л<0), />2(0), /КО), Рп(0). (2.2)

В частном случае, если начальное состояние системы S в точ-ности известно 5(0) = Sh то начальная вероятность РДО) = 1, а все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на к-м шаге из состояния Si в состояние Sj называется условная вероятность того, что система S после к-то шага окажется в состоянии S; при условии, что непосредственно перед этим (после к — 1 шага) она находилась в состоянии Sr

Поскольку система может пребывать в одном из п состояний, то для каждого момента времени t необходимо задать п2 вероятностей перехода Pip которые удобно представить в виде следующей матрицы:

Рп Рц

Рп Р2 2

Р\п Pin

(2.3)

W-

rnl

0,2

где Ру - вероятность перехода за один шаг из состояния Sj в состояние S/,

Ри — вероятность задержки системы в состоянии S;.

Матрица (2.3) называется переходной или матрицей переходных вероятностей.

Если переходные вероятности не зависят от номера шага (от времени), а зависят только от того, из какого состояния в какое осуществляется переход, то соответствующая цепь Маркова называется однородной.

Переходные вероятности однородной марковской цепи Ру образуют квадратную матрицу размера п х п.

Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного (из /-го) состояния, в том числе и переход в самое себя.

Элементы столбцов показывают вероятности всех возможных переходов системы за один шаг в заданное (j-t) состояние (иначе говоря, строка характеризует вероятность перехода системы из состояния, столбец — в состояние).

Сумма вероятностей каждой строки равна единице, так как переходы образуют полную группу несовместных событий:

14 =1, /= In. у=1

4. По главной диагонали матрицы переходных вероятностей стоят вероятности Ри того, что система не выйдет из состояния Sh а останется в нем.

Если для однородной марковской цепи заданы начальное распределение вероятностей (2.2) и матрица переходных вероятностей IJ^Vll (2.3), то вероятности состояний системы Р;(к) (/ = l9n;j =1,л) определяются по рекуррентной формуле:

(2.5)

S Pj(k-\) Pjh (/ = 1,«; у = 1,Л). у=1

Пример 2.1. Рассмотрим процесс функционирования системы автомобиля. Пусть автомобиль (система) в течение одной смены (суток) может находиться в одном из двух состояний: исправном (5j) и неисправном (52)- Граф состояний системы представлен на рис. 2.2.

: 0,2

12

Pi 1=0,8

с&

Р2 2 = 0,1

X5D

P2i = 0,9

Рис. 2.2. Граф состояний автомобиля

В результате проведения массовых наблюдений за работой автомобиля составлена следующая матрица вероятностей перехода:

^11=

(2.6)

0,8 0,2 0,9 0,1

где = 0,8 — вероятность того, что автомобиль останется в исправном состоянии;

Р\2 = 0,2 — вероятность перехода автомобиля из состояния «исправен» в состояние «неисправен»;

/*2і = 0,9 — вероятность перехода автомобиля из состояния «неиспра-вен» в состояние «исправен»;

Р22 — 0,1 — вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан

о"

Л0) =

, т.е.

Требуется определить вероятности состояний автомобиля через трое суток.

Используя матрицу переходных вероятностей, определим вероятности состояний Pj(lc) после первого шага (после первых суток):

Рх(1) = Рх(0)Рхх + Р2(0)Р2\ = 0 • 0,8 + 1 • 0,9 = 0,9;

Р2( 1) = РХ(0)РХ2 + Р2(0)Р22 = 0 • 0,2 + 1 • 0,1 = 0,1.

Вероятности состояний после второго шага (после вторых суток) таковы:

Рх(2) = Р\(1)Рп + РгіХ)Рг\ = 0,9 • 0,8 + 0,1 • 0,9 = 0,81; Р2(2) = РХ(1)РХ2 + Р2(1)Р22 = 0,9 • 0,2 + 0,1 . 0,1 = 0,19.

Вероятности состояний после третьего шага (после третьих суток) равны

Рх(3) = РХ(2)РХХ + Р2(2)Р2Х = 0,81 • 0,8 + 0,19 • 0,9 = 0,819;

Р2(3) = Рх(2)РХ2 + Р2(2)Р22 = 0,81 • 0,2 + 0,19 • 0,1 = 0,181.

Таким образом, после третьих суток автомобиль будет находиться в исправном состоянии с вероятностью 0,819 и в состоянии «неисправен» с вероятностью 0,181.

Пример 2.2. В процессе эксплуатации ЭВМ может рассматриваться как физическая система 5, которая в результате проверки может оказаться в одном из следующих состояний:

Sx - ЭВМ полностью исправна;

- ЭВМ имеет неисправности в оперативной памяти, при которых она может решать задачи;

— ЭВМ имеет существенные неисправности и может решать ограниченный класс задач;

— ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (состояние б*!). Проверка ЭВМ производится в фиксированные моменты времени tx, t2, /3. Процесс, протекающий в системе S, может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных вероятностей имеет вид: 0,3 0,4 0,1 0,2 0 0,2 0,5 0,3 0 0 0,4 0,6 0 0 0 1,0

Определите вероятности состояний ЭВМ после трех проверок. Решение

Граф состояний имеет вид, показанный на рис. 2.3. Против каждой стрелки проставлена соответствующая вероятность перехода. Начальные вероятности состояний /^(О) = 1; Р2(0) = />3(0) = /^(О) = 0.

По формуле (2.5), учитывая в сумме вероятностей только те состояния, из которых возможен непосредственный переход в данное

состояние, находим: ЛО) = Л(°)Лі = 1 • 0,3 = 0,3; ЛО) = Л(0)Л2 = 1 • 0,4 = 0,4; ЛО) = Л(0)Лз = 1 • 0,1 = 0,1; ЛО) = Л(0)Л4 = 1 • 0,2 = 0,2; Л( 2) = Л0)Л] = 0,3 • 0,3 = 0,09; Л( 2) = ЛО)Л2 + ЛО)Л2= = 0,3 • 0,4 + 0,4 • 0,2 = 0,20; Л(2) = Л(1)Лз + ЛО)Лз + ЛО)Лз= 0,27; Л(2) = ЛО)Л4 + ЛО)Л4 + Р3(1)РМ + ЛО)Л4= 0,44; Л(3) = Л(2)Лі = 0,09 • 0,2 1 = 0,027; Л( 3) = Л(2)Л2 + Л(2)Л2= = 0,09 • 0,4 + 0,20 • 0,2 = 0,076; Л(3) = Л(2)Лз + Л(2)Лз + Л(2)Лз= 0,217; Л(3) = Л(2)Л4 + Л(2)Л4 + Л(2)Л4 + Л(2)Л4 = = 0,680.

Итак, вероятности состояний ЭВМ после трех проверок следующие: РХ(Ъ) = 0,027; Р20) = 0,076; Р3(3) = 0,217; РЦЗ) = 0,680.