Марковские цепи с конечным числом состояний и непрерывным временем.

0,3

0,7

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

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S₁, S₂,…, S_n, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t₁, t₂, t₃, …, называемые шагами.

Если система переходит из одного состояния в другое случайно, то говорят, что имеет место случайный процесс с дискретным временем.

Случайный процесс называется марковским, если вероятность перехода из любого состояния S_i в любое состояние S_j не зависит от того, как и когда система S попала в состояние S_i (т.е. в системе S отсутствует последствие). В таком случае говорят, что функционирование системы S описывается дискретной цепью Маркова.

Переходы системы S в различные состояния удобно изображать с помощью графа состояний (рис.1).

Рис. 1

Вершины графа S1, S₂, S₃ обозначают возможные состояния системы. Стрелка, направленная из вершины S _i в вершину S_j обозначает переход Si → Sj; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i-той вершине графа, обозначает, что система остается в состоянии Si с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу nхn, элементами которой являются вероятности переходов p _ij между вершинами графа. Например, граф на рис.1 описывается матрицей P:

"0,7 0,1 0,2" P = 0,4 0 0,6 0,2 0,5 0,3

называемой матрицей вероятностей переходов. Элементы матрицы p _ij удовлетворяют условиям:

0<p_ij <1; (1.1)

n

^Yjpij = 1. (1.2)

Условие (1.1) - обычное свойство вероятностей, а условие (1.2) (сумма элементов любой стрелки равна 1) означает, что система S обязательно либо переходит их какого-то состояния Si в другое состояние, либо остается в состоянии Si.

Элементы матрицы p_ij дают вероятности переходов в системе за один шаг. Переход

Si → Sj за два шага можно рассматривать как происходящий на первом шаге из S _i в некоторое промежуточное состояние S_k и на втором шаге из S_k в Si. Таким образом, для элементов матрицы вероятностей переходов из Si в S_j за два шага получим:

n

pi ⁽ j ²⁾ =∑pikpkj. (13)

k=1

В (m)

общем случае перехода Si → Sj за m шагов для элементов p _{i j} матрицы

вероятностей переходов справедлива формула:

pikpkj , 1 ≤ l ≤ m-1. (1.4)

k=1

Полагая в (1.4) l = 1 и l = m - 1 получим два эквивалентных выражения для p_{i j}^m):

pi ( jm)=∑ pik pk ( mj -1); (1.5)

k=1

n
(m) (m-1)

pij =∑ pⁱ k pkj . (1.6)

k=1

Пример 1.Для графа на рис.1 найти вероятность перехода системы из состояния S1 в состояние S₂ за 3 шага.

Решение.Вероятность перехода S1 → S₂ за 1 шаг равна p ₁₂ = p ₁₂ = 0,1. Найдем

вначале p₁⁽²₂⁾, используя формулу (1.5), в которой полагаем m = 2.

Получим:

p ₁⁽₂ = ∑ p _{1 k}pk2 =р ₁₁ р ₁₂ + р ₁₂ + р ₂₂ + р ₁₂ р ₃2 = 0,7⋅ 0,1 + 0,1 ⋅ 0+0,2 ⋅ 0,5 = 0,17.

k=1

Аналогично pп⁾ = ∑ p 1 k p k ⁽²2⁾ .

k=1

Как видно из этой формулы, в дополнение к p ₁^{(2 )} необходимо вычислить также

p⁽2²₂⁾ = ∑p2kpk2 =p21p12 +p₂₂p22 + p₂₃p32 = 0,4 ⋅0,1+0⋅0 + 0,6 ⋅0,5 = 0,34 .

k=1

p ₃2 = ∑ p _{3 k} pk2 = p ₃₁ p ₁2 + p32p ₂₂ + p ₃₃ p ₃2 =0⋅0,1+0,5⋅0 + 0,3⋅0,5=0,15. k=1

Таким образом

p ₁₁ p ₁₂ ..... p _{1 n}

