1
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 o
wartościach ze skończonego zbioru, zwanego przestrzenią stanów S = {D, K, P}. Zdarzenie
0
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
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
P =
]
p
[
ij
=
D
K
P
0
5
0
5
0
25
0
5
0
25
0
5
0
5
0
0
,
,
,
,
,
,
,
- Np. prawdopodobieństwo
5
0,
p
DP
oznacza, że w czasie od chwili n do n+1 szansa
przejścia bohatera z domu do pracy wynosi 50%.
- Np. trzeci wiersz tej macierzy jest warunkowym rozkładem zmiennej losowej
1
n
X
pod
warunkiem, że
P
X
n
Załóżmy, że w momencie n bohater jest w domu. Gdzie można go zastać po upływie godziny?
1
)
D
X
(
P
n
W pracy (ścieżka DP)?
5
0
1
5
0
1
1
,
,
)
D
X
(
P
)
D
X
P
X
(
P
)
P
X
,
D
X
(
P
n
n
n
n
n
W domu (DD), w knajpie (DK)?
0
1
...
)
D
X
,
D
X
(
P
n
n
,
5
0
1
,
...
)
K
X
,
D
X
(
P
n
n
Jeśli wiemy, że
1
)
D
X
(
P
n
, to prawdopodobieństwa stanu w chwili n+1 (po n+1 krokach):
0
1
)
D
X
(
P
n
,
5
0
1
,
)
K
X
(
P
n
,
5
0
1
,
)
P
X
(
P
n
Powyższe prawdopodobieństwa stanowią rozkład zmiennej losowej
1
n
X
, zapisywany jako
]
,
,
[
]
d
[
j
,
n
n
5
0
5
0
0
1
1
d
2
A jakie jest prawdopodobieństwo, że po 2 godzinach będzie znów w domu (ścieżki DDD lub
DKD lub DPD)?
)
D
X
(
P
n 2
)
D
X
,
P
X
,
D
X
(
P
)
D
X
,
K
X
,
D
X
(
P
)
D
X
,
D
X
,
D
X
(
P
n
n
n
n
n
n
n
n
n
2
1
2
1
2
1
)
D
X
,
D
X
(
P
)
D
X
,
D
X
D
X
(
P
n
n
n
n
n
1
1
2
)
D
X
,
K
X
(
P
)
D
X
,
K
X
D
X
(
P
n
n
n
n
n
1
1
2
)
D
X
,
P
X
(
P
)
D
X
,
P
X
D
X
(
P
n
n
n
n
n
1
1
2
Zauważmy, że
)
D
X
D
X
(
P
)
D
X
,
D
X
D
X
(
P
n
n
n
n
n
1
2
1
2
)
K
X
D
X
(
P
)
D
X
,
K
X
D
X
(
P
n
n
n
n
n
1
2
1
2
)
P
X
D
X
(
P
)
D
X
,
P
X
D
X
(
P
n
n
n
n
n
1
2
1
2
brak pamięci o stanie z chwili wcześniejszej niż n+1, zatem
)
D
X
(
P
n 2
)
D
X
(
P
)
D
X
D
X
(
P
)
D
X
D
X
(
P
n
n
n
n
n
1
1
2
)
D
X
(
P
)
D
X
K
X
(
P
)
K
X
D
X
(
P
n
n
n
n
n
1
1
2
)
D
X
(
P
)
D
X
P
X
(
P
)
P
X
D
X
(
P
n
n
n
n
n
1
1
2
375
0,
...
Jak więc oblicza się prawdopodobieństwo ścieżki np. DPD?
25
0
5
0
5
0
1
2
1
,
,
,
p
p
d
)
D
X
,
P
X
,
D
X
(
P
PD
DP
nD
n
n
n
A ścieżki DPKPDK, jeśli na pewno zaczął od domu?
DK
PD
KP
PK
DP
p
p
p
p
p
Jeśli wiemy, że
1
)
D
X
(
P
n
, to prawdopodobieństwa stanu po n+2 krokach wynoszą
)
D
X
(
P
n 2
0,375,
5
0
2
,
)
K
X
(
P
n
,
125
0
2
,
)
P
X
(
P
n
,
więc rozkładem zmiennej losowej
2
n
X
jest
]
,
,
,
[
]
d
[
j
,
n
n
125
0
5
0
375
0
1
2
d
Macierz prawdopodobieństw przejścia w dwóch krokach
D K P
)
(2
P
=
]
p
[
)
(
ij
2
=
D
K
P
375
0
5
0
125
0
25
0
5
0
25
0
125
0
5
0
375
0
,
,
,
,
,
,
,
,
,
Np. prawdopodobieństwo
125
0
2
,
p
)
(
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%
3
Def.: Skończonym łańcuchem Markowa (SŁM) o przestrzeni stanów S ={1,2,...,r} nazywa się
proces stochastyczny
N
n
n
}
X
{
, dla którego spełniona jest własność Markowa (własność
braku pamięci)
)
n
(
p
)
i
X
|
j
X
(
P
)
i
X
,...,
i
X
,
i
X
|
j
X
(
P
ij
n
n
n
n
n
n
1
0
0
1
1
1
,
przy czym
0
0
0
1
1
)
i
X
,...,
i
X
,
i
X
(
P
n
n
n
, dla
S
i
,...,
i
,
i
,
j
,
i
n
1
1
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
ij
n
n
p
)
i
X
|
j
X
(
P
1
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.
0
ij
p
,
1
1
r
j
ij
p
.
Def.: Rozkładem łańcucha w chwili n (bezwarunkowym) nazywa się wektor
]
d
,
...
,
d
,
d
[
d
nr
n
n
n
2
1
, gdzie
)
j
X
(
P
d
n
nj
SJŁM jest dany macierzą przejścia P i rozkładem początkowym
0
d
Macierz przejścia w m krokach
]
p
[
)
m
(
ij
)
m
(
P
,
przy czym
)
i
X
j
X
(
P
p
m
n
n
)
m
(
ij
;
Dla SJŁM macierz
)
m
(
P
jest m-tą potęgą macierzy P, czyli
m
)
m
(
P
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
macierzowym ma postać:
P
d
d
1
n
n
(*)
Zatem
P
d
d
0
1
2
0
1
2
P
d
P
d
d
…
n
n
P
d
d
0
(**)
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