Pólya-féle urnamodell I

2012. szeptember 5, 15:30

K¨ oMaL, 2012. szeptember (1. lap)

P´ olya-f´ ele urnamodell I.

1. Bevezet´ es Hogyan magyar´ azhat´ ok azok a jelenségek, mikor több, egymással verseng˝o, hasonló esélyekkel indul´ o alternat´ıva köz¨ ul valamelyik egy rövid id˝on bel¨ ul átveszi a vezetést, és ha az el˝ onyt megkaparintotta, onnantól kezdve a többinek már nincs esélye ˝ot behozni? Miért haszn´ alja a világ elsöpr˝o többsége az egyébként kevésbé hatékonynak tartott QWERTY billenty˝ uzetet? A sok, alapvet˝oen hasonló szolgáltatást ny´ ujt´ o k¨ oz¨ osségi hál´ ozat létezése ellenére miért vált elsöpr˝o népszer˝ uség˝ uvé a Facebook? A val´ osz´ın˝ uségsz´ am´ıt´ as egyik alapvet˝o gondolatk´ısérlete P´ olya Gy¨ orgy (1887– 1985) nevéhez f˝ uz˝ odik, és épp ezt a jelenségkört modellezi. Egy id˝oben véletlen¨ ul növeked˝ o rendszerben a kezdeti id˝ oszakban megvalósuló véletlen lépesek olykor sokkal meghat´ aroz´ obb´ a v´ alnak a t´ avoli jöv˝obeli véletlen kimenetel szempontjából, mint a kés˝ obbi lépések. A P´ olya-féle urna folyamat után, a cikk második felében egyéb kapcsol´ od´ o modelleket is v´ azolunk, melyek mind erre a szálra f˝ uzhet˝ok fel. Ezeket a kombinatorikus megk¨ ozel´ıtéssel jól megérthet˝o modelleket részletesen tárgyalja [2] és [3]. Magyar nyelven is elérhet˝o, klasszikus le´ırásért lásd [1]-et. A sz´ ohaszn´ alatr´ ol megjegyezz¨ uk, hogy bár az urna” kifejezés mai f¨ ullel kissé ” bizarrul hangozhat, a matematikus társadalom mégis ezt a szót használja történelmi okokból1 , amikor dobozokban elhelyezett sz´ınes golyók véletlen kih´ uzásairól beszél. A magyar nyelv˝ u matematikai irodalom is meg˝orzi ezt a szóhasználatot, és ennek megfelel˝ oen mi is ´ıgy tesz¨ unk. A megérteshez a kombinatorikus valósz´ın˝ uség valamint a határérték fogalmának ismerete sz¨ ukséges. Az egyéb felmer¨ ul˝o fogalmakat a szemléletességet szem el˝ott tartva igyekszem bemutatni. 2. A P´ olya-f´ ele urnamodell alapesete 2.1. A modell Egy dobozban kezdetben két golyó van, egy piros és egy zöld. A dobozban lév˝o piros goly´ ok arány´ at jel¨ olj¨ uk R0 -lal, jelen esetben tehát R0 = 1/2. Az els˝ o lépés abb´ ol áll, hogy véletlenszer˝ uen (minden golyónak azonos esélyt adva, azaz egyenletes eloszl´ assal) kih´ uzzuk az egyik golyót a dobozból és megnézz¨ uk a sz´ınét, majd visszatessz¨ uk. Ezen k´ıv¨ ul tesz¨ unk a dobozba még egy u ´j golyót is, 1 M´ ar Jacob Bernoulli 1713-as Ars Conjectandi c. munk´ aj´ aban is a latin urna sz´ o jelenik meg, ˝ o ebben az agyag edényben helyez el gondolatban sz´ınes kavicsokat, ezek k¨ oz¨ ul h´ uz ki gondolatban egy p´ ar darabot, és az ´ıgy az urn´ aban marad´ o véletlen kavicshalmazban vizsg´ alja a k¨ ul¨ onb¨ oz˝ o sz´ınek ar´ any´ anak eloszl´ as´ at.

K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6

1



