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

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

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

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

 

 

 

Якщо переходи системи з Si у Sj можливі тільки в строго визначені, заздалегідь фіксовані моменти t1, t2, ..., маємо процес з дискретним часом.

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

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

S1(0), S2(1), S3(2), S4(3), S5(4), ...

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

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

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

P11 P12 ... P1j ... P1n

P21 P22 ... P2j ... P2n

[Pij]= .... .... ... .... ... .... (1)

Pi1 Pi2 ... Pij ... Pin

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

Pn1 Pn2 ... Pnj ... Pnn

 

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

Pij=P(Sj(k)/Si(k-1)),

для i=1-n

 

Знайдемо імовірності станів p1(k), p2(k), ..., pn(k) після будь-якого k кроку.

Нехай у початковий момент система знаходиться в стані Sm тоді p1(0)=0, p2(0)=0, pn(0)=0. За перший крок система перейде в один зі станів S1,S2,Sm,S з імовірностями Pm1, Pm2, Pmm, Pmn отже

 

P1(1)=Pm1, P2(2)=Pm2, ..., Pm(1)=Pmm, ...,Pn(1)=Pmn (4.2)

 

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

Якщо деяка подія А може відбутися разом з деякими подіями Н1, H2, ..., Hn, що утворять повну групу неспільних подій (Hi - гіпотези), то

 

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

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

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

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

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

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

 

, i=1,n

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

, i=1,n

і для k кроку

, i=1,n

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

 

Приклад 1 По деякій цілі ведеться стрілянина чотирма пострілами в моменти t1, t2, t3, t4.

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

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

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

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

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

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

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

Визначити імовірності станів після 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

P1(0)=1

1 крок - 1 рядок , Р1(1)=0.3, P1(1)=0.4, P3(1)=0.2, P4(1)=0.1

2 крок P1(2)=P1(1)*P11=0.3*0.3=0.09

P2(2)=P1(1)*P12+P2(1)P22=0.3*0.4+0.4*0.4=0.28

P3(2)=P1(1)*P13+P2(1)*P23+P3(1)P33=0.28

P4(2)=P1(1)*P14+P2(1)*P24+P3(1)P34+P4(1)P44=

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

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

Р2(3)=Р1(2)*Р122(2)*Р22=0.09*0.4+0.28*0.4=0.14

Р3(3)=0.214

Р4(3)=0.611

4 крок Р1(4)=0.0081 S1

P2(4)=0.07 S2

P3(4)=0.1288 S3

P4(4)=0.7931 S4

 

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

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