Generador de Números Aleatorios sin Sesgo

De dónde salen los números

Los sorteos usan crypto.getRandomValues, el generador criptográficamente seguro del navegador, que se alimenta de entropía recogida por el sistema operativo y está diseñado para que observar su salida no diga nada útil sobre lo que vendrá después.

La alternativa obvia, Math.random, es otra cosa. Es un generador pseudoaleatorio rápido - normalmente xorshift128+ - pensado para la velocidad, inicializado a partir de algo como el estado del reloj y con un estado interno lo bastante pequeño como para que unas pocas salidas basten para recuperarlo y predecir el resto. La especificación de ECMAScript dice expresamente que no debe usarse con fines criptográficos.

Para elegir al ganador de una rifa la diferencia rara vez importa. Se usa igualmente porque no cuesta nada, y porque un generador que solo a veces es fiable es más difícil de razonar que uno que siempre lo es.

El sesgo del módulo

La forma sencilla de encajar un valor aleatorio en un rango es tomar el resto de dividirlo por el tamaño del rango, y es sutilmente incorrecta siempre que el rango no divida de forma exacta el rango del generador.

Toma un byte aleatorio, de 0 a 255, y pide un número del 1 al 10. Hay 256 bytes posibles y 10 respuestas posibles, y 256 no es múltiplo de 10. A seis de las diez respuestas les corresponden 26 bytes y a las otras cuatro 25, así que las seis primeras salen alrededor de un cuatro por ciento más a menudo que el resto. Con un rango del 1 al 100 la desviación es mayor, y del 1 al 200, mayor todavía.

La solución es el muestreo por rechazo: calcular cuántos valores en la parte alta del rango del generador provocarían el desequilibrio, descartar cualquier extracción que caiga ahí y volver a intentarlo. Aquí eso significa que los valores por encima del mayor múltiplo exacto del rango se desechan en lugar de plegarse. Cuesta alguna extracción extra de vez en cuando y hace que todos los números del rango sean exactamente igual de probables. La misma rutina respalda los generadores de contraseñas y de UUID de este sitio.

Sortear sin repetición

El modo sin repetición hace un muestreo sin reemplazo, que es lo que quieres para números de lotería, sorteos de premios y elegir un subconjunto aleatorio de una lista. Una vez que sale un valor, se retira del conjunto, así que ningún número aparece dos veces en un mismo resultado.

Para eso el rango debe contener al menos tantos valores como hayas pedido - no pueden salir seis números únicos de un rango de cuatro -, y la herramienta lo indica en lugar de quedarse en un bucle infinito. Ten en cuenta que esto limita el conjunto, no el orden: los números se siguen extrayendo en una secuencia aleatoria, así que el resultado es una mezcla de un subconjunto aleatorio y no una muestra ordenada. La ordenación está disponible por separado si quieres el resultado en orden.

Para qué no sirve

Es una buena herramienta para rifas, dados, datos de prueba, decidir qué tarea hacer primero y cualquiera de las cien pequeñas decisiones que la gente deja al azar.

No es la herramienta para generar una clave, una contraseña o un token, no porque la aleatoriedad sea insuficiente sino porque eso requiere una longitud y un alfabeto concretos: usa el generador de contraseñas para ello. Tampoco es adecuada para un sorteo público en el que los participantes tengan que confiar en el resultado: un número que aparece en una página no demuestra nada a quien no lo vio aparecer, y un sorteo verificable necesita una semilla publicada y un compromiso hecho antes del sorteo, que es un diseño completamente distinto.

Pseudoaleatorio, criptográfico y verdaderamente aleatorio

Un generador pseudoaleatorio es una función determinista: con el mismo estado inicial produce siempre la misma secuencia. Eso es una ventaja en simulaciones, donde importa la reproducibilidad, y un riesgo allí donde alguien pueda intentar predecir el siguiente valor. Math.random en JavaScript suele ser xorshift128+, rápido y con un estado interno pequeño que se puede reconstruir a partir de un puñado de salidas.

Un generador criptográficamente seguro está construido de modo que observar cualquier cantidad de salida no aporte información útil sobre el resto. Se siembra con la entropía que recoge el sistema operativo - variaciones de temporización, patrones de interrupciones, instrucciones de hardware como RDRAND - y se vuelve a sembrar de forma periódica. crypto.getRandomValues en el navegador y /dev/urandom en Unix son las interfaces habituales, y ambas son lo bastante rápidas como para que la seguridad salga prácticamente gratis.

