Matematika | Valószínűségszámítás » Márkus László - Véletlen bolyongás

Véletlen bolyongás Márkus László 2015. március 17 Márkus László Véletlen bolyongás 2015. március 17 1 / 31 Modell Deníció Modell: Egy egyenesen (1 dimenziós tér) Lépkedünk el®re vagy hátra (diszkrét lépéseket) Minden lépés független az el®z®t®l P(el®re) = p, P(hátra) = q Véletlen folyamatokra nézve tipikus viselkedés Példa: Mikroszkópikus zikai folyamatok Numerikus közelítés: diszkrét eseményekként kezelve Részecske mozgása - véletlen ütközések, impulzusok Folyadék/légnem¶ anyag: diúzió Márkus László Véletlen bolyongás 2015. március 17 2 / 31 Modell Alesetek Elnyel® falú bolyongás: Egy vagy mindkét irányban deniálunk egy határt Határ elérése/átlépése esetén terminál a folyamat Példa: Szerencsejáték Egyoldali elnyel® falú bolyongás: Játékos pénze 0-ra csökken (tönkrement) Kétoldali elnyel® falú bolyongás: Mindkét játékos pénze véges Márkus László Véletlen

bolyongás 2015. március 17 3 / 31 Modell Alesetek Szimmetrikus bolyongás: Egy számról indulunk (pl.: 0) El®re = +1, Hátra = −1 P(El®re) = P(Hátra) = 21 Lépések: X1 , X2 , . függetlenül egymástól ( Xi = +1 −1 1 2 1 2 0-ból indulva a lépések összege: Sn = Márkus László eséllyel eséllyel n P Xi i=1 Véletlen bolyongás 2015. március 17 4 / 31 Márkus László Modell Alesetek Véletlen bolyongás 2015. március 17 5 / 31 Modell Eloszlás Eloszlás: Nk,i Sk eloszlása: P (Sk = i) = k 2 Nk,i : origóból k lépés alatt az i-be vezet® utak száma Nk,i k páros  k páratlan k i páros 0 k+i 2   k i páratlan 0 k+i 2 Magyarázat: k+i 2 k−i 2 k+i 2 lépés i irányába tetsz®leges sorrendben lépés ellentétes irányba tetsz®leges sorrendben + k−i 2 =i Márkus László Véletlen bolyongás 2015. március 17 6 / 31 Jellemz®k - visszatérések 1 Nullába visszatérés Nullába visszatérés valószín¶sége:

Csak páros lépésben térhet vissza A visszatérés valószín¶sége: u2n = P = (S2n = 0) = A becslés Stirling formulából: n! ∼   2n ∼ n Márkus László 2n 22n ne2n

√ n n n n e e
√ n n e 1 22n 2n n
∼ √1 πn 2πn, innen √ 2π2n 22n √ =√ πn 2πn 2πn Véletlen bolyongás 2015. március 17 7 / 31 Jellemz®k - visszatérések 1 Nullába vissza nem térés Nullába egyszer sem térünk vissza 2n lépésb®l: P (S1 6= 0, S2 6= 0, ., S2n 6= 0) = = 2 · P (S1 > 0, S2 > 0, ., S2n > 0) = n n P P =2· P (S1 > 0, S2 > 0, ., S2n−1 > 0, S2n = 2r) = 2 P (Ar ) r=1 r=1 Ar : 0-ból indulva végig a pozitív oldalon maradva 2r-be jut Valószín¶ség kiszámítása: tükrözési elvvel Br : 0-ból pozitív irányban indulva 2r-be jut Br ∪ Ar = {S1 = 1} ∩ {S2n = 2r} P (S1 = 1, S2n = 2r) = 12 P (S2n−1 = 2r − 1) = Márkus László 1 N2n−1,2r−1 2 22n−1 Véletlen bolyongás 2015. március 17 8 / 31 Jellemz®k

- visszatérések 1 Márkus László Nullába vissza nem térés Véletlen bolyongás 2015. március 17 9 / 31 Jellemz®k - visszatérések 1 P (Br )-hez a jó utak Nullába vissza nem térés száma: Az els®, tengelyt érint® ponttól tükrözzük az utat a tengelyre Kölcsonösen egyértelm¶ megfeleltetés a jó utak és tükrözött utak között: P (Br ) = P (S1 = 1, S2n = −2r) = 21 P (S2n−1 = 2r + 1) = = ⇒ P (Ar ) = 1 N2n−1,2r+1 2 22n−1 N2n−1,2r−1 − N2n−1,2r+1 22n teleszkópos összeg ⇒2· n P 2 22n z n X }| { N2n−1,2r−1 − N2n−1,2r+1 =

2n−1 2n N2n−1,1 n n 1 = 22n−1 (N2n−1,1 − N2n−1,2n+1 ) = 2n−1 = 2n−1 = 2n = u2n 2 2 2 ⇒ P (S2n = 0) = P (S1 6= 0, S2 6= 0, ., S2n 6= 0) P (Ar ) = r=1 Márkus László r=1 Véletlen bolyongás 2015. március 17 10 / 31 Jellemz®k - visszatérések 1 Els® visszatérés Els® visszatérés 0-ba {2n-ikre térünk vissza el®ször} = {2n lépés során valamikor

járunk a 0-ban} {2n-2 lépés során valamikor járunk 0-ban} P({2n során valamikor 0}) = 1 − P ({2n alatt sohasem 0}) = 1 − u2n P2n = P({2n-ikre el®ször 0}) = 1 − u2n − (1 − u2n−2 ) = u2n−2 − u2n = Márkus László 1 n−1 u2n , u0 Véletlen bolyongás =1 2015. március 17 11 / 31 Jellemz®k - visszatérések 1 Valaha visszatérés Valaha visszatérünk: P (∃n : Sn = 0) P(Valaha vissza) = P( = ∞ P f2n = n=1 ∞ P ∞ S n=1 2n-ikre el®ször vissza) = u2n−2 − u2n = u0 = 1 n=1 ⇒ A bolyongás 1 valószín¶séggel visszatér® Márkus László Véletlen bolyongás 2015. március 17 12 / 31 Jellemz®k - visszatérések 2 Generátorfüggvények Generátorfüggvényes módszer a visszatér®ség bizonyítására általánosságban Lépések: X1 , X2 , . független, azonos eloszlású egész érték¶ valószín¶ségi változók S0 = 0, Sn = X1 + . + Xn , azaz Sn a mozgó pont helyzete un = P (Sn = 0), U (z) = ∞ P n=0 un z n

az un sorozat generátorfüggvénye, u0 = 1 fn = P (S1 6= 0, S2 6= 0, ., Sn−1 6= 0, Sn = 0) az n lépés utáni els® visszatérés valószín¶sége F (z) = ∞ P n=1 fn z n az fn sorozat generátorfüggvénye (f1 = P (S1 = 0)) Márkus László Véletlen bolyongás 2015. március 17 13 / 31 Jellemz®k - visszatérések 2 Generátorfüggvények Bizonyítás Ekkor un = P(n lépés után visszatérünk) = n P  P (Sk = 0, Sn = 0, Si 6= 0 : i ∈ {1, . , n − 1} {k} = k=1 . = n P fk un−k k=1 Ebb®l a generátorfüggvényekre: U (z) = 1 + F (z)U (z) ⇒ F (z) = 1 − Így P (∃n : Sn = 0) = Márkus László ∞ P n=1 fn = F (1) = 1 − 1 U (z) 1 U (1) Véletlen bolyongás 2015. március 17 14 / 31 Jellemz®k - visszatérések 2 Állítások Állítás: A bolyongás 1 valószín¶séggel visszatér® ⇔ Bizonyítás: Az el®z®ek szerint F (1) = 1 kell, és ez esetén lehet pontosan. De U (1) = Márkus László ∞ P n=0 1 U (1) ∞ P un

= ∞ n=0 = 0, azaz U (1) = ∞ un és ez adja az állítást. Véletlen bolyongás 2015. március 17 15 / 31 Jellemz®k - visszatérések 2 Állítások Állítás: Az asszimetrikus bolyongás nem visszatér® Bizonyítás: 2n lépésenként lehetséges a visszatérés A lépések:  Xi = +1 −1 p q(= 1 − p) 1 n n Ekkor u2n = 2n n p q (szimmetrikusra p = q = 2 )
2n √1 Stirling: 2n n ∼ πn 2
Így P u2n konvergens vagy divergens √1 (4pq)n konvergens vagy divergens ⇔ πn P n=1 Az x(1 − x) = −x2 + x polinomnak x = 12 -nél maximuma van, ez 1 1 4 , ezért pq ≤ 4 , egyenl®ség csak szimmetrikus esetben állhat. Márkus László Véletlen bolyongás 2015. március 17 16 / 31 Jellemz®k - visszatérések 2 Állítások ⇒ szimmetrikus esetben 4pq = 1, divergens ⇒ aszimetrikus esetben ∞ p 6= q => 4pq < 1 ⇒ P n=0 Márkus László un ∼ ∞ P un ∼ n=0 ∞ P n=1 √1 4pq n πn ∞ P n=1 √1 πn ∞ P < = ∞ sor

4pq n < ∞ n=1 Véletlen bolyongás 2015. március 17 17 / 31 Jellemz®k - visszatérések 2 Többdimenziós bolyongások visszatérhet®sége Többdimenziós bolyongások (szimmetrikus eset): Síkrács/térrács/r-dimenziós rács A bolygó pont egyenl® valószín¶séggel lép egységnyit a 4/6/2r irány valamelyikébe. Origóba visszatérés: minden koordinátatengely irányában ugyanannyi lépést tesz el®re és hátra. Márkus László Véletlen bolyongás 2015. március 17 18 / 31 Jellemz®k - visszatérések 2 Többdimenziós bolyongások visszatérhet®sége Többdimenziós bolyongások (folytatás) (r) u2n = 1 (2r)2n (2n)! 2 (u ! · u 1 2 ! · . · ur !) u1 +.+ur =n " #

2  2n 2 2n 2 dimenzióban: P (2) u2n = n 42n = n 22n ∼ 1 √ πn 2 = 1 πn  r 1  r  r2 1 2 r ≥ 3 dimenzióban már összeg, ∼ r−1 = const · 2 πn n ∞ ∞ 1 P P (2) így 2 dimenzióban: u2n ∼ =∞ n=0 u=1 πn ⇒ r ≥ 3 dimenzióban a

bolyongás nem visszatér®. (r) u2n Márkus László Véletlen bolyongás 2015. március 17 19 / 31 Jellemz®k - visszatérések 2 Többdimenziós bolyongások visszatérhet®sége Tétel: Pólya György A szimmetrikus bolyongás 1 és 2 dimenzióban 1 valószín¶séggel visszatér®, míg 3 vagy több dimenzióban 1-nél kisebb valószín¶séggel tér vissza. Márkus László Véletlen bolyongás 2015. március 17 20 / 31 Jellemz®k - visszatérések 2 Utolsó visszatérés Utolsó visszatérés: 2n lépés (véletlen id®pont) megtétele után mikor jártunk utoljára 0-ban T2n = max{2k : 0 ≤ k ≤ n, S2k = 0} T2n = 0 ha 2n lépés alatt még nem tértünk vissza egyszer sem Legyen α2k,2n = P (T2n = 2k) α2n,2k = P (S2k = 0, S2k+1 6= 0, ., S2n 6= 0) = u2k · u2n−2k (0-ba visszatérés és 0-ba vissza nem térés pontokból következik) Márkus László Véletlen bolyongás 2015. március 17 21 / 31 Jellemz®k - visszatérések 2 Utolsó

visszatérés Utolsó visszatérés (folytatás) n P P (T2n = 2k) = 1 k=0 ⇒ n P P (T2n = 2k) = k=0 ⇒ U (z) = n P u2k · u2n−2k = 1 k=0 ∞ P n=0 U (z) · U (z) = u2n z n : ∞ P n P u2k · u2n−2k · z n = 1 + z + z 2 + . = n=0 k=0 1 1−z 1 ⇒ U (z) = (1 − z)− 2 Márkus László Véletlen bolyongás 2015. március 17 22 / 31 Jellemz®k - egyebek Pozitív oldalon tett lépések Pozitív oldalon tett lépések Szerencsejáték analógia: hányszor vezet a játékos Bolyongó részecske a pozitív oldalon van: Sk > 0 ∨ (Sk = 0 ∧ Sk−1 > 0) Legyen z2n a 2n lépés során a pozitív oldalon tett lépések száma. Legyen π2k,2n = P (z2n = 2k) = P(2n lépésb®l 2k a pozitív oldalon) π2k,2n = k P r=1 + n−k P = r=1 k P r=1 P (felfelé indul, az els® visszatérés 2r-ben, z2n = 2k)+ P (lefelé indul, az els® visszatérés 2r-ben, z2n = 2k) = 1 2 · f2r · π2k−2r,2n−2r + Márkus László n−k P r=1 1 2 · f2r ·

π2k,2n−2r Véletlen bolyongás 2015. március 17 23 / 31 Jellemz®k - egyebek Pozitív oldalon tett lépések Állítás: π2k,2n = u2k · u2n−2k = α2k,2n Bizonyítás: Csak az els® egyenl®séget kell n szerinti indukcióval: Tegyük fel, hogy n − 1-ig igaz, ekkor n-re a fenti rekurzió: π2k,2n = k P 1 2 · u2n−2k · k P r=1 f2r · u2k−2r = u2k , r=1 Márkus László f2r · u2k−2r + n−k P 1 2 · u2k · n−k P f2r · u2n−2k−2r r=1 f2r · u2n−2k−2r = u2n−2k r=1 Véletlen bolyongás 2015. március 17 24 / 31 Jellemz®k - egyebek Arcsin törvény Arcsin törvény: Vizsgáljuk a pozitív oldalon tett lépések arányát: Valószín¶ségi változó, értékkészlete: [0, 1] Kérdés: határeloszlása, n ∞: z2n 2n ≤ b), 0 ≤ a < b < 1 P P π2k,2n = u2k · u2n−2k ∼ < b) = lim P (a < n∞ P (a ≤ z2n 2n z2n 2n k <b a≤ n k <b a≤ n az uP (itt precízebben kellene): 2n -re vonatkozó

aszimptotikából P ∼ √ k a≤ n <b ∼ Rb √ a π 2n ⇒ z2n πk √1 π(n−k) 1 x(1−x)dx = = k a≤ n <b π 1 q 1 k k n 1− ( ) n n ∼ √ b arcsin x a π 2 √ valószín¶ségi változók eloszlása ∼ π2 arcsin( x), (0, 1) tartományban (Konvergencia igaz ∀ a, b-re, így a variációs távolságban is) Márkus László Véletlen bolyongás 2015. március 17 25 / 31 Jellemz®k - egyebek S¶r¶ségfüggvénye (0, 1)-ben: 1 π Arcsin törvény 1 x(1−x) √ Minimum 12 -nél Maximumok: 0, 1 2n -nek is ugyanez a határeloszlása π2k,2n = α2k,2n ⇒ T2n ⇒ Valószín¶, hogy vagy nemrég jártunk 0-ban vagy csak az elején jártunk 0-ban, azóta nem ⇒ Legkevésbé valószín¶, hogy az út felénél jártunk 0-ban Márkus László Véletlen bolyongás 2015. március 17 26 / 31 Márkus László Jellemz®k - egyebek Arcsin törvény Véletlen bolyongás 2015. március 17 27 / 31 Jellemz®k - egyebek Origótól

távolság Origótól vett távolság n lépés után: Mn = max{S0 , S1 , ., Sn } Állítás: P (Mn ≥ r, Sn = k) = P (Sn = 2r − k)(0 ≤ r ≤ k) Bizonyítás: Tükrözési elvvel r szint els® elérését®l tükrözünk Kell: |{r szintet elér® vagy meghaladó, k-ban végz®d® n hosszú utak}| = |{2r-k-ban végz®d® utak}| Köztük a megfeleltetés kölcsönösen egyértelm¶ ⇒ számuk egyenl® Márkus László ⇒ valószín¶ségeik is Véletlen bolyongás 2015. március 17 28 / 31 Márkus László Jellemz®k - egyebek Origótól távolság Véletlen bolyongás 2015. március 17 29 / 31 Jellemz®k - egyebek Origótól távolság Origótól távolság (folytatás) Következmény: Megadhatjuk P(Mn ≥ r)-t P (Mn ≥ r) = P (Mn ≥ r, Sn ≥ r) + P (Mn ≥ r, Sn ≤ r − 1) Els® tag: (Sn ≥ r Mn ≥)r ⇒ P (Mn ≥ r, Sn ≥ r) = P (Sn ≥ r) Második tag: P (Mn ≥ r, Sn ≤ r − 1) = r−1 P P (Mn ≥ r, Sn = k) k=2r−n r szintet eléri a

bolyongás P⇒ r-et lépés felfelé, n-r lefelé ⇒ max 2r-n-ig süllyed ⇒ innen k ⇒ r−1 P P (Mn ≥ r, Sn = k) = k=2r−n n P r−1 P P (Sn = 2r − k) = k=2r−n P (Sn = m) = P (Sn ≥ r + 1) m=r+1 ⇒ P (Mn ≥ r) = P (Sn ≥ r) + P (Sn ≥ r + 1) Márkus László Véletlen bolyongás 2015. március 17 30 / 31 Jellemz®k - egyebek Origótól távolság Origótól távolság (utolsó) Következmény: P (Mn = r) = P (Mn ≥ r) − P (Mn ≥ r + 1) = = P (Sn ≥ r) + P (Sn ≥ r + 1) − P (Sn ≥ r + 1) − P (Sn ≥ r + 2) = = P (Sn = r) + P (Sn = r + 1) Ebb®l a két tagból csak egyik nem 0 Márkus László Véletlen bolyongás 2015. március 17 31 / 31