Modelo de Gilbert-Shannon-Reeds

En las matemáticas de barajar naipes , el modelo de Gilbert–Shannon–Reeds es una distribución de probabilidad en permutaciones de barajado aleatorio . ^[1] Forma la base para una recomendación de que una baraja de cartas debe barajarse siete veces para aleatorizarla completamente. ^[2] Recibe su nombre del trabajo de Edgar Gilbert , Claude Shannon y J. Reeds, reportado en un informe técnico de 1955 por Gilbert ^[3] y en un manuscrito inédito de Reeds de 1981.

El modelo

Una permutación aleatoria de una secuencia de elementos se obtiene dividiendo los elementos en dos subsecuencias contiguas y luego intercalando arbitrariamente las dos subsecuencias. Por ejemplo, esto describe muchas formas comunes de barajar una baraja de cartas, dividiendo la baraja en dos pilas de cartas que luego se barajan juntas. El modelo de Gilbert–Shannon–Reeds asigna una probabilidad a cada una de estas permutaciones. De esta manera, describe la probabilidad de obtener cada permutación, cuando se realiza una baraja aleatoria. El modelo puede definirse de varias formas equivalentes, describiendo formas alternativas de realizar esta baraja aleatoria:

• De manera muy similar a la forma en que los humanos barajan las cartas, el modelo de Gilbert-Shannon-Reeds describe las probabilidades obtenidas a partir de un determinado modelo matemático de cortar y luego barajar al azar una baraja de cartas. Primero, la baraja se corta en dos paquetes. Si hay un total de cartas, entonces la probabilidad de seleccionar cartas en la primera baraja y en la segunda baraja se define como . Luego, una carta a la vez se mueve repetidamente desde la parte inferior de uno de los paquetes hasta la parte superior de la baraja barajada, de modo que si quedan cartas en un paquete y quedan cartas en el otro paquete, entonces la probabilidad de elegir una carta del primer paquete es y la probabilidad de elegir una carta del segundo paquete es . ^[2] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n-k}$ ${\displaystyle {\tbinom {n}{k}}/2^{n}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x/(x+y)}$ ${\displaystyle y/(x+y)}$
• Una segunda descripción alternativa puede basarse en una propiedad del modelo, que genera una permutación de la baraja inicial en la que cada carta tiene la misma probabilidad de haber venido del primer o del segundo paquete. ^[2] Para generar una permutación aleatoria según este modelo, comience por lanzar una moneda al aire varias veces, para determinar para cada posición de la baraja mezclada si proviene del primer paquete o del segundo paquete. Luego divídala en dos paquetes cuyos tamaños sean el número de cruces y el número de caras lanzadas, y use la misma secuencia de lanzamiento de moneda para determinar de qué paquete sacar cada carta de la baraja mezclada. ${\displaystyle n}$
• Una tercera descripción alternativa es más abstracta, pero se presta mejor al análisis matemático. Se genera un conjunto de valores a partir de la distribución continua uniforme en el intervalo unitario y se los coloca en orden. Luego, el mapa de duplicación de la teoría de sistemas dinámicos asigna este sistema de puntos a una permutación de los puntos en la que el orden permutado obedece al modelo de Gilbert-Shannon-Reeds, y las posiciones de los nuevos puntos son nuevamente uniformemente aleatorias. ^{[2] [4]} ${\displaystyle n}$ ${\displaystyle x\mapsto 2x{\pmod {1}}}$

Entre todas las posibles permutaciones de barajado de una baraja de cartas, el modelo de Gilbert–Shannon–Reeds otorga a casi todas las barajas la misma probabilidad, , de ocurrir. Sin embargo, hay una excepción, la permutación identidad , que tiene una mayor probabilidad de ocurrir. ^[5] ${\displaystyle 1/2^{n}}$ ${\displaystyle (n+1)/2^{n}}$

Inverso

La permutación inversa de una baraja aleatoria se puede generar directamente. Para ello, se comienza con una baraja de n cartas y luego se reparten repetidamente las cartas inferiores de la baraja en una de dos pilas, eligiendo al azar con la misma probabilidad en cuál de las dos pilas se repartirá cada carta. Luego, cuando se hayan repartido todas las cartas, se vuelven a apilar las dos pilas. ^[2]

El efecto de los riffles repetidos