mégpedig olyan sz´ın˝ ut, mint amilyet az imént h´ uztunk. A dobozban tehát most három goly´ o van: ha pirosat h´ uztunk, akkor egy zöld és két piros, ha pedig zöldet h´ uztunk, akkor egy piros és két z¨ old. A dobozban lév˝o piros golyók arányát jelölj¨ uk R1 -gyel, ami teh´ at lehet 2/3 (pirosat h´ uztunk) vagy 1/3 (zöldet h´ uztunk). J¨ ohet a m´ asodik lépés: a most bent lév˝o három golyó köz¨ ul h´ uzunk véletlen¨ ul, egyenletes eloszl´ assal, megnézz¨ uk a sz´ınét, visszatessz¨ uk a dobozba egy u ´j, ugyanolyan sz´ın˝ u goly´ oval egy¨ utt. A most ott lév˝o piros golyók aránya, R2 , tehát lehet 3/4, 1/2 vagy 1/4, att´ ol f¨ ugg˝ oen, hogy mennyi volt R1 , és hogy milyen sz´ın˝ u golyót h´ uztunk most (l´ asd 1. ´ abra).

1. ´ abra. P´ olya-féle urnamodell, alapeset

Ugyan´ıgy haladva tov´ abb, ezt az elemi lépést ismételj¨ uk meg egymás után sokszor. Hogyha a dobozban n lépés után pn darab piros és zn darab zöld golyó találhat´ o, azaz a piros goly´ ok ar´ anya Rn =

pn , pn + zn

akkor a k¨ ovetkez˝ o állapotot u ´gy kapjuk, hogy h´ uzunk véletlenszer˝ uen a dobozból egy goly´ ot (Rn val´ osz´ın˝ uséggel pirosat, 1 − Rn valósz´ın˝ uséggel zöldet), és a visszatételével egyid˝ oben tesz¨ unk még egy ugyanilyen sz´ın˝ u golyót a dobozba. Az Rn+1 érték ennek megfelel˝ oen kétféle lehet, a) ha pirosat h´ uzunk, akkor Rn+1 = b) ha z¨ oldet h´ uzunk, akkor Rn+1 =

pn +1 , ennek valósz´ın˝ usége Rn , pn +zn +1 pn , ennek valósz´ın˝ usége 1 − Rn . pn +zn +1

Ez a P´ olya-féle urnamodell legegyszer˝ ubb esete. 2




2.2. A v´ eletlen ´ allapot r¨ ogz´ıtett sz´ am´ u l´ ep´ es megt´ etele ut´ an Milyen szab´ alyszer˝ uséget fedezhet¨ unk fel, rögz´ıtett n mellett, az Rn szám véletlen értékével kapcsolatban? K¨ onnyen látható, hogy Rn lehetséges értékei a (0, 1) intervallumban a k/(n + 2) alak´ u törtek, ahol 1 6 k 6 (n + 1), azaz ahogy n egyre nagyobb, az Rn értékkészlete kezdi egyenletesen s˝ ur˝ un kitölteni a teljes (0, 1) intervallumot. De milyen eséllyel lesz Rn értéke éppen k/(n + 2), valamilyen adott k-ra? Világos, hogy Rn , a piros golyók aránya az n-edik lépés után épp annak az aktuális (feltételes) val´ osz´ın˝ uségét adja meg, hogy a következ˝o, (n + 1)-edik lépésnél piros sz´ın˝ u goly´ ot h´ uzunk, feltéve, hogy már eljutottunk az n-edik lépésig. Az els˝ o pár lépésben a megval´ osulások valósz´ın˝ uségeit könnyen kiszámolhatjuk, például az 1. ´ abr´ at k¨ ovetve. R1 értéke kétféle lehet, a) R1 = 2/3, ha pirosat h´ uzunk els˝ore, ennek esélye 1/2, vagy b) R1 = 1/3, ha z¨ oldet h´ uzunk, ennek esélye ugyan´ ugy 1/2. R2 értékének kiszámol´ asakor ezt már figyelembe vessz¨ uk. Az 1. ´ abr´ ar´ ol leolvashat´ ok a k¨ ovetkez˝ o esetek val´ osz´ın˝ uségei: a) az R2 = 3/4 érték u ´gy érhet˝ o el, ha R1 = 2/3, és u ´jra pirosat h´ uzunk, ez az eseménysorozat 1/2 · 2/3 = 1/3 eséllyel történik. b) Az R2 = 1/2 érték kétféleképp érhet˝o el: i) vagy R1 = 2/3 és most z¨ oldet h´ uzunk, aminek az esélye 1/2 · 1/3 = 1/6, ii) vagy pedig R1 = 1/3 és most pirosat h´ uzunk, ennek esélye szintén 1/2 · 1/3 = 1/6. ¨ Osszess´ egében teh´ at az R2 = 1/2 értéket is 1/6 + 1/6 = 1/3 eséllyel érj¨ uk el. b) Vég¨ ul az R2 = 1/4 érték csak u ´ gy lehetséges, ha R1 = 1/3 és u ´jra zöldet h´ uzunk, ennek esélye ismét 1/2 · 2/3 = 1/3. Azaz R1 és R2 esetében is teljes¨ ul az, hogy az összes lehetséges érték között egyenletesen oszlik el a val´ osz´ın˝ uség, más szóval a változó az értékkészletén egyenletes eloszl´ as´ u. Véletlen-e, hogy n = 1 és n = 2 esetében ez ´ıgy van? 2.1. feladat. A merész olvas´ onak javasoljuk, ugorja ´ at a felvezetésként megadott a) és b) részfeladatokat, kezdje r¨ ogt¨ on az utols´ o, c) jel˝ u feladattal. a) Mi a val´ osz´ın˝ usége annak, hogy az urn´ ab´ ol kih´ uzott goly´ osorozat els˝ o k eleme mind piros, az azut´ ani l = n − k eleme pedig mind z¨ old? b) R¨ ogz´ıts¨ unk egy A ⊂ {1, 2, . . . , n}, |A| = k elemsz´ am´ u részhalmazt. Mi a val´ osz´ın˝ usége annak, hogy az urn´ ab´ ol kih´ uzott goly´ osorozat els˝ o n eleme k¨ oz¨ ul pontosan az A-beli sorsz´ am´ u goly´ ok pirosak? c) Mi a val´ osz´ın˝ usége annak, hogy az urn´ ab´ ol kih´ uzott goly´ osorozat els˝ o n eleme k¨ oz¨ ul pontosan k darab piros? A 2.1. feladatban felfedezett tulajdonságot felcserélhet˝oségnek” nevezik. Azt ” jelenti, hogy egy adott sorozat megvalósulásának valósz´ın˝ usége invariáns a permutáK¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6

