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

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью. Для такого процесса моменты t₁, t₂, когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t, а номер шага 1, 2, k, Случайный процесс в этом случае характеризуется последовательностью состояний S(0), S(1), S(2), S(k), где S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы после первого шага; S(k) - состояние системы после k -го шага...

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

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

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

P₁(0), P₂(0), P_i(0), P_n(0).

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

Вероятностью перехода (переходной вероятностью) на k -м шаге из состояния S_i в состояние S_j называется условная вероятность того, что система S после k -го шага окажется в состоянии S_j при условии, что непосредственно перед этим (после k - 1 шага) она находилась в состоянии S_i.

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

где Р_ij – вероятность перехода за один шаг из состояния S_i в состояние S_j;

Р_ii – вероятность задержки системы в состоянии S_i.

Такая матрица называется переходной или матрицей переходных вероятностей.

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

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

Отметим некоторые ее особенности:

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

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

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

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

Если для однородной Марковской цепи заданы начальное распределение вероятностей и матрица переходных вероятностей , то вероятности состояний системы P_i(k) (i, j = 1, 2, n) определяются по рекуррентной формуле:

, (3.1)

Пример 1. Рассмотрим процесс функционирования системы - автомобиль. Пусть автомобиль (система) в течение одной смены (суток) может находиться в одном из двух состояний: исправном (S₁) и неисправном (S₂). Граф состояний системы представлен на рис. 3.2.

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

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

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

P₁₂ = 0,2 – вероятность перехода автомобиля из состояния «исправен» в состояние «неисправен»;

P₂₁ = 0,9 – вероятность перехода автомобиля из состояния «неисправен» в состояние «исправен»;

P₂₂ = 0,1 – вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан , т.е. Р₁(0) = 0 и Р₂(0) =1.

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

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

P₁(1) = P₁(0)×P₁₁ + P₂(0)×P₂₁ = 0?0,8 + 1?0,9 = 0,9;

P₂(1) = P₁(0)×P₁₂ + P₂(0)×P₂₂ = 0?0,2 + 1?0,1 = 0,2.

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

P₁(2) = P₁(1)×P₁₁ + P₂(1)×P₂₁ = 0,9×0,8 + 0,1×0,9 = 0,81;

P₂(2) = P₁(1)×P₁₂ + P₂(1)×P₂₂ = 0,9×0,2 + 0,1×0,1 = 0,19.

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

P₁(3) = P₁(2)×P₁₁ + P₂(2)×P₂₁ = 0,81×0,8 + 0,19×0,9 = 0,819;

P₂(3) = P₁(2)×P₁₂ + P₂(2)×P₂₂ = 0,81×0,2 + 0,19×0,1 = 0,181.

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

Пример 2. В процессе эксплуатации ЭВМ может рассматриваться как физическая система S, которая в результате проверки может оказаться в одном из следующих состояний: S₁ - ЭВМ полностью исправна; S₂ - ЭВМ имеет неисправности в оперативной памяти, при которых она может решать задачи; S₃ - ЭВМ имеет существенные неисправности и может решать ограниченный класс задач; S₄ - ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (состояние S₁). Проверка ЭВМ производится в фиксированные моменты времени t₁, t₂, t₃. Процесс, протекающий в системе S, может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных вероятностей имеет вид

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

Решение. Граф состояний имеет вид, показанный на рис. 3.3. Против каждой стрелки проставлена соответствующая вероятность перехода. Начальные вероятности состояний P₁(0) = 1, P₂(0) = P₃(0) = P₄(0) = 0.

Рис. 3.3. Граф состояний ЭВМ

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

P₁(1) = P₁(0)×P₁₁ = 1×0,3 = 0,3;

P₂(1) = P₁(0)×P₁₂ = 1×0,4 = 0,4;

P₃(1) = P₁(0)×P₁₃ = 1×0,1 = 0,1;

P₄(1) = P₁(0)×P₁₄ = 1×0,2 = 0,2;

P₁(2) = P₁(1)×P₁₁ = 0,3×0,3 = 0,09;

P₂(2) = P₁(1)×P₁₂ + P₂(1)×P₂₂ = 0,3×0,4 + 0,4×0,2 = 0,20;

P₃(2) = P₁(1)×P₁₃ + P₂(1)×P₂₃ + P₃(1)×P₃₃ = 0,27;

P₄(2) = P₁(1)×P₁₄ + P₂(1)×P₂₄ + P₃(1)×P₃₄ + P₄(1)×P₄₄ = 0,44;

P₁(3) = P₁(2)×P₁₁ = 0,09×0,3 = 0,027;

P₂(3) = P₁(2)×P₁₂ + P₂(2)×P₂₂ = 0,09×0,4 + 0,20×0,2 = 0,076;

P₃(3) = P₁(2)×P₁₃ + P₂(2)×P₂₃ + P₃(2)×P₃₃ = 0,217;

P₄(3) = P₁(2)×P₁₄ + P₂(2)×P₂₄ + P₃(2)×P₃₄ + P₄(2)×P₄₄ = 0,680.

Итак, вероятности состояний ЭВМ после трех проверок следующие: P₁(3) = 0,027; P₂(3) = 0,076; P₃(3) = 0,217; P₄(3) = 0,680.

Задача 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени t₁, t₂, t₃, t₄.

Возможные состояния системы: S₁ – цель невредима; S₂ – цель незначительно повреждена; S₃ – цель получила значительные повреждения; S₄ – цель полностью поражена. В начальный момент времени цель находится в состоянии S₁. Определить вероятности состояний цели после четырех выстрелов если матрица переходных вероятностей имеет вид: