Tóth Bálint

A kártyakeverés matematikája

című, 2006. május 23-ai előadása alapján írták Lovász László és Nagy Gergely diákok, Surányi László tanár

Az előadás jegyzetének elkészítését támogatta:
Budapest Bank Budapestért Alapítvány

Az előadás címéről

Tegyük fel, hogy négyen valamilyen kártyajátékot szeretnének játszani, például francia kártyával bridzselni. Nem a szabályok érdekelnek minket, összesen annyit kell tudnunk, hogy a bridzset az 52 kártyás, tehát egy pakli, joker nélküli francia kártyával játssza négy játékos, mindegyiküknek 13 lapot osztanak rögtön az elején. Minket most csak az a kérdés érdekel, hogy hogyan osszuk ki a lapokat úgy, hogy elég véletlenszerű legyen a leosztás. Nyilván nem felelne meg a célnak, ha egy frissen vásárolt kártyacsomagból egyből osztani kezdenénk (miután a jokereket kitettük), hiszen a boltban vásárolt pakli még „rendezett”, a kártyák „sorban” jönnek: először a treffek, aztán a többi szín, ráadásul mindegyik szín sorba rendezve a kettestől az ászig. Előbb „jól meg kell kevernünk” a kártyát, például úgy, hogy ketté választjuk a kártyacsomagot és az egyik felét belekeverjük a másik felébe, majd ezt párszor megismételjük? De hányszor? Ha egyszer csináljuk, akkor nagy valószínűséggel többen is hosszú egyszínű sorokat fognak kapni, tehát korántsem lesz „véletlenszerű” a keverés. Viszont ha 15-ször megismételjük ezt a keverést, akkor már mindenki úgy fogja érezni, hogy elég véletlenszerű lesz a leosztás. A kérdés az, hogy hányszor kell a műveletet megismételnünk ahhoz, hogy az eredmény már „véletlenszerű” legyen.

Már a kérdés pontos feltevéséhez is szükség van fogalmak tisztázására. Miután a középiskolában csak nagyon érintőlegesen tananyag a véletlen matematikája, azaz a valószínűségszámítás, szükséges az alapfogalmaktól elindulnunk. Nem fogunk minden fogalmat pontosan definiálni, néha az intuícióra kell hagyatkoznunk, de a felépítésre mindenképp szükségünk lesz. Magának az előadásnak a témájához csak az előadásnak kb. a közepén fogunk eljutni, addigra lesz kezünkben minden fogalom, hogy pontosan feltehessük kérdéseinket.

Kezdjük tehát az alapfogalmaknál. Látszólag elkanyarodunk és nem a véletlen, hanem a valószínűség definiálásával kezdjük. Ez azonban általános eljárás a matematikában, sőt a természettudományban: a valószínűség a véletlen mérőszáma, vagyis megmondja, hogy egy esemény mennyire „véletlen”. (Gondoljuk meg: a legtöbb fizikai fogalomnál sem azt mondjuk meg, hogy mi az, hanem azt adjuk meg, hogy hogyan mérjük az illető mennyiséget.) De az épp most mondottakból az is világos, hogy a valószínűség definiálásához szükséges azt is megmondanunk, hogy mi az esemény. És miután az egyes események valószínűségét egymáshoz viszonyítva tudjuk mérni, meg kell adni az „eseménytért” is, tehát az összes olyan eseményt, amit egymáshoz képest mérni akarunk. De – legalábbis abban az esetben, ha véges sok lehetséges esemény van – nyilván vannak összetettebb és tovább nem bontható elemi események. A kártyakeverés esetében ezek az 52 kártya lehetséges sorrendjei (a kiosztás előtt) – és a megfigyelés összes lehetséges eredménye, tehát a kísérlet összes lehetséges kimenetele alkotja az eseménytért. Általában a definíció a következő:

Tehát egyrészt a biztos esemény valószínűségét egynek vesszük, ezzel „normáljuk” a valószínűségeket. Minden egyes (tovább nem bontható) elemi eseménynek adunk egy pozitív „súlyt” – hogy hogyan, minek az alapján, ezt minden esetben el kell előbb döntenünk –, és ez lesz az egyes elemi események valószínűsége. Egy összetett esemény valószínűségét ezek után úgy állapítjuk meg, hogy megnézzük: milyen elemi eseményekből tevődik össze és ezek súlyát összeadjuk.

Például a bridzs esetében, ahol az elemi események a pakli egyes sorrendjei, semelyik sorrendet nem tüntetjük ki, minden sorrendet ugyanolyan súllyal látunk el. (Ez látszólag ellentmond annak, hogy „kezdetben”  a kártyacsomag rendezett, de éppen egy olyan állapothoz akarunk eljutni, amikor semmit nem tudhatunk a sorrendről, tehát minden sorrend egyformán valószínű.) Miután 52! a lehetséges sorrendek száma, az egyes elemi események – sorrendek –  valószínűsége egyformán 1/52! Most megkérdezhetjük, hogy a négy játékos közül – ezeket szokás a négy égtájjal Északnak, Délnek, Nyugatnak és Keletnek nevezni – az egyik, pl. Nyugatnak milyen valószínűséggel lesz három ásza. Ehhez annyit kell tennünk, hogy meg kell számolnunk azokat a sorrendeket, amelyekben Nyugatnak három ász jut. (Persze ehhez tudnunk kell, hogy a sorrendben hanyadik lapokat kapja ő, de ez ismert.)

A definícióból következik pár alapvető tétel:

Ez világos, hiszen az unió-esemény valószínűségét úgy kapjuk, hogy a hozzá tartozó összes elemi esemény valószínűségét összeadjuk, ezt az összegzést pedig elvégezhetjük úgy is, hogy az egyes A_i halmazbeli elemi eseményeket összeadjuk, és az így kapott eredményeket összeadjuk, hiszen egyetlen elemi eseményt sem fogunk kétszer számba venni.

Bemelegítésül nézzünk egy elég ismert példát:

A következő fogalom a feltételes valószínűség fogalma. Ez elég egyszerű fogalom, de enélkül nem tudjuk értelmezni sem az előadás címében jelzett kérdést, sem számtalan lényeges más kérdést. Ismét a fenti bridzs-példát használva ismét azt kérdezzük, hogy milyen valószínűség­gel fog Nyugat három ászt kapni? Említettük, hogy ezt hogy kell kiszámolni: megszámoljuk, hogy hány olyan sorrend van, amelyben Nyugatnak három ásza van, s ezek számát elosztjuk az összes lehetséges eset számával, 52!-sal.

De tegyük fel, hogy a lapok kiosztása után, még mielőtt Nyugat megnézné a lapját, pl. Észak megsúgja neki, hogy nála pontosan egy ász van. Most nyilván megváltozik annak az esélye, hogy nála három ász lesz. (Nem beszélve arról az esetről, ha azt tudja meg, hogy Északnál két ász van: ekkor nullára csökken annak a valószínűsége, hogy nála három ász legyen.) Mi tör­tént? Nyugat nem kapott ugyan teljes felvilágosítást a kérdésére, de megtudott valami rész­információt, s ez módosítja az esélyeit. Általában is ez a helyzet: egy A esemény valószínűsé­gét szeretnénk megtudni, ha valami H feltételt tudunk, ami ugyan nem ad teljes fel­világosítást. (Persze az információ adhat teljes felvilágosítást, de lehet teljesen irreleváns is az információ. A példánknál maradva: ha Északnál két ász van, ez már a kérdésünk szempontjá­ból teljes felvilágosítást ad, biztosan tudni fogjuk, hogy Nyugatnál nem lehet, azaz nulla való­színűséggel lehet három ász. Másrészt meggondolható, hogy ha például Nyugat azt árulja el, hogy nála van treff, ezzel a kérdésünk vonatkozásában semmit nem árult el.)

Vegyük tehát azt az esetet, amikor az  esemény valószínűsége érdekel minket, de tudjuk (vagy feltételezzük), hogy a H esemény bekövetkezett. Ennek az információnak (vagy feltevésnek) a figyelembevételével máshogy kell számolnunk a valószínűséget. Erre vonatkozik az alábbi jelölés és képlet.

