Barajar es más difícil de lo que parece: un millón de pruebas del mezclado de una línea

Un millón de mezclas de cuatro elementos

Cuatro elementos tienen veinticuatro órdenes. Es lo bastante pequeño para contarlo de forma exhaustiva, y eso lo convierte en el caso de prueba adecuado: lanza un mezclado un millón de veces, cuenta con qué frecuencia sale cada uno de los veinticuatro, y un mezclado justo tiene que poner unos 41 667 en cada casilla. Todo lo que favorezca sistemáticamente algunos órdenes aparecerá como un bulto, y un solo número — el estadístico ji-cuadrado — convierte toda la tabla en un veredicto. Con 23 grados de libertad, un método justo puntúa alrededor de 23, y cualquier cosa por encima de 27,32 ocurriría menos del 5 % de las veces solo por azar.

El de una línea puntuó 125 397. Ni 30, ni 300 — cinco mil veces el umbral. El orden más frecuente, BADC, salió 62 810 veces; el más raro, DBCA, 30 998. El orden original ABCD sobrevivió intacto 62 485 veces, vez y media más de lo debido. Pasar el mismo millón por un Fisher-Yates bien escrito produjo 10,3, que es el aspecto de un método justo: los extremos fueron 41 434 y 41 879, una dispersión de en torno al 1 %. Estirar la prueba a cinco elementos ensancha aún más la brecha — 229 683 frente a 89,0 — porque cada elemento extra da al algoritmo de ordenación una decisión más que tomar mal.

No veinticuatro probabilidades, sino dos

Los recuentos no están dispersos. Ordenados, caen en dos grupos apretados: ocho órdenes en torno a 62 500 y dieciséis en torno a 31 250. Son exactamente 1/16 y 1/32 de un millón, y la aritmética cierra — 8 × (1/16) + 16 × (1/32) = 1. Cuatro millones de pruebas más contrastaron esa hipótesis directamente y produjeron un ji-cuadrado de 19,7 con 23 grados de libertad, un buen ajuste. Así que el mezclado de una línea en este motor no es aproximadamente uniforme con un temblor: es una distribución de dos valores en la que la mitad de la masa de probabilidad se apiña en un tercio de los resultados.

Los ocho órdenes favorecidos comparten una propiedad digna de notar: ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC y DBAC mantienen todos la C fuera de las dos primeras posiciones. No es misticismo, es el algoritmo de ordenación asomando. Un array de cuatro elementos es corto, así que V8 nunca abandona su camino de inserción binaria; el comparador se llama 4,5 veces de media, y 4,5 lanzamientos de moneda no pueden generar 24 resultados equiprobables, porque 24 no divide ninguna potencia de dos. El sesgo está horneado en la forma del árbol de decisión antes incluso de que intervenga el azar.

El sesgo pertenece al motor, no al lenguaje

ECMA-262 exige que la función de comparación pasada a sort sea un comparador coherente: transitivo, antisimétrico y que dé la misma respuesta para el mismo par siempre. Un comparador construido sobre Math.random rompe los tres en una sola llamada. La respuesta de la especificación no es definir qué ocurre, sino decir que si el comparador es incoherente el resultado de la ordenación queda definido por la implementación. Esa única frase es toda la historia. No has escrito un mezclado con estadísticas inusuales — has escrito un programa cuya salida el estándar se niega a especificar.

La consecuencia práctica es que estos recuentos miden un motor en una versión, no una constante universal. V8 ha cambiado su ordenación más de una vez; una ejecución en otro motor, o en el mismo tras una actualización, producirá otra distribución grumosa, y un array lo bastante largo para disparar el camino de fusión producirá otra más. Nada en el estándar lo prohíbe, y nada te avisa cuando ocurre. Un mezclado cuyas propiedades estadísticas se mueven cuando se parchea el entorno de ejecución no es un mezclado que puedas testear.

Fisher-Yates y el error de índice que lo arruina