Bayer y Diaconis (1992) analizaron matemáticamente la distancia de variación total entre dos distribuciones de probabilidad en permutaciones: la distribución uniforme en la que todas las permutaciones son igualmente probables, y la distribución generada por aplicaciones repetidas del modelo de Gilbert-Shannon-Reeds. La distancia de variación total mide cuán similares o diferentes son dos distribuciones de probabilidad; es cero solo cuando las dos distribuciones son idénticas, y alcanza un valor máximo de uno para distribuciones de probabilidad que nunca generan los mismos valores entre sí. Bayer y Diaconis informaron que, para barajas de n cartas barajadas veces, donde θ es una constante arbitraria, la distancia de variación total es cercana a uno cuando θ es significativamente menor que cero, y cercana a cero cuando θ es significativamente mayor que cero, independientemente de  n . En particular, sus cálculos mostraron que para n  = 52, cinco riffles producen una distribución cuya distancia de variación total desde el uniforme todavía es cercana a uno, mientras que siete riffles dan una distancia de variación total de 0,334. Este resultado fue ampliamente difundido como una implicación de que las barajas de cartas deberían barajarse siete veces para aleatorizarlas completamente. ^{[6] [7] [8]} ${\displaystyle {\tfrac {3}{2}}\log _{2}n+\theta }$

Se han realizado análisis similares utilizando la divergencia de Kullback-Leibler , una distancia entre dos distribuciones de probabilidad definidas en términos de entropía ; la divergencia de una distribución con respecto a la uniformidad puede interpretarse como el número de bits de información que aún se pueden recuperar sobre el estado inicial de la baraja de cartas. Los resultados son cualitativamente diferentes: en lugar de tener un umbral claro entre aleatorio y no aleatorio en las mezclas, como ocurre con la distancia de variación total, la divergencia decae más gradualmente, disminuyendo linealmente a medida que el número de mezclas varía de cero a (momento en el que el número de bits de información restantes es lineal, menor por un factor logarítmico que su valor inicial) y luego disminuye exponencialmente hasta que, después de las mezclas, solo queda un número constante de bits de información. ^{[9] [10]} ${\displaystyle {\tfrac {3}{2}}\log _{2}n}$ ${\displaystyle \log _{2}n}$ ${\displaystyle {\tfrac {3}{2}}\log _{2}n}$

Referencias

1. Diaconis, Persi (1988), Representaciones grupales en probabilidad y estadística , Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, California: Institute of Mathematical Statistics, ISBN 978-0-940600-14-0, Sr.  0964069.
2. Bayer, Dave ; Diaconis, Persi (1992), "Siguiendo el rastro del juego de cola de milano hasta su guarida" (PDF) , The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR  2959752, MR  1161056.
3. Gilbert, E. (1955), Teoría de la mezcla , Memorándum técnico, Bell Labs
4. Lalley, Steven P. (1999), "Mezclas de Riffle y sus sistemas dinámicos asociados", Journal of Theoretical Probability , 12 (4): 903–932, doi :10.1023/A:1021636902356, MR  1729462, S2CID  123898250.
5. Esto se desprende inmediatamente del Teorema 1 de Bayer y Diaconis (1992) junto con la observación de que la permutación identidad tiene una secuencia ascendente y todas las demás permutaciones de riffle tienen exactamente dos secuencias ascendentes. Lalley (1999) en cambio afirma erróneamente que todas las permutaciones son probables.
6. Austin, David (diciembre de 2010), ¿Cuántas veces tengo que barajar esta baraja?, Columnas destacadas de AMS.
7. Numb3rs 519: Ritos animales, Actividades matemáticas de Numb3rs, Departamento de Matemáticas de la Universidad de Cornell.
8. Kolata, Gina (9 de enero de 1990), "Al barajar cartas, el 7 es el número ganador", New York Times.
9. Trefethen, LN ; Trefethen, LM (2000), "¿Cuántas barajas se deben hacer para aleatorizar una baraja de cartas?", Actas de la Royal Society of London. Series A: Ciencias matemáticas, físicas y de ingeniería , 456 (2002): 2561–2568, Bibcode :2000RSPSA.456.2561T, doi :10.1098/rspa.2000.0625, MR  1796496, S2CID  14055379.
10. Stark, Dudley; Ganesh, A.; O'Connell, Neil (2002), "Pérdida de información en el barajado rápido", Combinatorics, Probability and Computing , 11 (1): 79–95, doi :10.1017/S0963548301004990, MR  1888184, S2CID  29990983.