Quants cops cal escartejar? : Un problema de probabilitats i teoria de grups

Butlletí de la Societat Catalana de Matemàtiques Vol. 13, núm. 1, 1998. Pàg. 65–79. Quants cops cal escartejar? Un problema de probabilitats i teoria de grups∗ Frederic Utzet El problema de què ens ocuparem és molt curt d’enunciar: tenim un joc de cartes i volem saber quants cops cal escartejar-les de manera que quedin ben remenades. La resolució, però, serà llarga i tindrà molts ingredients: caldrà definir què vol dir que les cartes quedin ben remenades, buscar models de les diferents maneres d’escartejar i, un cop ben traduït tot al llenguatge matemàtic, cercar la manera d’atacar el problema. La resolució, que s’ha obtingut en els darrers deu anys, es pot dur a terme utilitzant tècniques molt diverses: a més del càlcul de probabilitats, es poden utilitzar diferents eines algebraiques o d’anàlisi funcional. He escollit presentar la via original d’atac del genial matemàtic americà Persi Diaconis, que utilitza la teoria de representació de grups, ja que m’ha semblat que és la que millor s’adapta a ser explicada —a grans trets, això sí— en una hora, i que a més utilitza resultats coneguts a partir del segon curs de la carrera de matemàtiques. 1 Plantejament del problema. Què vol dir «ben remenades» i altres definicions Òbviament abans de començar cal precisar el llenguatge. Per concretar les idees (i no escriure massa) ho pensarem amb tres cartes que, en un joc nou, abans de remenar, estaran en l’ordre a b c, on aés la carta de dalt de tot, bla del mig, i cla de baix. Després d’escartejar-les, direm que les cartes estan «ben remenades» si hi ha la mateixa probabilitat d’obtenir qualsevol de les 3! ordenacions possibles: abc acb bac bca cab cba En altres paraules, cadascuna d’aquestes ordenacions té probabilitat 1/6. (Es diu que tenim una probabilitat uniforme sobre el conjunt de les ordenacions). Al contrari, si algú després d’escartejar només obtingués les ordenacions abc acb ∗Aquest text reprodueix, amb alguns complements, la conferència inaugural del curs 96-97 de la Secció de Matemàtiques de la Universitat Autònoma de Barcelona. Agraeixo molt als professors Agustí Reventós i Joan Josep Carmona la seva confiança; malgrat la feina que em va portar, va ser un honor i una satisfacció fer-la. 66 Frederic Utzet cadascuna amb probabilitat 1/2, òbviament les cartes estarien mal barrejades, i ens podrien fer moltes trampes en el joc. Els professionals de les cartes (jugadors, il.lusionistes, tafurs, etc.) sempre han sabut que la gent acostuma a escartejar malament i quan, per exemple, un il.lusionista dóna a un espectador una baralla de cartes i li diu «remeni ben remenat...», i l’espectador barreja dos o tres cops, l’estructura de les cartes quasi no ha canviat, i el mag en treurà partit. Gardner ([12, cap. 6]) explica diversos jocs amb cartes interessants que exploten aquesta idea; val a dir que alguns d’aquests trucs no surten sempre, però sí que funcionen amb una alta probabilitat. A molts espectacles de màgia hi acostuma a haver trucs que depenen de l’atzar (amb cartes o sense): quan surten bé tenen un enorme éxit, ja que ningú s’explica la trampa; quan no van bé, els màgics tenen preparat un altre final, no tan brillant, però que els permet evitar el ridícul. També els jugadors de cartes ho fan servir: per exemple, en un llibre dels anys 301s’explica com utilitzar que les cartes estan mal escartejades per guanyar al bridge (com a incís, observem que des de finals dels anys 60 s’utilitzen màquines d’escartejar als campionats internacionals de bridge; quan s’escarteja a mà, si es fa un contrast estadístic es rebutja la hipòtesi que les cartes han quedat ben barrejades; quan es fa l’escartejat a màquina, el contrast accepta que han quedat ben remenades). Tornant al nostre problema, quan hom escarteja un joc de cartes no ho fa un cop, sino que utilitza un procediment iteratiu repentint diferents vegades la mateixa tècnica. Anem ara a pensar diferents mètodes d’escartejar: 1. Un mètode determinista Posem la 1a. carta al 3r. lloc: abc 1a.remenada -→bca 2a.remenada -→cab -→ · · · Per a conèixer el resultat de l’escarteig, nomès cal saber quants cops s’ha escartejat. 2. Un mètode aleatori Agafem la 1a. carta i la coloquem a l’atzar. El resultat, ara, ja no serà segur, sinó que es poden obtenir les ordenacions abc,bca obac, cadascuna amb probabilitat 1/3. Així, el resultat de remenar un cop serà la probabilitat següent: Ordenació abc acb bac bca cab cba Probabilitat 1/3 0 1/3 1/3 0 0 Quan tornem a escartejar, caldrà fer un diagrama d’arbre com el de la figura 1 per poder calcular les probabilitats. Després de cada escarteig tindrem una probabilitat sobre el conjunt {abc, acb, bac, bca, cab, cba}. Designarem per Pla probabilitat corresponent al primer escarteig, per P∗2la del segon, i així successivament. Tindrem: 1 E. Cumbelston, Contract bridge Red Book on Play, Winston, Philadelphia, 1930 (citat per Diaconis [5]). Quants cops cal escartejar? 67 Figura 1 Ordenació abc acb bac bca cab cba P1/3 0 1/3 1/3 0 0 P∗22/9 1/9 2/9 2/9 1/9 1/9 P∗35/27 4/27 5/27 5/27 4/27 4/27 .. .. . . Aquestes probabilitats convergeixen cap a la probabilitat uniforme, que designarem per U: Ordenació abc acb bac bca cab cba U1/6 1/6 1/6 1/6 1/6 1/6 Amb qualsevol sistema raonable d’escartejar tindrem que P∗n-→ n→∞ U, (en un sentit que definirem més endavant). La taula de les probabilitats del mètode determinista, per contra, posa de manifest les seves limitacions: Ordenació abc acb bac bca cab cba P0 0 0 1 0 0 P∗20 0 0 0 1 0 .. . . .. 68 Frederic Utzet Figura 2 i resulta obvi que aquestes probabilitats no poden convergir a la uniforme. Introduirem a la secció següent uns conceptes que permetran donar rigor a l’estudi. Per començar, definirem una distància d(P, Q) entre dues probabilitats P, Q (que serà un nombre entre 0 i 1), i demostrarem que si el procediment d’escartejar és raonable (expressió que definirem), aleshores d(P∗n, U) -→ n→∞ 0. Aquest, però, és un resultat asimptòtic sense gaire utilitat pràctica, ja que un illusionista o un jugador no en tenen prou amb saber que algun dia les cartes quedaran ben remenades: volen saber quants cops s’ha de remenar. Afinarem l’estudi fins a obtenir la velocitat de convergència de la successió. Però encara més, Persi Diaconis va demostrar que si el procediment d’escartejar és raonable, aleshores es produeix el fenomen que reflecteix la figura 2, on d(n) =d(P∗n, U). Així, si n < n0, aleshores d(n) ≃1 i és com si no haguéssim remenat. Si n≥n0, aleshores d(n) -→0 amb velocitat exponencial. Per tant, a n0es presenta un tall realment interessant. Aquests fenòmens de tall es donen en diferents situacions i tenen molt interés teòric i aplicat (per exemple, els algorismes per ordenar llistes). A part del problema d’escartejar, on hi ha una solució combinatòria directa (Bayer i Diaconis [3]), s’han trobat tres maneres d’estudiar aquests problemes: •Mètodes probabilístics: utilitzant temps d’atur forts, deguts a Aldous i Diaconis [1]. •Mètodes algebraics: aplicant representació de grups finits, de Diaconis i Shahshahani [8]. •Anàlisi funcional: utilitzant desigualtats de Sobolev logarítmiques, de Diaconis i Saloff-Coste [7, 8]. Com veieu, a tots aquests resultats hi intervé Persi Diaconis, que és un matemàtic a qui agrada especialment combinar les probabilitats amb altres branques de les matemàtiques, com la teoria de nombres, per exemple. Diaconis té una biografia força curiosa (vegeu [4]): nascut l’any 1945, als 14 anys va deixar l’escola i va marxar Quants cops cal escartejar? 69 de casa per seguir un il.lusionista de carrer. Cap als vint anys, intrigat pels jocs de mans on intervé l’atzar, va voler estudiar una mica de probabilitat, i un amic li va recomanar l’excel.lent llibre de Feller [10]. Com era d’esperar, no va entendre res; però en lloc d’anar plorant a demanar en Feller un camí màgic a la teoria de la probabilitat, Diaconis es va matricular a l’escola per estudiar matemàtiques: tenia 24 anys. Ha fet una carrera científica fulgurant, escrivint llibres i articles d’un gran nivell matemàtic i d’una extraordinària creativitat i originalitat. Als 37 anys li va ser concedit el premi de la Fundació MacArthur, el premi als genis (el sou de professor durant 5 anys sense fer cap classe) que s’atorga anualment a una persona entre tots els camps de la ciència i la tècnica. Actualment és professor a la Universitat de Harvard. 2 Probabilitats sobre el grup simètric Una millor manera de representar la barreja de kcartes seria utilitzar el grup de les permutacions de kelements, Sk(grup simètric); d’aquesta manera ens fixarem en l’acció d’escartejar, i no tant en el resultat que obtenim. Cada permutació serà una possible barreja; així, amb les tres cartes, l’escarteig de passar la carta de dalt de tot a baix el representarem per π= 1 2 3 3 1 2!, on l’aplicació i֏π(i) indica que la carta en la posició iabans de remenar passa a la posició π(i) després de fer-ho. Notem que la segona fila no dóna la nova ordenació. Insistim que la permutació es refereix a l’acció de remenar, mentre que l’ordenació és el resultat de remenar, que dependrà de l’ordre inicial. A l’inrevés, a qualsevol possible forma de remenar li correspon una (i només una) permutació. Considerem ara una altra remenada, per exemple la que canvia la primera carta per la tercera, que correspon a la permutació τ= 1 2 3 3 2 1!. La barreja que consisteix a aplicar primer πi després τés, precisament, la permutació producte, τ◦π, multiplicades, com és habitual, de dreta a esquerra: τ◦π= 1 2 3 1 3 2!. A partir d’ara escriurem les permutacions sense la fila de dalt; així, posarem només π=(π(1)π(2)···π(k)). Amb aquestes notacions, cada forma d’escartejar assignarà una probabilitat als element del grup Sk. Així, l’escartejat que consisteix a posar la primera carta a l’atzar serà ara la probabilitat Permutació (123) (132) (213) (231) (312) (321) Probabilitat 1/3 0 1/3 1/3 0 0 Considerem un determinat mètode d’escartejar donat per una probabilitat Psobre Sk. Aplicar-lo dues vegades vol dir primer escollir a l’atzar (segons P) una permutació (posem π), ordenar les cartes d’acord amb aquesta permutació, escollir una 70 Frederic Utzet segona permutació (posem τ) i tornar a ordenar les cartes; per tant, el resultat final correspon al fet d’haver aplicat una permutació τ◦πa l’ordenació inicial de les cartes. Tota aquesta operació defineix una probabilitat, que designarem P∗2, sobre Sk. Per calcular aquesta probabilitat notem que les dues eleccions son independents, i que amb P∗2elegirem una determinada permutació σa través d’elegir qualsevol permutacions πiτtals que σ=τ◦π. Llavors, P∗2(σ) =X τ◦π=σ P(π)P(τ) =X π∈S3 P(π)P(σ ◦π−1). Evidentment aquest procediment és equivalent al diagrama d’arbre que hem utilitzat anteriorment. Iterant el procés podrem calcular P∗n 3 Probabilitats sobre grups finits Estendrem les idees anteriors a una probabilitat sobre un grup. Sigui Gun grup finit; una probabilitat sobre Gés una aplicació P:G-→[0,1] tal que X s∈G P(s) =1. La probabilitat d’un subconjunt de Ges calcula per P(A) =X s∈A P(s), A ⊂G. S’anomena probabilitat uniforme sobre Gla probabilitat que dóna la mateixa massa a tots els elements de G: U(s) =1 Card(G),∀s∈G. Donades dues probabilitats PiQsobre G, es defineix el seu producte de convolució per Q∗P(s) =X t∈G P(t)Q(s t−1). També, per a dues probabilitats, la distància de la variació es defineix per d(P, Q) =max A⊂G|P(A) −Q(A)| =1 2X s∈G |P(s) −Q(s)|. El següent teorema tanca la primera etapa del nostre recorregut: 1 Teorema (Perron–Frobenius) Si Pno està concentrada en una classe lateral d’un subgrup, aleshores lim nd(P∗n, U) =0. Quants cops cal escartejar? 71 Comentaris: 1. I. Csiszar, Informationstheoretishe Konvergenzbegriffe, Im Raum der Wahrscheinlichkeits-Verteilingen, Pub. Math. Inst., Hungarian Acad. Sciences VII, 137–158, 1962 (referència citada per Diaconis [5]) explica «el perquè de tot plegat»: A l’anar fent convolucions, l’entropia augmenta; el màxim d’entropia s’assoleix amb la probabilitat uniforme. 2. Un mètode d’escartejar serà raonable si la probabilitat corresponent compleix la hipòtesi del teorema. La probabilitat de l’escartejat determinista està concentrada en {(312)}, que és una classe lateral de S3. 4 Càlculs explícits per a una passejada aleatòria sobre la circumferència Veurem ara un exemple on la distància d(P∗n, U) pot ser calculada amb una molt bona aproximació. Pensem en Zpcom ppunts sobre una circumferència. Imaginem una partícula inicialment en el zero i que cada segon es mou a dreta o esquerra amb probabilitat 1/2. Equivalentment, tenim una probabilitat Psobre el grup Zpdefinida per P(1)=P(p −1)=1/2. Després de dues passes tindrem una probabilitat P∗2, i així successivament. Per tal d’estudiar el comportament asimptòtic de P∗nutilitzarem una tècnica habitual en matemàtiques, que consisteix a canviar els nostres objectes (en aquest cas, probabilitats sobre Zp) per uns d’equivalents però amb més bones propietats respecte a l’operació o la característica que ens interessa (en aquest cas, la convolució). Concretament, utilitzarem la transformada de Fourier, que en la situació que ens ocupa s’anomena (a matemàtica aplicada) trasformada discreta de Fourier. Donada una probabilitat Qsobre Zp, o, més generalment, un vector de dimensió p,Q=(Q(0), . . . , Q(p −1)), li associem un vector complex b Q=(b Q(0), . . . , b Q(p −1)) definit per b Q(j) = p−1 X k=0 e2πijk/pQ(k), que s’anomena transformada de Fourier de Q. Aquest vector b Qté les següents propietats: •Fórmula d’inversió de Fourier: Q(j) =1 p p−1 X k=0 e−2πijk/p b Q(k), és a dir, la transformada de Fourier b Qdetermina Q. 72 Frederic Utzet •Trivialització de la convolució: la transformada de Fourier canvia el producte de convolució per un producte ordinari. Æ Q∗R (j) =b Q(j) b R(j). En particular, Å Q∗n(j) =b Q(j)n. Aquesta darrera propietat ens serà especialment important per a calcular el valor de d(P∗n, U), ja que el càlcul directe de P∗nés molt enfarfegat, mentre que el de b Qnés molt senzill. Utilitzar la transformada de Fourier és com «calçar-se les botes de set llegües». •Fórmula de Plancharel, que estableix la conservació del producte escalar: X j Q(j)R(j) =1 pX kb Q(k) b R(k). Tornem a la passejada aleatòria sobre Zp: recordem que teníem la probabilitat definida per P(1)=P(p −1)=1/2. Aleshores b P(j) =cos 2πj p, j =0,...,p−1. La probabilitat uniforme sobre Zp, U(j) =1 p,∀j∈Zp, té una transformada de Fourier molt senzilla, ja que la suma de les parrels p-èsimes de la unitat és zero: b U(j) =1 p p−1 X k=0 e2πijk/p =(1, j =0, 0, j =1,...,p−1. Llavors, per a j=0 Å P∗n(0)=cos2π0 pn=1-→ n→∞ 1=b U(0), i per a j6= 0, Å P∗n(j) =cos2πj pn -→ n→∞ 0=b U(j), d’on és ben evident que lim nd(P∗n, U) =0. Però anem a afinar més els càlculs per tal d’establir la velocitat de convergència: Quants cops cal escartejar? 73 d(P∗n, U)2=1 4p−1 X j=0 |P∗n(j) −U(j)|2 ≤1 4p p−1 X j=0P∗n(j) −U(j)2(Cauchy −Schwarz) =1 4 p−1 X j=0Å P∗n(j) −b U(j)2(Plancharel) ≤1 4 p−1 X j=1b P(j)2n=1 4 p−1 X j=1cos2πj pn . Ara s’utilitza la desigualtat cosx≤e−x2/2, x ∈[0, π/2], i treballant una mica s’arriba al següent teorema: 2 Teorema Sigui pimparell, p≥7. Per a qualsevol n≥p2, d(P∗n, U) ≤e−αn/p2, i per a qualsevol n, d(P∗n, U) ≥1 2e−αn/p2−βn/p4, on α=π2/2iβ=π4/11. Amb aquest teorema a la mà, podem afirmar que calen p2passos per quedar pròxims a la probabilitat uniforme. 5 El cas general: representacions d’un grup finit La generalització de l’anàlisi de Fourier utilitza la representació d’un grup finit. Sigui, doncs, Gun grup finit. Una representació de Gés un homomorfisme ρ:G→GL(V), on Vés un espai vectorial de dimensió finita sobre el cos dels nombres complexos iGL(V) és el grup de les aplicacions lineals bijectives de Ven V. La dimensió de V s’anomena dimensió de la representació. També és fonamental la noció de representació irreductible, que ens proporciona els elements bàsics amb què es construeixen totes les representacions. Direm que una representació ρés irreductible si no existeix cap subespai Wde Vno trivial tal que ρ(s)(W) ⊂W,∀s∈G. Sigui ara Quna probabilitat (o una funció) sobre G. La transformada de Fourier de Qassociada a la representació ρés la matriu b Q(ρ) =X s∈G Q(s)ρ(s). Les propietats fonamentals de la transformada discreta de Fourier són també certes en aquesta situació general: