Lancuchy_Markowa.pdf

BartoszNaskr¦cki

Ła«cuchyMarkowa

referatdlaKołaNaukowegoMatematyków,31.05.2006.

1.Czymjestła«cuch?

Processtochastyczny:funkcja,któraprzyporz¡dkowujezbiorowiindeksów

procesu(zazwyczajjesttoczas)warto±ci,którele»¡wprzestrzenizdarze«lo-

sowych.

Ła«cuchemnazywamyprocesstochastyczny,któryjestokre±lonyna dyskret-

nej przestrzenistanów.

2.ProcesyMarkowa

ProcesMarkowa toci¡gzdarze«,wktórymprawdopodobie«stwoka»de-

gozdarzeniazale»yjedynieodwynikupoprzedniego.Wuj¦ciumatematycznym

procesyMarkowatotakieprocesystochastyczne,którespełniaj¡własno±¢Mar-

kowa.

3.Ła«cuchyMarkowa

Ła«cuchyMarkowa totakieprocesyMarkowa,którezdeﬁniowanes¡na

dyskretnejprzestrzenistanów.

Ła«cuchMarkowajestci¡giem X 1 ,X 2 ,X 3 ,... zmiennychlosowych.Dziedzin¦

tychzmiennychnazywamy przestrzeni¡stanów ,arealizacje X n to stany wczasie

n .Je±lirozkładwarunkowy X n +1 jestfunkcj¡wył¡czniezmiennej X n :

P ( X n | X 0 ,X 1 ,...,X n − 1 )= P ( X n | X n − 1 )

4.Reprezentacjamacierzowa

Ła«cuchyMarkowamo»naopisywa¢j¦zykiemalgebryliniowej.

Załó»my,»erozpatrujemyła«cuch,wktórymwyst¦puje n rozró»nialnych

stanów.Ka»dyznichopisywanyjestprzezzmienn¡0 ¬ x i ¬ 1,którawyra»a

prawdopodobie«stwoznalezieniasi¦wstanie i .

Otrzymujemywektorstanu:

x =( x 1 ,...,x n )

Jesttowektorstochastyczny,czylizachodziwarunek:

x 1 + ... + x n =1

Ewolucj¦ła«cuchaopisujezestawliczb,któreopisuj¡prawdopodobie«stwo

przej±ciazestanu i dostanu j :

0 ¬ q ij ¬ 1

Liczbytetworz¡macierz:

q 11 q 12 ... q 1 n

q 21 q 22 ... q 2 n

. . . . . . . . . . . .

q n 1 q n 2 ... q nn

P =

6 6 6 4

7 7 7 5

Macierztajestmacierz¡stochastyczn¡,czyli:

8 1 ¬ i ¬ n q i 1 + ... + q in =1

Wektorstanupocz¡tkowegooznaczamyprzez x (0) .

Stanukładuwchwili n +1wzale»no±ciodstanuwchwili n opisujerównanie:

x ( n +1) = x ( n ) P

Jakonaturalnywniosekotrzymujemy:

x ( n ) = x (0) P n

5.Ła«cuchypochłaniaj¡ce

Deﬁnicja1. Ła«cuchMarkowanazywamypochłaniaj¡cym(AMC),je±liistnie-

jetakistani,zktóregoniemo»nawyj±¢,czyli:

q ii =1 ^8 i 6 = j [ q ij =0]

Stantakinazywamystanempochłaniaj¡cym(ang. absorbingstate ).

Stannieb¦dacystanempochłaniaj¡cymnazywamystanemprzej±ciowym

(ang. transientstate ).

6.Posta¢kanonicznała«cuchapochłaniaj¡cego

P =

0 I

— Q –macierztranzytywna

— 0 –macierzzerowa

— I –macierzidentyczno±ciowa

— R –macierzprzej±ciadostanówpochłaniaj¡cych

7.Podstawowewłasno±ci

Twierdzenie1. Prawdopodobie«stwopochłoni¦ciawła«cuchupochłaniaj¡cym

wynosi1,inaczej:

Q n n !1

−! O m,m

Twierdzenie2. WAMCmacierzI − Qjestodwracalna,ajejodwrotno±ci¡