3



cióra nézve: a val´ osz´ın˝ uség csak a sorozatban szerepl˝o arányoktól f¨ ugg, a sorrendt˝ol nem. A felcserélhet˝ oségnek a P´ olya-féle urnamodell az egyik tankönyvi alappéldája. 2.2. feladat. Bizony´ıtsuk be tetsz˝ oleges n ∈ N-re, hogy Rn azonos val´ osz´ın˝ uséggel veszi fel az ¨ osszes lehetséges értékét! (Az értékkészlet természetesen n-t˝ ol f¨ ugg.) 2.3. Sz´ am´ıt´ og´ epes k´ıs´ erlet Vegy¨ unk egy r¨ ogz´ıtett n értéket (n = 10), és ind´ıtsuk el ugyanannak a Pólyaurna k´ısérletnek sok (N = 1000) f¨ uggetlen példányát, mindig egy piros és egy zöld golyóval kezdve, és futtassuk n lépésig. Ezekben a f¨ uggetlen k´ısérletekben mindig jegyezz¨ uk fel, mi j¨ ott ki Rn = R10 értékére, és rajzoljuk fel a gyakorisági ábrát, más néven hisztogramot, ebb˝ ol az N = 1000 k´ısérletb˝ol. Az általunk ´ırt program seg´ıtségével el˝ o´ all´ıtott példa-hisztogramot lásd a 2. ´ abra tetején.

2. ´ abra. P´ olya-féle urnamodell alapesetének hisztogramja, illetve norm´ alt hisztogramjai 10 lépés ut´ an, k¨ ul¨ onb¨ oz˝ o k´ısérletsz´ amok mellett

Tegy¨ uk fel, hogy az n = 10 v´ alasztást rögz´ıtj¨ uk, de N értékét, azaz a k´ısérletek számát v´ altoztatni akarjuk, és az eredmény¨ ul kapott hisztogramokat össze akarjuk vetni egym´ assal. Hogyha a k¨ ul¨ onb¨ oz˝o N -ekre el˝oáll´ıtott hisztogramokat u ´gy normáljuk, hogy az oszlopok által lefedett tartomány ter¨ ulete mindig azonos legyen, akkor az ¨ osszevetés kényelmes lesz, mert a lépték minden ábránkon azonos, lásd a 2. ´ abra als´ o sorozat´ at. R¨ ogz´ıtett n mellett N növelésével az ábra egyre inkább hasonl´ıt a feladatban bizony´ıtott elméleti eloszláshoz tartozó, egyenletes hisztog4