El algoritmo correcto — el Algoritmo P de Knuth — recorre el array desde el último índice hasta el segundo, y en cada posición i saca un índice j uniformemente entre 0 e i inclusive, y luego intercambia las posiciones i y j. Tres detalles sostienen toda la demostración. El bucle desciende. El sorteo incluye la propia i, así que un elemento puede quedarse donde está. Y el rango se encoge en uno cada iteración, de modo que el número de caminos de ejecución es n × (n−1) × … × 2 = n!, exactamente el número de permutaciones. Una biyección entre caminos de ejecución y resultados es lo que significa uniformidad, y vale para todo n, no solo para los que probaste.

Cambia un carácter y se rompe. La variante habitual recorre el array hacia arriba y saca j de todo el array cada vez, lo que parece más aleatorio y no lo es. Esa versión tiene n^n caminos de ejecución, y n^n nunca es múltiplo de n! para n mayor que 2, así que algunas permutaciones han de ser alcanzables por más vías que otras. Medida sobre el mismo millón de pruebas puntuó 29 913 — mil veces el umbral, con el orden más frecuente en 58 698 y el más raro en 31 233. Es el más peligroso de los dos errores precisamente porque se parece a la versión del libro de texto y pasa cualquier inspección visual.

Sesgo de módulo: la segunda forma de torcer un mezclado

Fisher-Yates necesita un entero uniforme en un rango, y la forma obvia de sacarlo de un valor aleatorio de 32 bits es tomar el módulo del tamaño del rango. Eso es uniforme solo si el rango divide exactamente a 2^32. Normalmente no lo hace: 2^32 módulo 52 es 48, así que 48 de los 52 resultados reciben una preimagen más que los otros cuatro. A 32 bits el exceso resultante ronda la millonésima de por ciento y nadie lo verá jamás. Encoge la fuente a un solo byte y la misma aritmética se vuelve brutal: 256 módulo 52 vuelve a ser 48, pero ahora 48 resultados obtienen 5 preimágenes y 4 obtienen solo 4 — un exceso del 25 %, visible en unos pocos miles de sorteos.

El arreglo es el muestreo por rechazo y no cuesta casi nada. Calcula el mayor múltiplo del rango que cabe en tu fuente — para un sorteo de 32 bits y un rango de 52 es 2^32 menos 48 — vuelve a sortear siempre que el valor caiga por encima, y toma el módulo solo de los valores aceptados. La región de rechazo son 48 valores de 4 294 967 296, así que el número esperado de sorteos extra es de uno entre noventa millones. Pagas una comparación por llamada y compras uniformidad exacta, el mejor intercambio de todo este artículo.

Math.random no es una barajadora de cartas

Incluso un Fisher-Yates perfecto está limitado por el generador que tiene debajo. Una baraja de 52 cartas tiene 52! órdenes, es decir 8,07 × 10^67, o unos 2^225,6. El generador tras Math.random en V8 lleva 128 bits de estado interno, así que puede alcanzar como mucho 2^128 ≈ 3,4 × 10^38 órdenes de baraja — una fracción de 4,2 × 10^-30 del total. La abrumadora mayoría de los mezclados de una baraja estándar sencillamente no es producible, por muchas veces que lo llames. Es un techo matemático duro, no un fallo de implementación, y se aplica a todo generador pseudoaleatorio con menos estado que el espacio que se le pide cubrir.

Otras dos propiedades importan en la práctica. Math.random no es semillable ni reproducible: la especificación no ofrece forma de fijar un punto de partida, y exige explícitamente que realms distintos produzcan secuencias distintas, así que un fallo que viste una vez no se puede reproducir. Y no es impredecible en sentido criptográfico — un observador que vea suficientes salidas puede reconstruir el estado y predecir el resto. Si alguien puede ganar adivinando tu mezclado — un sorteo, un rifa con premio, un token de seguridad, cualquier cosa barajada ante un público — usa crypto.getRandomValues, con muestreo por rechazo encima. Si el mezclado es un plano de asientos o un test de práctica, Math.random con un Fisher-Yates correcto está perfectamente bien.

Preguntas frecuentes

¿Ordenar con un comparador aleatorio siempre está sesgado, o solo en algunos navegadores?