jestmacierz:

N = I + Q + Q 2 + ... + Q n + ...

ij-tapozycjamacierzyNjestoczekiwan¡warto±ci¡liczby„odwiedze«”stanu

jprzyzało»eniu,»eproceszacz¡łsi¦wstaniei.

Twierdzenie3. Oczekiwanawarto±¢ilo±cikrokówzanimła«cuchzostaniepo-

chłoni¦tywyra»asi¦wzorem:

t = Nc

gdzie:

t 1

. . .

t n

. . .

t =

6 4

7 5 , c =

6 4

7 5 ,

t i opisujeoczekiwan¡ilo±¢krokówprzedpochłoni¦ciem,je±liła«cuchrozpo-

cz¡łsi¦wstaniei.

Twierdzenie4. ij-tyelementmacierzyB = NRopisujeprawdopodobie«stwo,

»ezaczynaj¡cwstanieiła«cuchzostaniepochłoni¦tywstaniepochłaniaj¡cym

8.Ła«cuchyregularneiergodyczne

Deﬁnicja2. Ła«cuchMarkowanazywamyergodycznym,je±lizdowolnegosta-

numo»naprzej±¢dodowolnegoinnego(niekonieczniewjednymkroku).

Deﬁnicja3. Ła«cuchMarkowanazywamyregularnym,je±li:

9 n 2 N [ P n =[ q ( n )

ij ] ^8 i,j 2{ 1 ,...,n } [ q ( n )

ij > 0]]

9.Własno±ciła«cuchówregularnychiergodycznych

Twierdzenie5. Dlamacierzyprzej±ciaPła«cucharegularnegoistniejema-

cierzWstochastyczna,którejkolumnys¡wektoramistałymi,awierszes¡takie

same:

P n n !1

−! W

Ponadtowektorwierszowywmawszystkiewyrazydodatnie.

Twierdzenie6. Istniejedokladniejedenwektorstochastycznywtaki,»eje±li

Pjestmacierz¡regularn¡,to:

w = wP

Ponadtowektor w jestwierszemmacierzy W zpoprzedniegotwierdzenia.

Twierdzeniedziałatak»edlaogólniejszychmacierzy P ła«cuchówergodycz-

nych.

Twierdzenie7. Dladanegowektorastanupocz¡tkowegovimacierzyPła«-

cucharegularnegozachodzi:

n !1 vP n = w

Wektor w jestwektoremwierszowymmacierzy W .

lim

10.Macierzfundamentalna

Dlamacierzyergodycznych(ijednocze±nieregularnych)odpowiednikiem

macierzyfundamentalnej N jestmacierz:

Z =( I − P + W ) − 1

11.Macierz M

M =[ m ij ]

8 i = j [ m ij =0]

8 i 6 = j [ m ij 6 =0]

Liczba m ij oznacza±rednioczekiwanyczas,pojakimzaczynaj¡cwstanie i

znajdziemysi¦porazpierwszywstanie j .

Dlawektorastanustabilnego w mo»emyrozpatrzy¢wektorzło»onyzod-

wrotno±cikolejnychelementówtegowektora:

w =( w 1 ,w 2 ,...,w n )

r =

w 1 , 1

w 2 ,..., 1

w n

Elementywektora r maj¡interpretacj¦±redniegoczasupowrotudostanu i .

Twierdzenie8. ElementymacierzyMwyra»aj¡si¦równo±ci¡:

m ij = z jj − z ij

w j

12.Prawowielkichliczbdlamacierzyergodycznych

NiechH ( n )

j b¦dziestosunkiemilo±ci„odwiedzin”stanujdoilo±cikrokówn.

Wówczas:

8 e> 0

h P | H ( n )

j − w j | >e n !1

−! 0 i

niezale»nieodstanupocz¡tkowegoi.

Literatura

—AmericanMathematicalSociety: Handbookofprobability (rozdz.11)

—Nicolson: LinearAlgebrawithApplications (rozdz. MatrixAlgebra )

—Kostrikin: Wst¦pdoalgebry ,tom2(rozdziałomacierzachnieujemnych)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: