Permutación aleatoria de riffles

En las matemáticas de permutaciones y el estudio del barajado de cartas , una permutación de barajado rápido es una de las permutaciones de un conjunto de elementos que se pueden obtener mediante un único barajado rápido , en el que una baraja de cartas ordenada se corta en dos paquetes y luego los dos paquetes se intercalan (por ejemplo, moviendo las cartas una a la vez desde la parte inferior de uno u otro de los paquetes hasta la parte superior de la baraja ordenada). Comenzando con un conjunto ordenado (1 secuencia ascendente), matemáticamente un barajado rápido se define como una permutación en este conjunto que contiene 1 o 2 secuencias ascendentes. ^[1] Las permutaciones con 1 secuencia ascendente son las permutaciones identidad. ${\displaystyle n}$ ${\displaystyle n}$

Como caso especial de esto, un -shuffle , para números y con , es un barajado en el que el primer paquete tiene cartas y el segundo paquete tiene cartas. ^[2] ${\displaystyle (p,q)}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p+q=n}$ ${\displaystyle p}$ ${\displaystyle q}$

Enumeración combinatoria

Dado que una -shuffle está completamente determinada por cómo se asignan sus primeros elementos, la cantidad de -shuffles es ${\displaystyle (p,q)}$ ${\displaystyle p}$ ${\displaystyle (p,q)}$ $${\displaystyle {\binom {p+q}{p}}.}$$

Sin embargo, el número de barajas distintas no es exactamente la suma de esta fórmula sobre todas las opciones de y sumando (que sería ), porque la permutación identidad se puede representar de múltiples maneras como una baraja para diferentes valores de y . En cambio, el número de permutaciones distintas de barajas de una baraja de cartas, para , es ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle (p,q)}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle n=1,2,3,\dots }$

1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... (secuencia A000325 en la OEIS )

De manera más general, la fórmula para este número es ; por ejemplo, hay 4503599627370444 permutaciones aleatorias de una baraja de 52 cartas. ${\displaystyle 2^{n}-n}$

El número de permutaciones que son tanto una permutación de mezcla aleatoria como la permutación inversa de una mezcla aleatoria es ^[3] Para , esto es $${\displaystyle {\binom {n+1}{3}}+1.}$$ ${\displaystyle n=1,2,3,\dots }$

1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... (secuencia A050407 en la OEIS )

y porque hay exactamente 23427 barajas invertibles. ${\displaystyle n=52}$

Distribución aleatoria

El modelo de Gilbert–Shannon–Reeds describe una distribución de probabilidad aleatoria en barajadas aleatorias que coincide bien con las barajadas humanas observadas. ^[4] En este modelo, la permutación identidad tiene probabilidad de ser generada, y todas las demás permutaciones aleatorias tienen la misma probabilidad de ser generadas. Basándose en su análisis de este modelo, los matemáticos han recomendado que se le den siete barajadas aleatorias a una baraja de 52 cartas para aleatorizarla completamente. ^[5] ${\displaystyle (n+1)/2^{n}}$ ${\displaystyle 1/2^{n}}$

Patrones de permutación

Un patrón en una permutación es una permutación más pequeña formada a partir de una subsecuencia de algunos valores en la permutación al reducir estos valores al rango de 1 a mientras se preserva su orden. Varias familias importantes de permutaciones pueden caracterizarse por un conjunto finito de patrones prohibidos, y esto es cierto también para las permutaciones de barajado rápido: son exactamente las permutaciones que no tienen 321, 2143 y 2413 como patrones. ^[3] Así, por ejemplo, son una subclase de las permutaciones vexilares , que tienen 2143 como su único patrón prohibido mínimo. ^[6] ${\displaystyle k}$ ${\displaystyle k}$

Barajas perfectas

Un barajado perfecto es un barajado en el que la baraja se divide en dos paquetes de igual tamaño, y en el que el intercalado entre estos dos paquetes se alterna estrictamente entre los dos. Hay dos tipos de barajado perfecto, un barajado hacia adentro y un barajado hacia afuera , los cuales pueden ser realizados de manera consistente por algunas personas bien entrenadas. Cuando una baraja se baraja repetidamente utilizando estas permutaciones, sigue siendo mucho menos aleatoria que con barajadas típicas de barajado, y volverá a su estado inicial después de solo una pequeña cantidad de barajadas perfectas. En particular, una baraja de 52 cartas volverá a su orden original después de 52 barajadas hacia adentro u 8 barajadas hacia afuera. Este hecho forma la base de varios trucos de magia. ^[7]

Álgebra

Las combinaciones aleatorias se pueden utilizar para definir el álgebra aleatoria . Se trata de un álgebra de Hopf en la que la base es un conjunto de palabras y el producto es el producto aleatorio denotado por el símbolo sha ш, la suma de todas las combinaciones aleatorias de dos palabras.

En álgebra exterior , el producto de cuña de una forma a y una forma a se puede definir como una suma sobre barajas. ^[2] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle (p,q)}$

Véase también

• Permutaciones de Gilbreath , las permutaciones formadas al invertir uno de los dos paquetes de cartas antes de barajarlos.

Referencias

1. Aldous, David ; Diaconis, Persi (1986), "Barajar cartas y tiempos de parada" (PDF) , The American Mathematical Monthly , 93 (5): 333–348, doi :10.2307/2323590, JSTOR  2323590, MR  0841111
2. Weibel, Charles (1994). Introducción al álgebra homológica , pág. 181. Cambridge University Press, Cambridge.
3. Atkinson, MD (1999), "Permutaciones restringidas", Matemáticas discretas , 195 (1–3): 27–38, doi : 10.1016/S0012-365X(98)00162-9 , MR  1663866.
4. Diaconis, Persi (1988), Representaciones grupales en probabilidad y estadística , Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, CA: Institute of Mathematical Statistics, ISBN 0-940600-14-5, Sr.  0964069.
5. Kolata, Gina (9 de enero de 1990), "Al barajar cartas, el 7 es el número ganador", New York Times.
6. Claesson, Anders (2004), Patrones de permutación, fracciones continuas y un grupo determinado por un conjunto ordenado , tesis doctoral, Departamento de Matemáticas, Chalmers University of Technology, CiteSeerX 10.1.1.103.2001 .
7. Diaconis, Persi ; Graham, RL ; Kantor, William M. (1983), "Las matemáticas de las mezclas perfectas", Advances in Applied Mathematics , 4 (2): 175–196, CiteSeerX 10.1.1.77.7769 , doi :10.1016/0196-8858(83)90009-X, MR  0700845 .