ramhoz. Azt, hogy a hisztogramok N növelésével valóban az elméletihez tartanak, a statisztika alaptétele mondja ki. 2.3. feladat. ´ Irjuk meg a P´ olya-féle urnamodell alapesetének algoritmus´ at egy tetsz˝ oleges, ´ altalunk elérhet˝ o programnyelven2 és ´ all´ıtsunk el˝ o a 2. ábrákhoz hasonl´ okat! A 2.2. feladat áll´ıt´ as´ ab´ ol kiolvasható, hogy n növelésével Rn elméleti eloszlása a (0, 1) intervallumon értelmezett u ´gynevezett folytonos egyenletes eloszláshoz tart (ennek u ´gynevezett s˝ ur˝ uségf¨ uggvénye” a v´ızszintes vonal, ahol a vonal alatti ter¨ ulet ” 1-re van norm´ alva). Ez m´ ar ¨ onmagában is érdekes tény, ámde ennél egy sokkal er˝osebb áll´ıt´ as is igaz. A k¨ ovetkez˝ o fejezetben e felé az áll´ıtás felé haladunk. 3. A v´ eletlen sorozat tulajdons´ agai 3.1. A P´ olya-f´ ele urnamodell ´ altal´ anosabb esetei Miel˝ ott tov´ abblép¨ unk tov´ abbi megfigyelések felé, tág´ıtsuk ki egy kissé a vizsgált modellek k¨ orét. A Pólya-féle urnamodell 2.1. fejezetben vázolt alapesete többféleképpen is által´ anos´ıthat´ o, péld´ aul a kezdeti feltétel variálásával. A golyók számának n¨ ovelésére szolg´ al´ o algoritmust változatlanul hagyjuk, viszont ahelyett, hogy kezdetben 1 piros és 1 z¨ old goly´ ot tennénk az urnába, ind´ıtsunk p0 piros és z0 zöld golyóval (p0 > 1, z0 > 1). ´ Altal´ anos´ıthatjuk ennél jobban is az urna modellt. Például u ´gy, hogy nem csak két sz´ınt enged¨ unk meg, hanem egy el˝ore rögz´ıtett, K elemszám´ u sz´ınhalmazból válogatva tesz¨ unk kezdetben az urn´ aba r1 darab c1 sz´ın˝ u, r2 darab c2 sz´ın˝ u, . . . , rK darab cK sz´ın˝ u goly´ ot. Ha az olvasóban felmer¨ ul, meg tudunk-e engedni végtelen sok sz´ınt is, még egy kis t¨ urelmet kér¨ unk t˝ole, egy kés˝obbi fejezetb˝ol ez is ki fog der¨ ulni. Egyel˝ ore maradjunk a két sz´ın használata melletti általános´ıtásnál, mert ez is rejteget még érdekességet. 3.2. Mi a helyzet a v´ eletlen sorozattal? A 2.2. feladatban bizony´ıtott áll´ıtás rögz´ıtett n mellett mond valamit az Rn véletlen sz´ am (val´ osz´ın˝ uségi v´ altoz´ o) lehetséges értékeir˝ol, és az értékek megvalósulásának val´ osz´ın˝ uségeir˝ ol (a val´ osz´ın˝ uségi változó eloszlásáról). Olyan t´ıpus´ u eredmény ez, mint mikor a 2.3. feladatban meg´ırt programunk futásakor nem ´ırattuk ki a fut´ as k¨ ozben érintett Rj értékeket (j < n), hanem minden egyes futáskor csak az általunk el˝ ore kiszemelt n mellett voltunk k´ıváncsiak Rn kimeneteleire. Hogy éppen hogyan jutottunk el addig a véletlen számig, azt nem vizsgáltuk. Természetes módon felmer¨ ulhet benn¨ unk ugyanakkor a kérdés, megállap´ıthatunk-e valamit a véletlen sz´ amsorozat egészér˝ol (véletlen folyamatról) is, ami egy-egy ilyen szimul´ aci´ o sor´ an el˝ o´ all. Feljegyezhetnénk sok, egymástól f¨ uggetlen¨ ul 2

A cikkben szerepl˝ o szimul´ aci´ okat Python nyelven ´ırtam, a k´ od szerkesztéséhez és futtat´ as´ ahoz Eclipse-t haszn´ altam (Pydev modullal), a képek megjelen´ıtéséhez pedig Gnuplotot. Ezek mindegyike ingyen hozz´ aférhet˝ o.


