Markowa.pdf

(135 KB) Pobierz
L.Kowalski
–Łańcuchy Markowa
Łańcuchy Markowa
Łańcuchy Markowa to procesy dyskretne w czasie i o dyskretnym zbiorze stanów,
"bez pamięci".
Zwykle będziemy zakładać,
że
zbiór stanów to podzbiór zbioru liczb całkowitych Z lub
zbioru
{
0, 1, 2, ....
}
jako uproszczenie zapisu
{
S
0
,
S
1
,
S
2
, ....
}
.
Łańcuchem Markowa
nazywamy proces będący ciągiem zmiennych losowych
X
0
, X
1
, ...
Określonych na wspólnej przestrzeni probabilistycznej, przyjmujących wartości całkowite
i spełniające warunek
P
(
X
n
=
j X
0
=
i
0
,
X
1
=
i
1
, ...,
X
n
−
1
=
i
n
−
1
)
=
=
P
(
X
n
=
j X
n
−
1
=
i
n
−
1
)
∧
n
i
0
,...,
i
n
−
1
,
j
⊂
{
0 ,1, 2 ,....
}
∧
Zatem dla łańcucha Markowa rozkład prawdopodobieństwa warunkowego położenia w n-tym
kroku zależy tylko od prawdopodobieństwa warunkowego położenia w kroku poprzednim
a nie od wcześniejszych punktów trajektorii (historia).
Niech
(
p
ijn
)
=
P
(
X
n
=
j X
n
−1
=
i
)
oznacza prawdopodobieństwo warunkowe przejścia w n-tym kroku ze stanu i do stanu j.
(n
Jeśli
p
ij
)
nie zależą od n to łańcuch nazywamy
jednorodnym (jednorodnym w czasie)
i stosujemy zapis
p
ij
.
Zakładając,
że
numery stanów są całkowite, nieujemne można prawdopodobieństwa przejść
zapisać w macierzy
(
n
p
00 )
(
n
=
p
10 )
L
(
n
p
01 )
L
(
n
p
11 )
L
L L
P
(
n
)
W pierwszym wierszu mamy kolejno prawdopodobieństwo pozostania w stanie 0 w n-tym
kroku i prawdopodobieństwa przejścia w n-tym kroku ze stanu o numerze 0 do stanów o
numerach 1, 2, itd. Analogicznie określone są pozostałe wiersze.
1
L.Kowalski
–Łańcuchy Markowa
Dla łańcuchów jednorodnych powyższą macierz oznaczamy
P
i ma ona postać
p
00
P
=
p
10
L
a)
(
p
ijn
)
≥
0
p
01
L
p
11
L
L L
Własności macierzy prawdopodobieństw przejść:
b) suma każdego wiersza jest równa 1.
Zauważmy też,
że
w macierzy tej nie może istnieć kolumna złożona z samych zer.
Każdą macierz spełniającą warunki a), b) nazywamy
macierzą stochastyczną.
Będziemy dalej przyjmować najczęściej,
że
rozpatrywane łańcuchy Markowa mają skończona
liczbę stanów.
p
i
(n) - prawdopodobieństwo znalezienia się w stanie i po n krokach (rozkład zmiennej
losowej X
n
). Prawdopodobieństwa te stanowią składowe wektora p(n), jest to rozkład
łańcucha
Markowa po n krokach
.
p
i
(0) - prawdopodobieństwo znalezienia się w
wektora p(0).
stanie i w chwili początkowej (rozkład
zmiennej losowej X
0
- rozkład początkowy). Prawdopodobieństwa te stanowią składowe
p
ij
- prawdopodobieństwo przejścia od stanu i do stanu j w jednym (dowolnym) kroku,
P = [p
ij
]-
macierz prawdopodobieństw przejść
(w jednym kroku), jest
to macierz
stochastyczna.
Przykład.
Błądzenie przypadkowe z odbiciem. Np. gdy stany 0 i 4 są odbijające
[
0
]
1
→
←
q

[
1
]
p
→
←
q

0
q
P
=
0
0
0
[
2
]
1
0
q
0
0
0
p
0
q
0
p
→
←
q

0
0
p
0
1
[
3
]
p
→
←
1

[
4
]
0
0
0
p
0
2
L.Kowalski
–Łańcuchy Markowa
Przykład.
Błądzenie przypadkowe z pochłanianiem. Np. gdy stany 0 i 4 są pochłaniające
1
[
0
]
←
[
1
]

q
p
→
←
q

1
q
P
=
0
0
0
[
2
]
0
0
q
0
0
0
p
0
q
0
p
→
←
q

0
0
p
0
0
[
3
]
p
→
[
4
]
1
0
0
0
p
1
Problem ruiny gracza
jest szczególnym
przypadkiem błądzenia przypadkowego
z pochłanianiem. Gracz dysponuje początkowo kwotą k zł. W kolejnych etapach z
prawdopodobieństwem p wygrywa 1zł albo z prawdopodobieństwem q = 1- p przegrywa 1zł.
Gra kończy się gdy gracz osiągnie kwotę w > k zł lub przegra wszystko.
Zatem mamy dwa stany pochłaniające 0 i w.
Graf i macierz rozpatrywanego łańcucha są następujące.
1
[
0
]
←
[
1
]