Az 1. ábrán szemléltetjük, hogy miről van szó. Kékkel jelöltük a teljes eseménytért, tehát az  halmazt. Zölddel jelöljük a H eseményhez tar­tozó elemi események „terét”, tehát azt a részt, amire figyelmünket fordítjuk, miután feltesszük (vagy megtudjuk), hogy H igaz. A kérdés most az, hogy ezen a részen milyen valószínűséggel következik be (a feketével jelölt) A. Ehhez nyilván tudnunk kell, hogy milyen valószínűséggel következik be az  esemény, és ezt kell a H esemény bekövetkezésének valószínűségéhez viszonyítanunk, hiszen most ez a „az eseménytér”, ennek kell 1 valószínűséggel bekövetkeznie.

A feltételes valószínűséget időnként egy esemény feltétel nélküli valószínűségének kiszámítására alkalmazzuk valamely teljes eseményrendszer segítségével.

Ez az állítás csak kinézetre bonyolult: az összeadandók előző definíciónk alapján éppen az egyes  események bekövetkezésének a  valószínűségével egyenlők, s ezek páronként diszjunkt események, együtt tehát épp az A valószínűségét adják.

Szükségünk lesz még az úgynevezett „toronyszabályra”. Ez időben egymás után következő eseményekkel foglalkozik. Hogy rögtön példát is mondjunk:

Ennek alapján érthető az úgynevezett

A toronyszabály tehát azt mondja ki, adja meg, hogy hogyan számolható ki annak a valószínűsége, hogy egymás után az A₁, A₂, …, A_n események következnek be. Kiszámoljuk, hogy az i-edik esemény milyen valószínűséggel következik be, feltéve hogy előtte az A₁, A₂,…,A_i–1 események következtek be, majd ezeket a feltételes valószínűségeket összeszorozzuk.

A következő fogalom az események függetlensége.

Két esemény esetén ez azt jelenti, hogy az A esemény valószínűsége nem változik, ha tudjuk, hogy B bekövetkezik, azaz P(A) = P(A|B). Ez a definíció formálisan nem szimmetrikus. Vagyis: mi két esemény függetlenségéről beszéltünk, de itt csak azt mondtuk meg, hogy A mikor független B-től. Ám ha ide beírjuk a feltételes valószínűség fenti definícióját és átszorzunk a nevezővel, akkor azt kapjuk, hogy P(A∩B)=P(A)P(B). Szavakban ez azt jelenti, hogy a két esemény együttes bekövetkezésének valószínűsége megegyezik a két esemény valószínűségének szorzatával. Ebből viszont következik, hogy ha A független B-től, akkor B is független A-tól, tehát valóban beszélhetünk a két esemény egymástól való függetlenségéről.

Több esemény függetlenségével kapcsolatban azonban fontos eloszlatni egy tévedést: ehhez nem elég, hogy bármely két esemény független legyen. Mondok egy példát rögtön, amit egy életre meg kell jegyezni, hogy ne kövessük el az említett a hibát, amit még könyvben is láttam elkövetni. Tehát tegyük fel, hogy két kockával dobunk, az egyik zöld, a másik piros. Az A esemény legyen az, hogy a zöld kockán párosat dobunk, a B esemény az, hogy a piros kockán párosat dobunk, a C pedig az, hogy a két dobott szám összege páros. Mármost nyilvánvaló, hogy mindhárom esemény 1/2 valószínűséggel következik be, bármely kettő pedig független, mert együttes bekövetkezésük valószínűsége ¼. Ám a három esemény egyáltalán nem független egymástól, mert ha bármely kettő bekövetkezéséről van információnk, abból el tudjuk dönteni, hogy a harmadik bekövetkezik-e. Ha például A is, B is bekövetkezik, akkor C is biztosan bekövetkezik, ha egyik sem következik be, C akkor is biztos, stb. Tehát

