´ TOVABBI FELADATOK A k¨ ovetkez˝ o feladatok v´eletlen bolyong´asokkal kapcsolatos k´erd´esekr˝ ol sz´olnak. Tekints¨ uk egy szab´alyos p´enzdarab v´egtelen sok egym´ as ut´ ani (f¨ uggetlen) dob´as´at, ´es tekints¨ unk egy r´eszecsk´et, amely az orig´ob´ ol indul el, ´es az eg´esz sz´amok r´acs´ an l´epked a k¨ ovetkez˝ o szab´aly szerint. Tart´ ozkodjon a r´eszecske az n − 1-ik l´ep´es ut´ an n = 1, 2, . . . , valamely j-pontban. Ekkor az n-ik l´ep´esben a r´eszecske a j + 1 pontba l´ep, ha az n-ik p´enzdob´ as eredm´enye fej, (azaz ebben az esetben 1-et l´ep jobbra), ´es a j − 1 pontba l´ep, ha az n-ik dob´as eredm´enye ´ır´as, (azaz ebben az esetben 1-et l´ep balra). A r´eszecske altal egym´ ´ as ut´ an megtett l´ep´esek sorozat´at a r´eszecske bolyong´as´anak nevezz¨ uk. 1.) 2.) 3.) 4.)
Feladatok. Mi annak a val´ osz´ın˝ us´ege, hogy a r´eszecske a bolyong´as 2n-ik l´ep´es´eben visszat´er az orig´oba? Mi annak a val´ osz´ın˝ us´ege, hogy a r´eszecske a bolyong´as 2n-ik l´ep´es´eben t´er vissza el˝ osz¨ or az orig´oba? Mi annak a val´ osz´ın˝ us´ege, hogy a r´eszecske a bolyong´as 2n-ik l´ep´esben visszat´er az orig´oba, ´es az azt megel˝oz˝ o l´ep´esekben csak nem negat´ıv sz´amokat l´atogatott meg? Mi annak a val´ osz´ın˝ us´ege, hogy a r´eszecske a bolyong´as els˝ o n l´ep´es´eben csak nem negat´ıv sz´amokat l´atogatott meg?
Megold´ asok: 1.) A r´eszecske akkor l´ep vissza az orig´oba a bolyong´as 2n-ik l´ep´es´eben, ha az els˝ o 2n l´ep´esben pontosan n-szer l´epett jobbra, ´es n-szer l´epett balra, azaz az o els˝ 2n ¨ ilyen 2n p´enzdob´ asban n darab fej ´es n darab ´ır´as dob´as volt. Osszesen n −2n 2n hosz´ us´ ag´ u dob´assorozat van, ´ e s mindegyiknek a val´ o sz´ ın˝ u s´ e ge 2 . Ez´ert a 2n −2n . keresett val´ osz´ın˝ us´eg n 2 2. Vezess¨ uk be a bolyong´as X(0), X(1), . . . , X(2n) p´aly´ ait, ahol X(j) jel¨oli a r´eszecske tart´ozkod´asi hely´et a j-ik l´ep´es megt´etele ut´ an, (term´eszetesen X(0) = 0), ´es tekints¨ uk a p´alya ´ altal meghat´ arozott (0, X(0), (1, X(1)), . . . , (2n, X(2n)) pontokat osszek¨ot˝ ¨ o t¨or¨ ottvonalat. Sz´ am´ıtsuk ki az olyan p´aly´ ak sz´am´at, amelyekre X(j) < 0 minden 1 ≤ j ≤ 2n − 1 indexre ´es X(2n) = 0. Az ilyen p´aly´ ak a´ltal meghat´ arozott t¨or¨ ottvonalak ´ atmennek az (1, −1), ´es a (2n − 1, −1) pontokon, ´es X(j) < 0, ha 1 ≤ j ≤ 2n − 1. Az olyan pontok sz´ama, amelyekre az a´ltaluk meghat´ arozott . Sz´ a moljuk t¨or¨ ottvonalak ´ atmennek az (1, −1), ´es a (2n − 1, −1) pontokon 2n−2 n−1 ki h´any olyan p´alya van ezek k¨ oz¨ ott, amelyre l´etezik olyan l sz´am, amelyre X(l) ≥ 0. Egy ilyen p´aly´ ara l´etezik olyan j, 1 ≤ j ≤ 2n − 1, index is, amelyre X(j) = 0, ´es jel¨olje j0 a legkisebb ilyen indexet. Az ¨ osszesz´ amoland´o, az (1, −1) ´es (2n − 1, 1) pontokat ¨ osszek¨ot˝ o “rossz” g¨orb´eket meghat´ aroz´o p´aly´ ak sz´am´at meghat´ arozhatjuk a k¨ ovetkez˝ o t¨ ukr¨ oz´esi elv seg´ıts´eg´evel. Minden ilyen p´aly´ anak feleltess¨ uk meg azt az ¯ ¯ ¯ X(j), 1 ≤ j ≤ 2n − 1 p´aly´ at, amelyre X(j) = Xj , ha 1 ≤ j ≤ j0 , ´es X(j) = −X(j), ha j0 < j ≤ 2n − 1. (Az´ert nevezz¨ uk ezt a m´ odszert t¨ ukr¨ oz´esi elvnek, mert geometriailag a k¨ ovetkez˝ ok´epp interpret´alhat´ o. Vegy¨ uk a p´alya a´ltal meghat´ arozott t¨or¨ ottvonalat, hagyjuk el bel˝ ole a (0, 0) ´es a (2n, 0) pontot, illetve az e pontokb´ol kiindul´o szakaszt, ´es n´ezz¨ uk azt a t¨or¨ ottvonalat, amelyet u ´gy kapunk, hogy ennek a t¨or¨ ottvonalnak az abszcissza els˝ o el´er´ese ut´ an lev˝ o r´esz´et t¨ ukr¨ ozz¨ uk az abszcissza 1
¯ lek´epez´es k¨ tengelyre.) Be lehet l´atni, hogy ez az X(·) → X(·) olcs¨on¨ osen egy´ertelm˝ u ¯ megfeleltet´es az ¨ osszesz´ amoland´o X(j), 1 ≤ j ≤ 2n − 1 p´aly´ ak ´es azon X(j), 1≤ ¯ ¯ ¯ j ≤ 2n − 1, p´aly´ ak k¨ ott, amelyekre X(1) = −1, ´es X(2n − 1) = 1. Az X(t) tipus´ u oz¨ 2n−2 ak, ahol 2n − 2 l´ep´esben n − 2-szer p´aly´ ak sz´ama n . (Ezek ugyanis olyan p´aly´ l´ep¨ unk balra, ´es n-szer l´ep¨ unk jobbra.) Ez´ert azon X(j), 0 ≤ j ≤ 2n, p´aly´ ak sz´ama, amelyekre X(j) ≥ 0 valamilyen 1 ≤ j ≤ 2n−1 indexre, ´es X(2n) = 0 2n−2 . Innen n azon X(j), 0 ≤ j ≤ 2n, p´aly´ aksz´ama, amelyekre X(j) < 0 minden 1 ≤ j ≤ 2n − 1 2n−2 2n−2 2n−2 1 2n−2 n−1 = n n−1 . Mivel = n−1 1 − n indexre ´es X(2n) = 0, n−1 − n −2n minden 2n hossz´ us´ ag´ u p´alya val´ osz´ın˝ us´ege 2 , ´es figyelembe kell venni azokat a p´aly´ akat is, amelyekre X(2n) = 0, ´es X(j) > 0 1 ≤ j ≤ 2n − 1 indexre, ez´ert a keresett val´ osz´ın˝ us´eg n222n 2n−2 n−1 . 2n 1 3.) A v´ alasz (n+1)22n n . Ezt a 2. feladat megold´ as´ahoz hasonl´oan bizony´ıthatjuk, de k¨ ozvetlen¨ ul is visszavezethetj¨ uk r´a. A feladat felt´eteleit teljes´ıt˝ o 2n hossz´ us´ ag´ u p´aly´ ak sz´am´at ¨ osszesz´ amolhatjuk u ´gy, hogy minden ilyen p´alya el´e elhelyez¨ unk egy +1 ut´ ana pedig egy −1 l´ep´est. ´Igy a keresett 2n hossz´ us´ ag´ u p´aly´ ak sz´ama megegyezik az olyan 2n + 2 hossz´ u p´aly´ ak sz´am´aval, amelyekre X(2n + 2) = 0, ´es X(j) > 0, ha 1 ≤ j ≤ 2n + 1. 4.) Elegend˝o a feladatot p´aratlan, azaz 2n + 1 alak´ u l´ep´essz´ amok eset´en megoldani. Ugyanis ilyen esetben a bolyong´as ´ert´eke az utols´ o l´ep´esben egy p´aratlan ´ert´ek˝ u sz´am, ´es ha ez nem negat´ıv, akkor a bolyong´as ´ert´eke k¨ ovetkez˝o l´ep´es ut´ an is nem negat´ıv. Jel¨olje pk = pk (2n + 1) annak a val´ osz´ın˝ us´eg´et, hogy a bolyong´as 2n + 1 l´ep´esben a k pontba ker¨ ul, ´es a bolyong´as az els˝ o 2n + 1 l´ep´es valamelyik´eben negat´ıv ´ert´eket is felvesz, Pk = Pk (2n + 1) pedig jel¨olje annak a val´ osz´ın˝ us´eg´et, hogy a bolyong´as a 2n + 1-ik l´ep´esben a k pontba jut. Ekkor a minket ´erdekl˝ o esem´eny ∞ P komplementer´enek a val´ osz´ın˝ us´ege pk , ´es a vizsg´alt esem´eny val´ osz´ın˝ us´ege 1−
∞ P
k=−∞
pk . Ez´ert a feladat megold´ asa ´erdek´eben ´erdemes kisz´ amolni a pk val´ o-
k=−∞
sz´ın˝ us´egeket. Ezt a 2. feladat megold´ as´ahoz hasonl´oan a t¨ ukr¨ oz´esi elv seg´ıts´eg´evel megtehetj¨ uk. Vegy¨ uk ´eszre, hogy Pk = pk = 0, ha k p´aros sz´am, ´es Pk = pk , ha k < 0. Ha k p´aratlan pozit´ıv sz´am, akkor pk = P−k−2 . Ugyanis, ha tekint¨ unk egy olyan bolyong´ast, amelyre az ´ altala meghat´ arozott t¨or¨ ottvonal a 2n + 1-ik l´ep´es ut´ an a k pontba ´er, (k ≥ 1,) ´es valamely kor´ abbi id˝ opontban megl´ atogatja a −1 pontot, ´es t¨ ukr¨ ozz¨ uk e t¨or¨ ottvonalnak a −1 pont els˝ o megl´ atogat´asa ut´ ani r´esz´et az y = −1 egyenesre, akkor k¨ olcs¨on¨ osen egy´ertelm˝ u megfeleltet´est l´etes´ıt¨ unk ezen bolyong´asok ´es az olyan bolyong´asok k¨ oz¨ ott, amelyeknek az ´ert´eke a 2n + 1-ik l´ep´es ut´ an −k − 2. ∞ P P P Ez´ert pk = P−k−2 = Pk+2 , ha k ≥ 1. Innen 1 − pk = 1 − Pk+2 − Pk = k=−∞
1−
P
Pk = P1 . E sz´amol´ asban felhaszn´altuk, hogy
k>0
∞ P
k≤0
Pk = 1, ´es P2k = 0 . minden k-ra. Ez´ert a keresett val´ osz´ın˝ us´eg 2n + 1 param´eterrel 2−2n−1 2n+1 n k6=1
k=−∞
2
Az el˝ oz˝ o feladatokhoz kapcsol´ od´ o tov´ abbi probl´em´ ak. 5.) Adjunk nagy n sz´amokra j´ o aszimptotik´ at az els˝ o ´es m´ asodik feladat megold´ as´aban kapott eredm´eny nagys´agrendj´ere, azaz annak val´ osz´ın˝ us´eg´ere, hogy egy bolyong´as az n-ik l´ep´esben visszat´er az orig´oba, illetve annak val´ osz´ın˝ us´eg´ere, hogy a bolyong´as az n-ik l´ep´esben t´er oda vissza el˝ osz¨ or. √ n nagy Megold´ as: Alkalmazzuk a Stirling formul´ at, amely szerint n! ∼ 2πn ne n-re, azaz a k´et oldalon lev˝ o kifejez´esek h´anyadosa 1-hez tart, ha n → ∞. Ennek √ 2n 2n (2n)! 4πn ( e ) √1 22n . Innen az els˝ = alapj´ an 2n o feladat eredm´enye ∼ 2 n n! 2πn ( n )2n = πn e 2n −2n 2n−2 1 √1 , a m´ √ 1 a sodik feladat eredm´ e nye pedig 2 ∼ 2n n n2 n−1 ∼ 4 πn3/2 . πn
Egy bolyong´as 1 val´ osz´ın˝ us´eggel visszat´er az orig´oba. Ez k¨ ovetkezik p´eld´aul a 4. feladat eredm´eny´eb˝ ol. Az ugyanis, hogy a bolyong´as nem t´er vissza az orig´ oba azt jelenti, hogy az vagy minden n ≥ 1 id˝ opontban pozit´ıv vagy minden n ≥ 1 id˝ opontban negat´ıv ´ert´eket vesz fel. Viszont a 4. feladat eredm´ e nye alapj´ a n mind a k´ e t esem´eny −1/2 −2n−1 2n+1 ∼ const. n → 0, ha n → ∞.) A val´ osz´ın˝ us´ege nulla. (Ugyanis 2 n m´ asodik ´es ¨ ot¨ odik feladat eredm´enye alapj´ an viszont meg lehet mutatni, hogy ez csak sok´ara k¨ ovetkezik be, az els˝ o visszat´er´es idej´enek a v´ arhat´ o ´ert´eke v´egtelen. Ezen k´et all´ıt´ ´ asnak t¨obb bizony´ıt´ asa ismeretes. Most egy olyan megold´ ast t´argyalunk, amely k´et onmag´ ¨ aban is ´erdekes azonoss´ag bizony´ıt´ as´an alapul. 6.) R¨ ogz´ıts¨ unk egy n pozit´ıv eg´esz sz´amot ´es a [0, n] intervallumot. Tekints¨ unk egy olyan bolyong´ast, amely valamely x (eg´esz) sz´amhoz tartoz´o pontb´ ol indul ki, 0 ≤ x ≤ n. Annak a val´ osz´ın˝ us´ege, hogy a bolyong´as a 0 ´es n pontok k¨ oz¨ ul az n pontot x x l´atogatja meg el˝ osz¨ or n , annak, hogy a 0 pontot, 1 − n . 7.) Tekints¨ uk az el˝ oz˝ o feladatban vizsg´alt x pontb´ ol kiindul´o bolyong´ast. A 0 vagy n pont valamelyik´enek az els˝ o megl´ atogat´as´ahoz sz¨ uks´eges l´ep´essz´am v´ arhat´ o ´ert´eke x(n − x). Az 5. ´es 6. feladat megold´ as´aban felhaszn´aljuk azt a t´enyt, hogy 1 annak a val´ osz´ın˝ us´ege, hogy a 0 ´es n pont valamelyik´et megl´ atogatjuk, s˝ ot az is igaz, hogy a k´et pont valamelyik´enek az els˝ o megl´ atogat´as´ahoz sz¨ uks´eges l´ep´essz´ am v´ arhat´ o ´ert´eke v´eges. Azt´ an egy k¨ ul¨ on feladatban ezt is bel´ atjuk. A 6. ´es 7. feladat megold´ asa. 6.) Legyen p(x) annak a val´ osz´ın˝ us´ege, hogy az x pontb´ ol kiindulva az n pontot l´atogatjuk meg el˝ osz¨ or, q(x), hogy a 0 pontot. Ekkor p(x) + q(x) = 1, p(0) = 0, p(n) = 1, ´es p(x) = 21 (p(x − 1) + p(x + 1)) minden 1 ≤ x ≤ n − 1 sz´amra. Legyen p(1) = y. Ekkor alkalmazva rekurzive a p(x) = 12 (p(x − 1) + p(x + 1)) azonoss´agot minden k = 1, 2, . . . sz´amra kapjuk, hogy p(k) = ky, k = 1, . . . , n − 1 V´eg¨ ul alkal1 mazva ezt az azonoss´agot x = n − 1-re kapjuk, hogy (n − 1)y = 2 ((n − 2)y + 1), ahonnan y = n1 , p(x) = nx , q(x) = 1 − nx . 7.) Jel¨olje f (x) a 0 vagy n pont valamelyik´enek az els˝ o megl´ atogat´as´ahoz sz¨ uks´eges l´ep´essz´ am v´ arhat´ o ´ert´ek´et, ha az x pontb´ ol indul a bolyong´as. Ekkor f (x) = 1 (f (x − 1) + f (x + 1)) + 1, ha 1 ≤ x ≤ n − 1, ´es f (n) = 0, f (0) = 0. Vezess¨ uk be a 2 1 g(x) = f (x)−x(n−x). Mivel x(n−x) = 2 [(x−1)(n−(x−1))+(x+1)(n−(x+1))]+1, 3
ez´ert g(x) = 12 [g(x − 1) + g(x + 1)], ha 1 ≤ x ≤ n − 1. Tov´ abb´a g(0) = g(n) = 0, ahonnan g(x) = 0, f (x) = x(n − x) minden 0 ≤ x ≤ n sz´amra.
8.) L´ assuk be a 6. ´es 7. feladat m´eg hi´ anyz´o r´esz´et, azt hogy a tekintett bolyong´asokban a 0 vagy n pont valamelyik´enek az els˝ o megl´ atogat´as´ahoz sz¨ uks´eges l´ep´essz´am v´ arhat´ o ´ert´eke v´eges. Megold´ as: Jel¨olje Ak azt az esem´enyt, amely akkor k¨ ovetkezik be, ha a bolyong´as m-ik l´ep´ese minden kn < m < (k + 1)n sz´amra +1-gyel egyenl˝o. Vezess¨ uk be azt a Z val´ osz´ın˝ us´egi v´ altoz´ ot, amely kn-nel egyenl˝o, ha az Ak esem´eny bek¨ovetkezik, de az Aj esem´eny j < k indexre nem k¨ ovetkezik be. Ekkor a Z val´ osz´ın˝ us´egi v´ altoz´ o ny´ılv´an nagyobb, mint a keresett l´ep´essz´ am. Ez´ert el´eg megmutatni, hogy EZ < ∞. Ez viszont k¨ onnyen ellen˝ orizhet˝o, mert P (Z = kn) = (1 − p)k−1 p, −n p=2 param´eterrel. 9.) Mutassuk meg a 6. ´es 7. feladat eredm´eny´enek a seg´ıts´eg´evel, hogy egy az orig´ob´ ol indul´ o bolyong´as 1 val´ osz´ın˝ us´eggel visszat´er az orig´oba, viszont a visszat´er´eshez sz¨ uks´eges l´ep´essz´ am v´ arhat´ o ´ert´eke v´egtelen. Megold´ as: El´eg megmutatni, hogy a visszat´er´es felt´eteles val´ osz´ın˝ us´ege 1, az els˝ o visszat´er´es idej´enek felt´eteles v´ arhat´ o ´ert´eke pedig v´egtelen ama felt´etel mellett, hogy a bolyong´as els˝ o l´ep´ese +1 volt. Eme felt´etel mellett viszont annak a val´osz´ın˝ us´ege, hogy a bolyong´as a null´ aba hamarabb t´er vissza, mint az n pontba 1 − n1 . Innen n → ∞ hat´ar´ atmenettel kapjuk, hogy az orig´oba val´ o visszat´er´es val´ osz´ın˝ us´ege 1. Hasonl´ oan az orig´oba val´ o els˝ o visszat´er´es idej´enek a v´ arhat´ o ´ert´eke nagyobb, mint annak az id˝ onek a v´ arhat´ o ´ert´eke, ami arra kell, hogy vagy az orig´ot vagy az n pontot el´erj¨ uk. De ez ut´ obbi v´ arhat´ o ´ert´ek n-nel egyenl˝o. Innen n → ∞ hat´ar´ atmenettel kapjuk a v´ arhat´ o ´ert´ekre vonatkoz´ o a´ll´ıt´ ast.
10.) Minden x > 0 sz´amra
1 1 − 3 x x
ϕ(x) < 1 − Φ(x) <
1 ϕ(x), x
ahol Φ(x) ´es ϕ(x) a standard norm´ alis eloszl´ as ´es s˝ ur˝ us´egf¨ uggv´eny. ´ Altal´ anosabban, minden k ≥ 0-ra teljes¨ ul a 2k+1 X l=0
2k
X (−1)l cl (−1)l cl ϕ(x) < 1 − Φ(x) < ϕ(x) , x2l+1 x2l+1
ha x > 0
l=0
egyenl˝otlens´eg alkalmas cl > 0 konstansokkal, ahol c0 = 1, c1 = 1, c2 = 3, ´es a tov´ abbi konstansok is explicit m´ odon megadhat´ oak. Megold´ as: Parci´alis integr´al´ assal kapjuk, hogy minden x > 0 sz´amra Z Z ∞ ∞ √ 2 1 −u2 /2 2π(1 − Φ(x)) = e du = ue−u /2 du u x Z ∞ x Z ∞ 1 −u2 /2 1 −u2 /2 1 −x2 /2 1 −x2 /2 du ue − e − e du = = e x u2 x u3 x x Z ∞ 1 −x2 /2 3 −u2 /2 1 −x2 /2 = e − 3e + e du. x x u4 x 4
Az 1−Φ(x) kifejez´esre a m´ asodik sorban kapott kifejez´esb˝ ol kapjuk, hogy 1−Φ(x) < 1 1 1 ϕ(x) < ϕ(x), a harmadik sorban kapott kifejez´ e sb˝ o l pedig azt, hogy − x x x3 1 − Φ(x). Az ´ altal´ anosabb ´ all´ıt´ as tov´ abbi parci´ alis integr´al´ assal hasonl´o m´ odon bizony´ıthat´ o be. Megjegyz´es: Sok vizsg´alatban el´eg az 1 − Φ(x) f¨ uggv´eny nagys´agrendj´et olyan pon1 −x2 /2 toss´ aggal tudni, hogy 1 − Φ(x) ∼ const. x e nagy x sz´amokra. Ez heurisztikusan R x+h 1 −u2 /2 R ∞ 1 −u2 /2 √ e du ∼ x du, ahol a h a k¨ ovetkez˝ ok´epp l´athat´ o. 1 − Φ(x) = x √2π e 2π konstanst u ´gy ´erdemes v´ alasztani, hogy az integrandus a konstansszoros´ ara cs¨okkenjen. 1 1 2 2 Ez azt sugallja, hogy v´ alasszuk h-t h = -nek, mert (x+ x ) = x +2+o(1), ´es 1−Φ(x) = R x+h 1 −u2 /2 x R ∞ 1 −u2 /2 2 −x2 /2 √ e √ e . Hasonl´ o megdu ∼ x du ∼ const. he−x /2 = const. x e x 2π 2π gondol´ as alapj´ an azt v´ arjuk, hogy ha u(x) sima, (differenci´ alhat´ o) monoton f¨ uggv´eny, R ∞ −u(t) 1 amely gyorsan tart v´egtelenhez a v´egtelenben, akkor x e dt ∼ const. u′ (x) e−u(x) nagy x sz´amokra. 11. Legyenek ξ1 , ξ2 , . . . , f¨ uggetlen, standard norm´ alis eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ ok. Mutassuk meg, hogy minden x val´ os sz´amra lim P
n→∞
p −x/2 . max ξk < 2 log n − log log n − log 4π + x = e−e
1≤k≤n
√ Megold´ a s: Vezess¨ uk be az xn = 2 log n − log log n − log 4π + x jel¨ol´est, ´es ´ırjuk n fel a P max ξk < xn = Φ(xn )n = (1 − (1 − Φ(xn )) azonoss´agot. Az ezen 1≤k≤n
azonoss´ag jobboldal´ an ´ all´ o kifejez´est j´ ol tudjuk becs¨ ulni az 1 − Φ(x) kifejez´esre az el˝ oz˝ o feladatban adott o ´es fels˝o korl´ at seg´ıts´ eg´evel. Val´ oban, fel´ırhatjuk, hogy als´ n √ n 2 π log n 2 1 P max ξk < xn ≤ 1 − √2πx abb´a, = 1 − √2πx n1 e−x/2 . Tov´ e−xn /2 n n 1≤k≤n √ 2 π log n mivel lim √2πx = 1, innen azt kapjuk, hogy n→∞
n
lim sup P n→∞
max ξk < xn
1≤k≤n
1 ≤ lim sup 1 − e−x/2 n n→∞
n
= e−e
−x/2
Hasonl´ oan, a P
max ξk < xn
1≤k≤n
n 1 1 1 −x2n /2 − 3 e ≥ 1− √ xn 2π xn √ n 1 −x/2 1 2 π log n 1 e − 3 = 1− √ xn xn n 2π
egyenl˝otlens´egb˝ol kapjuk, hogy lim inf P n→∞
5
max ξk < xn
1≤k≤n
≥ e−e
−x/2
.
.
Megjegyz´es: N´emi sz´amol´ as mutatja, hogy a 11. feladat eredm´enye ekvivalens a k¨ ovetkez˝ o ´ all´ıt´ assal: Ha ξ1 , ξ2 , . . . , f¨ uggetlen, standard norm´ alis eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ ok, akkor minden x val´ os sz´amra lim P
n→∞
p x log log n − log 4π √ <√ max ξk − 2 log n − 1≤k≤n 2 2 log n 2 log n
= e−e
−x
.
A 11. feladat eredm´enye alapj´ an f¨ uggetlen, standard norm´ alis eloszl´ as´ u ξ1 , . . . , ξn √ val´ osz´ın˝ us´egi v´ altoz´ ok max ξk maximuma majdnem 1 val´ osz´ın˝ us´eggel a 2 log n sz´am 1≤k≤n
k¨ ozel´eben koncentr´ a√ l´ odik. Nem neh´ez bel´ atni a fenti sz´amol´ asokhoz hasonl´o m´ odon, abb t´argyaland´o val´ ohogy E max ξk ≤ 2 log n. A 2008. ´evi Schweitzer verseny al´ 1≤k≤n
sz´ın˝ us´egsz´am´ıt´ asi feladata azt ´ all´ıtja, hogy ez a becsl´es nem csak f¨ uggetlen norm´ alis val´ osz´ın˝ us´egi v´ altoz´ okra ´erv´enyes.
12. Legyenek ξ1 , . . . , ξn (nem felt´etlen¨ ul f¨ uggetlen) nulla v´ arhat´ o ´ert´ek˝ u norm´ alis elosz2 l´as´ u val´ osz´ın˝ us´egi v´ altoz´ ok, amelyekre Eξk ≤ 1, 1 ≤ k ≤ n. Ekkor E max ξk ≤ 1≤k≤n
p
2 log n.
Megold´ as. Legyen Z = E max ξk . Ekkor a Jensen egyenl˝otlens´eg alapj´ an tetsz˝ole1≤k≤n
ges t ≥ 0 sz´amra eEtZ ≤ EetZ , azaz EZ ≤ 2
net
/2
, innen E max ξk ≤ 1≤k≤n
´es t =
√
1 t
log EetZ . Mivel EetZ ≤ E
n P
k=1
Eetξk ≤
2 log n t 1 log net /2 = + , t t 2
2 log n v´ alaszt´ assal ad´ odik a feladat ´ all´ıt´ asa.
A centr´ alis hat´areloszl´ast´etel szerint sok f¨ uggetlen val´ osz´ın˝ us´egi v´ altoz´ o o¨sszege nagyon ´ altal´ anos felt´etelek mellett k¨ ozel norm´ alis eloszl´ as´ u. Az al´ abb t´argyaland´o Cramer–L´evy t´etel szerint viszont egy ilyen ¨ osszeg csak akkor lehet pontosan norm´ alis eloszl´ as´ u, ha az ¨ osszes ¨ osszeadand´ o norm´ alis eloszl´ as´ u. Cramer–L´ evy t´ etel. Legyen ξ ´es η k´et f¨ uggetlen val´ osz´ın˝ us´egi v´ altoz´ o, amelyekre ξ +η norm´ alis eloszl´ as´ u. Ekkor ξ ´es η is norm´ alis eloszl´ as´ u. Ennek az eredm´enynek rendk´ıv¨ ul ´erdekes t¨ort´enete van. Ezt az a´ll´ıt´ ast Paul L´evy, aki h´ıres volt rendk´ıv¨ uli intuici´ oj´ar´ ol, fogalmazta meg sejt´es form´aj´aban, ´es e sejt´es n´eh´ any k¨ ovetkezm´eny´et is megadta. Harald Cramer bizony´ıtotta be L´evy sejt´es´et. Bizony´ıt´ as´aban fontos szerepet j´ atszottak bizonyos komplex f¨ uggv´enytani gondolatok. L´evy ezzel a bizony´ıt´ assal el´egedetlen volt, mert ˝ o m´ as meggondol´asok alapj´ an l´atta, hogy sejt´ese igaz. Az, hogy mi volt L´evy heurisztik´ aj´anak az alapja val´ osz´ın˝ uleg o¨r¨ ok rejt´ely marad. Cramer bizony´ıt´ as´anak gondolata a k¨ ovetkez˝ o volt. Jel¨olje ϕ(t) = Eeitξ ´es ψ(t) = Eeitη , −∞ < t < ∞, ξ ´es η karakterisztikus f¨ uggv´eny´et. Feltehetj¨ uk, hogy ξ+η standard 6
2
norm´ alis eloszl´ as´ u. Ekkor ϕ(t)ψ(t) = e−t /2 . Azt kell bel´ atni, hogy ez az azonoss´ag csak u ´gy teljes¨ ulhet, ha ϕ(·) ´es ψ(·) norm´ alis eloszl´ asok karakterisztikus f¨ uggv´enyei. A f˝ o probl´em´at az okozza, hogy rendk´ıv¨ ul neh´ez kihaszn´alni a bizony´ıt´ asban azt a t´enyt, hogy ϕ(t) ´es ψ(t) karakterisztikus f¨ uggv´enyek, azaz nagyon speci´alis tulajdons´ag´ u f¨ uggv´enyek. Cramer a k¨ ovetkez˝ o m´ odon gy˝ozte le ezt a neh´ezs´eget. Bel´ atta, hogy nemcsak a ξ+η hanem a ξ ´es η val´ osz´ın˝ us´egi v´ altoz´ ok abszolut ´ert´ekei is rendk´ıv¨ ul kis val´ osz´ın˝ us´eggel vesznek fel nagy ´ert´ekeket. Innen k¨ ovetkezik, hogy hogy mind a ϕ(·) mind a ψ(·) f¨ uggv´eny kiterjeszthet˝o egy az eg´esz komplex sz´ams´ıkon holomorf f¨ uggv´enny´e, ´es a 2 ϕ(z)ψ(z) = e−z /2 azonoss´ag minden komplex sz´amra ´erv´enyes. Ez´ert a ϕ(z) f¨ uggv´eny sehol sem nulla, ´es defini´alhatjuk a log ϕ(z) holomorf f¨ uggv´enyt. Innen ´es a ϕ(z) f¨ uggv´eny nagys´ag´ ara kapott becsl´esekb˝ol, illetve a Liouville t´etel egy nem-trivi´ alis v´ altoAz 2 +Bz+C zat´ab´ ol k¨ ovetkezik, hogy ϕ(z) = e alak´ u. Ezen eredm´eny seg´ıts´eg´evel k¨ onnyen l´athat´ o, hogy ϕ(t) egy norm´ alis eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ o karakterisztikus f¨ uggv´enye. Ugyanez elmondhat´ o a ψ(t) f¨ uggv´enyr˝ol is. 13.) Bizony´ıtsuk be a Cramer–L´evy t´etelt. Megold´ as. L´ assuk el˝ osz¨ or be, hogy l´etezik olyan B > 0 ´es C > 0 sz´am, amelyre −Cx2 P (|ξ| > x) ≤ Be minden x > 0 sz´amra. L´etezik olyan A > 0 sz´am, amelyre 1 P (|η| < A) ≥ 2 . Ekkor az x > A sz´amokra P (|ξ| > x) ≤ 2P (|ξ| > x, |η| < A) ≤ 2 2 2P (|ξ + η| > x − A) ≤ 4e−(x−A) /2 . Innen k¨ ovetkezik, hogy P (|ξ| > x) ≤ Be−Cx minden x > A sz´amra alkalmas B > 0 ´es C > 0 sz´amokkal. A B sz´am esetleges n¨ovel´es´evel el´erhetj¨ uk, hogy ez az egyenl˝otlens´eg mindenR x > 0 sz´amra ´erv´enyes ∞ legyen. Fel´ırhatjuk, hogy |Eezξ | ≤ EeRe zξ ≤ Ee|Re z||ξ| = 0 e|Re z|x F ( dx) minden komplex z sz´amra, ahol F (x) = P (|ξ| < x) a |ξ| val´ osz´ın˝ us´egi v´ altoz´ o eloszl´ asf¨ uggv´enye. Innen a most bizony´ıtott egyenl˝otlens´eg alapj´ an parci´ alis integr´al´ assal azt kapjuk, hogy zξ
Z
∞
|Re z|x
Z
∞
2
(1 − F (x))d e ≤ B|Re z| e−Cx +|Re z|x dx 0 0 √ 2 K2 (Re z)2 |Re z|2 /C 2 ≤ K1 eK2 |z| 2π/C ≤ K1 e = B|Re z|e
|Ee | ≤
alkalmas K1 > 0 ´es K2 > 0 sz´amokkal. Vezess¨ uk be a ϕ(z) = Eeizξ ´es ψ(z) = Eeizη f¨ uggv´enyeket minden komplex z sz´amra. Val´ os t ´ert´ekekre megszor´ıtva e f¨ uggv´enyek a ξ ´es η val´ osz´ın˝ us´egi v´ altoz´ ok karakterisztikus f¨ uggv´enyeivel egyenl˝oek. Az eddigi becsl´esek alapj´ an |ϕ(z)| ≤ 2 2 K1 eK2 |z| , ´es hasonl´oan |ψ(z)| ≤ K1 eK2 |z| alkalmas K1 > 0, ´es K2 > 0 sz´amokkal. Tov´ abb´a a ϕ(z) ´es ψ(z) f¨ uggv´enyek holomorfak az eg´esz komplex sz´ams´ıkon. Ennek indokl´ as´aul Weierstrass t´etel´ere ´erdemes hivatkozni, amely szerint egy tartom´anyban egyenletesen korl´ atos holomorf f¨ uggv´enyek limesze is holomorf ebben a tartom´anyban. Ezenk´ıv¨ ul azt kell ´eszrevenni, hogy a ξ ´es η val´ osz´ın˝ us´egi v´ altoz´ ok alkalmas diszkr´et k¨ ozel´ıt´es´evel a ϕ(·) ´es ψ(·) f¨ uggv´enyeket el˝ o´all´ıthatjuk ϕ(z) = lim ϕn (z) ´es ψ(z) = lim ψn (z) alakban, ahol ϕn (z) ´es ψn (z) olyan holomorf n→∞ n→∞ P bk z f¨ uggv´enyek, (e k¨ ozel´ıt˝ o f¨ uggv´enyek ak alak´ uak alkalmas ak ´es bk konstansok2 kal, ahol v´eges ¨ osszegeket vesz¨ unk), amelyekre |ϕn (z)| ≤ K1 eK2 |z| , ´es |ψn (z)| ≤ 7
2
K1 eK2 |z| minden n = 1, 2, . . . indexre ´es z komplex sz´amra. A holomorf f¨ uggv´e2 nyek egy´ertelm˝ u kiterjeszt´es´er˝ ol sz´ol´ o eredm´eny alapj´ an ϕ(z)ψ(z) = e−z /2 minden z sz´amra, ´es speci´ alisan ϕ(z) 6= 0 minden z sz´amra. Innen az is k¨ ovetkezik, hogy defini´alhatjuk az eg´esz komplex sz´am´ıkon holomorf d ϕ(z) log ϕ(z) f¨ uggv´enyt, ´es arra Re (log ϕ(z) ≤ log K2 + Ks |z|2 . Val´ oban, mivel dzϕz holomorf az eg´esz komplex sz´ams´ıkon, ´es ϕ(0) = 1, tekinthetj¨ uk a log ϕ(z) f¨ uggd R z du ϕ(u) v´eny k¨ ovetkez˝ o verzi´oj´at: log ϕ(z) = 0 ϕu du, ahol tetsz˝oleges a 0 ´es z pontot osszek¨ot˝ ¨ o sz´ep g¨orb´en tekinthetj¨ uk a fenti komplex integr´alt. Mivel |elog ϕ)z) | = 2 2 2 |ϕ(z)| ≤ K1 eK2 |z | , ´es |eKz | = eRe (Kz ) minden z komplex sz´amra innen ad´ odik, hogy Re (log ϕ(z)) ≤ log K1 + K2 |z|2 . Re (log ϕ(z)) harmonikus f¨ uggv´eny, (mert egy holomorf f¨ uggv´eny val´ os r´esze). Ez´ert a fenti egyenl˝otlens´egb˝ol ´es a Liouville t´etel egy m´ely ´ altal´ anos´ıt´ as´ab´ ol k¨ ovetkezik, hogy Re (log(ϕ(x + iy)) az x ´es y v´ altoz´ ok egy egy m´ asodfok´ u polinomja, ´es ennek analitikus kieg´esz´ıt´ese log ϕ(z) = 2 2 Az + Bz + C alak´ u. Ez´ert ϕ(t) = eAt +Bt+C alak´ u. Tov´ abb´a mivel ϕ(t) karakterisztikus f¨ ugv´eny, ez´ert ϕ(0) = 1, ϕ′ (0) = im = iEξ, ϕ′′ (0) = −σ 2 = −Eξ 2 . Innen 2 2 ϕ(t) = e−σ t /2+imt , egy norm´ alis eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ o karakterisztikus f¨ uggv´enye.
8