5



el˝oálló ilyen sorozatot, és ezekr˝ ol a véletlen sorozatokról is megkérdezhetnénk, vajon milyen tulajdons´ agokkal rendelkeznek. 3.1. feladat. A kor´ abban ´ırt sz´ am´ıt´ ogépes programunkkal ´ all´ıtsunk el˝ o f¨ uggetlen k´ısérletekb˝ ol el˝ o´ all´ o véletlen p´ aly´ akat, m´ as néven trajekt´ ori´ akat, a P´ olya-urna alapesetében (p0 = 1, z0 = 1). Az általunk ´ırt programmal kész´ıtett trajektóriákat lásd a 3. ´ abr´ an. Ezek megfigyelésével máris tehet¨ unk néh´ any kezdeti megállap´ıtást.

3. ´ abra. Trajekt´ oi´ ak a P´ olya-féle urnamodellben (p0 = 1, z0 = 1)

Az algoritmusr´ ol által´ anoss´ agban megállap´ıthatjuk azt, hogy a piros golyó h´ uzás´ anak éppen aktu´ alis val´ osz´ın˝ usége id˝oben véletlenszer˝ uen változik, ahogyan az urnában a piros goly´ ok ar´ anya az összes golyóhoz képest mindig más és más. Ugyanakkor egyetlen goly´ o betételének hatása erre az arányra, ahogy haladunk el˝ore az id˝ oben, egyre kisebb és kisebb, hiszen az u ´j golyó megjelenése az éppen aktuális ar´ anyt már egyre kevésbé tudja megváltoztatni. 3.2. feladat. Az 3. ábr´ an mintha hiperbolikus ´ıvdarabok jelennének meg. Miért van ez? 3.3. feladat. Ha visszatekint¨ unk a 2.2. feladatban bizony´ıtott eredményre, l´ atjuk, hogy a programunkat (p0 = 1, z0 = 1)-b˝ ol sokszor elind´ıtva az Rn = R10 értékek atlaga sok k´ısérlet ut´ ´ an 1/2. Jegyezz¨ unk fel most minden trajekt´ ori´ an két értéket, R1 -et és R10 -et. Mi a megval´ osult R10 értékek ´ atlaga azokon a trajekt´ ori´ akon, ame´ mennyi azokon, amelyeken R1 = 2/3? lyeken R1 = 1/3? Es 6




3.3. A megfigyel´ esek matematikai h´ attere Ez a számunkra egyel˝ ore k´ısérleteken alapuló megfigyelés pontossá is tehet˝o, és a valósz´ın˝ uségsz´ am´ıt´ asnak egy k¨ ul¨ onleges fejezetéhez, az u ´gynevezett martingálelmélethez kalauzol benn¨ unket. Anélk¨ ul, hogy a prec´ız defin´ıcióhoz elengedhetetlen¨ ul sz¨ ukséges elméleti hátteret megk´ısérelnénk itt megadni, a lényeget mégis vázoljuk. Azok a véletlen folyamatok, amelyek mindig az éppen aktuális (véletlen) poz´ıciójukat szeretnék megtartani”, k¨ ulönös jelent˝oség¨ uk van, és a martingál elnevezést ” kapták. Ezek, ha egy adott lépéskor megfigyelj¨ uk ˝oket, a véletlen érték ismeretében a következ˝ o lépésben v´ arhat´ oan” pontosan ugyanott maradnak. Ez nem azt jelenti, ” hogy a k¨ ovetkez˝ o lépésben nem mozdulnak el, hanem azt, hogy a valósz´ın˝ uségekkel s´ ulyozott átlagos elmozdul´ asuk nulla. A témakörben az egyik leggyakrabban használt tétel szerint pedig, ismét nem teljesen prec´ızen megfogalmazva, hogyha egy ilyen véletlen folyamat értékkészlete korlátos, akkor annak a véletlen folyamatnak bármilyen tipikus megval´ osulása olyan számsorozat lesz, amelynek létezik a határértéke. (A tipikus megval´ osulás” fogalmát jelen cikkben nem definiáljuk.) ” 3.4. Alkalmazhat´ o ez az er˝ os eszk¨ oz ebben az esetben? Sz´ amoljunk! Ahhoz, hogy l´ assuk, ez az er˝ os tétel valóban alkalmazható a Pólya-féle urnamodell fenti által´ anos´ıt´ asainak esetében, a két feltétel fennállását vizsgájuk. Az értékkészlet nyilv´ anval´ oan korl´ atos, Rn csak (0, 1)-ben mozog, tehát a tétel másik feltétele r¨ ogt¨ on teljes¨ ul. A m´ asik feltétel igazolása érdekében ellen˝orizz¨ uk, hogy a marting´ alokat definiál´ o tulajdonság igaz az Rn folyamatra. Képzelj¨ uk el, hogy n lépést már megtett¨ unk, és a szokásos módon jelölj¨ uk pn -nel az n-edik lépés ut´ an a piros golyók szám´ at, zn -nel a zöldek számát, Rn -nel pedig a piros goly´ ok ar´ any´ at az ¨ osszeshez képest. Ekkor a) ha a k¨ ovetkez˝ o lépésben pirosat h´ uzunk, akkor a piros golyók száma pn + 1 pn +1 lesz, teh´ at Rn+1 értéke p +z , ennek a valósz´ın˝ usége +1 n

