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