Permutación aleatoria

En las matemáticas de las permutaciones y el estudio de barajar naipes , una permutación barajada es una de las permutaciones de un conjunto de elementos que se pueden obtener mediante una sola baraja , en la que una baraja de cartas ordenada se corta en dos paquetes y luego, los dos paquetes se entrelazan (por ejemplo, moviendo las cartas una por una desde la parte inferior de uno u otro de los paquetes hasta la parte superior del mazo ordenado). Comenzando con un conjunto ordenado (1 secuencia ascendente), matemáticamente una mezcla aleatoria 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 sorteo 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 un -shuffle está completamente determinado por cómo se asignan sus primeros elementos, el número de -shuffles es ${\displaystyle (p,q)}$ ${\displaystyle p}$ ${\displaystyle (p,q)}$

$${\displaystyle {\binom {p+q}{p}}.}$$

Sin embargo, el número de rifles distintos no es exactamente la suma de esta fórmula sobre todas las opciones de y sumando (que sería ), porque la permutación de identidad se puede representar de múltiples maneras como una mezcla para diferentes valores de y . En cambio, el número de permutaciones distintas de barajado 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 el 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 aleatoria como la permutación inversa de una mezcla aleatoria es ^[3]

$${\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 el OEIS )

y hay exactamente 23427 combinaciones aleatorias invertibles. ${\displaystyle n=52}$

Distribución aleatoria

El modelo de Gilbert-Shannon-Reeds describe una distribución de probabilidad aleatoria en mezclas rápidas que coincide bien con las mezclas humanas observadas. ^[4] En este modelo, la permutación de identidad tiene probabilidad de generarse y todas las demás permutaciones de rifle tienen la misma probabilidad de generarse. Basándose en su análisis de este modelo, los matemáticos han recomendado que a una baraja de 52 cartas se le den siete rifles para poder 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 reduciendo estos valores al rango de 1 a preservando su orden. Varias familias importantes de permutaciones pueden caracterizarse por un conjunto finito de patrones prohibidos, y esto también se aplica a las permutaciones aleatorias: 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 único patrón mínimo prohibido. ^[6] ${\displaystyle k}$ ${\displaystyle k}$

Mezclas perfectas

Una barajada perfecta es un sorteo en el que la baraja se divide en dos paquetes del mismo tamaño y en el que el entrelazado entre estos dos paquetes alterna estrictamente entre los dos. Hay dos tipos de barajado perfecto, un barajado de entrada y un barajado de salida , los cuales pueden ser realizados de forma consistente por algunas personas bien entrenadas. Cuando un mazo se baraja repetidamente usando estas permutaciones, sigue siendo mucho menos aleatorio que con las típicas barajas rápidas, y volverá a su estado inicial después de sólo una pequeña cantidad de barajadas perfectas. En particular, una baraja de 52 cartas volverá a su orden original después de 52 barajas u 8 barajas. Este hecho constituye la base de varios trucos de magia. ^[7]

Álgebra

Se pueden utilizar combinaciones aleatorias para definir el álgebra aleatoria . Esta es un álgebra de Hopf donde 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 y una forma se puede definir como una suma barajada . ^[2] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle (p,q)}$

Ver también

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

Referencias

1. Aldous, David ; Diaconis, Persi (1986), "Barajar cartas y detener tiempos" (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. 181. Prensa de la Universidad de Cambridge, Cambridge.
3. Atkinson, MD (1999), "Permutaciones restringidas", Matemáticas discretas , 195 (1–3): 27–38, doi : 10.1016/S0012-365X(98)00162-9 , SEÑOR  1663866.
4. Diaconis, Persi (1988), Representaciones de grupos en probabilidad y estadística , Notas de conferencias del Instituto de Estadística Matemática — Serie de monografías, 11, Hayward, CA: Instituto de Estadística Matemática, ISBN 0-940600-14-5, señor  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 , Ph.D. tesis, Departamento de Matemáticas, Universidad Tecnológica de Chalmers, CiteSeerX 10.1.1.103.2001 .
7. Diaconis, Persi ; Graham, RL ; Kantor, William M. (1983), "Las matemáticas de las mezclas aleatorias perfectas", Avances en Matemáticas Aplicadas , 4 (2): 175–196, CiteSeerX 10.1.1.77.7769 , doi :10.1016/0196-8858(83)90009- X, SEÑOR  0700845 .