Марківський випадковий процес з дискретними станами і дискретним часом
Марківський процес, що протікає в деякій системі 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)*Р12+Р2(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)), то матимемо