La aleatoriedad verdadera, procedente de una fuente física como el ruido térmico o la desintegración radiactiva, existe en módulos de hardware y en servicios como random.org. Para casi cualquier propósito es innecesaria: un generador criptográfico bien sembrado resulta indistinguible de ella en cualquier prueba que alguien pueda ejecutar.

Barajar una lista sin sesgarla

El barajado intuitivo - ordenar con un comparador aleatorio - es incorrecto, y lo es de una forma que supera una revisión superficial. Los ordenamientos por comparación suponen un orden consistente, así que un comparador aleatorio produce distribuciones que favorecen mucho a ciertas permutaciones, y el resultado cambia según la implementación del ordenamiento. Parece barajado y no lo está.

El algoritmo correcto es Fisher-Yates: recorre la lista desde el final y, para cada posición, elige un índice aleatorio entre cero y esa posición inclusive, y luego intercambia. Todas las permutaciones son igual de probables y el costo es lineal. Casi todas las bibliotecas estándar traen una implementación correcta; donde no la hay, el bucle ocupa cuatro líneas.

Seleccionar un subconjunto es la misma operación detenida antes: baraja las primeras k posiciones y quédate con ellas. Sortear índices al azar y descartar los repetidos también funciona, pero se degrada mucho cuando k se acerca al tamaño de la lista, que es justo el punto en el que la mayoría de las implementaciones improvisadas empiezan a dar vueltas durante un rato perceptible.

Cómo se ve de verdad una secuencia aleatoria

La gente juzga mal el azar, y el error va siempre en la misma dirección: los datos realmente aleatorios contienen muchos más agrupamientos de los que admite la intuición. En cien lanzamientos de moneda, una racha de seis o siete caras es probable en lugar de sospechosa, y la secuencia sin rachas largas es la que probablemente se inventó.

Por eso la función de reproducción aleatoria de los servicios de streaming casi nunca es aleatoria. Un barajado real pone al mismo artista tres veces seguidas con la frecuencia suficiente como para que los usuarios lo reporten como un fallo, así que los algoritmos separan a los artistas a propósito: menos aleatorio, más parecido a lo que la gente entiende por barajar.

Conviene resistirse a dos intuiciones relacionadas: la falacia del jugador, que espera que un resultado ya deba tocar después de una racha del contrario, y el efecto cumpleaños, que hace que las coincidencias sean mucho más probables de lo esperado: con veintitrés personas ya hay un cincuenta por ciento de probabilidad de que dos compartan cumpleaños. Ambas son consecuencia del mismo error de apreciación sobre lo mucho que el azar se agrupa.

Cuando quieres los mismos números siempre

Las simulaciones, el contenido generado por procedimientos y el trabajo estadístico necesitan reproducibilidad: la misma semilla produciendo la misma secuencia, para poder volver a examinar un resultado y reconstruir un error. Un generador criptográfico es justamente la herramienta equivocada ahí, porque no se lo puede sembrar de forma deliberada.

Lo habitual es usar un generador pseudoaleatorio pequeño y bien probado - PCG, xoshiro o el Mersenne Twister en código antiguo - sembrado de forma explícita y registrado. En las pruebas, imprimir la semilla cuando algo falla convierte un fallo intermitente en uno reproducible, que es la diferencia entre un error que se corrige y una prueba que alguien desactiva.

Mantén los dos generadores separados y no dejes nunca que uno sembrado se filtre en código relevante para la seguridad. El patrón que causa problemas es una función utilitaria que sirve tanto para barajar datos de prueba como para generar tokens; en ese momento una secuencia determinista pasa a proteger algo que no debería.

Un sorteo que la gente acepte como justo

La equidad tiene dos partes: el mecanismo y la evidencia. El mecanismo aquí es sólido: una fuente criptográfica con muestreo por rechazo, de modo que todos los valores del rango son igual de probables. La evidencia es lo que una página no puede aportar, porque un número que aparece en una pantalla no le demuestra nada a quien no estaba mirando.

Cuando hay dinero u obligaciones de por medio, la construcción estándar es commit-and-reveal: publica un hash de la lista de participantes y de la semilla antes de cerrar las inscripciones, realiza el sorteo después con un método público y difunde la semilla para que cualquiera pueda recalcular el resultado. Así se cambia la confianza en el organizador por una cuenta que cualquiera puede comprobar.

Para los casos cotidianos - quién presenta primero, por qué tarea empezar, quién se queda con la última entrada - nada de eso hace falta. La equidad que importa ahí es que todos los presentes vean aparecer el mismo resultado al mismo tiempo, y por eso un sorteo a la vista de todos vale más que un número que alguien lee en su propia pantalla.