q
p
→
←
q

L
p
→
←
q

[
k
]
0
0
q
0
L
p
→
←
q

L
p
→
←
q

[
w
−1
]
p
→
[
w
]
1
1
q
P
=
0
0
L
0
rozkład pocz
ą
tkowy okre
ś
la X
0
= k
0
0 .... 0
p
0 .... 0
0
p
.... 0
q
0 .... 0
L
L
L
0 0 .... 1
0
Je
ś
li przez r(k) oznaczymy prawdopodobie
ń
stwo ruiny gracza, który rozpocz
ą
ł gr
ę
z kwot
ą
k zł to rozwi
ą
zuj
ą
c równanie rekurencyjne
r
(
k
)
=
qr
(
k
−
1)
+
pr
(
k
+
1)
z warunkami r(0) = 1, r(w) = 0, otrzymujemy,
ż
e prawdopodobie
ń
stwo ruiny gracza wynosi
q
q
 
−
 
p
p
 
 
r
(
k
)
=
w
q
 
−
1
p
 
w
k
gdy
p
≠
q
3
L.Kowalski
–Łańcuchy Markowa
oraz
r
(
k
)
=
1
−
k
w
gdy
p
=
q
=
1
2
Je
ś
li przez z(k) oznaczymy prawdopodobie
ń
stwo zdobycia przez gracza kwoty w, który
rozpocz
ą
ł gr
ę
z kwot
ą
k zł to rozwi
ą
zuj
ą
c równanie rekurencyjne
z
(
k
)
=
pz
(
k
+
1)
+
qr
(
k
−
1)
z warunkami z(0) = 0, z(w) = 1, otrzymujemy
q
 
−
1
p
z
(
k
)
=
 
w
q
 
−
1
p
 
oraz
z
(
k
)
=
k
w
k
gdy
p
≠
q
gdy
p
=
q
=
1
2
Zauwa
ż
my,
ż
e r(k) + z(k) = 1 co oznacza,
ż
e gra musi si
ę
sko
ń
czy
ć
.
Przykład.
Elektron mo
ż
e znajdowa
ć
si
ę
w jednym ze stanów (orbit) 1, 2, ....w zale
ż
no
ś
ci od posiadanej
energii. Przej
ś
cie z i - tej do j - tej orbity w ci
ą
gu 1 sekundy zachodzi
z prawdopodobie
ń
stwem
c
i
e
Wyznacz c
i
, i macierz P.
−
α
j
−
i
,
α
> 0 jest dane.
Przykład.
Narysuj graf ła
ń
cucha Markowa odpowiadaj
ą
cy macierzy prawdopodobie
ń
stw przej
ść
1 / 2 0 1 / 2
P
=
1 / 2 1 / 3 1 / 6
1 / 2 1 / 2 0
Przykład.
Zapisz macierz P dla ła
ń
cuch a Markowa przedstawionego grafem
[
0
]
1
→
1/ 4
←
[
1
]
/4
3
→
[
2
]
1
→
1/ 2
←
[
3
]
1/ 2
→
4/
←
5
[
4
]
1/5
4
L.Kowalski
–Łańcuchy Markowa
P(n) = P
n
= [p
ij
(n)]
- macierz prawdopodobieństw przejść od stanu i do stanu j w n krokach,
Równanie Chapmana, - Kołmogorowa:
p
i j
(
k
+
l
)
=
∑
p
i m
(
k
)
p
m j
(
l
)
m
Własność:
Znając rozkład początkowy i macierz P możemy wyznaczyć rozkład zmiennej losowej X
n
czyli prawdopodobieństwo znalezienia się w poszczególnych stanach po n krokach:
(p
0
(n), p
1
(n), ...) = (p
0
(0), p
1
(0), ...)P
n
.
czyli
Mamy też własność
:
Przykład.
Rozpatrzmy łańcuch Markowa o macierzy
p(n) = p(o)P
n
p(m + n) = p(m)P
n
0
0,5
0,5
P
=
0 0,25 0,75
0,5 0,5
0
i rozkładzie początkowym p(0) = (1, 0, 0).
Po pierwszym kroku prawdopodobieństwa znalezienia się w poszczególnych stanach są
równe
0
0,5
0,5
p
(1)
=
p
(0)
P
=
[1,0,0]
0 0,25 0,75
=
[0,5;0;0,5]
0,5 0,5
0
Po drugim kroku prawdopodobieństwa znalezienia się w poszczególnych stanach są równe
0,25 0,25
0,5
p
(2)
=
p
(0)
P
2
=
[1,0,0]
0,375 0,438 0,188
=
[0,5;0,25;0,25]
0,25 0,125 0,625
Po trzecim kroku prawdopodobieństwa znalezienia się w poszczególnych stanach są równe
0,375 0,188 0,438
p
(3)
=
p
(0)
P
3
=
[1,0,0]
0,281 0,203 0,516
=
[0,375; 0,188; 0,438]
0,438 0,344 0,219
Obliczając kolejne potęgi macierzy P możemy wyliczone wartości p(n) zestawić dla
n = 1, ..., 12 w następującej tabeli i przedstawić na wykresie.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin