1_Podstawy_teorii_SJLM.pdf

(351 KB) Pobierz
406575780 UNPDF
1. PODSTAWY TEORII SKOŃCZONYCH ŁAŃCUCHÓW MARKOWA
Przykład 1
Mieszkaniec wioski błądzi po niej zatrzymując się w jednym z trzech punktów: miejsce pracy (P),
knajpa (K), dom (D). Po godzinie pobytu w jednym miejscu czuje potrzebę odmiany. Wychodząc z
pracy rzuca monetą i w zależności od wyniku idzie do domu albo do knajpy. Szanse, że po wizycie
w knajpie uda się natychmiast do domu wynoszą tylko 25%, podobnie jak przejście do pracy, za to
prawdopodobieństwo pozostania w knajpie przez kolejną godzinę jest równe 0,5. W domu jest
żona, która ma pięćdziesięcioprocentowe szanse nakłonić męża do pójścia do pracy, więc tylko w
połowie przypadków udaje mu się zahaczyć o knajpę.
Miejsce bohatera po n krokach (godzinach), n{0,1,2, ...} jest zmienną losową n
X= D oznacza, że w chwili 0 bohater jest w domu.
Uwaga : Definicja zmiennej losowej ... wartości liczbowe. W teorii ŁM konwencja: stany
zamiast liczb (D zamiast 1, K zamiast 2 itd.)
Ciąg zmiennych { n
0
X} jest procesem stochastycznym.
Od czego zależy miejsce pobytu bohatera w chwili n+1 (czyli rozkład prawdopodobieństwa
zmiennej 1
n X )?
- od jego miejsca w chwili n (rozkładu prawdopodobieństwa zmiennej n
X)
- od wyniku rzutu monetą w pracy, obecności kolegów w knajpie oraz żony w domu
(prawdopodobieństw zmiany stanu)
Macierz prawdopodobieństw przejścia w jednym kroku
D K P
D
K
P
0
0
,
5
0
,
5
P = ]
[ ij =
p
0
,
25
0
,
5
0
,
25
0
,
5
0
,
5
0
DP oznacza, że w czasie od chwili n do n +1 szansa
przejścia bohatera z domu do pracy wynosi 50%.
p 
0,
- Np. trzeci wiersz tej macierzy jest warunkowym rozkładem zmiennej losowej 1
n X pod
X n
Załóżmy, że w momencie n bohater jest w domu. Gdzie można go zastać po upływie godziny?
1
warunkiem, że P
(P n
W pracy ( ścieżka DP)?
X
 )D
(P
X
n
,D
X
n
1
)P
(P
X
n
1
P
X
n
)D
(P
X
n
)D
0
,
5
1
0
,
5
W domu (DD), w knajpie (DK)?
0
X
n
,D
X
...
1
)D
, 5
(P n
X
n
,D
X
1
K
)
...
0
,
Jeśli wiemy, że 1
(P n , to prawdopodobieństwa stanu w chwili n +1 (po n +1 krokach):
0
X
 )D
Powyższe prawdopodobieństwa stanowią rozkład zmiennej losowej 1
X
)D
1
(P n
X
1 ,
K
)
, 5
(P n
X
1 ,
)P
n X , zapisywany jako
d
n
1
d[ j
n
,
]
[
0
0
,
5
0
,
5
]
1
X o
wartościach ze skończonego zbioru, zwanego przestrzenią stanów S = {D, K, P}. Zdarzenie
- Np. prawdopodobieństwo 5
(P n
(P n , 5
A jakie jest prawdopodobieństwo, że po 2 godzinach będzie znów w domu (ścieżki DDD lub
DKD lub DPD)?
(P n2
X
)D
(P
X
n
,D
X
n
1
,D
X
n
2
)D
(P
X
n
,D
X
n
1
,K
X
n
2
)D
(P
X
n
,D
X
n
1
,P
X
n
2
)D
(P
X
n n 1
)D
2
D
X
1
,D
X
n
)D
(P
X
n
,D
X
n
(P
X
n n 1
)D
2
D
X
1
,K
X
n
)D
(P
X
n
,K
X
n
(P
X
n
 1
2
D
X
n
1
,P
X
n
)D
(P
X
n
,P
X
n
)D
Zauważmy, że
(P
X
n
2
D
X
n
1
,D
X
n
)D
(P
X
n
2
D
X
n
1
)D
(P
X
n
2
D
X
n
1
,K
X
n
)D
(P
X
n
2
D
X
n
1
K
)
(P
X
n
2
D
X
n
1
,P
X
n
)D
(P
X
n
2
D
X
n
1
)P
brak pamięci o stanie z chwili wcześniejszej niż n +1, zatem
X
)D
(P
X
n n 1
2
D
X
1
)D
(P
X
n
D
X
n
)D
(P
X
n
)D
(P
X
n n 1
2
D
X
1
K
)
(P
X
n
K
X
n
)D
(P
X
n
)D
(P
X
n
 1
2
D
X
n
1
)P
(P
X
n
P
X
n
)D
(P
X
n
)D
Jak więc oblicza się prawdopodobieństwo ścieżki np. DPD?
375
...
0,
(P
X
n
,D
X
n
1
,P
X
n
2
)D
d
nD
p
DP
p
PD
1
0
,
5
0
,
5
0
,
25
A ścieżki DPKPDK, jeśli na pewno zaczął od domu?
pp 
DP
PK
p
KP
p
PD
p
DK
Jeśli wiemy, że 1
(P n , to prawdopodobieństwa stanu po n +2 krokach wynoszą
X
 )D
(P n2 0,375, 5
X
)D
(P n
X
2 ,
K
)
, 125
(P n
X
2 ,
)P
,
więc rozkładem zmiennej losowej 2
n X jest
]
d
Macierz prawdopodobieństw przejścia w dwóch krokach
n
2
d[ j
n
,
]
[
0
,
375
0
,
5
0
,
125
D K P
D
K
P
0
,
375
0
,
5
0
,
125
(2 P = ]
)
p[ )
ij 2 =
(
0
,
25
0
,
5
0
,
25
0
,
125
0
,
5
0
,
375
DP oznacza, że w czasie od chwili n do n +2 szansa
przejścia bohatera z domu do pracy (bez względu na to, gdzie był w chwili n +1) wynosi
12,5%
p )(
0 2 ,
2
(P n2
Np. prawdopodobieństwo 125
406575780.001.png 406575780.002.png
Def .: Skończonym łańcuchem Markowa (SŁM) o przestrzeni stanów S ={1,2,...,r} nazywa się
proces stochastyczny N
X{ , dla którego spełniona jest własność Markowa (własność
n }
n
braku pamięci)
(P
X
n
 1
1
j
|
X
n
,i
X
n
1
i
n
1
,...,
X
0
i
0
)
(P
X
n
j
|
X
n
i
)
p
ij
(
n
)
,
0
Def .: Skończonym jednorodnym łańcuchem Markowa (SJŁM) nazywa się SŁM, dla którego
prawdopodobieństwa przejścia są stałe w czasie
(P
X
n
,i
X
n
 )
1
i
n
1
,...,
X
0
i
0
, dla S
,i n
,j
i
,
i
1
,...,
i
1
(P 
X
n
1
j
|
X
n
i
)
p
ij
Prawdopodobieństwa przejścia w jednym kroku zapisuje się w postaci r-wymiarowej macierzy
przejścia ]
P .
[ ij
p
Macierz przejścia P jest macierzą stochastyczną , tzn.
r
j ij p .
Def .: Rozkładem łańcucha w chwili n (bezwarunkowym) nazywa się wektor
]
0
d
nn 2
d[
1
,
d
n
,
...
,
d
nr
, gdzie )j
Pd n
nj
(
X
SJŁM jest dany macierzą przejścia P i rozkładem początkowym 0
d
Macierz przejścia w m krokach
]
)
p[ )
ij
(
m
przy czym )
p
ij
(
)m
P
(
X
n
j
X
n
;
m
i
Dla SJŁM macierz )
( P jest m -tą potęgą macierzy P , czyli
m
P
Bezwarunkowe prawdopodobieństwa stanu nj d można obliczyć z wzoru na
prawdopodobieństwo całkowite (jak wyżej w przykładowych obliczeniach), co w zapisie
m acierzowym ma postać:
)m( P
dd 1
nn (*)
P
Zatem
P
1
dd
12 P
P
d
0
2
…
dd 0
n P
n
(**)
Wzory (*) i (**) służą więc do obliczenia rozkładu łańcucha (tym samym zmiennej n
X) w
chwili n , gdy znany jest rozkład z poprzedniej chwili lub rozkład początkowy
3
przy czym 0
ij p , 1
1
m( P ,
m
dd 0
406575780.003.png 406575780.004.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin