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

(2.1)

(2.2)

(2.1)

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

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

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

Понятно, что для каждого k:

Начальным распределением вероятностей Марковской цепи называется распределение вероятностей в момент t = 0: P₁ (0), P₂ (0), P_n (0). В частном случае, если S (0) = S_i, то P_i (0) = 1, а остальные равны 0.

Вероятностью перехода из состояния S_i в состояние S_j (переходной вероятностью) называется вероятность того, что система окажется в состоянии S_j ,при условии, что до этого она находилась в состоянии S_i. Поскольку система может пребывать в одном из n состояний, то для каждого момента надо задать n² вероятностей, которые записывают в матрицу переходных вероятностей:

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

Отметим особенности переходной матрицы:

• каждая строка характеризует выбранное состояние системы и её элементы – это вероятности переходов за один шаг из этого состояния в любое другое или в само себя;

• элементы столбцов показывают вероятности переходов из любого состояния в конкретное;

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

• по главной диагонали стоят вероятности того, что система не выйдет, а останется в прежнем состоянии.

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

. (2.1)

Пример.

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

Рис. 2.2. Граф возможных состояний системы S

Пусть матрица переходных вероятностей имеет вид: , где

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

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

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

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

Пусть в начальный момент времени автомобиль был исправен, т. е. P₁ (0) = 1, P₂(0) = 0. Тогда, найдём вероятности состояний системы в момент времени t = 1:

P₁ (1) = P₁ (0) p₁₁ + P₂ (0) p₂₁ = 0,8

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

В момент времени t = 2:

P₁ (2) = P₁ (1) p₁₁ + P₂ (1) p₂₁ = 0,80,8 + 0,20,9 = 0,82

P₂ (2) = P₁(1) p₁₂+ P₂ (1) p₂₂ = 0,80,2 + 0,20,1 = 0,18.

В момент времени t = 3:

P₁ (3) = P₁(2) p₁₁ + P₂(2)p₂₁ = 0,820,8 +0,180,9 = 0,818

P₂ (3) = P₁(2) p₁₁ +P₂(2)p₂₁ =0,182.

Т. е. после трёх суток автомобиль будет находиться в состоянии «исправен» с вероятностью 0,818 , а «неисправен» – с вероятностью 0,182.

Заметим, что формулу (2.1) можно переписать в матричном виде:

P (k) = P (k-1)  P, (2.2)

где P (k) = ( P₁(k), P₂ (k), … ,P_n (k) ) – вектор вероятностей состояний системы в момент k;

P = {p_ij} – матрица переходных вероятностей.

Действительно:

(1,0)  = (0,8;0,2)

(0,8;0,2)  = (0,82;0,18)

(0,82;0,18)  = (0,818;0,182).

В матричном виде вычисления вести удобней.