Ezután már rátérhetünk a Markov-láncokra, ezek lesznek segítségünkre eredeti, kártyakeverési problémánk megválaszolásában. Valami véletlen mozgásáról van szó, amely véges – vagy néhány később sorra kerülő példában meg­szám­lálhatóan sok, de mindenképp diszkrét – állapotban lehet. Diszkrét időegységenként változtatja állapotát. Az állapotok véges vagy megszámlálhatóan végtelen halmazát S-sel jelöljük. A később terítékre kerülő 2. példa állapotainak rendszere látható a 2. ábrán.

Az egyes pontok az állapotokat (megengedett állapotokat) jelölik, a zöld nyílak azt mutatják, hogy melyik állapotból melyikbe mehet át (közvetlenül, tehát egy időegység múltán) a véletlen mozgás. Ezekre rá van írva egy-egy pozitív szám, az α állapotból a β állapotba mutató nyíl jelöli, hogy a mozgás milyen valószínűséggel fog az α állapotból a β állapotba átmenni (egy időegység múltán). Ezt a mennyiséget p_αβ-val jelöljük. Ez az átmeneti valószínűség. Tehát itt nem-determinisztikus mozgásról van szó, mintegy sorshúzás dönti el, hogy egy adott állapotból hogyan megy tovább a mozgás (vagy folyamat). Ha például veszünk a boltban egy pakli kártyát, akkor a kiinduló állapot még nagyon rendezett, mint mondtuk. A következő (egy keverési művelet utáni) állapot már nem eldönthető (nem determinált) és aránylag rendezetlenebb, véletlenszerűbb lesz. Éppen azt kérdezzük, hogy hány lépés (azaz: hány keverési művelet) után lesz már „tényleg véletlen” a sorrend.

Mármost ilyen véletlen mozgás még nagyon sokféle van és nagyon bonyolult a kezelésük is. A p_αβ átmeneti valószínűség általában sok mindentől függ, például az összes azt megelőző állapottól. Ez nagyon bonyolulttá teszi az általános esetet. A Markov-láncok esetében azonban van egy lényeges egyszerűsítés, nevezetesen feltesszük, hogy a p_αβ valószínűség csak a pillanatnyi állapottól függ, a korábbiaktól nem! Feltesszük tehát, hogy a mozgásnak ilyen értelemben nincs memóriája, tehát az, hogy mi fog történni, csak a pillanatnyi állapottól függ, telje­sen mindegy, hogy a folyamat hogyan jutott ebbe az állapotba. Ez nagyon erős feltétel, mégis természetes, és jól alkalmazható sok esetben, például a kártyakeverésnél, de a genetikában is. Képletben ez azt jelenti, hogy p_αβ= P(β|α) és ez a β állapot csakis a pillanatnyi állapotot jelöli. Analógia lehet a fizikai differenciálegyenletek példája, ahol csak egy pillanatnyi állapottól (pl. a rendszerben levő részecskék pillanatnyi helyzetétől és sebességétől) függ, hogy utána mi fog történni – de csak analógia, hiszen ott determinisztikus folyamattal van dolgunk!

Jelöljük S-sel a Markov-lánc lehetséges állapotainak halmazát és tegyük fel, hogy S alemainek száma n. A Markov-lánchoz tartozik tehát egy n×n-es négyzetes mátrix (a mátrixokról lásd a KöMaL 2006. májusában megjelent cikket Hermann Pétertől – sajnos egyelőre nem érhető el a neten –). Ennek a mátrixnak például a második sor és ötödik oszlop metszéspontjában álló eleme azt adja meg, hogy milyen valószínűséggel jut a mozgás a második állapotból az ötödikbe. Nyilvánvaló, hogy egy ilyen mátrix minden eleme egy-egy nemnegatív szám, s az egy sorban álló számok összege egy. Hiszen egy adott állapotból csak a véges sok adott állapot egyikébe kerülhet a mozgás és ezek az állapotok páronként kizárják egymást. Tehát a fent mondott értelemben teljes eseményrendszert alkotnak.

Ez utóbbi feltevés azt jelenti, hogy a gráf „nem esik szét”, sem az nem történik meg, hogy ha eljutunk egy részébe, onnan nem tudunk visszajutni egy másik részébe. Ez a kikötés nem nagyon szorítja meg a vizsgálódásainkat. Ha ugyanis egy Markov-láncra nem teljesül, nem nehéz belőle egy másikat csinálni, ami ugyanúgy megfelel céljainknak, de teljesül rá az irreducibilitás feltétele.

A legtöbb esetben még egy megkötéssel élünk (bár látni fogunk olyan példát is, ahol ez nem teljesül): feltesszük, hogy nincs benne periódus. Ez a következőt jelenti: a gráf egy tetszőleges pontjából kiinduló körök hosszának legnagyobb közös osztója egy. Ez egy páros gráfra például nem teljesül, hiszen ott egy tetszőleges adott állapotból csak minden párosadik lépésben juthatunk vissza ugyanabba az állapotba. Páros gráfban minden kör hossza páros, tehát a hosszak legnagyobb közös osztója is legalább kettő. Ezt, mint mondtam, a legtöbb esetben kizárjuk.

Ha egy véletlen folyamatban adott egy rögzített, most tehát határozott, determinisztikus, nem véletlen útvonal, és azt kérdezzük, hogy mi ennek trajektóriának a valószínűsége, akkor ezt általában a toronyszabállyal számíthatjuk ki. Ez tehát így szólt: Ha adva van egy α₀, α_{1,  ... ,} α_n rögzített útvonal, akkor annak a valószínűsége, hogy az X₀, X₁,  ... , X_n útvonal ezzel megegyezik a torony-szabály szerint:

Csakhogy a Markov-lánc esetében a mozgásnak nincs memóriája, tehát már a második feltételes valószínűség egyszerűsödik, s ugyanígy minden utána következő is:

S most lássunk pár konkrét példát a Markov-láncokra, a nagyon egyszerűekből indulva.

Itt tehát két állapot van: S={0,1}, 0-val jelezzük, hogy szabad a vonal, 1-gyel, hogy foglalt. A Markov-mátrix most a következő:

Itt az első sorral nincs gond. Az első elem azt fejezi ki, milyen valószínűséggel marad szabad egy szabad állapot. Ez akkor történik, ha nem érkezik hívás az időegység alatt. Ennek valószínűsége 1–p. Ugyanígy az első sor második eleme azt fejezi ki, hogy milyen valószínűséggel lesz foglalt a szabad állapot. Ehhez az kell, hogy érkezzen egy hívás, ennek valószínűsége p. A második sor már bonyolultabb: itt a vonal foglalt. Mikor lesz szabad? Ha egyrészt befejeződik a hívás, ennek q a valószínűsége, másrészt nem érkezik új hívás, ennek valószínűsége 1–p. Az eredmény a kettő szorzata, hisz feltettük, hogy az aktuális beszélgetés befejezése és az új hívás érkezése egymástól független események. Valamivel még ennél is bonyolultabb a második sor második elemének kiszámolása: itt az időegység elején foglalt és a végén is foglalt a vonal. Ez kétféleképp is lehetséges: a) befejeződik a „régi” beszélgetés (q valószínűséggel) és érkezik új (p valószínűséggel), ennek az eseménynek a valószínűsége a függetlenség miatt pq, b) nem fejeződik be a régi (1–q) és ekkor mindegy, hogy érkezik-e új hívás vagy sem, hiszen ha érkezik, az „kárba megy”. Az utóbbi esemény valószínűsége tehát 1–q. Könnyen ellenőrizhető, hogy a Markov-mátrixra kirótt feltételek teljesülnek.

Most tehát három állapot van: S={0,1,2}, ahol 0=szabad, 1=foglalt és nincs várakozó, 2=foglalt és van várakozó.

Hosszú idejű várakozás

Sokszor az érdekel minket, hogy hogyan viselkednek „hosszú távon” a Markov-láncok, tehát mi történik, ha sokáig várunk. Ez érdekel a kártyakeverésnél is. Tehát az érdekel minket, hogy egy bizonyos β állapotot nagyon sok lépés után milyen valószínűséggel ér el az állapot.

Nyilvánvaló, hogy , annak megfelelően, hogy β=α vagy nem. Másrészt definíció szerint . Általában azt állítjuk, hogy

Az érdekel minket, hogy mi történik hosszú idő után egy Markov-lánccal. Kialakul-e egyfajta állandóság és egyenletesség. A kártyakeverés esetében például az a kérdés, hogy ha hosszú ideig keverünk, előbb-utóbb kialakul-e egy olyan állapot, amelyben minden sorrend egyformán valószínű. Matematikailag kicsit pontosabb formában így fogalmazhatjuk meg a kérdést: ha a lépésszám, n a végtelenhez tart, akkor stabilizálódik-e – konvergál-e – az egyes állapotok valószínűsége? Vagyis: ha elég sok lépést teszünk, tetszőlegesen megközelíthetjük-e azt a helyzetet, amikor minden állapot (sorrend) egyformán valószínű? Ez a következőt jelenti:

A kártyakeverés matematikai modellje

Szükségünk van egy matematikai modellre, ez a következő:

Tekintsük az 52 kártya összes sorrendjét, ezt a halmazt – az összes 52-edrendű permutációk halmazát – a matematikában S₅₂-vel jelöljük. Tehát S = S₅₂.

Ismeretes, hogy ilyen permutációból 52! darab van, ami irdatlanul nagy szám, kb. . Ha ennyi aranyatomot vennénk és azt egy kocka alakú aranytömbbe öntenénk, ennek az aranykockának az oldalhossza csillagászati méretű lenne. Ezt a mennyiséget tehát gyakorlatilag végtelennek is tekinthetjük. A Markov-láncnak tehát ennyi állapota lesz.

Megjegyzem, hogy a továbbiak matematikájához felhasználjuk, hogy a permutációk csoportot alkotnak, de erre csak utalni fogok. (A permutációk egy véges halmazon végzett transzformációk, ugyanúgy, ahogy például a sík egybevágósági transzformációi a sík pontjainak halmazán végzett transzformációk. Ezeket a transzformációkat alkalamazhatom egymás után, s akkor újra egy permutációt – illetve egy egybevágóságot – kapok. Az egymás után alkalmazást nevezik a transzformációk szorzásának. Erre mint műveletre alkotnak csoportot a permutációk.)

A keverés egy lehetséges matematikai modellje a következő: A kártyacsomag tetejéről valahány lapot leemelünk („emelés”), a jobb kezünkbe fogjuk a leemelt j darab lapot, a bal kezünkbe a b darab megmaradt lapot (j+b=52), és valamilyen véletlen sorrendben összefésüljük a két kupacot. Így kapjuk az új sorrendet.

Először is számoljuk ki, hogy egy sorrendből hány másikhoz tudunk így eljutni, vagy másképp: egy adott sorrendnek hány ilyen keverése van? Egyszerű kombinatorikai feladat annak belátása, hogy ha b lap marad a bal kezünkben, azt  féle különböző sorrendben rakhatjuk a többi közé, oly módon, hogy ne az eredeti sorrendet kapjuk vissza éskülönböző b-kre ezek a sorrendek mind különbözőek. (Gondoljunk arra a helyzetre, amikor már összefésültük a két kupacot, és írjuk fel a sorrendet úgy, hogy csak azt jelöljük, hogy melyik kártya melyik kezünkből „származik”. A b darab „balkezes” kártyának éppen ennyiféle elrendezése lehetséges, ha a kiinduló helyzetet nem engedjük meg. A „balkezes” kártyák egymáshoz viszonyított sorrendje viszont adott, az a keverés során nem változik.) Ezt a mennyiséget kell tehát minden b-re összeadni és az összeghez még hozzáadni 1-et, ami a az eredeti sorrend visszaállítását képviseli.  Tehát az összes elérhető sorrend száma:

(Megengedjük, hogy ne emeljünk egyetlen lapot sem és azt is, hogy minden lapot leemeljünk, ezért megy az összegzés 0-tól és tart 52-ig.) A keveréssel megkapható sorrendek száma az összes lehetséges sorrendhez képest nagyon kicsi. Mondhatjuk:

Valóságos csoda, hogy mégis meg tudjuk keverni a kártyacsomagot, sőt: az összes sorrendet megkaphatjuk, méghozzá elég gyorsan.

Be lehet bizonyítani, hogy

Persze ez egy általános tétel speciális esete, s mivel a keverések száma egész, ez azt jelenti, hogy legfeljebb hat keveréssel megkaphatunk minden permutációt. Jól értsük meg: ez az állítás arra az esetre vonatkozik, amikor előre meghatározhatjuk, hogy mikor hogyan emelünk és keverünk. Tehát ha determinisztikus módon hajtjuk végre a keveréseket, akkor ennyi lépésben eljuthatunk minden keveréshez. Ez még így is valóságos csoda, hiszen a gráfnak irdatlan sok pontja van, kb. . Ehhez képest minden pont foka elenyészően kicsi: . A gráf tehát nagyon ritka. Állításunk azt mondja, hogy mégis minden pontjából minden pontjába „hamar” el lehet érni. Gráfelméleti nyelven: az átmérője kicsi, pontosan: hat, azaz bármely két pont távolsága – a legrövidebb út hossza az egyik pontból a másikba – legfeljebb hat hosszúságú.

Egyelőre tehát ott tartunk, hogy tudjuk, hány pontja van a Markov-láncunkhoz tartozó gráfnak és tudjuk azt is, hogy egy pontból hány él indul. Most azt is meg kell állapítanunk, hogy egy adott sorrendből egy másikba milyen valószínűséggel jutunk el. Ezt a következőképpen számoljuk ki:

– Annak a valószínűsége, hogy pontosan b kártyát emelek le, .

– Az emelés és az összefésülés egymástól független műveletek.

– Az, hogy az összefésülésnél a következő kártyát melyik kezemből veszem, arányos azzal, ahány kártya van éppen ebben a kezemben. Tehát például legyen a jobb kezemben 20 kártya, a bal kezemben 32. Ekkor az, hogy az első négy lapot jbbj sorrendben fogom összefésülni: .

Ha így kiszámolom a valószínűségeket, akkor minden, egy keverési művelettel megvalósítható („kikeverhető”) és a kiindulótól különböző sorrend valószínűsége egyaránt , míg a kiinduló sorrend visszaállításának valószínűsége 53xlesz.

Hogy miért jó ez a modell, az jobban látszik, ha a fordított műveletet, ennek a keverésnek az inverz műveletét nézem.

Mi a fordított művelet? Veszem az egyes lapokat sorban, és egy érme feldobásával döntöm el, hogy a soron következő lapot a bal (írás) vagy a jobb (fej) kezemnek megfelelő kupacba teszem, majd a végén a bal kupacot a jobb kupac alá helyezem.

Könnyen belátható, hogy ez tényleg az inverzkeverés. Matematikai szempontból lényegtelen, hogy az eredeti keverést vagy annak az inverzét vizsgáljuk. Ez csak annyit változtat a dolgon, hogy időben visszafele nézzük a folyamatot. És így minden lépés természetes, az érme feldobása is, az egymás alá helyezés is. (Ha az inverz művelettel minden állapotból d állapotba juthatunk el, az eredeti művelettel is minden állapotból d állapotba juthatunk el, és minden lépés egyformán valószínű, akkor ez azt jelenti, hogy az eredeti állapotból is minden elérhető állapotba ugyanolyan valószínűséggel juthatunk el.)

Most már kész a gráf, persze felrajzolni nem fogom, és a mátrixot sem írom fel: mindkettő irdatlanul nagy lenne.

Azt állítom, hogy az egyes állapotok valószínűsége idővel stabilizálódik. Vagyis van egy stacionárius állapot. Azt állítom, hogy

Elvileg elképzelhető volna, hogy nem az egyenletes eloszlás a stacionárius állapot, hanem például egy olyan állapot, ahol a pikkek inkább a középen helyezkednek el, vagy az ászok aránylag közel vannak egymáshoz. Persze, nem így van, de ezt bizonyítanunk kell. A bizonyítás tulajdonképpen egyszerű, csak szükséges hozzá pár fogalom. Először is π-vel fogjuk jelölni az állapotok valószínűségi eloszlását. Ezen a következőt értjük: π egy olyan függvény, amely minden állapothoz hozzárendel egy pozitív valós számot, ennek az állapotnak a valószínűségét. Az összes állapotokra összeadva ezeket az értékeket pontosan egyet kapunk:

ahol az összegzés az összes állapotra történik. A mi esetünkben az összes sorrendre összegzünk, vagyis ez az  összeg 52! tagból áll.

A π eloszlást tekinthetem egy 52! hosszú sorvektornak is:

Érdemes meggondolni, hogy ha ezt a sorvektort jobbról megszorzom a keverés Markov-mátrixával, az M= mátrixszal, akkor a kapott sorvektor épp azt mutatja, hogy, feltéve, hogy jelenleg az állapotok eloszlása π, milyen eloszlású lesz az állapotok valószínűsége egy lépés múlva. Hiszen az i-edik állapotba, azaz α_i állapotba éppen  valószínűséggel jut a folyamat, s ez éppen a π sorvektornak és az M mátrix i-edik oszlopának szorzata, tehát a πM sorvektor i-edik eleme.

Azt kell még észrevennünk, hogy

Az előbb mondottak szerint ez éppen azt fejezi ki, hogy az időben nem változik az állapotok eloszlása.

Azt állítjuk, hogy

Az előbb már láttuk, hogy minden keverésnek van inverze. (Ez nem minden Markov-láncra igaz, de a Markov-láncok egy nagy osztályára igaz.) Ez pontosan azt jelentette, hogy minden állapotba ugyanannyi féleképp lehet eljutni, ahány állapot elérhető belőle és mindegyiknek egyforma a valószínűsége. Ebből viszont következik, hogy

Most használtuk, hogy a permutációk csoportot alkotnak, ezért a kártyakeverés mátrixa bisztochasztikus mátrix. Könnyen ellenőrízhetjük, hogy bisztochasztikus M mátrix esetében az egyenletes eloszlásnak megfelelő konstans v vektor kielégíti az egyenletet. Ez jelen esetben 52! darab 1/52!-ból áll. Hiszen minden eleme egyenlő és összességében egy oszlopnyi P_αβ-val szorozzuk, ezek összege pedig egy.

„Végtelenül sok” idő után egyre közelebb kerülünk a stacionárius állapothoz, ami jelen esetben az egyenletes eloszlás. Vagyis nagyon sok keverés után közelítőleg egyforma lesz minden sorrend valószínűsége.

Hány keverés elég?

Befejezésül még felvethető az a kérdés, hogy akkor hány keverés elég? Hány keverés után mondhatjuk, hogy már „majdnem” egyenletes az egyes sorrendek valószínűsége?

A választ itt csak jelezni tudom, akit érdekel, erről a témáról az egyetemen egy speciálelőadást tartok, ott majd szeretettel várom.

Bevezetjük a d_n számot, amely azt mutatja, hogy n keverés utáni eloszlás milyen „messze” van a stacionárius eloszlástól.

, ahol az α az indulási állapot, π a stacionárius állapot és azt jelzi, hogy milyen valószínűséggel leszünk a β állapotban n lépés után. Ez a d_n egy 0 és 1 közötti szám. Azt akarjuk, hogy ez a szám nagyon kicsi, azaz nullához közeli szám legyen. A kérdés az, hogyan kell ehhez n-et (a lépésszámot) megválasztanunk. Erre egy nevezetes cikk válaszol, már a címével is: „Seven shuffles suffice!” Hét(-nyolc) keverés elég. S valóban: ha egy pókerpartiban valaki 15-ször megkeveri a paklit, azt társai idővel kirakják, mert túl sokat kell rá várni.

Mit jelent ez matematikailag? Tegyük fel, hogy nem 52, hanem m lapból álló kártyacsomagot akarunk megkeverni. Bonyolult számolással belátható, hogy a fenti d_n érték  lépésig (itt c egy pontosan kiszámítható konstans) nagyon közel van 1-hez, ennél az értéknél hirtelen nagyon közel kerül 0-hoz, és nagyobb n-ekre már közel marad. Ez az érték 52 lapnál 7 körül van, tehát valóban: hét-nyolc keverés elég.