Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

2. A KÁRTYAKEVERÉSRŐL

2. A KÁRTYAKEVERÉSRŐL

Amikor a kártyák eloszlására vonatkozó kérdéseket a valószínűségszámítás alapján válaszoljuk meg, hallgatólagosan mindig feltesszük, hogy az a csomag kártya, amelyből a lapokat kiosztják, „jól össze van keverve”. E kifejezést a kártyások gyakran használják, de mivel nem szokták precízen definiálni, nem árt először röviden foglalkozni e kérdéssel.

Valószínűségszámítási szempontból egy csomag kártyát akkor nevezünk jól megkevertnek, ha a keverés után a lapok összes lehetséges sorrendje, permutációja ugyanakkora valószínűséggel bír; n

n lap esetében n! n ! permutáció lehetséges, tehát jól összekevert az a kártyacsomag, amelynél feltehetjük, hogy minden egyes sorrendnek a valószínűsége (1/n!) 1 n ! . Egy tetszőleges, a kártyák sorrendjétől függő A A esemény valószínűsége tehát (k/n!) k n ! , ahol k k jelenti azoknak a sorrendeknek a számát, amelyek mellett az A A esemény bekövetkezik.

Például, ha egy 52 lapos kártyát megkeverünk, annak a valószínűsége, hogy a legfelül fekvő lap ász legyen, (1/13)

1 13 -dal egyenlő; ugyanis az 52! sorrend közül egy meghatározott ásszal kezdődő sorrendek száma 51! (hiszen ha pl. a legfelső lap a kőr ász, az alatta levő 51 lap 51! sorrendben helyezkedhet el), tehát mivel a csomagban 4 ász van, k=4⋅51! k = 4 51! , és így a keresett valószínűség

(k/52!)=(4⋅51!/52!)=(4/52)=(1/13).
k 52! = 4 51! 52! = 4 52 = 1 13 .

A valóságban a keverés úgy történik, hogy az egyik játékos (vagy a kártya keverését végző gép) 10–20-szor végez el egy bizonyos mozdulatot. Minden egyes mozdulat a kártyacsomag egy átrendezését, vagyis egy permutáció alkalmazását jelenti a kártyák sorrendjére. Egy számsorozat permutációi tudvalevőleg csoportot alkotnak.

Két permutáció, pl. P

P és Q Q szorzatán (amit PQ P Q -val jelölünk) azt értjük, hogy először elvégezzük a P P átrendezést, és az eredményül kapott sorrenden végrehajtjuk a Q Q átrendezést. Például, ha n=32 n = 32 , vagyis 32 lapos (magyar) kártyáról van szó, és P P a

1 … … 16 17 … … 32 17 … … 32 1 … … 16
1 16 17 32 17 32 1 16

permutáció, tehát első helyre az eredetileg 17-ik helyen levő lap kerül, második helyre az eredetileg 18-ik helyen levő lap, és így tovább, az utolsó helyre az eredetileg a 16-ik helyen álló lap (ez úgy hajtható végre, hogy a 32 lapos kártyacsomagról együtt leemelem a felső 16 lapot, ezt leteszem az asztalra, és erre ráteszem az alsó tizenhat lapot), és Q=P

Q = P , vagyis másodszorra is ugyanazt a műveletet végzem, akkor PQ=P^2=I P Q = P 2 = I az azonos permutáció, tehát a két művelet végeredményeként újból az eredeti sorrend áll elő.

A keverés folyamatára mármost két kézenfekvő matematikai modellt (a tényleges folyamat leegyszerűsített képét) állíthatunk fel. Az első modellt determinisztikus modellnek, a másodikat sztochasztikus modellnek fogjuk nevezni. Először tegyük fel, hogy a keverő minden egyes mozdulatnál pontosan ugyanazt az átrendezést végzi a kártyacsomagon. Ha ezt a permutációt P

P -vel jelöljük, akkor e mozdulat k k -szor való elvégzése egyenértékű az eredeti sorrend egyetlen átrendezésével, mégpedig a P P permutáció k k -adik hatványának megfelelő átrendezésével. Az ilyen keverési eljárás elvi szempontból nem kielégítő, hiszen (elvben) pontosan kiszámítható, hogy mi lesz a végeredmény, de gyakorlatilag sem megfelelő, mégpedig annál kevésbé, minél kisebb a P P permutáció rendje, vagyis az a legkisebb r r pozitív egész szám, amelyre P^r=I P r = I , ahol I I az azonos permutációt jelenti, amelynél minden lap a helyén marad. (A fent példaként említett P P permutációnak a rendje r=2 r = 2 .) Ugyanis, ha a P P permutáció rendje r r , akkor ez azt jelenti, hogy a P P , P^2 P 2 , …, P^r P r permutációk mind különbözők (P P minden magasabb hatványa viszont már megegyezik ezek egyikével), tehát akárhányszor is ismétlünk egy r r -ed rendű P P permutációt, ezáltal elvileg nem tudunk létrehozni r r -nél több különböző sorrendet. Persze, ha létezne olyan P P permutáció, amelynek rendje n! n ! , ennek ismétlésével minden sorrendet létrehozhatnánk; ilyen permutáció azonban nem létezik, ha n≥3 n 3 ; ugyanis az n n -ed rendű szimmetrikus csoport nem ciklikus (sőt nem is Abel-csoport, míg a ciklikus csoportok azok). Tisztán matematikai szempontból igen érdekes kérdés a permutációk rend szerinti eloszlása; e kérdéssel foglalkozik Erdős Pál és Turán Pál egy nemrégiben megjelent dolgozata [1]; mivel azonban a keverésnél valóban soha nem pontosan ugyanazt a műveletet ismételjük meg (még akkor sem, ha gép végzi a keverést), a kérdéssel itt nem foglalkozunk részletesen.[17] A keverés másik – a valósághoz sokkal közelebb álló – modellje a következő:

Feltesszük, hogy az egyes keverő mozdulatok a véletlentől is függnek, és egy mozdulatnál bizonyos valószínűséggel minden permutáció felléphet. Feltesszük továbbá, hogy az egyes mozdulatok egymástól függetlenek. Pontosabban ez azt jelenti, hogy ha n

n elem n! n ! lehetséges permutációját valahogy megszámozzuk és Q_j Q j jelöli azt a permutációt, amely a j j -edik sorszámot kapja, akkor a keverés minden egyes mozdulatával a keverő a Q_j Q j permutációt q_j q j valószínűséggel hajtja végre (j=1,2,…,n!) ( j = 1 , 2 , , n ! ) . (Természetesen ∑_(j=1)^(n!)g_j=1 j = 1 n ! g j = 1 .) Ha tehát a keverő i i -edik mozdulatánál a Π_i Π i permutációt hajtja végre, akkor Π_i Π i véletlen permutáció, amelynek eloszlása

P(Π_i=Q_j)=q_j (j=1,2,…,n! i=1,2,…),
P ( Π i = Q j ) = q j ( j = 1 , 2 , , n ! i = 1 , 2 , ) ,

(azaz a Π_i

Π i véletlen permutáció q_j q j valószínűséggel lesz egyenlő egy előírt Q_j Q j permutációval), és Π_i Π i eloszlása független a Π_1,…,Π_(i–1) Π 1 , , Π i 1 permutációktól.

Ez esetben k

k mozdulat után (ha a lapok eredetileg az

1,2,…,n
1 , 2 , , n

sorrendben voltak) a

Π_1Π_2…Π_k=Π^((k))
Π 1 Π 2 Π k = Π ( k )

permutáció jön létre. A Π^((k))

Π ( k ) permutációk ún. Markov-láncot alkotnak. Mármost ismeretes, hogy ha a {q_j} { q j } eloszlás olyan, hogy az összes permutáció csoportjának tetszőleges valódi G G részcsoportjára

(2.1)

∑_(Q_j∈G)g_jl1
Q j G g j l 1

(vagyis az eloszlás nincs egy valódi részcsoportra koncentrálva), akkor nagy k

k esetében Π^((k)) Π ( k ) eloszlása közel egyenletes lesz, vagyis minden permutáció körülbelül ugyanolyan (közel (1/n!)) ( közel  1 n ! ) valószínűséggel fog létrejönni nagyszámú keverőművelet után; pontosabban ez esetben[18]

(2.2)

lim_(k→∞)P(Π^((k))=Q_j)=(1/n!)(j=1,2,…,n!)
lim k P ( Π ( k ) = Q j ) = 1 n ! ( j = 1 , 2 , , n ! )

[A (2.1) feltétel teljesül például, ha j

j minden egyes értékére q_jg0 q j g 0 .]

Gyakorlatilag a mondottakból az következik, hogy ha a keverés minden egyes mozdulata véletlenszerű, elvben minden átrendezést létrehozhat, és ha elég nagyszámú keverő mozdulatot teszünk, akkor indokolt az a feltevés, hogy a lap „jól össze van keverve”. Arra a kérdésre, hogy mi értendő „elég” nagyszámú mozdulaton, itt nem térünk ki.

Mindenesetre érdemes volt a keverés folyamatával ilyen részletesen foglalkoznunk, hiszen tudvalevőleg a hamiskártyások leggyakrabban alkalmazott fogása éppen a nem kielégítő keverés. (Lásd az 5-öt is!)



[17] Erdős és Turán [1]-ben bebizonyítják, hogy az n!

n ! permutáció közül a legtöbbnek a rendje az e^((1∕2–ε)log^2n) e ( 1 2 ε ) log 2 n és e^((1∕2+ε)log^2n) e ( 1 2 + ε ) log 2 n határok közé esik, ahol εg0 ε g 0 tetszőleges kicsiny számnak választható, ha n n elég nagy (itt log n n az n n szám természetes logaritmusát jelöli). A kártyakeverésre vonatkoztatva ez azt jelenti, hogy 52 kártya legtöbb permutációja esetében kevesebb, mint 200 000 200 000 -szer kell a keverő mozdulatot megismételni, hogy a kártyák újból az eredeti sorrendbe kerüljenek. Összehasonlításul vegyük figyelembe, hogy 52! egy 68 jegyű számóriás.

[18] E tétel speciális esete a valószínűségszámítás centrális határeloszlás-tétele topológikus csoportokra vonatkozó általánosításának, amely a Haar-mértékhez való konvergenciára ad feltételt. L. pl. [2] és [3].