p ₂₁ p ₂₂ ..... p2n
................................

_p_{n 1} p_n2........... p_nn

Если обозначить через P ^(m) матрицу, элементами которой являются p вероятности переходов из Si в S _j за m шагов, то справедлива формула

где матрица ^{P m} получается умножением матрицы P саму на себя m раз.

O(1)

Исходное состояние системы характеризуется вектором состояния системы Q (называемым также стохастическим вектором).

Q = (q ₁, q2,…,q _n ),

где qj-вероятность того, что исходным состоянием системы является S_j состояние. Аналогично (1.1) и (1.2) справедливы соотношения

n

Хq_i= 1.

i=1

Обозначим через

(m)

вектор состояния системы после m шагов, где q_j - вероятность того, что после m шагов система находится в Si состоянии. Тогда справедлива формула

Q⁽m)=Q-Pm. (1.8)

Пример 2.Найти вектор состояния системы, изображенный на рис.1 после двух шагов.

Решение.Исходное состояние системы характеризуется вектором Q=(0,7; 0; 0,3).

После первого шага (m = 1) система перейдет в состояние Q ⁽¹⁾

"0,7 0,1 0,2

0,4 0 0,6 0,2 0,5 0,3 + 0 •0 + 0,3 •0,5; 0,7 •0,2 + 0 •0,6 + 0,3 •0,3) = (0,55; 0,22; 0,23).

r После второго шага система окажется в состоянии Q⁽²⁾

0,7 0,1 0,2

(1)

0,4 0 0,6 0,2 0,5 0,3

Ответ: Состояние системы S после двух шагов характеризуется вектором (0,519; 0,17; 0,311).

При решении задач в примерах 1, 2 предполагалось, что вероятности переходов P_ij остаются постоянными. Такие марковские цепи называются стационарными. В противном случае марковская цепь называется нестационарной.

Если система S может переходить в другое состояние случайным образом в произвольный момент времени, то говорят о случайном процессе с непрерывным временем. В отсутствии последействия такой процесс называется непрерывной марковской цепью. При этом вероятности переходов S_i → S_j для любых i и j в любой момент времени равны нулю (в силу непрерывности времени). По этой причине вместо вероятности перехода P_ij вводится величина λ_ij - плотность вероятности перехода из состояния S_i в состояние S_j, определяемая как предел

(t+Δ t)-p_ij ( t )

(i ≠ j).

Если величины λ_ij не зависят от t, то марковский процесс называется однородным. Если за время Δt система может изменить свое состояние не более чем один раз, то говорят, что случайный процесс является ординарным. Величину λ_ij называют интенсивностью перехода системы из S_i в S_j. На графе состояний системы численные значения λ_ij ставят рядом со стрелками, показывающими переходы в вершины графа (рис. 2).

Рис. 2

Зная интенсивности переходов можно найти величины p1(t), p₂(t),…, p_n(t) -вероятности нахождения системы S в состояниях S₁, S₂,…, S_n соответственно. При этом выполняется условие

n

j=1 Распределение вероятностей состояний системы, которое можно характеризовать вектором p(t) = (p₁(t),p₂(t),...,p_n(t)), называется стационарным, если оно не

зависит от времени, т.е. все компоненты вектора p являются константами.

Состояния Si и Sj называются сообщающимися, если возможны переходы Si ↔ S_j (на рис. 2 сообщающимися являются состояния S1 и S₂, а S ₁, S₃ и S₂, S₃ такими не являются).

Состояние Si называется существенным, если всякое S_j , достижимое из Si, является сообщающимся с Si. Состояние Si называется несущественным, если оно не является существенным (на рис. 2 существенными являются состояния S1 и S₂).

Если существуют предельные вероятности состояний системы

pj = limpj(t), (j = 1,n) (2 3)

не зависящие от начального состояния системы, то говорят, что при t → ∞ в системе устанавливается стационарный режим.