1. ábra. Pólya-féle urnamodell, alapeset

 

A 2.1. feladatban felfedezett tulajdonságot ,,felcserélhetőségnek'' nevezik. Azt jelenti, hogy egy adott sorozat megvalósulásának valószínűsége invariáns a permutációra nézve: a valószínűség csak a sorozatban szereplő arányoktól függ, a sorrendtől nem. A felcserélhetőségnek a Pólya-féle urnamodell az egyik tankönyvi alappéldája.

 

 

2.2. feladat. Bizonyítsuk be tetszőleges $n\in \text{N}$-re, hogy $R_n$ azonos valószínűséggel veszi fel az összes lehetséges értékét! (Az értékkészlet természetesen $n$-től függ.)

 

 

2.3. Számítógépes kísérlet

Vegyünk egy rögzített $n$ értéket ($n=10$), és indítsuk el ugyanannak a Pólya-urna kísérletnek sok ($N=1000$) független példányát, mindig egy piros és egy zöld golyóval kezdve, és futtassuk $n$ lépésig. Ezekben a független kísérletekben mindig jegyezzük fel, mi jött ki $R_n=R_{10}$ értékére, és rajzoljuk fel a gyakorisági ábrát, más néven hisztogramot, ebből az $N=1000$ kísérletből. Az általunk írt program segítségével előállított példa-hisztogramot lásd a 2. ábra tetején.

 

 

2. ábra. Pólya-féle urnamodell alapesetének hisztogramja, illetve normált hisztogramjai 10 lépés után, különböző kísérletszámok mellett

 

Tegyük fel, hogy az $n=10$ választást rögzítjük, de $N$ értékét, azaz a kísérletek számát változtatni akarjuk, és az eredményül kapott hisztogramokat össze akarjuk vetni egymással. Hogyha a különböző $N$-ekre előállított hisztogramokat úgy normáljuk, hogy az oszlopok által lefedett tartomány területe mindig azonos legyen, akkor az összevetés kényelmes lesz, mert a lépték minden ábránkon azonos, lásd a 2. ábra alsó sorozatát. Rögzí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 hisztogramhoz. Azt, hogy a hisztogramok $N$ növelésével valóban az elméletihez tartanak, a statisztika alaptétele mondja ki.

 

 

 

2.3. feladat. Írjuk meg a Pólya-féle urnamodell alapesetének algoritmusát egy tetszőleges, általunk elérhető programnyelven² és állítsunk elő a 2. ábrákhoz hasonlókat!

 

A 2.2. feladat állításából kiolvasható, hogy $n$ növelésével $R_n$ elméleti eloszlása a $\left(\mathrm{0,1}\right)$ intervallumon értelmezett úgynevezett folytonos egyenletes eloszláshoz tart (ennek úgynevezett ,,sűrűségfüggvénye'' a vízszintes vonal, ahol a vonal alatti terület 1-re van normálva). Ez már önmagában is érdekes tény, ámde ennél egy sokkal erősebb állítás is igaz. A következő fejezetben e felé az állítás felé haladunk.

 

 

3. A véletlen sorozat tulajdonságai
3.1. A Pólya-féle urnamodell általánosabb esetei

 

Mielőtt továbblépünk további megfigyelések felé, tágítsuk ki egy kissé a vizsgált modellek körét. A Pólya-féle urnamodell 2.1. fejezetben vázolt alapesete többféleképpen is általánosítható, például a kezdeti feltétel variálásával. A golyók számának növelésére szolgáló algoritmust változatlanul hagyjuk, viszont ahelyett, hogy kezdetben 1 piros és 1 zöld golyót tennénk az urnába, indítsunk $p_0$ piros és $z_0$ zöld golyóval ($p_0\ge 1$, $z_0\ge 1$).
Általánosíthatjuk ennél jobban is az urna modellt. Például úgy, hogy nem csak két színt engedünk meg, hanem egy előre rögzített, $K$ elemszámú színhalmazból válogatva teszünk kezdetben az urnába $r_1$ darab $c_1$ színű, $r_2$ darab $c_2$ színű, $\text{...}$, $r_K$ darab $c_K$ színű golyót. Ha az olvasóban felmerül, meg tudunk-e engedni végtelen sok színt is, még egy kis türelmet kérünk tőle, egy későbbi fejezetből ez is ki fog derülni. Egyelőre 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életlen sorozattal?

 

