EMM_09.pdf

Elementy modelowania

matematycznego

ýaıcuchy Markowa:

zagadnienia graniczne.

Ukryte modele Markowa.

Jakub Wrblewski jakubw@pjwstk.edu.pl

http://zajecia.jakubw.pl/

KLASYFIKACJA STANìW

Stan i jest osiĢgalny z j, jeĻli istnieje

niezerowa ĻcieŇka z j do i.

Zbir stanw C jest zamkniħty, jeĻli

Ňaden stan spoza C nie jest

osiĢgalny ze stanu naleŇĢcego do C.

Jednoelementowy zbir zamkniħty

nazywamy stanem pochþaniajĢcym.

ýaıcuch nazywamy nieprzywiedlnym, jeĻli kaŇdy stan i jest

osiĢgalny z dowolnego stanu j.

(ýaıcuchy nieprzywiedlne m.in. nie majĢ stanw pochþaniajĢcych)

KLASYFIKACJA STANìW 2

Stan i jest powracajĢcy, jeĻli wychodzĢc ze stanu i z

prawdopodobieıstwem 1 do niego kiedyĻ wrcimy.

W przeciwnym przypadku stan nazywamy chwilowym.

Stan i jest powracajĢcy, jeĻli (dla p (n) Î elementw macierzy P n ):

(

)

W þaıcuchu nieprzywiedlnym albo wszystkie stany sĢ powracajĢce,

albo wszystkie stany sĢ chwilowe.

ýAİCUCHY OKRESOWE

Czasem moŇemy wrcię do pewnego stanu tylko w szczeglnej

liczbie krokw. Np. w przypadku bþĢdzenia losowego na prostej

caþkowitoliczbowej (prawdop. ď przejĻcia w lewo lub prawo)

wrcimy do punktu wyjĻcia tylko w parzystej liczbie krokw.

Okresem stanu i þaıcucha nazywamy liczbħ:

NWD

{ 0

(

)

JeĻli w þaıcuchu okres kaŇdego stanu jest rwny 1, to þaıcuch

taki nazywamy nieokresowym.

W þaıcuchu nieprzywiedlnym wszystkie stany majĢ ten sam okres.

PRZYKýAD

Projektujemy sieciowĢ grħ przygodowĢ (MUD).

Terenem gry jest mapa zþoŇona z 25 lokacji

poþĢczonych w kwadratowĢ siatkħ. W grze

uczestniczĢ postacie niezaleŇne (NPC, sterowane

przez komputer) oraz postacie graczy, pojawiajĢce

siħ w nieznanym momencie w jednej z lokacji.

Postacie NPC w jednostce czasu mogĢ albo pozostaę

w danej lokacji (prawdop. ď), albo przenieĻę siħ do

jednej z lokacji sĢsiednich z jednakowym

prawdopodobieıstwem.

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

¤ na mapie pojawia siħ jedna postaę

NPC, a po dþuŇszym czasie jeden

gracz. Jakie jest

prawdopodobieıstwo, Ňe siħ od razu

spotkajĢ?

¤ czy to prawdopodobieıstwo

zaleŇy od lokacji?

1/8

1/2

1/4

16 17 18

1/8

1/4

PRZYKýAD Î c.d.

Ruch postaci niezaleŇnych (NPC) opisuje þaıcuch Markowa o 25

stanach (macierz przejĻcia ma rozmiar 25ċ25):

P =

0.5, 0.25, 0, 0, 0, 0.25, 0, 0, 0, 0, 0, ...

0.166, 0.5, 0.166, 0, 0, 0, 0.166, 0, 0, 0, 0,

0, 0.166, 0.5, 0.166, 0, 0, 0, 0.166, 0, 0, 0,

0, 0, 0.166, 0.5, 0.166, 0, 0, 0, 0.166, 0, 0,

0, 0, 0, 0.25, 0.5, 0, 0, 0, 0, 0.25, 0,

0.166, 0, 0, 0, 0, 0.5, 0.166, 0, 0, 0, 0.166,

0, 0.125, 0, 0, 0, 0.125, 0.5, 0.125, 0, 0, 0,

0, 0, 0.125, 0, 0, 0, 0.125, 0.5, 0.125, 0, 0,

0, 0, 0, 0.125, 0, 0, 0, 0.125, 0.5, 0.125, 0,

0, 0, 0, 0, 0.166, 0, 0, 0, 0.166, 0.5, 0,

0, 0, 0, 0, 0, 0.166, 0, 0, 0, 0, 0.5, ...

...

Czy pozycja startowa NPC ma znaczenie dla sytuacji

po dþuŇszym czasie?

TWIERDZENIE ERGODYCZNE

Niech P bħdzie macierzĢ przejĻcia nieprzywiedlnego

þaıcucha Markowa o skoıczonej liczbie stanw n.

JeŇeli þaıcuch ten jest nieokresowy, to istnieje

jednoznacznie wyznaczony rozkþad stacjonarny, czyli taki

wektor ʩ, Ňe:

Ã =

Jest to rozkþad prawdopodobieıstwa znalezienia siħ þaıcucha

w stanie i po odpowiednio dþugim czasie, niezaleŇnie od

stanu poczĢtkowego.

TWIERDZENIE ERGODYCZNE

Î c.d.

Nieprzywiedlny, nieokresowy þaıcuch Markowa z

rozkþadem stacjonarnym ma ponadto nastħpujĢce cechy:

a) wszystkie stany sĢ powracajĢce,

b) rozkþad stacjonarny rwny jest (dla dowolnego stanu j):

lim

( )

(

)

c) wartoĻę 1/p i okreĻla Ļredni czas powrotu þaıcucha do

pozycji i.

PRZYKýAD Î c.d.

W naszym problemie þaıcuch Markowa speþnia

zaþoŇenia twierdzenia ergodycznego:

¤ ýaıcuch jest nieprzywiedlny, gdyŇ istnieje ĻcieŇka

þĢczĢca dowolne dwa stany.

¤ ýaıcuch jest nieokresowy, gdyŇ kaŇdy stan ma okres 1

(bo p ii >0 dla kaŇdego stanu).

Wniosek: prawdopodobieıstwo znalezienia siħ NPC w dowolnym

miejscu po dþuŇszym czasie nie zaleŇy od pozycji startowej NPC.

Istnieje rozkþad stacjonarny i moŇemy policzyę go, rozwiĢzujĢc

odpowiedni ukþad rwnaı liniowych.

PRZYKýAD Î c.d.

Wynik Î prawdopodobieıstwa znalezienia siħ NPC

w poszczeglnych lokacjach po dþugim czasie:

0,06

0,0250

0,0375

0,0250

0,05

0,0375

0,0500

0,0375

0,04

0,03

0,0375

0,0500

0,0375

0,02

0,0375

0,0500

0,0375

0,01

0,0250

0,0375

0,0250

Zgodnie z wnioskami z tw. ergodycznego, startujĢc na Ļrodkowym

polu bħdziemy Ļrednio czekali 20 kolejek na przybycie NPC.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: