Марківський випадковий процес з дискретними станами і дискретним часом

Марківський процес, що протікає в деякій системі S, (“процес без наслідку”), має наступні властивості: для t₀ імовірність будь-якого стану в майбутньому (t>t₀) залежить тільки від її стану в даний момент часу (t=t₀) і не залежить від того, коли і яким чином система прийшла в цей стан (від передісторії процесу).

Випадковий процес називається процесом з дискретними станами, якщо можливі стани системи можна перелічити S₁, S₂, S₃..., а сам процес полягає в тому, що час від часу S стрибком (миттєво) з початкового стану в інші.

Для такої системи можна зобразити “граф станів”

Якщо переходи системи з S_i у S_j можливі тільки в строго визначені, заздалегідь фіксовані моменти t₁, t₂,..., маємо процес з дискретним часом.

Якщо переходи можливі в будь-який, заздалегідь невідомий, випадковий момент часу, маємо процес з неперервним часом.

Розглянемо марківський випадковий процес з дискретними станами і дискретним часом як функцію цілочисельного аргументу 1, 2,.., k (номер кроку). Позначимо S_i^(k)- після k кроків система в S_i для k події S₁^(k), S₂^(k),.., S_i^(k),.., S_n^(k)- повна група подій. Процес, що відбувається в системі, можна представити як ланцюг подій:

S₁⁽⁰⁾, S₂⁽¹⁾, S₃⁽²⁾, S₄⁽³⁾, S₅⁽⁴⁾,...

такий ланцюг називається Марківським, якщо для будь-якого кроку імовірність переходу з S_i у S_j не залежить від того, коли і як система прийшла в S_i. P_ij^(k)- перехідна імовірність: імовірність того, що на k кроці система перейде з S_i у S_j.

Марківський ланцюг називається однорідним якщо, перехідна імовірність не залежить від номера кроку k. У протилежному випадку- неоднорідний.

Розглянемо однорідний Марківський ланцюг S₁, S₂,.., S_n із заданою матрицею переходу.

P₁₁ P₁₂... P_1j... P_1n

P₂₁ P₂₂... P_2j... P_2n

[P_ij]=...................... (1)

P_i1 P_i2... P_ij... P_in

......................

P_n1 P_n2... P_nj... P_nn

Якщо за 1 крок система не може перейти з S_i у S_j то відповідно P_ij=0, P_ii- імовірність того, що система залишиться в S_i. Очевидно, що P_ij- умовна імовірність

P_ij=P(S_j^(k)/S_i^(k-1)),

для i=1-n

Знайдемо імовірності станів p₁(k), p₂(k),..., p_n(k) після будь-якого k кроку.

Нехай у початковий момент система знаходиться в стані S_m тоді p₁(0)=0, p₂(0)=0, p_n(0)=0. За перший крок система перейде в один зі станів S_1,S_2,S_m,S з імовірностями P_m1, P_m2, P_mm, P_mn отже

P₁(1)=P_m1, P₂(2)=P_m2,..., P_m(1)=P_mm,...,P_n(1)=P_mn (4.2)

Імовірності станів після 2 кроків обчислимо по формулі повної імовірності.

Якщо деяка подія А може відбутися разом з деякими подіями Н₁, H₂,..., H_n, що утворять повну групу неспільних подій (H_i - гіпотези), то

У нашому випадку, гіпотези:

- після 1 кроку система в S₁

- після 2 кроки система в S₂

- після n кроку система в S_n

Їхня імовірність дає (4.2.).

Умова імовірності події (система після 2 кроків в S_i) дає матриця переходу (1.).

, i=1,n

Формально, додаються всі P_ij, фактично нерівні 0. Аналогічно для 3 кроку.

, i=1,n

і для k кроку

, i=1,n

рекурентна формула для k кроку через k-1.

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

Можливі стани цілі:

S₁ - ціль непошкоджена

S₂ - ціль незначно ушкоджена

S₃ - ціль має істотні ушкодження

S₄ - ціль зруйнована

Задано граф станів (мал.)

У початковий момент часу ціль у S₁.

Визначити імовірності станів після 4х пострілів.

	0,3	0,4	0,2	0,1
	0,0	0,4	0,4	0,2
[ Pij ] =	0,0	0,0	0,3	0,7
	0,0	0,0	0,0	1,0

P₁(0)=1

1 крок - 1 рядок, Р₁(1)=0.3, P₁(1)=0.4, P₃(1)=0.2, P₄(1)=0.1

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.4=0.28

P₃(2)=P₁(1)*P₁₃+P₂(1)*P₂₃+P₃(1)P₃₃=0.28

P₄(2)=P₁(1)*P₁₄+P₂(1)*P₂₄+P₃(1)P₃₄+P₄(1)P₄₄=

=0.3*0.1+0.4*0.2+0.2*0.7+0.1*1=0.35

3 крок Р₁(3)=Р₁(2)*Р₁₁=0.09*0.3=0.027

Р₂(3)=Р₁(2)*Р₁₂+Р₂(2)*Р₂₂=0.09*0.4+0.28*0.4=0.14

Р₃(3)=0.214

Р₄(3)=0.611

4 крок Р₁(4)=0.0081 S₁

P₂(4)=0.07 S₂

P₃(4)=0.1288 S₃

P₄(4)=0.7931 S₄

Розглянемо більш загальний випадок - неоднорідного марківського ланцюга, для якого перехідні імовірності міняються від кроку до кроку.

Якщо нам задана матриця переходу для будь-якого кроку [P_ij^(k)], а P_ij^(k)=P(S_j^(k)/S_i^(k)), то матимемо

Дата добавления: 2014-01-04