Siempre sesgado, pero sesgado de forma distinta en cada sitio. El estándar exige un comparador coherente y declara el resultado definido por la implementación cuando no lo recibe, así que cada motor — y cada versión de cada motor — produce su propia distribución grumosa. En Node 26.3.0 el caso de cuatro elementos colapsa a solo dos probabilidades, 1/16 para ocho órdenes y 1/32 para los otros dieciséis, lo que un test de cuatro millones de pruebas confirma con un ji-cuadrado de 19,7 con 23 grados de libertad. Otro motor no te dará esas cifras exactas: te dará otras cifras equivocadas. Eso es peor que un sesgo conocido y fijo, porque no hay nada estable contra lo que testear y una actualización del entorno de ejecución puede cambiar la estadística de tu sorteo sin cambiar una línea de tu código.

¿Cómo escribo Fisher-Yates para que sea realmente correcto?

Empieza en el último índice y baja hasta el índice 1. En cada posición i, saca j uniformemente entre 0 e i inclusive, y luego intercambia los elementos en i y j. Tres cosas tienen que estar bien a la vez: el bucle desciende, el sorteo incluye la propia i, y el rango se encoge en uno cada iteración. Si logras las tres, el número de caminos de ejecución es exactamente n factorial, uno por permutación, lo que hace la salida uniforme para cualquier longitud de array y no solo para las que casualmente probaste. La variante que sube y saca j de todo el array cada vez es el error clásico: tiene n elevado a n caminos, que nunca es múltiplo de n factorial por encima de n = 2, y midió un ji-cuadrado de 29 913 en la prueba de cuatro elementos donde un mezclado justo puntúa alrededor de 23.

¿Necesito crypto.getRandomValues, o basta con Math.random?

La prueba es si alguien podría ganar prediciendo el resultado. Barajar preguntas de un test, sentar una clase, aleatorizar el orden de unos ejercicios: Math.random dentro de un Fisher-Yates correcto vale, y la diferencia no se verá jamás. Sortear un premio, elegir una muestra de auditoría, generar cualquier cosa que se comporte como un token: usa crypto.getRandomValues, porque Math.random es un generador pseudoaleatorio cuyo estado interno se puede reconstruir a partir de una tirada modesta de salidas, tras lo cual todo valor futuro es predecible. Hay una segunda razón, más callada. Una baraja de 52 cartas tiene unos 2^225,6 órdenes y el generador de V8 lleva 128 bits de estado, así que alcanza como mucho un orden de baraja entre 10^30. Ese techo es inherente al tamaño del estado, no a la calidad del algoritmo.

¿Qué es exactamente el sesgo de módulo y cuándo importa?

Es lo que ocurre cuando aprietas un rango que no divide a tu fuente. Toma un valor aleatorio de 32 bits y redúcelo módulo 52: obtienes un número de 0 a 51, pero 2^32 dividido entre 52 deja un resto de 48, así que 48 de esos resultados tienen un valor fuente más que los cuatro restantes. A 32 bits el exceso resultante ronda la millonésima de por ciento — de verdad despreciable. La misma aritmética sobre una fuente de 8 bits es otro animal: 256 módulo 52 también es 48, pero ahora los resultados favorecidos reciben 5 valores fuente y los otros solo 4, un exceso del 25 % que unos pocos miles de sorteos destapan. El arreglo es el muestreo por rechazo: rechazar todo sorteo igual o superior al mayor múltiplo del rango que quepa en tu fuente, lo que para 32 bits y un rango de 52 descarta 48 valores de 4 290 millones, un sorteo entre noventa millones.

¿Cómo puedo testear mi propio mezclado sin base estadística?

Encoge el problema hasta poder contarlo todo. Toma un array de cuatro elementos, mézclalo un millón de veces y lleva la cuenta de cuántas veces sale cada uno de los veinticuatro órdenes — un diccionario indexado por la cadena concatenada basta. Después mira dos números: el recuento mayor dividido entre el menor, y el recuento del orden original sin mezclar. Un mezclado justo da una razón cercana a 1,01 con ese tamaño de muestra y deja el orden original en torno a 1 de cada 24. En las mediciones de aquí, Fisher-Yates dio 1,011 y la ordenación de una línea dio 2,026, con el orden intacto apareciendo un 50 % más de lo debido. No necesitas el ji-cuadrado para ver esa brecha; el ji-cuadrado solo te dice cuán imposible es, y 125 397 frente a un umbral de 27,32 es más o menos lo más imposible que una medición puede ser.