n

Rn =

pn , pn + zn

b) ha viszont z¨ oldet h´ uzunk, akkor a piros golyók száma pn marad, tehát az u ´j p ar´ any Rn+1 értéke p +zn +1 lesz, ennek valósz´ın˝ usége pedig n

n

1 − Rn =

zn . pn + zn

Hogy mennyi az Rn sz´ am ismeretében Rn+1 feltételes várható értéke, u ´gy kapjuk meg, hogy mindkét sz´ oba j¨ ov˝o értéket megszorozzuk a valósz´ın˝ uség¨ ukkel, és ´ıgy ¨ osszeadjuk ˝oket, pn pn zn pn pn + 1 + = = Rn . pn + zn + 1 pn + zn pn + zn + 1 pn + zn pn + zn Ennek a sz´ amol´ asnak az eredménye épp Rn , azaz a folyamat n-edik lépésében kapott érték ismeretében a k¨ ovetkez˝o lépés által okozott elmozdulás feltételes v´ arhat´ o értéke nulla. Ez a sz´ amolás p0 és z0 bármely értéke mellett érvényes. K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6

7



A Pólya-féle urnamodellben a vizsgált véletlen folyamat tehát valóban egy korlátos marting´ al, aminek a 3.3. szakaszban vázolt tétel szerint tehát létezik a határértéke (ami azonban egy véletlen sz´ am!). A határérték valósz´ın˝ uségi eloszlása a folytonos egyenletes eloszl´ as a (0, 1) intervallumon. Ez ¨ osszefoglalva teh´ at azt jelenti, hogy a véletlen trajektóriák, melyeknek véges szeleteit a sz´ am´ıt´ ogépes programunkkal meg is figyelhetj¨ uk (3. ´ abra), végtelen ” hossz´ u ideig futtatva” mind be´ allnak egy-egy (véletlen) értékre. 3.5. Trajekt´ ori´ ak ´ es hamis ´ erm´ ek Amikor a P´ olya-féle modellt el˝ oször ismerj¨ uk meg, lehet az az érzés¨ unk, hogy egy-egy h´ uz´ as véletlenségében a folyamat teljes m´ ultja közrejátszik. Hamar rájöv¨ unk azonban arra, hogy ez nem egészen van ´ıgy: az (n + 1)-edik h´ uzás során nem lényeges, hogy az urn´ aban lév˝ o golyók milyen sorrendben ker¨ ultek oda, csak a piros golyók aktu´ alis ar´ anya, Rn sz´ am´ıt. Azt azonban egy pillanatig sem gondoljuk (és nem is volna igaz), hogy az egym´ as utáni h´ uzások f¨ uggetlenek volnának egymástól. De akkor mi a helyzet a k¨ ovetkez˝ o gondolatmenettel? K´ odoljuk az n lépésb˝ ol áll´ o k´ısérleteket egy-egy n-hossz´ u, P és Z bet˝ ukb˝ol álló n sorozattal, azaz a trajekt´ ori´ akat k´ odoljuk a Bn = {P, Z} elemeivel, az egymás után kih´ uzott goly´ ok sz´ınének megfelel˝oen. E halmaz azon részhalmazát, mely sorozatokban pontosan pn darab P bet˝ u szerepel, jelölje Bn(pn ) , ennek elemszáma ( ) n |Bn(pn ) | = p . n A 2.1. feladat c) szakasz´ anak megoldásakor kapott kombinatorikus formulából kiolvashat´ o, hogy adott n mellett egy rögz´ıtett Rn arány, azaz rögz´ıtett pn szám´ u piros goly´ o ¨ osszes lehetséges el˝ o´ allási sorrendje mind azonos valósz´ın˝ uséggel történik. Ez azt jelenti, hogy az Rn arányhoz vezet˝o n-hossz´ u trajektóriák, a Bn(pn ) halmaz elemei mind egyforma val´ osz´ın˝ uséggel állnak el˝o. pn Vegy¨ unk egy hamis érmét, mégpedig olyat, ami rögz´ıtett Rn = p +z valósz´ın n n˝ uséggel esik a piros oldal´ aval felfelé, (1 − Rn ) valósz´ın˝ uséggel pedig a zöld oldalával felfelé. Egy k´ısérlet álljon abb´ ol, hogy feldobjuk ezt az érmét n-szer, a dobások egym´ ast´ ol legyenek f¨ uggetlenek, és jegyezz¨ uk fel a dobások eredményeit P és Z bet˝ ukkel. 3.4. feladat. Adjunk m´ odszert a Bn(pn ) trajekt´ oria halmazon egyenletes eloszl´ as gerner´ al´ as´ ara ennek a k´ısérletnek a kis m´ odos´ıt´ as´ aval! Ha n-et egyre ink´ abb n¨ ovelj¨ uk, akkor fenti, Rn -hamis érmés k´ısérlet eredményeképp el˝ o´ all´ o sorozatban egyre valósz´ın˝ ubb, hogy a P bet˝ uk aránya közel van Rn -hez. Ezt u ´ gy h´ıvj´ ak, hogy a nagy számok gyenge törvénye. A nagy sz´ amok er˝ os t¨ orvénye is igaz, ami pedig azt mondja ki, hogy ha el˝oáll´ıtunk egy végtelen hossz´ u” sorozatot egy hamis érmével, legyen a hamis ” érme piros oldallal felfelé esésének valósz´ın˝ usége θ, akkor a véletlen sorozat egyre hosszabb véges szeleteit nézve a benne szerepl˝o P bet˝ uk aránya θ-hoz tart. 8




Ha teh´ at r¨ ogz´ıt¨ unk egy θ értéket, akkor azon feltétel mellett, hogy a Pólya-féle urnamodell trajekt´ ori´ aja épp ehhez a θ-hoz tart, magát a trajektóriát el˝oáll´ıthatjuk u ´gy is, hogy vesz¨ unk egy θ-hamis érmét, és azt végtelen sokszor feldobjuk. A 3.3. szakaszban pedig láttuk, hogy a határérték, Θ egyenletes eloszlás´ u valósz´ın˝ uségi változ´ o a [0, 1] intervallumon. Az eddigi megfigyeléseket ¨ osszerakva tehát a következ˝ot kaptuk. Vegy¨ unk egy Θ val´ osz´ın˝ uségi v´ altozót, amely egyenletes eloszlás´ u a [0, 1] intervallumon. A kisorsolt érték legyen θ, ez teh´ at most már egy ismert érték a [0, 1] intervallumból. Vegy¨ unk egy hamis érmét, amely ezzel a θ valósz´ın˝ uséggel esik a piros oldalával felfelé, (1 − θ) val´ osz´ın˝ uséggel pedig a zöld oldalával felfelé. Dobjuk fel ezt az érmét végtelen sokszor, és jegyezz¨ uk fel a dobások eredményeit P és Z bet˝ ukkel. Az ´ıgy kapott végtelen sorozat ugyanolyan eloszlás´ u, mint amit a Pólya-féle urnamodell alapesetében, a kih´ uzott goly´ ok sz´ınét feljegyezve kapunk. 3.5. feladat. Azok a kedves olvas´ ok, akik az integr´ al´ as szab´ alyaival m´ ar tiszt´ aban vannak, bizony´ıts´ ak be a fenti ´ all´ıt´ ast a nagy sz´ amok er˝ os t¨ orvényére val´ o hivatkoz´ as nélk¨ ul: sz´ amolj´ ak ki a ∫ 1 n−k θk (1 − θ) dθ 0

