Elementy modelowania
matematycznego
A
ańcuchy Markowa.
Jakub Wróblewski [e-mail]
http://zajecia.jakubw.pl/
A
AC
CUCH MARKOWA
Przykład:
Rozważmy problem częstości występowania w języku
poszczególnych liter. Załóżmy, że interesuje nas nie tyle częstość
(prawdopodobieństwo) bezwzględne, co częstość uzależniona od
poprzedniej litery. Np. po literze  c częściej występuje  h niż  k ,
chociaż litera  k jest w języku polskim powszechniejsza.
Definicja:
A
ańcuchem Markowa nazywamy ciąg zmiennych losowych Xn
o wartościach w pewnym zbiorze S taki, że dla każdego n:
P(X = sn X1 = s1,& , X = sn-1) = P(X = sn X = sn-1)
n n-1 n n-1
czyli wartość zmiennej n zależy tylko od wartości dla n-1.
1
MACIERZ PRZEJÅšCIA
Z definicji łańcucha Markowa wynika, że prawdopodobieństwo
przejścia ze stanu i do j jest zawsze jednakowe. Oznaczmy je pij.
Reprezentacja macierzowa przykładowego łańcucha Markowa:
p11 p12 p13 p14 0 1 0 0
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
p21 p22 p23 p24 ÷Å‚ ìÅ‚0.5 0 0.5 0
ìÅ‚ ÷Å‚
P = =
ìÅ‚
p31 p32 p33 p34 ÷Å‚ ìÅ‚0.3 0 0 0.7÷Å‚
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
ìÅ‚
p41 p42 p43 p44 ÷Å‚ ìÅ‚0.3 0 0.2 0.5÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
Reprezentacja graficzna powyższego przykładu:
1
2
1
0.5
0.5
0.3
0.3
0.5 0.7
3
4
0.2
MACIERZ PRZEJÅšCIA
Macierz przejścia może być użyta do policzenia, z jakimi
prawdopodobieństwami znajdziemy się w poszczególnych stanach
w kolejnym kroku. Np. jeśli w poprzednim przykładzie startujemy z
pozycji 1 lub 3 z jednakowym prawdopodobieństwem, to rozkład
prawdopodobieństwa w kolejnym kroku uzyskamy mnożąc wektor
prawdopodobieństw wyjściowych przez macierz przejścia:
0 1 0 0
ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚
p1 = p0P = (0.5, 0, 0.5, 0)ìÅ‚0.5 0 0.5 0 ÷Å‚ = (0.15, 0.5, 0, 0.35)
ìÅ‚0.3 0 0 0.7÷Å‚
ìÅ‚ ÷Å‚
ìÅ‚0.3 0 0.2 0.5÷Å‚
íÅ‚ Å‚Å‚
Ogólnie, wektor (rozkład) prawdopodobieństw po k krokach
uzyskamy wymnażając wyjściowy rozkład przez Pk.
2
SYMULACJA ZJAWISK
Prawdopodobieństwa przejścia łańcucha Markowa można znalez
ć
doświadczalnie, zliczając przypadki przejść między stanami.
Znaleziony łańcuch może być użyty do symulacji badanego zjawiska.
Przykład: Mamy zbiór N liter polskiego alfabetu. Przez pij oznaczmy
prawdopodobieństwo, że po literze i następuje litera j. Możemy
znalez
ć macierz P=(pij) analizując dostatecznie duży zbiór tekstów.
Macierz P będzie miała różne wartości, w zależności od
analizowanego języka.
Symulacja powstawania słów: startujemy od losowej litery i,
następnie losujemy kolejną zgodnie z rozkładem (pi1, ... piN).
Oznaczmy wylosowanÄ… literÄ™ przez j. Potem losujemy kolejnÄ… z
rozkładem (pj1, ... pjN) itd. Utworzone w ten sposób słowo zwykle nic
nie znaczy, ale brzmi prawdopodobnie.
ROZKA
AD STACJONARNY
Rozkład prawdopodobieństwa Ą na zbiorze stanów łańcucha
Markowa, który nie zmienia się po wykonaniu jednego kroku,
nazywamy rozkładem stacjonarnym:
Ä„ = Ä„P
To, czy taki rozkład istnieje i jest jednoznacznie wyznaczony,
zależy m.in. od rodzaju stanów występujących w danym łańcuchu.
3
KLASYFIKACJA STANÓW
Stan i jest osiągalny z j, jeśli istnieje
niezerowa ścieżka z j do i.
3 1
Zbiór stanów C jest zamknięty, jeśli
żaden stan spoza C nie jest
2
osiągalny ze stanu należącego do C.
Jednoelementowy zbiór zamknięty
nazywamy stanem pochłaniającym.
1
Przykład  zagadnienie ruiny gracza. Gracz ma kapitał początkowy N.
Z prawdopodobieństwem p wygrywa 1, z prawdop. 1-p przegrywa 1.
Jakie jest prawdopodobieństwo, że zbankrutuje (dojdzie do 0)?
4