A 2.2. feladatban bizonyított állítás rögzített $n$ mellett mond valamit az $R_n$ véletlen szám (valószínűségi változó) lehetséges értékeiről, és az értékek megvalósulásának valószínűségeiről (a valószínűségi változó eloszlásáról). Olyan típusú eredmény ez, mint mikor a 2.3. feladatban megírt programunk futásakor nem írattuk ki a futás közben érintett $R_j$ értékeket $\left(j<n\right)$, hanem minden egyes futáskor csak az általunk előre kiszemelt $n$ mellett voltunk kíváncsiak $R_n$ kimeneteleire. Hogy éppen hogyan jutottunk el addig a véletlen számig, azt nem vizsgáltuk.
Természetes módon felmerülhet bennünk ugyanakkor a kérdés, megállapíthatunk-e valamit a véletlen számsorozat egészéről (véletlen folyamatról) is, ami egy-egy ilyen szimuláció során előáll. Feljegyezhetnénk sok, egymástól függetlenül előálló ilyen sorozatot, és ezekről a véletlen sorozatokról is megkérdezhetnénk, vajon milyen tulajdonságokkal rendelkeznek.

 

 

3.1. feladat. A korábban írt számítógépes programunkkal állítsunk elő független kísérletekből előálló véletlen pályákat, más néven trajektóriákat, a Pólya-urna alapesetében $(p_0=1$, $z_0=1)$.

 

Az általunk írt programmal készített trajektóriákat lásd a 3. ábrán. Ezek megfigyelésével máris tehetünk néhány kezdeti megállapítást.

 

 

3. ábra. Trajektóriák a Pólya-féle urnamodellben ($p_0=1$, $z_0=1$)

 

Az algoritmusról általánosságban megállapíthatjuk azt, hogy a piros golyó húzásának éppen aktuális valószínűsége időben véletlenszerűen változik, ahogyan az urnában a piros golyók aránya az összes golyóhoz képest mindig más és más. Ugyanakkor egyetlen golyó betételének hatása erre az arányra, ahogy haladunk előre az időben, egyre kisebb és kisebb, hiszen az új golyó megjelenése az éppen aktuális arányt már egyre kevésbé tudja megváltoztatni.

 

 

3.2. feladat. Az 3. ábrán mintha hiperbolikus ívdarabok jelennének meg. Miért van ez?

 

 

3.3. feladat. Ha visszatekintünk a $\mathrm{2.2.}$ feladatban bizonyított eredményre, látjuk, hogy a programunkat $(p_0=1$, $z_0=1)$-ből sokszor elindítva az $R_n=R_{10}$ értékek átlaga sok kísérlet után $1/2$. Jegyezzünk fel most minden trajektórián két értéket, $R_1$-et és $R_{10}$-et. Mi a megvalósult $R_{10}$ értékek átlaga azokon a trajektóriákon, amelyeken $R_1=1/3?$ És mennyi azokon, amelyeken $R_1=2/3?$

 

 

 

3.3. A megfigyelések matematikai háttere

 

Ez a számunkra egyelőre kísérleteken alapuló megfigyelés pontossá is tehető, és a valószínűségszámításnak egy különleges fejezetéhez, az úgynevezett martingálelmélethez kalauzol bennünket. Anélkül, hogy a precíz definícióhoz elengedhetetlenül szüksé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ülönös jelentőségük van, és a martingál elnevezést kapták. Ezek, ha egy adott lépéskor megfigyeljük őket, a véletlen érték ismeretében a következő lépésben ,,várhatóan'' pontosan ugyanott maradnak. Ez nem azt jelenti, hogy a következő lépésben nem mozdulnak el, hanem azt, hogy a valószínűségekkel súlyozott átlagos elmozdulásuk 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ósulása olyan számsorozat lesz, amelynek létezik a határértéke. (A ,,tipikus megvalósulás'' fogalmát jelen cikkben nem definiáljuk.)

 

 

3.4. Alkalmazható ez az erős eszköz ebben az esetben? Számoljunk!

 

