¿Cómo barajar una baraja por partes?

Question

Esta pregunta es principalmente una curiosidad, pero proviene de una experiencia práctica (todos los jugadores de Carrera por la galaxia por ejemplo, deben haberse hecho la pregunta).

Supongamos que tengo una baraja de cartas que quiero barajar. Por desgracia, la baraja es tan grande que no puedo sostenerla por completo en mis manos. Digamos que la baraja contiene $kn$ cartas, y que las operaciones que puedo realizar son 1. cortar un mazo en cualquier número de submazos, sin mirar las cartas pero recordando para todos $i$ donde el $i$ -enésima carta de la parte superior del mazo original; 2. reunir varios mazos en un solo mazo en cualquier orden (pero suponiendo que no se entrecruzan los distintos mazos, ni se cambia el orden dentro de ninguno de ellos); 3. barajar cualquier mazo de como máximo $n$ tarjetas. Supongamos además que dicha barajada consiste en aplicar una permutación aleatoria desconocida extraída uniformemente.

He aquí la pregunta: ¿es posible diseñar un número finito de tales operaciones de modo que la baraja resultante tenga una ley uniforme entre todas las permutaciones posibles de la baraja original? En caso afirmativo, ¿cuántas barajadas son necesarias, o suficientes, para conseguirlo?

El caso $k=2$ parece ya interesante.

Answer 1

Una distribución verdaderamente uniforme, no. (Bueno, tu pregunta no está del todo bien planteada, pero argumentaré esto para la mayoría de las formas de hacerlo). Hay $(kn)!$ formas factoriales de barajar una baraja de $kn$ tarjetas. Así que quieres que cada permutación ocurra con probabilidad $1/(kn)!$ . En particular, para cada primo $p \leq kn$ , usted quiere $p$ en el denominador de la probabilidad de que se produzca cada permutación. Veamos sus operaciones: Reordenación $i$ las cubiertas sólo pueden introducir primos $\leq i$ . Barajando perfectamente un $n$ la baraja de cartas sólo puede introducir primos $\leq n$ . El corte depende del modelo matemático que se utilice para el corte; si todos los puntos de corte tienen la misma probabilidad, sólo se obtienen los primos que dividen $n(n-1)\ldots (n-i+1)$ . Imagino que otros modelos de corte causarán problemas similares.

La cuestión más estudiada es cómo obtener una distribución de probabilidad que sea extremadamente cercana al azar. Hay muchos buenos resultados al respecto; véase Siguiendo el rastro de la cola de milano hasta su guarida .

Answer 2

Aunque la respuesta de David resuelve la pregunta original, no hay razón para limitarse al caso en que el número total de cartas sea un múltiplo de $n$ . En general, podemos preguntarnos si es posible barajar completamente una baraja con $M$ tarjetas si sólo $n$ -Los submecados de cartas son directamente barajables.

Como señala David, esto es necesariamente imposible si existe un primo $p$ para lo cual $n < p \leq M$ . Esto significa que el caso más pequeño que aún está abierto es $n=3$ y $M=4$ . Es decir, ¿es posible aleatorizar completamente una baraja de 4 cartas si sólo se pueden barajar 2 o 3 cartas a la vez?

Answer 3

Suponiendo que quieras una respuesta práctica a "Tengo demasiadas cartas en mis manos a la vez; ¿cómo puedo barajarlas razonablemente bien en un tiempo relativamente corto?", puede que quieras considerar una "barajada paralela", distribuyendo el trabajo entre varios jugadores con la esperanza de que podamos conseguir un mazo adecuadamente barajado en menos minutos de reloj de pared que una barajada de una sola persona, incluso si requiere más operaciones totales y minutos de jugador que una barajada de una sola persona.

Me recuerda al "diagrama de mariposa FFT" utilizado en el procesamiento digital de señales y a la "red Omega" utilizada en algunos clusters de ordenadores, basada en la "interconexión perfecta".

http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg

http://github.com/vijendra/Omega-network/raw/master/16X16.png

Algoritmo paralelo de barajar y dar: (para $k \le n$ )

• de alguna manera, da a k jugadores n cartas a cada uno (o bien coge un bloque de n cartas de la parte superior para cada jugador, o reparte uniformemente las cartas a los k jugadores)
• barajar: cada uno de los k jugadores baraja uniformemente su submazo de n cartas
• repartir: cada uno de los k jugadores reparte por igual -- boca abajo -- su submazo a los otros k jugadores (incluida ella misma). De forma equivalente, cada jugadora divide su submantel en k submanteles iguales y distribuye un submantel a cada jugador (incluida ella misma). Después de que todos los jugadores hayan repartido, cada jugador reúne sus cartas (unas cuantas de cada jugador, incluida ella misma) en un submazo de n cartas.
• barajar: (como arriba)

En esta etapa (1 ronda), hemos hecho el equivalente a aleatorizar cada fila de una matriz, y luego cada columna. Cualquier carta particular podría ser en cualquier lugar después de una ronda de barajar-descartar-barajar, con igual probabilidad. Por desgracia, en esta fase, todavía hay algunas permutaciones que tienen probabilidad cero. Por ejemplo, las posibles permutaciones equivalentes a una rotación por cizalla (RBS) ("¿cómo rotar un mapa de bits?") requieren 3 cizallas. Lo más cercano que puede producir una sola ronda de barajar-desbaratar-barajar es 2 cizallas, lo que no es suficiente para producir esas permutaciones. Así que continuamos con la segunda ronda:

• trato: (como arriba)
• barajar: (como arriba)
• reunir todas las subcubiertas en una gran cubierta completa

El algoritmo completo de 2 rondas shuffle-deal-shuffle-deal-shuffle puede producir cualquier permutación posible, pero cada permutación no tiene exactamente la misma probabilidad.

Cada uno de los dos pasos de "reparto" mezcla al menos tan bien como una sola barajada de las cartas completas. El documento - por Dave Bayer y Persi Diaconis - que David Speyer mencionó demuestra que $m = \frac{3}{2} \log_2 (kn) + \theta$ barajan los rizos son suficientes.