1
Rekurentn´ı jevy
Znaˇcen´ı 1.1 (posloupnost v´ ysledk˚ u pokusu). Mˇejme posloupnost opakovan´ ych (i z´avisl´ ych) pokus˚ u, kde kaˇzd´ y m´ a tut´eˇz koneˇcnou nebo spoˇcetnou mnoˇzinu v´ ysledk˚ u {E1 , E2 , ...}. Pak {Ej1 , ..., Ejn } znaˇc´ı jev, ˇze i-t´ y pokus skonˇcil Eji pro i ∈ {1, n}. Definice 1.2 (jev v posloupnosti pokus˚ u). Necht’ pro vˇsechny koneˇcn´e posloupnosti v´ ysledk˚ u plat´ı P∞ (a) P (Ej1 , ..., Ejn−1 ) = jn =1 P (Ej1 , ..., Ejn−1 , Ejn ) pro 1 < n < ∞ (b) O kaˇzd´e posloupnosti lze rozhodnout, zda m´a ˇci nem´a vlastnost ξ. Pak ˇrekneme, ˇze ξ nast´ av´ a na n-t´em m´ıstˇe posloupnosti Ej1 , Ej2 , ..., pokud posloupnost {Ej1 , ..., Ejn } m´ a vlastnost ξ. Definice 1.3 (rekurentn´ı jev). Vlastnost ξ je rekurentn´ı jev, pokud ξ nastal na n-t´em a (n + m)t´em m´ıstˇe {Ej1 , ..., Ejn+m }. Pak plat´ı P (Ej1 , ..., Ejn+m ) = P (Ej1 , ..., Ejn ) · P (Ejn+1 , ..., Ejn+m ) Definice 1.4 (v´ yskyt v n-t´em pokusu). Pro rekurentn´ı jev ξ definujeme pro 1 ≤ n < ∞ posloupnosti 1. {un }, kde un = P (ξnastane v n-t´em pokusu) 2. {fn }, kde fn = P (ξnastane v n-t´em pokusu poprv´e) Speci´ alnˇe definujeme u0 := 1, f0 := 0. Pak fn tvoˇr´ı rozdˇelen´ı pravdˇepodobnosti, un ale ne. Pozn´ amka 1.5 (vztah fn a un ). Pokud ξ nastal v kroku n, musel nˇekdy nastat poprv´e. Pokud to bylo v k-t´em kroku, lze uvaˇzovat, ˇze ξ nastal na konci posloupnosti d´elky n − k. Pak plat´ı (dle vˇety o u ´pln´e pravdˇepodobnosti) pro n ≥ 1: un = f1 · un−1 + f2 · un−2 + ... + fn · u0 Coˇz je konvoluce bez prvn´ıho ˇclenu (proto jsme dodefinovali u0 a f0 ). P∞ Pozn´ amka 1.6 (vytvoˇruj´ıc´ı funkce rekurzivn´ ıch jev˚ u). Vytvoˇruj´ıc´ı funce {un } je U (x) = n=0 un · P ∞ xn , vytvoˇruj´ıc´ı funkce {fn } je F (x) = n=0 fn · xn . Pro n > 0 m˚ uˇzeme zapsat rovnice tvaru un = f0 · un + f1 · un−1 + f2 · un−2 + ... + fn · u0 . Ty vyn´ asob´ıme xn , seˇcteme je po sloupc´ıch a dostaneme U (x) = u0 · x0 + U (x) · F (x). Plat´ı tedy n´ asleduj´ıc´ı vˇeta: Vˇ eta 1.7. U (x) − 1 = F (x) · U (x) resp. F (x) =
1 U (x) − 1 resp. U (x) = . U (x) 1 − F (x)
Pozn´ amka 1.8.P{fn } ud´ av´ a rozdˇelen´ı n´ahodn´e veliˇciny T1 , kter´a popisuje ˇcek´an´ı na prvn´ı v´ yskyt ∞ ξ. Pokud f = n=1 fn < 1, potom T1 je nevlastn´ı n´ahodn´a veliˇcina (T1 = ∞) a pravdˇepodobnost, ˇze jev nenastal, je 1 − f . Definice 1.9 (doba n´ avratu). Mˇejme nez´avisl´e n´ahodn´e veliˇciny Ti , 1 ≤ i ≤ r se stejn´ ym rozdˇelen´ım {fn }. Ti interpretujeme avratu, tedy poˇcet pokus˚ u mezi (i − 1)-n´ım a i-t´ ym v´ yskytem. Pr jako dobu n´ Pak T (r) = i=1 Ti je doba ˇcek´ an´ı na r-t´y v´yskyt. (r)
Znaˇcen´ı 1.10 (pravdˇepodobnost r-t´eho n´avratu). Znaˇc´ıme fn = P (ξnastane po r-t´e v n-t´em pokusu). (r) Speci´ alnˇe f0 := 0. Vˇ eta 1.11 (vytvoˇruj´ıc´ı funkce pro r-t´ y n´avrat). Pro rekurentn´ı jevy lze vytvoˇruj´ıc´ı funkci r-t´ych (r) n´ avrat˚ u spoˇc´ıtat jako r-tou mocninu vytvoˇruj´ıc´ı funkce prvn´ıch n´ avrat˚ u, tedy {fn } = {fn }r? . 1
D˚ ukaz. Pro r = 2 podobnˇe jako v pˇredchoz´ı vˇetˇe. Uvaˇzujeme, ˇze fn2 = f0 fn + f1 fn−1 + ... + fn f0 (pokud jev poprv´e nastal v kroku k, lze uvaˇzovat, ˇze nastal poprv´e tak´e na konci posloupnosti d´elky n − k). Coˇz je u ´pln´ a konvoluce pro n ≤ 0. Vznikl´e rovnice vyn´asob´ıme xn a seˇcteme po sloupc´ıch, coˇz d´ a poˇzadovan´ y v´ ysledek. Pro r > 2 plyne indukc´ı. Vˇ eta 1.12. Pravdˇ n r-kr´ at, P∞epodobnost, ˇze rekurzivn´ı jev nastane v nekoneˇcn´e posloupnosti alespoˇ je f r , kde f = n=0 fn . (r)
Pozn´ amka 1.13 (chov´ an´ı fn ). Funkce r-t´ ych n´avrat˚ u se chov´a podobnˇe jako souˇcet nez´avisl´ ych n´ ahodn´ ych veliˇcin - jde vlastnˇe o nez´ avisl´e n´ahodn´e veliˇciny T1 , T2 , ..., kter´e pˇredstavuj´ı doby mezi n´ avraty jevu. Po nast´ an´ı jevu zapom´ın´aP m pˇredchoz´ı pokusy. Proto se doba ˇcek´an´ı na r-t´ y v´ yskyt r ξ d´ a popsat n´ ahodnou veliˇcinou T (r) = i=1 Ti , viz. 1.9.
1.1
Klasifikace rekurentn´ıch jev˚ u
Definice 1.14 (trval´ y a pˇrechodn´ y rekurentn´ı jev). Rekurentn´ı jev ξ je P∞ (a) trval´y, pokud f = n=0 fn = 1, (b) pˇrechodn´y, pokud f < 1. Pozn´ amka 1.15. ξ je trval´ y, pak P (ξ nastane v nekoneˇcn´e posloupnosti pokus˚ u ∞×) = 1. ξ je pˇrechodn´ y, pak
– P (—”—) = 0. P∞ – u = n=0 < +∞ a tak´e f =
u−1 u
(viz vytvoˇruj´ıc´ı funkce F , U ).
Definice 1.16 (Stˇredn´ı doba n´ avratu). Pro trval´ y jev ξ oznaˇc´ıme µ = ET1 = stˇredn´ı dobu n´ avratu ξ.
P∞
n=1
n · fn za
Definice 1.17. Pokud µ < +∞, jev ξ oznaˇcujeme za nenulov´y, pokud µ = +∞, za nulov´y. Definice 1.18. Rekurentn´ı jev ξ je periodick´y, pr´avˇe kdyˇz ∃λ > 1∀n, λ - n : un = 0. Nejvˇetˇs´ı takov´e λ se naz´ yv´ a perioda jevu ξ.
1.2
Pˇ r´ıklady
Definice 1.19 (N´ ahodn´ a proch´ azka po pˇr´ımce). Mˇejme posloupnost nez´avisl´ ych n´ahodn´ ych veliˇcin X1 , X2 , ... ∼ Alt(p). Jednoduch´ a n´ a hodn´ a proch´ a zka s pravdˇ e podobnost´ ı zdaru p je poPn tom posloupnost {Sn }∞ , kde S = X . n n=0 i=1 i Pˇr´ıklad 1.20 (N´ ahodn´ a proch´ azka po pˇr´ımce). Mˇejme jednoduchou n´ahodnou proch´azku po pˇr´ımce av´ a ξ n´ avrat do poˇc´atku, jestliˇze Sn = 0 (tedy poˇcet zdar˚ u a nezdar˚ u je v s p = 21 . V ˇcase n nast´ n-t´em kroku stejn´ y). Uk´ aˇzeme, ˇze ξ je periodick´ y jev trval´ y pro p = 12 a pˇrechodn´ y jinak. ˇ sen´ı. Zˇrejmˇe u2n+1 = 0 (v lich´em kroku se nelze vr´atit) a u2n = 2n pn (1 − p)n ∼ Bi(2n, p) Reˇ n (n× tam, n× zpˇet). ξ je tedy periodick´ y jev. √ Pozn´ amka 1.21. Vyuˇz´ıv´ ame Stirlingovu formuli: n! ≈ nn · e−2n√· 2πn. √ 2n 2n (2n)2n (2n)2n ·e−4n · 4πn 2√ · 2 √ √ √ Pak n2 = (2n)! · 2 πn . n!n! = n!n! = nn ·e−2n · 2πn·nn ·e−2n · 2πn = 2πn TO BE DONE
2
Pˇr´ıklad 1.22 (N´ ahodn´ a symetrick´ a proch´azka po ˇctvercov´e s´ıti). p = 14 . Chceme opˇet zn´at un . Zafixujeme si poˇcet krok˚ u v jednom smˇeru jako i, ostatn´ı z nˇej plynou (pro u2n to ˇcin´ı i krok˚ uv opaˇcn´em smˇeru a n − i v obou zb´ yvaj´ıc´ıch). Potom u2n =
n X i=0
∞ X 1 1 n! ≈ · ⇒ un = ∞ i!i!(n − i)!(n − i)! 42n πn n=1
Jde tedy o periodick´ y trval´ y rekurentn´ı jev. Pˇr´ıklad 1.23 (N´ ahodn´ a symetrick´ a proch´azka ve tˇrech rozmˇerech). Mus´ıme zafixovat dva smˇery, st´ ale multinomick´e rozdˇelen´ı, jiˇz pˇrechodn´ y jev. TODO pˇr´ıklad s hodem minc´ı a v´ypoˇctem un , fn
1.3
Limitn´ı vˇ eta
Vˇ eta 1.24. Necht’ ξ je rekurentn´ı neperiodick´y jev. Potom ( 1 µ<∞ lim un = µ n→∞ 0 µ=∞ Pozn´ amka 1.25. µ znaˇc´ı stˇredn´ı dobu n´avratu ξ, viz 1.16. Pro nulov´y rekurentn´ı jev je ET1 = ∞. Vˇ eta 1.26. Necht’ ξ je rekurentn´ı trval´y periodick´y jev s periodou λ. Potom ( λ µ<∞ lim uλn = µ n→∞ 0 µ=∞
1.4
Asymptotick´ e rozdˇ elen´ı ˇ cetnosti rekurentn´ıch jev˚ u
Vˇ eta 1.27. Necht’ rekurentn´ı jev ξ je trval´y. Oznaˇc´ıme Nn poˇcet v´yskyt˚ u do ˇcasu n a T (r) dobu (r) ˇcek´ an´ı na r-t´y v´yskyt ξ. Potom jevy [Nn ≥ r] a [T ≤ n], 1 ≤ r ≤ n < ∞ jsou ekvivalentn´ı. Pˇredpokl´ adejme d´ ale, ˇze rozdˇelen´ı dob prvn´ıch n´ avrat˚ u m´ a koneˇcnou stˇredn´ı hodnotu ET1 = µ a 2 koneˇcn´y rozptyl varT1 = σ 2 . Potom Nn ∼ N ( nµ , nσ ) a plat´ ı 3 µ (r) T − rµ √ lim P ≤ r = Φ(y), y ∈ R1 r→∞ σ r Pr 1. T (r) = i=1 Ti Pr 2. ET (r) = E( i=1 Ti ) = r · ET1 = rµ var(T (r) ) = var(—”—) = r · varT2 = rσ 2 3. [Nn ≥ r] = [T (r) ≤ n], 1 ≤ r ≤ n < ∞ 4. Pˇripomenut´ı - centr´ aln´ı limitn´ı vˇeta: Mˇejme X1 , X2 , ... nez´avisl´e n´ahodn´e promˇenn´e s rozdˇelen´ım EX1 = µ a rozptylem varX1 = σ 2 < ∞. Pn X −nµ i=1 √ i Pak limn→∞ P < x →x→∞ Φ(x). nσ 2 2
5. Nn ∼ N ( nµ , nσ y ”kouknu a vid´ım”. µ3 ) - pr´ ENn ≈
n µ
(viz dalˇs´ı vˇeta)
Rozptyl nen´ı jasn´ y, mus´ı se uhodnout. √ 6. P (Nn ≥ r) →r→∞ Φ n−rµ rσ 2
A 3
7. P (T (r) ≤ x) = P
Pr
i=1
√
Ti − rµ rσ 2
x − rµ ≤ √ rσ 2
→xto∞ Φ
x − rµ √ rσ 2
Vˇ eta 1.28. Necht’ rekurentn´ı jev ξ je trval´y a nenulov´y. Potom pro n → ∞ plat´ı ENn ≈ µ je stˇredn´ı doba n´ avratu.
1.5
n µ,
kde
Rovnice obnovy
Pozn´ amka 1.29. Limitn´ı vˇety pˇredchoz´ıch odstavc˚ u lze povaˇzovat za speci´aln´ı pˇr´ıpady urˇcit´e obecn´e vˇety, kterou lze formulovat analyticky bez pouˇzit´ı pravdˇepodobnostn´ıch pojm˚ u. Jak uvid´ıme, i tato obecn´ a vˇeta m´ a pravdˇepodobnostn´ı v´ yznam. Definice 1.30 (rovnice obnovy). Necht’ a0 , a1 , ... a b0 , b1 , ... jsou dvˇe posloupnosti takov´e, ˇze P∞ a0 = 0, an ∈ [0, 1], bn ≤ 0, n=0 bn < ∞. Poloˇzme un = bn + a0 un + a1 un−1 + ... + an u0 , tj. {un } = {bn } + {an } ? {un } Tento vztah se naz´ yv´ a rovnic´ı obnovy. Pozn´ amka 1.31. Plat´ı U (x) = B(x) + A(x)U (x) ≡ U (x) =
B(x) 1−A(x) .
Definice 1.32. Posloupnost {an } nazveme periodickou, pokud existuje λ > 1 tak, ˇze ∀n, λ - n : an = 0. Nejvˇetˇs´ı takov´e λ nazveme periodou. Vˇ eta 1.33. Necht’ posloupnost {an } je neperiodick´ a. Potom plat´ı: P∞ P∞ 1. Je-li n=1 an < 1, potom n=1 un < ∞. P∞ 2. Je-li zovat za rozdˇelen´ı doby n´ avratu nˇejak´eho trval´eho n=1 an = 1, tzn. {an } lze povaˇ neperiodick´eho rekurentn´ıho jevu ξ, potom ( P∞ b P∞ n=0 n P∞ n=1 nan < ∞ na n n=1 lim un = P∞ n→∞ 0 n=1 nan = ∞ P∞ 3. Je-li n=1 an > 1, potom pro n → ∞ je un ≈ A(x) = 1.
B(x) xn+1 ·A0 (x) ,
kde x < 1 je jedin´y koˇren rovnice
Vˇ eta 1.34. Necht’ posloupnost {an } je periodick´ a s periodou λ. Potom plat´ı: P∞ P∞ 1. Je-li n=1 an < 1, potom n=1 un < ∞. 2. Je-li µ = ∞, potom limn→∞ un = 0. P∞ avratu nˇejak´eho 3. Je-li µ < ∞, pak n=1 an = 1, tj. {an } lze povaˇzovat za rozdˇelen´ı doby n´ trval´eho periodick´eho rekurentn´ıho jevu ξ. Potom pro 0 ≤ j < λ plat´ı P∞ λ k=0 bkλ+j lim unλ+j = n→∞ µ a
n
1X lim uν = n→∞ n ν=1 TODO v´yklad, pozn´ amky k cel´e sekci
4
P∞
k=0 bk
µ
2
Markovovy ˇ retˇ ezce
Pˇr´ıklad 2.1 (Motivace). M´ ame rubikovu kostku, n´ahodnˇe s n´ı ot´aˇc´ıme. Jak dlouho bude trvat, neˇz se vr´ at´ıme do sestaven´eho stavu? Mohu n´ahodn´e ot´aˇcen´ı stˇenami rubikovy kostky popsat jako n´ ahodnou proch´ azku? Pokud ano, po jak´e struktuˇre? 6 stˇen, lze toˇcit tam a zpˇet ⇒ 12 moˇznost´ı. Celkem koneˇcnˇe mnoho stav˚ u, kaˇzd´ y m´a 12 soused˚ u. P E1 .. . En
E1 0
... ..
En
. 0
pi,j = P (pˇrechod Ei → Ej ) ⇒ na kaˇzd´em ˇr´adku bude 12 × 1/12. Ei jsou vˇsechny stavy RK. Jsou pr˚ uchody stavem E1 rekurentn´ım jevem? ⇒ ano. Zaj´ım´ a n´ as E(Ei → E1 ). Definice 2.2 (Markov˚ uv ˇretˇezec). Posloupnost pokus˚ u, z nichˇz kaˇzd´ y m´a tu samou koneˇcnou nebo ˇ jestliˇze spoˇcetnou mnoˇzinu moˇzn´ ych v´ ysledk˚ u E1 , E2 , ..., nazveme Markovov´ym ˇretˇezcem (MR), pravdˇepodobnost kaˇzd´e koneˇcn´e posloupnosti v´ ysledk˚ u (pokus˚ u nult´eho aˇz n-t´eho) je d´ana vztahem P (Ej0 , ..., Ejn ) = aj0 · pj0 ,j1 · pj1 ,j2 · ... · pjn−1 ,jn kde ak (k ∈ N) jsou pravdˇepodobnosti v´ ysledk˚ u nult´eho pokusu a pj,k (j, k ∈ N) je pro vˇsechny pokusy stejn´ a podm´ınˇen´ a pravdˇepodobnost v´ ysledku Ek za podm´ınky v´ ysledku Ej v pokuse pˇredchoz´ım (P (Ej → Ek ) = P (Ek |Ej )). ˇ budeme popisovat (P, a), kde P = (pi,j ) je ˇctvercov´a matice s (podm´ınˇen´ Znaˇcen´ı 2.3. MR ymi) pravdˇepodobnostmi pˇrechodu (prvn´ıho ˇr´adu) pi,j = P (Ei → Ej ) a a = (ai ) je poˇc´ateˇcn´ı rozdˇelen´ı pravdˇepodobnost´ı. P Pozn´ amka 2.4. Vˇsimnˇete si, ˇze P je stochastick´ a matice, tedy plat´ı ∀i : j pi,j = 1. ˇ Je dobr´e si vˇzdy namalovat graf MR... ( ( +1 ...p → Ei+1 ...p Pˇr´ıklad 2.5 (mal´ a/velk´ a). Ei bude znaˇcit stav moj´ı kapsy. Xi = , Ei = . −1 ...q → Ei−1 ...q
P bude nekoneˇcn´ a matice:
..
. P= 0 Zaˇc´ın´ ame vˇzdy ve stavu E0 , takˇze
.. q
.
..
.
0 q
p 0 .. .
p .. .
0 .. .
a = (..., 0, ..., 0, |{z} 1 , 0, ..., 0, ...) =a0
Pˇr´ıklad 2.6 (n´ ahodn´ a proch´ azka s pohlcuj´ıc´ı bari´erou). Podobnˇe jako v pˇredchoz´ım pˇr´ıpadˇe, s t´ım rozd´ılem, ˇze pˇri dosaˇzen´ı krajn´ıho stavu v nˇem z˚ ustanu.
5
Pˇr´ıklad 2.7 (n´ ahodn´ a proch´ azka s odr´ aˇzej´ıc´ı bari´erou). Podobnˇe jako v pˇredchoz´ım pˇr´ıpadˇe, s t´ım rozd´ılem, ˇze nam´ısto pˇrechodu do krajn´ıho stavu z˚ ust´av´am na m´ıstˇe.
Pˇr´ıklad 2.8 (sbˇeratel kup´ on˚ u). Pˇr´ıklad 2.9 (Ehrenfest˚ uv myˇslen´ y pokus). Pˇr´ıklad 2.10 (volby). Pˇr´ıklad 2.11 (ALOHA protokol).
6