Ahhoz, hogy lássuk, ez az erős tétel valóban alkalmazható a Pólya-féle urnamodell fenti általánosításainak esetében, a két feltétel fennállását vizsgáljuk. Az értékkészlet nyilvánvalóan korlátos, $R_n$ csak $\left(\mathrm{0,1}\right)$-ben mozog, tehát a tétel másik feltétele rögtön teljesül. A másik feltétel igazolása érdekében ellenőrizzük, hogy a martingálokat definiáló tulajdonság igaz az $R_n$ folyamatra.
Képzeljük el, hogy $n$ lépést már megtettünk, és a szokásos módon jelöljük $p_n$-nel az $n$-edik lépés után a piros golyók számát, $z_n$-nel a zöldek számát, $R_n$-nel pedig a piros golyók arányát az összeshez képest. Ekkor

$a)$	ha a következő lépésben pirosat húzunk, akkor a piros golyók száma $p_n+1$ lesz, tehát $R_{n+1}$ értéke $\frac{p_n+1}{p_n+z_n+1}$, ennek a valószínűsége $\begin{array}{c}{\displaystyle R_n=\frac{p_n}{p_n+z_n};}\end{array}$

$b)$	ha viszont zöldet húzunk, akkor a piros golyók száma $p_n$ marad, tehát az új arány, $R_{n+1}$ értéke $\frac{p_n}{p_n+z_n+1}$ lesz, ennek valószínűsége pedig $\begin{array}{c}{\displaystyle 1-R_n=\frac{z_n}{p_n+z_n}\mathrm{.}}\end{array}$

Hogy mennyi az $R_n$ szám ismeretében $R_{n+1}$ feltételes várható értéke, úgy kapjuk meg, hogy mindkét szóba jövő értéket megszorozzuk a valószínűségükkel, majd összeadjuk őket:

$\begin{array}{c}{\displaystyle \frac{p_n+1}{p_n+z_n+1}\frac{p_n}{p_n+z_n}+\frac{p_n}{p_n+z_n+1}\frac{z_n}{p_n+z_n}=\frac{p_n}{p_n+z_n}=R_n\mathrm{.}}\end{array}$

Ennek a számolásnak az eredménye épp $R_n$, azaz a folyamat $n$-edik lépésében kapott érték ismeretében a következő lépés által okozott elmozdulás feltételes várható értéke nulla. Ez a számolás $p_0$ és $z_0$ bármely értéke mellett érvényes. A Pólya-féle urnamodellben a vizsgált véletlen folyamat tehát valóban egy korlátos martingál, 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ám!). A határérték valószínűségi eloszlása a folytonos egyenletes eloszlás a $\left(\mathrm{0,1}\right)$ intervallumon.
Ez összefoglalva tehát azt jelenti, hogy a véletlen trajektóriák, melyeknek véges szeleteit a számítógépes programunkkal meg is figyelhetjük (3. ábra), ,,végtelen hosszú ideig futtatva'' mind beállnak egy-egy (véletlen) értékre.

 

 

3.5. Trajektóriák és hamis érmék

 

Amikor a Pólya-féle modellt először ismerjük meg, lehet az az érzésünk, hogy egy-egy húzás véletlenségében a folyamat teljes múltja közrejátszik. Hamar rájövünk azonban arra, hogy ez nem egészen van így: az $\left(n+1\right)$-edik húzás során nem lényeges, hogy az urnában lévő golyók milyen sorrendben kerültek oda, csak a piros golyók aktuális aránya, $R_n$ számít. Azt azonban egy pillanatig sem gondoljuk (és nem is volna igaz), hogy az egymás utáni húzások függetlenek volnának egymástól. De akkor mi a helyzet a következő gondolatmenettel?
Kódoljuk az $n$ lépésből álló kísérleteket egy-egy $n$-hosszú, $P$ és $Z$ betűkből álló sorozattal, azaz a trajektóriákat kódoljuk a $B_n={\left\{P\mathrm{,}Z\right\}}^n$ elemeivel, az egymás után kihúzott golyók színének megfelelően. E halmaz azon részhalmazát, mely sorozatokban pontosan $p_n$ darab $P$ betű szerepel, jelölje $B_n^{\left(p_n\right)}$, ennek elemszáma

$\begin{array}{c}{\displaystyle |B_n^{\left(p_n\right)}|=\left(\genfrac{}{}{0ex}{}{n}{p_n}\right)\mathrm{.}}\end{array}$

A 2.1. feladat $c)$ szakaszának megoldásakor kapott kombinatorikus formulából kiolvasható, hogy adott $n$ mellett egy rögzített $R_n$ arány, azaz rögzített $p_n$ számú piros golyó összes lehetséges előállási sorrendje mind azonos valószínűséggel történik. Ez azt jelenti, hogy az $R_n$ arányhoz vezető $n$-hosszú trajektóriák, a $B_n^{\left(p_n\right)}$ halmaz elemei mind egyforma valószínűséggel állnak elő.
Vegyünk egy hamis érmét, mégpedig olyat, ami rögzített $R_n=\frac{p_n}{p_n+z_n}$ valószínűséggel esik a piros oldalával felfelé, $\left(1-R_n\right)$ valószínűséggel pedig a zöld oldalával felfelé. Egy kísérlet álljon abból, hogy feldobjuk ezt az érmét $n$-szer, a dobások egymástól legyenek függetlenek, és jegyezzük fel a dobások eredményeit $P$ és $Z$ betűkkel.

 

 

3.4. feladat. Adjunk módszert a $B_n^{\left(p_n\right)}$ trajektória halmazon egyenletes eloszlás generálására ennek a kísérletnek a kis módosításával!

 

Ha $n$-et egyre inkább növeljük, akkor a fenti, $R_n$ hamis érmés kísérlet eredményeképp előálló sorozatban egyre valószínűbb, hogy a $P$ betűk aránya közel van $R_n$-hez. Ezt úgy hívják, hogy a nagy számok gyenge törvénye.
A nagy számok erős törvénye is igaz, ami pedig azt mondja ki, hogy ha előállítunk egy ,,végtelen hosszú'' sorozatot egy hamis érmével, legyen a hamis érme piros oldallal felfelé esésének valószínűsége $\theta$, akkor a véletlen sorozat egyre hosszabb véges szeleteit nézve a benne szereplő $P$ betűk aránya $\theta$-hoz tart.
Ha tehát rögzítünk egy $\theta$ értéket, akkor azon feltétel mellett, hogy a Pólya-féle urnamodell trajektóriája épp ehhez a $\theta$-hoz tart, magát a trajektóriát előállíthatjuk úgy is, hogy veszünk egy $\theta$-hamis érmét, és azt végtelen sokszor feldobjuk. A 3.3. szakaszban pedig láttuk, hogy a határérték, $\Theta$ egyenletes eloszlású valószínűségi változó a $\left[\mathrm{0,1}\right]$ intervallumon.
Az eddigi megfigyeléseket összerakva tehát a következőt kaptuk. Vegyünk egy $\Theta$ valószínűségi változót, amely egyenletes eloszlású a $\left[\mathrm{0,1}\right]$ intervallumon. A kisorsolt érték legyen $\theta$, ez tehát most már egy ismert érték a $\left[\mathrm{0,1}\right]$ intervallumból. Vegyünk egy hamis érmét, amely ezzel a $\theta$ valószínűséggel esik a piros oldalával felfelé, $\left(1-\theta \right)$ valószínűséggel pedig a zöld oldalával felfelé. Dobjuk fel ezt az érmét végtelen sokszor, és jegyezzük fel a dobások eredményeit $P$ és $Z$ betűkkel. Az így kapott végtelen sorozat ugyanolyan eloszlású, mint amit a Pólya-féle urnamodell alapesetében, a kihúzott golyók színét feljegyezve kapunk.

 

 

3.5. feladat. Azok a kedves olvasók, akik az integrálás szabályaival már tisztában vannak, bizonyítsák be a fenti állítást a nagy számok erős törvényére való hivatkozás nélkül: számolják ki a

$\begin{array}{c}{\displaystyle \underset{0}{\overset{1}{\int }}{\theta }^k{\left(1-\theta \right)}^{n-k}\text{d}\theta }\end{array}$

értékét, és vessék össze a $\mathrm{2.1.}$ feladat $b)$ szakaszának megoldásakor kapott kombinatorikus formulával!

 

 

3.6. Bolyongás a negyedsíkon

 