értékét, és vessék o anak megold´ asakor kapott kombina¨ssze a 2.1. feladat b) szakasz´ torikus formul´ aval! 3.6. Bolyong´ as a negyeds´ıkon A P´ olya-féle urnamodell két sz´ınt használó eseteinek trajektóriáit kézenfekv˝o módon tekinthetj¨ uk egy negyeds´ık egész koordinátáj´ u rácspontjain való bolyongásnak is. Az x tengelyen jel¨ olj¨ uk a piros, az y tengelyen pedig a zöld golyók számát. A pály´ ak a (p0 , z0 ) pontb´ ol indulnak, és az (i, j) pontból kétfelé léphetnek: az j i (i + 1, j) pontba i+j val´ osz´ın˝ uséggel, az (i, j + 1) pontba pedig i+j valósz´ın˝ uséggel (lásd 4. ´ abra). Ebben a reprezent´ aci´ oban Rn egyenletes eloszlása a (p0 + n, z0 ) és (p0 , z0 + n) pontokat ¨ osszek¨ ot˝ o átl´ os egyenes által tartalmazott rácspontokon valósul meg. A véletlen hat´ arérték pedig felfoghat´ o egy véletlen iránynak a (0, π) szögtartományban. 3.7. Milyen az eloszl´ as, ha nem egyenletes? Anélk¨ ul, hogy folytonos eloszl´ asokról prec´ızen szót ejtenénk, az eml´ıtés szintjén a´lljon itt, hogy m´ıg a legegyszer˝ ubb (egy piros, egy zöld golyóval való ind´ıtás) esetében egyenletes eloszl´ ast kapunk a limeszben, addig két sz´ın de általános (p0 piros, z0 z¨ old kezdeti állapot) esetben az u ´gynevezett Béta eloszláscsalád p0 -tól és z0 -tól f¨ ugg˝ o tagj´ ahoz jutunk. 3.6. feladat. A kor´ abbi feladat sor´ an meg´ırt programot is tegy¨ uk alkalmass´ a p0 és z0 k¨ ul¨ onb¨ oz˝ o értékeinek kezelésére! A Béta eloszl´ ascsal´ ad tagjainak hozz´ avet˝ oleges képét ´ıgy fel is rajzolhatjuk. Milyen v´ altoz´ ast figyelhet¨ unk meg a hisztogramon, ahogy p0 és z0 értékét v´ altoztatjuk? (Néh´ any eset elméleti képét l´ asd az 5. ábrán.) K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6

9



4. ´ abra. A P´ olya-féle urnamodell trajekt´ ori´ aja mint bolyong´ as a (p0 , z0 ) feletti negyeds´ık r´ acspontjain

5. ´ abra. Béta eloszl´ as képei k¨ ul¨ onb¨ oz˝ o paraméterek mellett

´ Erdekes megfigyelni, milyen hatása van annak, ha kezdetben ugyanannyi piros és zöld goly´ ot tesz¨ unk a dobozba, de nem egyet-egyet, hanem például ötöt-ötöt, vagy h´ uszat-h´ uszat. A hat´ arérték-hisztogram egyre cs´ ucsosabbá válik. Ez is azt sejteti, hogy konverg´ al a folyamat: minél nagyobb p + z, annál kevésbé távolodik p ol, még akkor is, ha n már nagyon nagy. el Rn a kezdeti R0 = p+z értékt˝ Az elnevezés eml´ıtése kedvéért álljon itt az is, hogy ha több, el˝ore rögz´ıtett szám´ u (K db) sz´ınnel ind´ıtunk, akkor az arányok vektora, amint n-nel a végte10




lenbe tartunk, az u ´gynevezett Dirichlet-eloszl´ ascsal´ ad kezdeti állapottól f¨ ugg˝oen paraméterezett tagj´ ahoz tart.

Hivatkoz´ asok [1] William Feller, Bevezetés a val´ osz´ın˝ uségsz´ am´ıt´ asba és alkalmaz´ asaiba. M˝ uszaki K¨ onyvkiad´ o (Budapest, 1978). [2] Robin Pemantle, A survey of random processes with reinforcement, Probability Surveys, 4 (2007), 1–79. [3] Jim Pitman, Combinatorial Stochastic Processes, Saint Flour Lectures (2002), Lecture Notes in Mathematics, Vol. 1875. Springer-Verlag (Berlin). Rudas Anna Budapesti M˝ uszaki és Gazdas´ agtudom´ anyi Egyetem Matematika- és Sz´ am´ıt´ astudom´ anyok Doktori Iskola [email protected]


11

Pólya-féle urnamodell I

Recommend Documents