Eötvös Loránd Tudományegyetem Természettudományi Kar
Antal Edina A véges állapotterű Markov-láncok keverési ideje és alkalmazásai BSc Szakdolgozat Matematika BSc Alkalmazott matematikus szakirány
Témavezető: Backhausz Ágnes Valószínűségelméleti és Statisztika Tanszék
Budapest, 2016
Köszönetnyilvánítás Köszönöm Édesanyámnak, hogy mindig elhitette velem, hogy mindenre képes vagyok. Köszönöm Édesapámnak, hogy mindig, minden helyzetbe én voltam a legjobb és legokosabb a számára. Köszönöm Húgomnak, hogy hiszi, hogy számomra nincs lehetetlen. Köszönöm Nagymamámnak, hogy minden egyes megmérettetésem előtt elmondott értem egy imát. Köszönöm barátaimnak, hogy a "Hogy áll a szakdoga?" és az "Úgy is sikerülni fog!" mondataikkal nem hagyták hogy lankadjon a figyelmem és folyamatos lelki erőt nyújtottak. És végül, de nem utolsó sorba köszönettel tartozom témavezetőmnek, Backhausz Ágnesnek, hogy mindig szakított rám időt, és minden apró vagy komolyabb kérdésemre türelemmel, illetve legnagyobb hozzáértéssel válaszolt, és a lehető legtöbb segítséget nyújtotta.
2
Tartalomjegyzék Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Markov-láncok
4 5
1.1. Markov-lánc bevezetése . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2. Irreducibilis és aperiodikus láncok és megállási idő . . . . . . . . . . . . . . 11 1.2.1. Kupongyűjtő probléma . . . . . . . . . . . . . . . . . . . . . . . . . 14 2. Markov-láncok keverési ideje
16
2.1. Keverési idő . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2. Erős stacionárius idő és keverési idő korlátja . . . . . . . . . . . . . . . . . 22 3. Kártyakeverés
24
3.1. Szimmetrikus csoportok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2. Keverések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.1. Csere keverés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.2. Top-to-random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.3. Összepörgetéses keverés (Riffle shuffle) . . . . . . . . . . . . . . . . 29 3.3. Inverziók száma szimulációkkal
. . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1. Csere keverés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.2. Top-to-random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.3. Összepörgetéses keverés . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.4. Függelék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3
Bevezetés A Markov-lánc diszkrét sztochasztikus folyamat, mely rendelkezik a Markov tulajdonsággal. Ez nem más mint az a sajátosság, hogy jövőbeli állapot csak a jelen állapottól függ és a múltbeliektől nem. A Markov tulajdonságot a mindennapi életben is észrevehetjük: az érmedobásnál a következő dobás kimenetelét nem befolyásolja az előző pár dobás. Illetve vannak komolyabb területek, ahol nagyon fontos és hasznos a Markov-láncok használata: gazdaságban például a tőzsdén, informatikában a beszédfelismerésnél, matematikai biológiában a génkeveredésnél, illetve egy igen érdekes területen is, a szerencsejátékban. A szakdolgozatom a Markov-láncok bevezetésén és alap definíciók megismertetésén túl a kártyakeverés matematikájáról szól. A fő kérdés: Hányszor kell megkevernünk a paklit, hogy a kártyák valóban véletlenszerű sorrendben legyenek? Egy matematikus szemében ez a kérdés nagyon pontatlan, hisz mit jelent az, hogy valóban véletlenszerű sorrend? Illetve mit értünk keverés alatt? Hogy az első kérdésre választ kapjunk meg kell ismernünk a Markov-láncokat, illetve tulajdonságaikat.(1. fejezet) Illetve ezeken kívül a keverési idő bemutatására is szükség van, melyhez a tejes variációs távolság és a konvergencia tétel elengedhetetlen.(2. fejezet) A második kérdésre három különböző választ is láthatunk. A szakdolgozat második felében az addigi tudásunkat három különböző kártyakeverési módszeren alkalmazzuk. (3. fejezet) Az első a Cserés keverés, mely a hétköznapokban kevésbé népszerű. A pakliból kiválasztunk két lapot és felcseréljük. A második a Top-to-random keverés, ahol a legfelső lapot levesszük és a pakliba egy tetszőleges helyre tesszük vissza. A harmadik a leggyakorlatiasabb és legismertebb, az Összepörgetéses keverés, mely a pókerasztaloknál is használt technika. A keverés neve sokatmondó, hisz a paklit két részre osztjuk és összepörgetjük. Végül a keveréseket R-ben írt szimulációs programokkal is bemutatom. 4
1. fejezet Markov-láncok 1.1.
Markov-lánc bevezetése
A következő fejezet [2] és [3] könyveken alapszik. A Markov-lánc valószínűségi változók egy sorozata, ahol a i + 1. változó állapotának eloszlását csak az i. változó határozza meg. Ezt Markov tulajdonságnak nevezzük. 1.1.1. Definíció. Legyen Ω={x1 , x2 , x3 , . . . } megszámlálható állapottér és X1 , X2 , . . . valószínűségi változók. Ekkor (X1 , X2 , . . . ) sorozat Markov-lánc, ha teljesül rá a Markov tulajdonság: P (Xt+1 = xt+1 |Xt = xt , Xt−1 = xt−1 . . . X1 = x1 ) = P (Xt+1 = xt+1 |Xt = xt )
(1.1)
minden t = 1, 2 . . . -re és x1 , . . . , xt+1 ∈ Ω-ra. 1.1.2. Megjegyzés. Az előző állítás csak az elsőrendű Markov-láncok esetében érvényes. Az n-ed rendű lánc esetében az i + 1. változó állapotának eloszlását az őt megelőző n darab változó határozza meg. A dolgozat során csak elsőrendű Markov-láncokkal fogunk foglalkozni. Minden Markov-lánchoz tartozik egy P átmeneti valószínűség mátrix, mely megmutatja hogy az egyes állapotokat mekkora valószínűséggel követ egy másik állapot. Pontosabban P egy |Ω| × |Ω| méretű mátrix, melynek a ij. eleme megmutatja a P (Xt+1 = i|Xt = j)
(1.2)
valószínűséget. A P mátrix sztochasztikus mátrix, mivel sorai eloszlások, az i. sora az Xt+1 eloszlása abban az esetben ha Xt = i. 5
1.1.3. Megjegyzés. Q n × n-es mátrix sztochasztikus, ha minden sorösszege egyenlő eggyel. n X
qij = 1
i = 1, . . . , n
(1.3)
j=1
Most a P egy lépéses átmeneti valószínűség mátrix, de a P segítségével akár t lépéssel későbbi állapot valószínűségét is megkaphatjuk. Ezt t lépéses átmeneti valószínűség mátrixnak hívjuk, és a P hatványozásával kapjuk meg. 1.1.4. Definíció. P legyen az átmeneti valószínűség mátrixa,az (X1 , X2 , . . . ) Markovlánchoz, ekkor P t , ahol t > 0 egész, a t-lépéses átmeneti valószínűség mátrixa. (t)
P t i. sorának j. elemét jelölje aij , vagyis (t)
aij = P (Xk+t = j|Xk = i).
(1.4)
Most egy egyszerű példán bemutatjuk hogy a gyakorlatban, hogy is néznek ki az eddig definiáltak. 1.1.5. Példa. A tudósok egy egeret egy labirintusba zárnak. A labirintus csak kétirányú útelágazásokból áll, azaz minden elágazásnál vagy jobbra, vagy balra tud menni.(1.1 ábra)
1.1. ábra. Az egér labirintusa A példánk a véletlen bolyongáshoz hasonlít, vagy felfele vagy lefele halad tovább a görbe, csak jelen esetben ez jobb és bal elágazás. Láthatjuk, hogy a véletlen bolyongáshoz hasonlóan az egyes elágazások megfigyelése is Markov-láncot alkot. Tehát az Ω állapottér a két 6
irányból áll. Ω ={j,b}, (X0 , X1 ....Xn ) pedig az egyes elágazásokat, illetve abban választott irányt jelölik. Tehát egy lehetséges állapotsorozat a következő: j b b j b j j . . . Ismerjük annak a valószínűsége hogy jobboldali elágazásból az egér balra megy, és annak is hogy egy baloldali elágazásból jobbra fordul. P {X1 = b|X0 = j} = p,
(1.5)
P {X1 = j|X0 = b} = q,
(1.6)
Ekkor fel tudjuk írni az átmeneti valószínűség mátrixát ennek a Markov-láncnak. ! P (j, j) P (j, b) P = P (b, j) P (b, b) Tehát ha beírjuk az ismert valószínűségeket, illetve figyelemben vesszük hogy P sztochasztikus, azaz P {X1 = j|X0 = j} = 1 − p,
(1.7)
a következőt kapjuk.
P =
1−p
p
q
1−q
! .
Az első sor Xt+1 -re vonatkozó feltételes eloszlást adja meg Xt = j feltételre, a második sor pedig Xt = b-re. Tegyük fel hogy az egér a legelső elágazásnál jobbra ment. Ekkor láttuk hogy annak a valószínűsége, hogy balra fordul: p, annak hogy újra jobbra: 1 − p. Szükségünk van egy kezdő eloszlásra is, mivel az első elágazásnál nem tudunk előző állapotból következtetni arra, hogy melyiket választja. A mi esetünkben, legyen az (1, 0). Ez azt jelenti hogy a nulladik elágazásnál biztos jobbra fordul. Nézzük a kétlépéses átmenetet, vagyis hogy ha először jobbra fordulunk milyen eloszlást kapunk a második elágazásra nézve. P {X2 = j|X0 = j} = (1 − p)(1 − p) + pq;
(1.8)
P {X2 = b|X0 = j} = (1 − p)p + p(1 − q).
(1.9)
Legyen µ vektor a t. elágazás állapotának eloszlása ,ha a kezdő eloszlás (1, 0) (következőekben röviden t. eloszlás). Tehát biztos hogy a nulladik elágazásnál jobbra fordul az egér. 7
µt := {P (Xt = j|X0 = j), P (Xt = b|X0 = j)}
(1.10)
Most, hogy ismerjük a kezdő eloszlást, illetve az átmeneti valószínűség mátrixot, ki tudjuk számolni a t. eloszlást is, mivel a t + 1. eloszlást megkaphatjuk a t. eloszlás és a P szorzataként is. µt = µt−1 P
(t > 1).
(1.11)
Ezt pedig rekurzívan vissza tudjuk vezetni µ0 -ra: µt = µ0 P t .
(1.12)
Tehát láthatjuk, hogy a t. eloszlást megkaphatjuk a kezdeti eloszlás és a t-lépéses átmeneti valószínűség mátrix szorzataként.
Mi történik, ha t-vel végtelenbe tartunk? Kérdés, hogy van-e korlátja a µt -knek,ami egyben azt is jelenti hogy megfelelően sok lépés utána a µt már nem változik. 1.1.6. Definíció. µt (1.11)-ben definiált eloszlás, ekkor lim µt = π.
(1.13)
t→∞
π-t stacionárius eloszlásnak nevezzük, mely teljesíti a következőt: π = πP
(1.14)
Kiszámolható hogy ekkor π(j) =
q p+q
p p+q
(1.15)
q p p p+ (1 − q) = . p+q p+q p+q
(1.16)
π(b) =
Hiszen, q p q (1 − p) + q= ; p+q p+q p+q Most újabb változót definiálunk: ∆t = µt (j) − 8
q p+q
(1.17)
A ∆t a µt és a π távolságát jelöli a t. lépésben. A t + 1. lépésben a ∆-t az előző lépésből a következőképpen számolhatjuk ki: ∆t+1 = µt+1 −
q q q = µt P − = µt (j)(1 − p) + µt (b)q − = (1 − p − q)∆t (1.18) p+q p+q p+q
Tudjuk hogy a p, q ∈ [0, 1] így levonhatóak a következőek: lim µt (j) = π(j)
lim µt (b) = π(b)
t→∞
t→∞
(1.19)
Tehát már ismerjük a π stacionárius eloszlást, mely a µt limesze a végtelenben, egy kétállapotú Markov-lánc esetén. Mit tudhatunk n állapot esetén? Egyértelmű, ha µ0 = π, akkor minden t-re a µt = π, azaz ha a stacionárius eloszlás a kezdeti eloszlás, akkor végig stacionárius eloszlásban marad. De általános n állapotú Markov lánc esetében is igaz az előbbi 1.14 képlet, mellyel egyenértékűek a következők: π(y) =
X
π(x)P (x, y)
∀y ∈ Ω
(1.20)
x∈Ω
1.2. ábra. Bolyongás a gráfon 1.1.7. Példa. Nézzünk egy egyszerű véletlen bolyongást egy konkrét G=(V,E) gráfon (1.2. ábra), ahol V a csúcsokat jelöli, |V|=n, az E az élek halmaza, tehát E ⊂ {{x, y} : x, y ∈ V, x 6= y}. Ha {x, y} ∈ E, tehát x és y szomszédok, azt a következőképpen jelöljük: x ∼ y. 9
Egy csúcs foka a szokásos módon a csúcs szomszédainak számát jelenti. Ekkor az egyszerű véletlen bolyongás a G-n egy Markov lánc, melynek állapottere a V, a csúcsok halmaza, és átmeneti válószínűség mátrixa
P (x, y) =
1 deg(x)
0
ha x ∼ y; különben.
Konkrétan a G gráf esetében(1.2 ábra) 0 0 0 1 0 0 0 0 1 1 2 2 P = 0 0 0 0 1 1 1 0 0 1 3 3 3 0 31 13 13 0
Tetszőleges y ∈ V csúcsra a következőt tudjuk: X
deg(x)P (x, y) =
x∼y
x∈Ω
Egyértelmű, hogy
P
x∈V
X deg(x) deg(x)
= deg(y)
(1.21)
deg(x) = 2|E|, hisz minden él pontosan két csúcsot köt össze.
Ebből adódóan, illetve az 1.20 egyenletből fel tudjuk írni a következőt π(y) =
deg(y) 2|E|
(1.22)
A G gráf esetében π=
1 2 1 3 3 , , , , 10 10 10 10 10
(1.23)
t → ∞ esetén nem csak az eloszlások változását, de az átmeneti valószínűség mátrixot is megfigyelhetjük. Az (1.12) összefüggés ismeretében láthatjuk, hogy µt változását a 1.1.4 Definícióból ismert t-lépéses átmeneti mátrixszal és a kezdő eloszlással is kifejezhetjük. Legyen Q = lim P t . A kérdés hogy mi jellemzi a Q-t. t→∞
Láthattuk, hogy a 1.1.5 példabeli P mátrix első sora π-hez tart, tehát a jobb oldali elágazásból a következő elágazásra vett eloszlás tart a π-hez, de hasonló számolások után láthatjuk, hogy a bal oldali elágazás esete is hasonló. Tehát általánosított esetben Q egy olyan n × n-es mátrix, melynek minden sora a stacionárius eloszlás. 10
A stacionárius eloszlás létezéséről és egyértelműségéről, a következő fejezetben még említést teszünk.
1.2.
Irreducibilis és aperiodikus láncok és megállási idő
Az irreducibilitás és aperiodicitás két egyszerű de hasznos tulajdonság. Egy Markov-lánc irreducibilis, ha bármelyik két állapot esetén eljuthatunk az egyik állapotból a másikba valahány lépés alatt. 1.2.1. Definíció. Egy Markov-lánc irreducibilis,(P a hozzá tartozó átmeneti valószínűség mátrix) ha minden x, y ∈ Ω létezik t egész, melyre P t (x, y) > 0. Az aperodikus Markov-lánc definiálásához, először is a periodikust kell megismernünk. 1.2.2. Definíció. Legyen P átmeneti valószínűség mátrix, τ (x) = {t ≥ 1 : P t (x, x) > 0} Ekkor a Markov-lánc periódusa a τ (x) halmaz legnagyobb közös osztója. Tehát ha annak a valószínűsége ,hogy t lépés után visszatérünk a kezdő állapotba, nagyobb mint 0, akkor a lánc periodikus. 1.2.3. Állítás. Ha P irreducibilis, akkor lnko(τ (x)) = lnko(τ (y)) ∀x, y ∈ Ω. Az alábbi állítás arról szól, hogy az előző definíció nem függ az állapottól irreducibilis lánc esetén. Bizonyítás. Legyen P irreducibilis és x, y rögzített állapotok. Ekkor létezik l és k, melyre P l (x, y) > 0 és P k (y, x) > 0. Legyen m = k + l. Ekkor m ∈ τ (x) ∩ τ (y), illetve τ (x) ⊂ τ (y) − m, ahol lnko(τ (y)) osztja a τ (x) minden elemét. Ebből adódik hogy lnko(τ (x)) ≤ lnko(τ (y)). Mivel az állapotok felcserélhetjük, akkor azt kapjuk lnko(τ (x)) ≤ lnko(τ (y)). 1.2.4. Definíció. A Markov-lánc aperiodikus, ha ∀x ∈ Ω periódus 1. A 1.2.3 és 1.2.4-ből következik a következő állítás. 1.2.5. Állítás. Ha P irreducibilis és aperodikus átmeneti valószínűség mátrix, létezik legalább egy r egész szám, melyre P r (x, y) > 0 ∀x, y ∈ Ω
11
1.3. ábra. Páratlan illetve páros körön bolyongás 1.2.6. Példa. Egy egyszerű példa a véletlen bolyongás az n-körön. Először is definiáljuk a véletlen bolyongást a körön. Legyen ω = 0, 1, . . . , n − 1, tehát a maradékosztályok mod n-re. Az átmeneti valószínűség mátrix pedig a következő:
P (j, i) =
1 2 1
2 0
ha i ≡ j + 1
mod n;
ha i ≡ j − 1
mod n;
különben
Az állapotok a kör egyes csúcsai. Tehát (Xt ) Markov-lánc véletlen bolyongás az n-körön, ami megfeleltethető az érmedobásnak is. Tehát ha az érme feldobás után fej lesz akkor óramutatóval megegyező irányba megyünk, ha írás, akkor az óramutatóval ellentétes irányba lépünk egyet. Ebből adódóan minden n ≥ 1 esetén a Markov-lánc irreducibilis. Ha a kör páros hosszú, akkor periodikus, mivel lnko(t : P t (x, x) > 0) = 2. Viszont egy páratlan hosszú kör esetén a Markov-lánc aperodikus lesz. 1.3 ábra De ez a feladat módosítható, ha azt szeretnénk, hogy minden n-re aperodikus legyen. Az átmeneti valószínűség mátrix a következő lesz:
12
P (j, i) = P (j, i) = P = P (j, i) = 0 Vagyis
1 2
1 4
ha i ≡ j + 1
1 2
ha i ≡ j
1 4
ha i ≡ j − 1
mod n;
mod n; mod n;
különben
valószínűséggel helyben marad, különben úgy lép mint az előbb.
A következőekben az elérési, illetve visszatérési időt fogjuk definiálni, mely a stacionárius eloszlás létezéséről szóló tételhez (1.2.9 tétel) szükséges. 1.2.7. Definíció. Legyen τx := min{t ≥ 0, Xt = x}
(1.24)
τx+ := min{t ≥ 1, Xt = x}
(1.25)
Ekkor τx az x elérési ideje. 1.2.8. Definíció. Legyen
Ekkor X0 = x esetén, τx+ az első visszatérési ideje x-nek. 1.2.9. Tétel. Legyen P egy irreducibilis Markov-lánc átmeneti valószínűség mátrixa, ekkor • egyértelműen létezik π eloszlás Ω-n, melyre igaz, hogy π = πP és π(x) > 0 minden x ∈ Ω-ra • π(x) =
1 Ex (τx )
Ezzel befejeztük a stacionárius eloszlás ismertetését. A következőekben egy érdekes problémát ismerhetünk meg, mely Markov-lánccal modellezhető.
13
1.2.1.
Kupongyűjtő probléma
Maga a probléma kitűzése a következő: n-féle kupon van. Egy urnában minden típusból van pontosan egy. Visszatevéssel húzhatunk az urnából. Az a kérdés, hogy hányszor kell húznunk, hogy minden típust legalább egyszer kihúzzuk. A probléma modellje legyen egy (Xt ) Markov-lánccal, ahol az egyes Xt az első t lépésben kihúzott kupont fajtájának száma. Ekkor egyértelmű hogy az X0 = 0. Ha már k-féle kupont összegyűjtöttünk, akkor csak n−k-féle hiányzik, de a következő húzásnál még mindig n-féle kupont húzhatunk ki, tehát P (Xt+1 = k + 1|Xt = k) = P (Xt+1 = k|Xt = k) =
n−k n
(1.26)
k n
(1.27)
1.2.10. Tétel. n-féle kupon esetén, ha visszatevéssel húzunk a típusokból, akkor E(τ ) = n
n X 1 k=1
k
,
(1.28)
ahol τ jelöli az időt, melyre az összes kupont összegyűjtöttük. Bizonyítás. Mivel τ megállási idő, ezért τ = τn = τ1 + (τ2 − τ1 ) + .. + (τn − τn−1 ). τk jelöli az időt, mikor az első k-féle kupon össze van gyűjtve. (τk − τk−1 ) geometriai eloszlású valószínűségi változó, mégpedig p =
n−k+1 n
paraméterrel. Mivel az első k − 1 fajta kupon
kihúzása után n − (k − 1) hiányzó kupon van, és ekkor az esélye annak hogy a következő egy új kupon legyen
n−k+1 , n
E(τ ) =
tehát E(τk − τk−1 ) =
n X
E(τk − τk−1 ) =
k=1
n X k=1
n . n−k+1
Ebből
n X n 1 =n n−k+1 k k=1
(1.29)
Ez egy hasznos tétel, de sokkal többet tudunk mondani τ várható értékéről, ha felP használjuk az analízisbeli összefüggést, miszerint | nk=1 k1 −log n| ≤ 1, amiből azt kapjuk, hogy |E(τ ) − n log n| ≤ n. 1.2.11. Tétel. Az előző tételben definiált τ , illetve tetszőleges c>0 esetén, P (τ > dn log n + cne) = e−c .
14
(1.30)
Bizonyítás. Legyen Ai az az esemény, mely azt jelenti, hogy az első dnlogn+cne húzásra nem húztuk ki az i. kupont. Ekkor P (τ > dn log n + cne) = P
[ n
≤
Ai
i=1
Ekkor az összeg minden tagja (1− n1 )dnlogn+cne (hisz
n X
P (Ai ).
(1.31)
i=1 1 n
a valószínűsége hogy a következő
az i. kupon), és mivel a húzások független, ezért
P {τ > dnlogn+cne} = P
[ n i=1
Ai
dnlogn+cne n X nlogn+cn 1 ≤ ≤ ne− n = ne−logn e−c = e−c . 1− n i=1 (1.32)
15
2. fejezet Markov-láncok keverési ideje 2.1.
Keverési idő
Egy véges állapotterű irreducibilis, aperodikus Markov-lánc egyes állapotainak eloszlása π-hez, a stacionárius eloszláshoz tart. A Markov-lánc keverési ideje az az időpont, mikor a jelen időpontban vett eloszlás és a stacionárius eloszlás távolsága "elég kicsi". Tehát a konvergencia gyorsaságára vagyunk kíváncsiak. Mielőtt a konvergenciáról bármit is tudnánk mondani, előtte meg kell ismerkednünk az eloszlások teljes variációs távolságával illetve az eloszlások csatolásával. A fejezetben szereplő definíciók és tételek a [2] könyvben szerepelnek.
A konvergencia gyorsaságának vizsgálatához szükséges egy metrika, mellyel meg tudjuk mérni az eloszlások távolságát. Erre szolgál a teljes variációs norma. 2.1.1. Definíció (Teljes variációs norma). Legyen µ és ν valószínűségi eloszlás az Ωn. Ekkor kµ − νkT V = max | µ(A) − ν(A) | . A⊂Ω
(2.1)
Tehát a definíció szerint µ és ν közötti távolság: az állapottéren vesszük azt az eseményt, melyre a két eloszlás szerinti valószínűségek különbsége maximális. Ez a távolság a két eloszlás távolsága is.
16
2.1.2. Példa. Nézzünk a korábbi példánkat, ahol az egerünk p valószínűséggel ment bal elágazásból egy jobboldalira, q valószínűséggel ment jobb elágazásról balra. Tehát az átmeneti valószínűség mátrixa 1−p
p
q
1−q
! ,
a stacionárius eloszlása pedig π=
p , p+q
q p+q
.
Tegyük fel hogy a kezdeti eloszlásunk, µ0 = (1, 0), azaz mindenképp jobbra fordul először az egér. Tehát ezen feltételek mellett a teljes variációs távolságra vagyunk kíváncsiak. A (2.1) képlet alapján: kµt − πkT V = ∆t = P t (j, j) − π(j) = π(b) − P t (j, b),
(2.2)
ahol a ∆t korábbról ismert. Az egyenlőség könnyen látható hisz jelen esetben két állapot van, tehát Ω = {j, b}, illetve négy lehetséges esemény van: (j,j),(j,b),(b,j),(b,b). Láttuk (1.17)-ben, hogy ∆t = (1 − p − q)t ∆0 .
(2.3)
Tehát a példa alapján arra a következtetésre jutunk, hogy két állapot esetén a Markov-lánc igen gyorsan, exponenciálisan tart a stacionárius eloszláshoz. A következőkben a teljes variációs távolságnak fontos tulajdonságait fogjuk látni. 2.1.3. Állítás. Legyen µ és ν két valószínűségi eloszlás az Ω-n. Ekkor kµ − νkT V =
1X | µ(x) − ν(x) | . 2 x∈Ω
(2.4)
Bizonyítás. Osszuk fel az állapotteret két részre! Az egyik, melyre a továbbiakban szükségünk van, azon x-ek halmaza, ahol µ(x) ≥ ν(x), ez a halmaz legyen B halmaz. Az A ⊂ Ω egy tetszőleges esemény. Ekkor µ(A) − ν(A) ≤ µ(A ∩ B) − ν(A ∩ B) ≤ µ(B) − ν(B).
(2.5)
Az egyenlőtlenség első része nyilván igaz, hiszen B pontosan az a halmaz volt, melyre a két valószínűség különbsége pozitív, tehát ha A tartalmaz B-n kívüli elemeket, akkor ezek csak 17
2.1. ábra. B = {x : µ(x) > ν(x)} Tehát az I. terület µ(B) − ν(B), az II. ν(B c ) − µ(B c ) ( [2] 4.1 ábra) csökkentik a különbséget. Másrészt az A∩B egyértelműen kisebb vagy egyenlő mint maga a B. Ilyen megfontolásból az is nyilvánvaló, hogy a komplementerére az egyenlőtlenség (−1)-szerese, azaz ν(A) − µ(A) ≤ ν(B c ) − µ(B c )
(2.6)
teljesül. Láthatjuk hogy mind a (2.5), mind a (2.6) egyenletek bal oldalának normája megegyezik, ebből következik, hogy 1 1X kµ − νkT V = (µ(B) − ν(B) + ν(B c ) − µ(B c )) = | µ(x) − ν(x) | 2 2 x∈Ω
(2.7)
Az előző bizonyításból következik az alábbi két állítás is. 2.1.4. Állítás. kµ − νkT V =
X
(µ(x) − ν(x)).
(2.8)
x∈Ω,µ(x)≥ν(x)
2.1.5. Állítás. Ha µ,ν,η valószínűségi eloszlások, akkor teljesül a háromszög egyenlőtlenség kµ − νkT V ≤ kµ − ηkT V + kη − νkT V .
(2.9)
µ és ν eloszlások csatolása, (X, Y ) tetszőleges valószínűségi változók csatolása, ahol X eloszlása µ, Y eloszlása pedig ν. A csatoláshoz nézzünk egy nagyon egyszerű, és népszerű példát. 18
2.1.6. Példa (Pénzérme feldobás). Tehát µ év ν eloszlása a pénzérme feldobás eloszlásával egyezzen meg. Feldobunk egy érmét, mely
1 2
valószínűséggel fej, és ugyanennyi
valószínűséggel írás. A µ és ν egyik csatolása: azt mondjuk hogy x, y ∈ {0, 1} esetén P {X = x, Y = y} = 14 , mivel annak a valószínűsége hogy az X 1 vagy 0 egyaránt 12 , illetve Y -ra is ugyan ez áll fent, és mivel függetlenek a valószínűségek szorzódnak. Egy másik lehetőség, hogyha azt mondjuk X=Y. Ekkor P {X = Y = x} =
1 2
(x ∈ {0, 1}), hisz vagy mind a kettő 1 vagy 0.
Vagyis P {X 6= Y } = 0. Legyen ϕ az együttes eloszlása (X, Y )-nak az Ω × Ω-n. Ekkor X
ϕ(x, y) =
y∈Ω
X
P {X = x, Y = y} = P {X = x} = µ(x),
(2.10)
P {X = x, Y = y} = P {Y = y} = ν(x).
(2.11)
y∈Ω
illetve X
ϕ(x, y) =
x∈Ω
X x∈Ω
Visszatérve előző példánkra, ϕ eloszlással kifejezve: 1 ϕ1 (x, y) = , x, y ∈ {0, 1}, 4 1 ha (x, y) ∈ {(0, 0), (1, 1)}; ϕ2 (x, y) = 2 0 ha (x, y) ∈ {(0, 1), (1, 0)}.
illetve
(2.12)
Ha két eloszlás nem azonos, akkor nem lehetséges hogy mindenhol azonosak legyenek, viszont a teljes variációs távolsággal meg tudjuk mondani, hogy a legjobb csatlás esetén mennyi arra a valószínűség, hogy X és Y különböző. 2.1.7. Állítás. kµ − νkT V = min{P (X 6= Y ) : (X, Y ) a µ és a ν csatolása}
(2.13)
Most hogy mindent ismerünk, kimondhatjuk a konvergenciatételt: 2.1.8. Tétel (Konvergenciatétel). Legyen P egy irreducibilis és aperodikus átmeneti valószínűség mátrix, és legyen π a stacionárius eloszlása. Ekkor létezik α ∈ (0, 1) és C>1, melyekre max kP t (x, ·) − πkT V = Cαt x∈Ω
19
minden t-re.
(2.14)
A konvergencia tétel azt mondja ki, hogy az eloszlások exponenciális sebességgel tartanak a stacionárius eloszláshoz. Bizonyítás. A 1.2.5 állítás alapján létezik egy r, melyre P r (x, y) pozitív lesz minden x, y-ra. Legyen Π egy mátrix, melynek |Ω| sora van és a soraiban a π stacionárius eloszlás szerepel. Legyen δ > 0 kellően kicsi, ekkor Ω végessége miatt P r (x, y) ≥ δπ(x)
∀x, y ∈ Ω.
(2.15)
Legyen θ = (1 − δ), ekkor P r = (1 − θ)Π + θQ
(2.16)
Q a megfelelő sztochasztikus mátrixra, mellyel az egyenlőtlenség egyenlő lesz. Kisebb számolásokkal bizonyítható hogy ha S sztochasztikus mátrix akkor SΠ = Π, illetve ΠS = Π minden S-re, melyre πS = π. Indukció segítségével megmutatjuk, hogy P rk = (1 − θk )Π + θk Qk
(2.17)
minden k ≥ 1 esetén. Ha k = 1, akkor 2.16 esetben vagyunk, tegyük fel hogy k = n-re (2.17) igaz, ekkor az indukciós lépés a következő P r(n+1) = P rn P = [(1 − θn )Π + θn Qn ]P r
(2.18)
A (2.16) segítségével a következő módon alakítjuk át: P r(n+1) = P rn P = (1 − θn )ΠP r + (1 − θ)θn Qn Π + θn+1 Qn Q
(2.19)
Most felhasználjuk hogy P r illetve Qn sztochasztikus mátrix, ekkor ΠP r = Π, illetve Qn Π = Π , így a következőt kapjuk: P r(n+1) = P rn P = (1 − θn+1 )Π + θn+1 Qn+1
(2.20)
És tényleg a (2.17)-et kaptuk k = n + 1 esetén, tehát minden k-ra igaz a állítás. Ha P j szorozzuk és átrendezzük az (2.17) egyenletet, akkor P rk+j − Π = θk (Qk P j − Π).
20
(2.21)
Nézzük az x0 sorára az egyenletet. Mivel a jobb oldal második tényezője maximum egy lehet, így igaz a következő. kP rk+j (x0 , · ) − πkT V ≤ θk
(2.22)
Definiáljuk a d(t) mennyiséget, mely a konvergenciatételben szereplő egyenlet bal oldalát jelöli, tehát d(t) := max kP t (x, ·) − πkT V . x∈Ω
(2.23)
Ezen felül (x, y) állapotpárokra is definiálhatjuk . ¯ := max kP t (x, ·) − P t (y, ·)kT V d(t) x∈Ω
(2.24)
A következő összefüggéseket ismerjük a két függvényre: • ¯ ≤ 2d(t) d(t) ≤ d(t)
(2.25)
¯ + t) ≤ d(s) ¯ d(t) ¯ d(s
(2.26)
•
• ¯ ¯ k d(kt) ≤ d(kt) ≤ d(t)
k, t ≥ 0
(2.27)
A következőekben bevezetjük a keverési idő, vagyis annak az időpontnak a jelölését, ahol már az eloszlás egy adott hibánál közelebb van a stacionárius eloszláshoz. tmix (ε) := min{t : d(t) < ε}
(2.28)
A következőkben ha nem jelöljük az ε-t, akkor ε = 41 -et értünk. 2.1.9. Állítás. Ha l egy nem negatív konstans, akkor ¯ mix (ε)) ≤ d(t ¯ mix (ε))l ≤ (2ε)l d(ltmix (ε)) ≤ d(lt
(2.29)
Tehát mint fentebb említettük ε=1/4, ezért d(ltmix ) ≤ 2−l 21
(2.30)
2.2.
Erős stacionárius idő és keverési idő korlátja
Az erős stacionárius idő megértéséhez, egy kártyakeverési algoritmust kell megismernünk, a Top-to-random keverést. Ez egy lassú keverési módszer. A módszer annyiból áll, hogy levesszük a felső kártyát és véletlenszerűen visszatesszük a pakliba. A kérdés az, hogy hány lépés után lesz a kártyák sorrendje véletlenszerű. τtop most legyen az az idő, jelen esetben keverések száma, melyre az eredeti legalsó lap a pakli tetejére kerül majd újra a pakliba helyezzük. 2.2.1. Állítás. Legyen (Xt ) véletlen bolyongás Sn -en (az {1, 2, ..n} permutációinak csoportja). Ha adott t időpontban k db kártya van az eredeti legalsó kártya alatt, akkor a k kártya k!-féle sorrendben állhat, és mindegyik permutáció ugyanakkora valószínűséggel következik be. τtop az előbbiekben definiált keverés szám. Ekkor Xτtop eloszlása egyenletes az Sn -en, és τtop független az Xτtop -tól Bizonyítás. t = 0 eset egyértelmű, mivel ekkor egy kártya sincs az eredeti legalsó alatt. Most t 6= 0 időpontban vagyunk. Ekkor két lehetőség van, a t + 1. időpontban vagy bekerül egy kártya az eredeti alsó alá, vagy nem. Ha az első eset következik be, akkor k + 1 helyre kerülhet az új kártya, így (k + 1)!-féle permutáció bármelyike egyforma falószínűséggel bekövetkezhet. A második eset következik be, akkor az alsó k kártya marad az eddigi permutációban.
Tehát a kártyák elrendezése a τtop időpontban egyenletes eloszlású a Sn -en. Ami azt jelenti hogy Xτtop a lánc stacionárius eloszlása.
Ekkor a stacionárius idő és a d(t) kapcsolatáról a következőt tudjuk: 2.2.2. Tétel. Ha τ erős stacionárius idő, akkor d(t) ≤ max Px (τ > t) x∈Ω
2.2.3. Megjegyzés. Az állítást az sx = maxy∈Ω 1 − retében egyszerű bizonyítani.
22
P t (x,y) , π(y)
(2.31) szeparációs távolság isme-
A következőekben a keverési idő tmix (ε) egy alsó korlátját nézzük meg, melyet a 3. fejezetben az inverz összepörgetéses keverés alsó korlátjának megadásánál használjuk fel(3.2.9 tétel). Egy ötlet segítségével írhatjuk fel az alsó korlátot. Az ötlet az, hogy ha a lehetséges állapotoknak egy jelentős részét még nem vette fel a Markov-lánc t lépés utána, akkor t időpontban nincs elég közel az egyenletes eloszláshoz. Legyen (Xt ) egy aperiodikus és irreducibilis Markov-lánc P átmeneti valószínűség mátrixszal. Az állapotterünk az Ω, a stacionárius eloszlás pedig π egyenletes eloszlás Ω felett. Most definiáljuk dki (x) = |{y : P (x, y) > 0}|,
(2.32)
az x fokát (nem gráfoknál használt értelemben), ami azoknak az állapotoknak a száma, amelyekbe x-ből egy lépés alatt eljuthatunk. Illetve definiáljuk ∆ = max dki (x)
(2.33)
x∈Ω
Legyen Ωxt azon állapotok halmaza, melyet x-ből elérhetünk t lépés után. Ekkor egyértelmű, hogy |Ωxt | ≤ ∆t . Ha ∆t < (1 − ε)|Ω|, akkor k P (x, ·) − π kT V ≥ P (x, Ωxt ) − π(Ωxt ) ≥ 1 −
∆t >ε |Ω|
(2.34)
Ez azt jelenti, hogy tmix () ≥
log(|Ω|(1 − ε)) . log ∆
23
(2.35)
3. fejezet Kártyakeverés Eljutottunk a Markov-lánc alkalmazásaihoz, azok közül is az egyik legérdekesebbet, a kártyakeverést nézzük meg. A hátralevő részben különböző technikákkal találkozhatunk és azok keverési idejeit figyeljük meg. A 3.1 és a 3.2 alfejezetbeli definíciók és tételek a [1], [2], [4], [5] könyvekben és cikkekben találhatóak meg.
3.1.
Szimmetrikus csoportok
Keverések előtt egy kis bevezetés szükséges a szimmetrikus csoportokról. Már említettük az Sn -t, mely a szimmetrikus csoport, tehát minden eleme egy n elemű halmaz melyeket sorrendjükben különböztetünk meg, tehát a csoportművelet a kompozíció. A pakli minden lapját sorszámozzuk meg 1-től n-ig, ekkor alkalmazhatjuk a szimmetrikus csoportokat a kártyakeverés során. Tehát az Sn elemei a kártyák sorrendjének is feleltethető meg. Az Sn egységeleme id, melyre id(k) = k, és minden σ ∈ Sn -hez létezik inverz permutáció. Legyen µ a szimmetrikus csoporton vett valószínűségi eloszlás. µ(σ) annak a valószínűsége, hogy σ-t alkalmazzuk keverésként. Ez azt takarja, ha van egy G asszociatív csoportunk egységelemmel és inverzelemmel, akkor a csoportban való véletlen bolyongás egy Markov-lánc G állapottérrel és P (g, gh) = µ(h) átmeneti valószínűség mátrixszal. Ha µ az Sn minden elemét generálja, akkor a lánc irreducibilis, ha µ(id) > 0 akkor pedig aperodikus. Ekkor minden keverésnek a stacionárius eloszlása az egyenletes eloszlás. A pármutációkat úgynevezett ciklusokkal is fel tudjuk írni. A ciklusok olyan diszjunkt 24
csoportok, melyekre teljesül, hogy egy csoportban lévő elemek csak egymással permutálódhatnak, másik csoport elemeivel nem. Például ha σ adott permutáció, mely az (abc) ciklussal egyezik meg, az elemeink, pedig az abcdef , ekkor ez azt jelenti, hogy σ(c) = a, σ(b) = c, σ(a) = b a többi elem pedig helyben marad. Tehát σ(abcdef ) = cabdef . Egy k hosszú ciklust k-ciklusnak nevezünk, speciálisan egy csere 2-ciklus. Az előző esetben (abc) egy 3-ciklus. Egy konkrét példa, ha σ ∈ S5 , akkor i = {12345}, σ a 4. és 1., illetve a 4. és 5. elemek cseréje, vagyis σ = {(45)(41)}, ezt diszjunkt ciklusokkal felírva σ = {(154)}, akkor σ(i) = {42351}. Ha azt mondjuk hogy i egy 5 lapos pakli, akkor a σ permutáció az a keverés, amikor az első kártya az 5. helyre, az 5. kártya a 4. helyre, és a 4. kártya pedig az 1. helyre kerül.
Most egy permutációt generáló algoritmust ismerhetünk meg, amely transzpozíciókat használ. Adott n db kártya sorszámozva. Ekkor legyen σ0 az identitás. Megmutatjuk, hogy hogyan kell a k. permutációból a k + 1.-et generálni. Legyen k = 1, 2, ...n − 1 és legyen Hk egy egyenletes eloszlású szám k és n között, a kártya, mellyel cseréljük az aktuálist. Ekkor az algoritmus a következő: σ (i) ha i 6= k, i 6= Hk , k−1 σk (i) = σk−1 (Hk ) ha i = k, σ (k) ha i = Hk k−1 Ezt a permutációt generáló algoritmust akár egy keverési technikának is tekinthetjük, igaz nem a leggyakorlatiasabb.
A transzpozíciók nem csak permutációk generálára használhatók, de egy permutáció paritását is meghatározzák. Legyen M (σ) előjele a σ ∈ Sn permutáció paritása, ekkor M (σ) =
Y
(σ(j) − σ(i))
(3.1)
1≤i<j≤n
Tehát ha σ0 az identitás, akkor a M (σ0 ) > 0, mivel az összes szám az eredeti helyén van. Ami eredetileg hátrébb volt, tehát nagyobb volt a sorszáma, annak most is nagyobb. Ha a σ1 egyetlen transzpozíció, akkor M (σ1 ) < 0, hisz legyen k < j a két felcserélt lap. 25
Az összes k < h < j-re a h mind a k-val, mind a j-vel inverzióban lesz, tehát ez nem változtatja az M előjelét, viszont maga a k és j is inverzióban van, ami (−1)-el szorozza az eredeti szorzatot. Ha az M pozitív, akkor azt mondjuk, hogy a permutáció páros, ha negatív, akkor páratlan. Tehát M páros ha páros sok transzpozícióból, páratlan, ha páratlan sok transzpozícióból áll. Minden permutáció felírható transzpozíciók kompozíciójaként. Adott egy n-ciklus, ekkor ezt n − 1 transzpozícióból felírhatjuk a következőképp (z1 z2 z3 ...zn ) = (z1 z2 )(z2 z3 )...(zn−1 zn )
3.2. 3.2.1.
(3.2)
Keverések Csere keverés
Korábban a 3.1-ben láthattuk, hogy hogyan állíthatunk elő permutációkat transzpozíciók segítségével. Arról is említést tettünk hogy ezt akár keverési technikaként is értelmezhető. Ekkor fel tudjuk tenni a kérdést, hogy mennyi keverés kell ahhoz hogy megkeverjük a paklit. 3.2.1. Tétel. Legyen Ak és Hk a két kártya a pakliban k időpontban. Ekkor Ak -ra a következőek igazak a k. keverésnél: • Ak -t nem keverjük, tehát helyben hagyjuk (marad), • Ak -t és Hk -t is keverjük , vagyis felcseréljük, vagy Ak = Hk (kever). Legyen τ az az időpont, mikor minden kártya a kever fázison átment. Ekkor τ erős megállási ideje a Markov-láncnak. 3.2.2. Tétel. Ha τ a 3.2.1-ban definiált megállási idő, akkor E(τ ) = 2n(log n + O(n)),
(3.3)
D2 (τ ) = O(n2 )
(3.4)
illetve
26
Bizonyítás. A probléma hasonlít a 1.2.10 Kupongyűjtő problémához, így ahhoz hasonlóan bizonyítjuk. τ = τ0 + τ1 + τ2 + ... + τn−1 , ahol τk azon transzpozíciók száma, melyre a k. kártya is meg lesz keverve. A τk -k függetlenek és geometriai eloszlásúak E(τ ) =
n−1 X k=0
(k+1)(n−k) n2
paraméterrel.
n2 . (k + 1)(n − k)
1 Két ismert összefüggés felhasználásával, miszerint (k+1)(n−k) = Pn 1 j=1 j = log n + O(n) a várható értéket bizonyítottuk.
(3.5) 1 ( 1 n+1 k+1
+
1 ), n−k
illetve
Mivel függetlenek a τk -k ezért szórásnégyzetük összeadható, ekkor az összeg szórásnégyzetét kapjuk. 2
D (τ ) =
n−1 X 1− k=0
(k+1)(n−k) n2 (k+1)(n−k) 2 n2
<
n−1 X k=0
n4 . (k + 1)2 (n − k)2
(3.6)
Ha a szummát két részre bontjuk, a következőt kapjuk:
2
D (τ ) <
X 0≤k
X n4 + (k + 1)2 (n − k)2
n/2≤k
2n4 n4 < n 2 (k + 1)2 (n − k)2 (2)
X 0≤k≤n/2
1 = O(n2 ) 2 (k + 1) (3.7)
Ezzel a szórásnégyzetét is megkaptuk. 3.2.3. Tétel. Cserés keverés esetén egy n lapos paklinál felső határ a keverési időre: tmix ≤ (2 + O(1))n log n.
(3.8)
3.2.4. Tétel. Cserés keverés esetén egy n lapos paklinál alsó határ a keverési időre: n−1 1−ε tmix (ε) ≥ log n . (3.9) 2 6 Ezek a határok elég tágak, de 1981-ben Diaconis és Shahshahani bizonyították, hogy 1 n log n 2
3.2.2.
keverés elég a pakli megkeveréséhez.[5]
Top-to-random
Már találkoztunk ezzel keverési technikával az erős stacionárius idő megismerésénél. Minden keverésnél a legfelső lapot leemeljük és visszahelyezzük a pakliba, egy véletlen helyre. A helyek azonos valószínűséggel választhatjuk. 27
Csak úgy mint a Csere keverésnél, ez a probléma is hasonlít a 1.2.10 Kupongyűjtő problémához. 3.2.5. Tétel ([5] 5.14. tétel). A top-to-random keverés esetén minden n-re a tmix (ε) ≤ n log n + n log ε−1 . Bizonyítás. Ekkor láthatjuk a 1.30 és az 2.2.2 alapján, hogy d(dn log n + nce) ≤ max Px (τ > dn log n + nce) ≤ e−c ,
(3.10)
x∈Ω
vagyis −1
d(dn log n + n log ε−1 e) ≤ max Px (τ > dn log n + n log ε−1 e) ≤ e− log ε x∈Ω
Tehát ez azt jelenti hogy tmix (ε) ≤ n log n + n log ε−1 .
=ε
(3.11)
Bizonyított, hogy tmix = n log n a top-to-random keverés esetén.
A Top-to-random keverés minden lépésben 1 lapot mozgat, a legfelsőt. Ezen kívül több egy lapot mozgató technika van, csakúgy mint a Card-cyclic-to-random, illetve a Card-cyclic-to-random whit relabeling keverés. A két technika hasonló keverési módszer. A Card-cyclic-to-random(CCTR) keverés annyiban tér el a Top-to-random keveréstől, hogy n lapos pakli estén a kártyák kapnak egy állandó címkét, 1-től n-ig, a keverést megelőzően, és a t. keverésnél a t mod n-edik címkéjű kártyát vesszük ki és helyezzük vissza.[1] Az első keverés során előfordulhat hogy egy kártyát többször is megkeverünk, ameddig egy másikhoz nem is nyúlunk, addig ennél keverésnél az n. lépésig biztosan minden kártyát megkevertünk pontosan egyszer. Könnyen azt gondolhatnánk hogy a ez a keverési technika jobb az előzőnél, de mégsem. 3.2.6. Tétel ([1] 1. és 2. tétel). Legyen a paklink n lapos. Ekkor Card-cyclic-to-random keverést használva létezik δ > 0, illetve θ, hogy δ ≤ θ és δn log n ≤ tmix ≤ θn log n. Tehát a keverési ideje a Top-to-random keverési idejével egyezik meg.
28
(3.12)
A harmadik a Card-cyclic-to-random whit relabeling (CCTRWR) keverés. Az előzőhöz haszonló keverési technika. A keverés pontos leírása a [4] cikkben megtalálható. Ezzel a technikával is tmix = n log n. A Csere keveréshez hasonlítva várható volt, hogy a tmix = n log n, hiszen a csere keverésben két lapot mozgatunk, és így
n 2
log n lépés volt szükséges, most fele annyi kártyát
mozgatunk, tehát 2-szer annyi időre van szükségünk.
3.2.3.
Összepörgetéses keverés (Riffle shuffle)
Az összepörgetéses keverés a leggyakrabban használt keverési módszer. A kaszinókban a pókerasztaloknál is ezzel a technikával keverik a kártyákat. Az eljárás lényege, hogy az n lapos kártyacsomagot két részre osztjuk, egyik rész az egyik, másik rész a másik kezünkben, majd "összepörgetjük". Az összepörgetést megfeleltethetjük egy másik folyamatnak amely érthetőbb. Azt mondjuk hogy egy asztalra dobáljuk a lapokat. Először a bal kezünkből dobunk pár lapot, majd a jobb kezünkből párat, majd megint a balból. Ezt addig folytatjuk, ameddig el nem fogynak a kártyák mind a két kezünkből. Többféleképp is lehet matematikailag modellezni az összepörgetést. Legyen V a pakli kettévágásának valószínűségi változója. Tehát az egyik kezünkben az első V db kártya a másikban n − V db kártya van. • V binom(n, 12 ) valószínűségi változó. Ekkor
n M
lehetőség van a kártyák összepörge-
tésére. Előfordulása egyenletes eloszlású. • V az előbbi valószínűségi változó, de a kártyákat egyesével dobáljuk. Tehát ha az a jobb oldali, b pedig a bal oldali kupacban van, akkor annak a valószínűsége hogy a következőnek a-t dobjuk:
a , a+b
annak a valószínűsége hogy b-t:
b . a+b
• Az összepörgetés inverz keverése a harmadik modell. Ekkor a kártyákat megcímkézzük.
1 2
valószínűséggel írunk a címkékre 0-t vagy 1-t. Az 1-eseket felülre rakjuk, a
0-kat alulra. Még egy számot (0 vagy 1) írunk az előző szám mellé a címkére, és az új szám szerint felülre rakjuk az 1-eseket és alulra a 0-kat. Addig folytatjuk, ameddig minden címke nem lesz különböző. (3.1 ábra) Az inverz keverésre vonatkozó tételeket fel tudjuk felhasználni, mivel az inverz és az eredeti eloszlás ugyanolyan gyorsan konvergál a stacionárius eloszláshoz, ami jelenleg az egyenletes eloszlás. Bővebben [2] 4.6 és 8.3 fejezeteiben lehet olvasni róla. 29
3.1. ábra. Inverz összepörgetéses keverés (forrás: http://blackjackassus.com/mathematica/) 3.2.7. Állítás. A τ legyen az inverz összepörgetéses keverések száma, melyre az összes kártya címkéje különböző. Ekkor τ erős megállási idő. 3.2.8. Állítás. n lapos pakli esetén tmix ≤ 2 log2 ( 4n ), ha összepörgetéses keverést alkal3 mazunk. Bizonyítás. Legyen τ az előző állításban definiált. Ha τ ≤ t, az azt jelenti hogy mind az n kártyához különböző címke tartozik t keverés után, tehát n−1 Y k P (τ ≤ t) = 1− t . 2 k=0
(3.13)
Hiszen a kártyáknak egymástól független 2t -féle címkéjük lehet. Annak a valószínűsége, hogy a második címke nem egyezik meg az elsővel (2t − 1)-féleképpen lehetséges. Tehát t
a valószínűsége, hogy különbözőek ( 2 2−1 t ). Ezt folytatjuk n − 1-ig, és ekkor megkapjuk a szorzatot. Legyen t = 2 log2 ( nc ), ekkor az állítás szerint, azt kell bizonyítani, hogy c = 34 . Így 2t = log
n2 . c2
Ekkor vegyük a logaritmusát az egyszerűbb számolásért:
n−1 Y k=0
k 1− t 2
=−
n−1 2 X ck k=0
k +O 2 2 n n
2
3 n 1 c2 n(n − 1) c2 = +O 4 = +O . 2 2n n 2 n (3.14)
Ezután ha e hatványára emeljük, és ∞-ben vesszük a határértékét, akkor lim
n→∞
P (τ ≤ t) c2
e− 2
= 1.
(3.15)
q Legyen c < 2 log( 43 ). Tudjuk, hogy lim P (τ ≤ t) = lim (1 − P (τ > t)). Ekkor az n→∞ n→∞ n előző egyenlőségből és a 2.2.2-ből azt kapjuk, hogy d 2 log2 √ = 14 . Legyen 2 log( 34 ) q c = 34 < 2 log( 43 ), így megkapjuk a várt eredményt, miszerint tmix ≤ 2 log2 ( 4n ), ha 3 ε = 14 . 30
Az összepörgetéses keverésre egy alsó korlátot is tudunk mondani. 3.2.9. Állítás. n lapos pakli és előre meghatározott 0 < ε és δ < 1 esetén, megfelelően nagy n-re tmix (ε) ≥ (1 − δ) log2 n, ha összepörgetéses keverést alkalmazunk. Tehát egy 52 lapos pakli esetén a pakli megkeveréséhez max kb. 12 és min kb. 5 − 6 keverés szüksége, de 1983-ban Aldous megmutatta hogy 23 log2 n keverés kell, ami esetünkben 8 − 9 keverés elég.[2]
3.3.
Inverziók száma szimulációkkal
Most az R segítségével modellezzük a Cserés keverést, a Top-to-random és a Összepörgetéses keverést. A stacionárus eloszlástól vett távolság helyett egy sokkal kézzelfoghatóbb dolgot, az inverziók számát figyeljük meg. 3.3.1. Állítás. Legyen X valószínűségi változó, mely az inverziók száma egy n lapos pak(n) liban egy véletlenszerűen, egyenletesen választott sorrendben. Ekkor E(X) = 22 . Bizonyítás. X-nek egy ekvivalens megfogalmazása: 1 ha az i. és a j. lap meg van cserélve, Xij = 0 különben. P
Xij . Tehát az X az pakliban lévő inverziók száma. Tudjuk, hogy max X = n2 , hisz két kártyát kell kiválasztanunk és felcserélnünk és ezt összesen n2 -féle módon tehetjük meg. Ekkor X :=
1≤i<j≤n
Ekkor keressük az E(X)-et. Mivel a várható érték lineáris leképezés, ezért X E(X) = E(Xij )
(3.16)
1≤i<j≤n
Ekkor csak azt kell kiszámolnunk hogy mennyi E(Xij ), mivel tudjuk hogy X
n 2
-tagú
összeg. Legyen k azon permutációk száma, melyben i. és a j. lap fel van cserélve. A szimmetria miatt tudjuk hogy k azoknak a permutációknak a száma is, ahol nincsenek felcserélve. Így k + k = n!, hisz n! db permutációja van n elemnek. Ekkor k = E(Xij ) =
n! 2
n!
1+
31
n! 2
1 0= . n! 2
n! , 2
(3.17)
Ezzel beláttuk, hogy n 1 E(X) = E(Xij ) = . 2 2 1≤i<j≤n X
(3.18)
Ekkor a tarokk, magyar, és francia kártya esetén:
n E(X)
3.3.1.
22
32
52
115,5
248
663
Csere keverés
A csere keverésnél
n 2
log n a szükséges keverések száma. Tehát ennyi keverés után az inver-
ziószám közelít a várthoz, mivel az egyes keveréseknél a stacionárius eloszlás az egyenletes eloszlás. Tehát alkalmazhatjuk 3.3.1 állítást. A tarokk kártya 22 lapos, tehát közel 15 keverés szükséges a pakli megkeveréséhez.(3.2 ábra) A magyar kártya 32 lapos, a megkeveréséhez 24 keverés kell. Ez azt jelenti hogy 24 keverés után már elég közel lesz a várható inverziószámhoz.(3.3 ábra) Az 52 lapos francia kártya megkeveréséhez 45 keverés szükséges.(3.4 ábra) Látszik hogy a kártyák száma jelentősen befolyásolja a tmix értékét. A Csere keverés forráskódja az 3.3.4 alfejezetben.
3.3.2.
Top-to-random
A Top-to-random keverésnél tmix = n log n. A tarokk kártya 22 lapos, tehát közel 30 keverés szükséges a pakli megkeveréséhez. (3.5 ábra) A magyar kártya 32 lapos, a megkeveréséhez 48 keverés kell.(3.6 ábra) Az 52 lapos francia kártya megkeveréséhez 89 keverés szükséges. (3.7 ábra) Mivel ez egy lassabb keverési módszer, ezért a kártyák számának nagysága jelentősebb mértékben befolyásolja keverési időt, mint az előző keverésben. A Top-to-random keverés forráskódja az 3.3.4 alfejezetben. 32
3.3.3.
Összepörgetéses keverés
Az Összepörgetéses keverésnél Aldous által bizonyított
3 2
log n lépés szükséges.
A tarokk kártya 22 lapos, tehát közel 6-7 keverés szükséges a pakli megkeveréséhez. (3.8 ábra) A magyar kártya 32 lapos, a megkeveréséhez 7-8 keverés kell. (3.9 ábra) Az 52 lapos francia kártya megkeveréséhez 8-9 keverés szükséges. (3.10 ábra) Ez egy elég gyors keverési módszer, ezért a különböző pakliknak a nagysága kevésbé befolyásolja a keverési időt. Az Összepörgetéses keverés forráskódja az 3.3.4 alfejezetben. Az Összepörgetéses keverés jelentősen gyorsabb, mint az Top-to-random és a Csere keverés, és a kártyák számának növekedésével a különböző keverési idők különbsége is arányosan nő a különböző módszereknél.( 3.11, 3.12 és 3.13 ábrák) Már korábban megállapítottuk, hogy a Csere keverés gyorsabb a Top-to-random keverésnél, hisz két lapot mozgat. Ez a 3.11, 3.12 és 3.13 ábrákon is látszik, hogy gyorsabban halad az inverzió szám várható értékéhez. Az is megfigyelhető, hogy az inverzió szám növekedése a Csere keverés esetében lassabb a vártnál. Azt gondolhatnánk, hogy kétszer olyan gyors lesz, mint a Top-to-random keverésnél, mivel a keverési ideje is kétszer olyan gyors. Ez azonban nem igaz, mivel a Top-to-random keverésnél meghatározott a kártya amelyet mozgatunk. Mivel mindig a legfelsőt vesszük ki és helyezzük vissza, így a legtöbbször újabb inverziók alakulnak ki egy keverés során. A Csere keverésnél a két keverendő kártya tetszőleges, így az is előfordulhat hogy egy inverzióban lévő párt cseréltünk ki. Tehát gyakrabban megtörténhet, hogy egy keverés után csökken az inverziók száma. A három keverés pontos keverési ideje a három fajta pakli esetében:
n
22
32
52
Csere keverés
14.76
24.08 44.61
Top-to-random
29.5
48.16
89.23
7.5
8.55
Összepörgetéses keverés 6.6891
33
3.2. ábra. Tarokk kártya megkeverése 100-szor Csere keveréssel, 50 keverés átlaga.
3.3. ábra. Magyar kártya megkeverése 100-szor Csere keveréssel, 50 keverés átlaga.
34
3.4. ábra. Francia kártya megkeverése 100-szor Csere keveréssel, 50 keverés átlaga.
3.5. ábra. Tarokk kártya megkeverése 150-szer Top-to-random keveréssel, 50 keverés átlaga.
35
3.6. ábra. Magyar kártya megkeverése 150-szer Top-to-random keveréssel, 50 keverés átlaga.
3.7. ábra. Francia kártya megkeverése 150-szer Top-to-random keveréssel, 50 keverés átlaga.
36
3.8. ábra. Tarokk kártya keverése 20-szor, Összepörgetéses keveréssel, 50 keverés átlaga
3.9. ábra. Magyar kártya keverése 20-szor, Összepörgetéses keveréssel, 50 keverés átlaga
37
3.10. ábra. Francia kártya keverése 20-szor, Összepörgetéses keveréssel, 50 keverés átlaga
3.11. ábra. Francia kártya 100-szor Top-to-random, Cserés és Összepörgetéses keveréssel, 50 keverés átlaga.
38
3.12. ábra. Magyar kártya 80-szor Top-to-random, Cserés és Összepörgetéses keveréssel, 50 keverés átlaga.
3.13. ábra. Tarokk kártya 60-szor Top-to-random, Cserés és Összepörgetéses keveréssel, 50 keverés átlaga.
39
Irodalomjegyzék [1] B. Morris, W. Ning and Y. Peres, Mixing time of the card-cyclic-to-random shuffle, Ann. Appl. Probab. 24 (2014), no. 5, 1835–1849. [2] D. A. Levin, Y. Peres and E. L. Wilmer, Markov chains and mixing times, Amer. Math. Soc., Providence, RI, 2009. [3] Major K.(szerk.), Markov-modellek, LAGRADE Kft., 2008. [4] J. Jonasson, Card-cyclic-to-random shuffling with relabeling, ALEA Lat. Am. J. Probab. Math. Stat. 12 (2015), no. 2, 793–810. [5] Philip Liang, Finite Markov chains and the Top-To-Random shuffle, August 30, 2013.(http://math.uchicago.edu/ may/REU2013/REUPapers/Liang.pdf)
40
3.3.4.
Függelék
Csere keverés forráskódja csere2<-function(S,N,I){ z=sum(choose(S,2))/2 x=vector(mode = "numeric",length = N+1) x=x+z dbcs<-matrix(data=0,nrow=I,ncol=N+1) check<-matrix(data=0, nrow=S, ncol=N+1) check[,1]<-c(1:S) for(a in 1:I){ kart<- c(1:S) if (N != 0) { for(j in 1:N) { akt<-sample(1:S,1) H<- sample(1:S,1) if (akt == 1){ if (H != S){ if(H!=1 && H!=2) {kart1 <-c(kart[H],kart[2:(H-1)], kart[1], kart[(H+1):S])} else if(H==1) {kart1 <-kart} else if (H==2) {kart1 <-c(kart[2], kart[1], kart[3:S])} } else if (H == S){ if(S!=1 || S!=2) {kart1 <-c(kart[S],kart[2:(S-1)], kart[1])} else if(S==1) {kart1<-kart} else if(S==2) {kart1 <-c(kart[2], kart[1])} } } 41
else if (akt == S){ if (H != 1){ if(H!=(S-1)&&H!=S) {kart1 <-c(kart[1:(H-1)],kart[S], kart[(H+1):(S-1)], kart[H])} else if(H==(S-1)) {kart1<-c(kart[1:(S-2)],kart[S],kart[(S-1)])} else if(H==S) {kart1<-kart} } else if (H == 1){ if(S!=1&&S!=2) {kart1 <-c(kart[S],kart[2:(S-1)], kart[1])} else if(S==1) {kart1<-kart} else if(S==2) {kart1<-c(kart[2],kart[1])} } } else if (H == akt){ kart1 <- kart} else if((akt-H)>0){ if (H !=1){ if(H!=(akt-1))
{kart1 <- c(kart[1:(H-1)], kart[akt], kart[(H+1):(akt-1)],kart[H], kart else if (H==(akt-1)) {kart1 <- c(kart[1:(H-1)], kart[akt], kart[H], kart[(akt+1):S])} } else if (H == 1){ if (akt!=2) {kart1 <- c( kart[akt], kart[2 : (akt-1)],kart[H], kart[(akt+1):S])} else if (akt==2) {kart1<-c(kart[2],kart[1],kart[3:S])} } } 42
else if((akt-H)<0){ if ( H != S){ if(akt!=(H-1))
{kart1<-c(kart[1:(akt-1)],kart[H], kart[(akt+1):(H-1)], kart[akt], kart else if(akt==(H-1)) {kart1<-c(kart[1:(akt-1)],kart[H], kart[akt], kart[(H+1):S])} } else if (H == S){ if(akt!=(S-1)) {kart1<-c(kart[1:(akt-1)],kart[H], kart[(akt+1):(S-1)], kart[akt])} else if (akt==(S-1)) {kart1<-c(kart[1:(S-2)],kart[S], kart[(S-1)])} } } kart<-kart1 check[,j+1]<-kart1 for (h in 1:(S-1)) {for (sz in (h+1):S) {if(kart[h]>kart[sz]) {dbcs[a,j+1]<-dbcs[a,j+1]+1} } } } } } atlcs<-seq(length=N+1, from=0, by=0) for(í in 1:N+1) {atlcs[í]<-mean(dbcs[ ,í])}
plot(atlcs, type="l", main="Cserés keverés", col="purple",lwd="2",xlab="Keverések szám lines(x,type = "l", col= "black", lwd="3") legend( "bottomright", legend=c("E(X)","Keverés"), fill=c("black", "purple")) } 43
Top-to-random keverés forráskódja ttr <- function(S,N,I){ z=choose(S,2)/2 x=seq(length=N+1,from=0, by=0) x=x+z dbti<-matrix(data=0,nrow=I,ncol=N+1) for(a in 1:I){ kart<- c(1:S) if (N != 0) { for(j in 1:N) { H <- sample(1:S,1) if (H == 1){ kart1 <- c(v[S], kart[1:(S-1)])} else if (H == S){ kart1 <- kart} else { kart1 <- c(kart[1:(H-1)], kart[S], kart[H:(S-1)])} kart<-kart1 for (h in 1:(S-1)) {for (sz in (h+1):S) {
if(kart[h]>kart[sz]) {dbti[a,(j+1)]<-dbti[a,(j+1)]+1} }
} } } } atlti<-seq(length=N+1, from=0, by=0) for(í in 1:N+1) {atlti[í]<-mean(dbti[ ,í])}
44
plot(atlti, type="l", main="Top-to-random", col="blue",lwd="2",xlab="Keverések szám lines(x,type = "l", col= "black",lwd="3") legend( "bottomright", legend=c("E(X)","TTR"), fill=c("black", "blue")) } Összepörgetéses keverés forráskódja riffle<-function(S,N,I) {z=choose(S,2)/2 x=vector(mode = "numeric",length = N+1) x=x+z db<-matrix(data=0,nrow=I,ncol=N+1) db[ ,1]=h<-seq(length=I, from=0, by=0) for(a in 1:I){ q<-sample(1:(S-1), N, replace = TRUE) u1<-u[1] uS<-u[S] u<-c(1:S) for (i in 1:N) { q1<-q[i]; z1<-u[1:q1]; z2<-u[(q1+1):S]; if(q1>=(S-q1)) {for(j in 1:(S-q1)) {u[(2*j)]<-z2[j]; u[(2*j)-1]<-z1[j] } if(q1>(S-q1)){
45
u[(2*(S-q1)+1):S]<-z1[((S-q1)+1):q1]}} else {for(k in 1:q1) {u[2*k]<-z1[k]; u[2*k-1]<-z2[k]; } u[(2*q1+1):S]<-z2[(q1+1):(S-q1)] } for (h in 1:(S-1)) {for (j in (h+1):S) { if(u[h]>u[j]) {db[a,i+1]<-db[a,i+1]+1} } } } } atl<-seq(length=N+1, from=0, by=0) for(í in 1:N+1) {atl[í]<-mean(db[ ,(í)])}
plot(atl,type="l",main="Összepörgetéses keverés", col="orange",lwd="2", xlab="Keverése lines(x,type = "l", col= "black",lwd="3") legend( "bottomright", legend=c("E(X)","Keverés"), fill=c("black", "orange")) }
46