A Pólya-féle urnamodell két színt használó eseteinek trajektóriáit kézenfekvő módon tekinthetjük egy negyedsík egész koordinátájú rácspontjain való bolyongásnak is. Az $x$ tengelyen jelöljük a piros, az $y$ tengelyen pedig a zöld golyók számát. A pályák a $\left(p_0\mathrm{,}{z}_0\right)$ pontból indulnak, és az $\left(i\mathrm{,}j\right)$ pontból kétfelé léphetnek: az $\left(i+\mathrm{1,}j\right)$ pontba $\frac{i}{i+j}$ valószínűséggel, az $\left(i\mathrm{,}j+1\right)$ pontba pedig $\frac{j}{i+j}$ valószínűséggel (lásd 4. ábra).

 

 

4. ábra. A Pólya-féle urnamodell trajektóriája mint bolyongás a $\left(p_0\mathrm{,}{z}_0\right)$ feletti
negyedsík rácspontjain

 

Ebben a reprezentációban $R_n$ egyenletes eloszlása a $\left(p_0+n\mathrm{,}{z}_0\right)$ és $\left(p_0\mathrm{,}{z}_0+n\right)$ pontokat összekötő átlós egyenes által tartalmazott rácspontokon valósul meg. A véletlen határérték pedig felfogható egy véletlen iránynak a $\left(\mathrm{0,}\pi \right)$ szögtartományban.

 

 

3.7. Milyen az eloszlás, ha nem egyenletes?

 

Anélkül, hogy folytonos eloszlásokról precízen szót ejtenénk, az említés szintjén álljon itt, hogy míg két szín esetén a legegyszerűbb (egy piros, egy zöld golyóval való indítás) esetben egyenletes eloszlást kapunk a limeszben, addig általános ($p_0$ piros, $z_0$ zöld kezdeti állapot) esetben az úgynevezett Béta eloszláscsalád $p_0$-tól és $z_0$-tól függő tagjához jutunk.

 

 

3.6. feladat. A korábbi feladat során megírt programot is tegyük alkalmassá $p_0$ és $z_0$ különböző értékeinek kezelésére! A Béta eloszláscsalád tagjainak hozzávetőleges képét így fel is rajzolhatjuk. Milyen változást figyelhetünk meg a hisztogramon, ahogy $p_0$ és $z_0$ értékét változtatjuk? $($Néhány eset elméleti képét lásd az 5. ábrán.)

 

 

5. ábra. Béta eloszlás képei különböző paraméterek mellett

 

Érdekes megfigyelni, milyen hatása van annak, ha kezdetben ugyanannyi piros és zöld golyót teszünk a dobozba, de nem egyet-egyet, hanem például ötöt-ötöt, vagy húszat-húszat. A határérték-hisztogram egyre csúcsosabbá válik. Ez is azt sejteti, hogy konvergál a folyamat: minél nagyobb $p+z$, annál kevésbé távolodik el $R_n$ a kezdeti $R_0=\frac{p}{p+z}$ értéktől, még akkor is, ha $n$ már nagyon nagy.
Az elnevezés említése kedvéért álljon itt az is, hogy ha több, előre rögzített számú ($K$ db) színnel indítunk, akkor az arányok vektora, amint $n$-nel a végtelenbe tartunk, az úgynevezett Dirichlet-eloszláscsalád kezdeti állapottól függően paraméterezett tagjához tart.

 

 

Hivatkozások

[1]	William Feller, Bevezetés a valószínűségszámításba és alkalmazásaiba. Műszaki Könyvkiadó (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).

 

${\displaystyle \begin{array}{c}\hfill {\displaystyle \text{<span style="font-weight: bold;">Rudas Anna</span><br><span style="font-size:12px;">Budapesti Műszaki és Gazdaságtudományi Egyetem<br></span><span style="font-size:12px;">Matematika- és Számítástudományok Doktori Iskola<br></span><span style="font-size:12px;"><span style="font-family: monospace; font-size: 120\%;">rudasa@math.bme.hu</span></span>}}\hfill \end{array}}$

²A cikkben szereplő szimulációkat Python nyelven írtam, a kód szerkesztéséhez és futtatásához Eclipse-t használtam (Pydev modullal), a képek megjelenítéséhez pedig Gnuplot-ot. Ezek mindegyike ingyen hozzáférhető.