Fundamentos de la Generación de Números Aleatorios en JavaScript

Ser capaz de generar (aparentemente) números aleatorios es un requisito esencial para muchas áreas de las matemáticas, la estadística, las ciencias, la tecnología y los juegos.

Por ejemplo, se pueden usar para asignar participantes a un grupo en un ensayo controlado aleatorio, para determinar el resultado de un juego de computadora o para encontrar soluciones aproximadas a problemas que de otro modo serían intratables. También utilizo con frecuencia números aleatorios para comprobar mis soluciones a problemas estadísticos perfectamente tratables. Los generadores criptográficos de números aleatorios, de los que no hablaremos aquí, se pueden utilizar en seguridad.

Types of Random Number Generator

Al menos para el propósito de este artículo, podemos pensar que hay tres categorías de colección de números aleatorios:

• “True” random numbers;
• Pseudorandom numbers;
• Quasirandom sequences.

Los generadores de números aleatorios verdaderos (o de hardware) (TRNG) utilizan procesos físicos del mundo real que se cree que son de naturaleza aleatoria para crear flujos de números. Los eventos de desintegración de una fuente radiactiva, por ejemplo, son aleatorios y no están correlacionados entre sí, también se puede utilizar el ruido atmosférico.

Los TRNG a menudo no son prácticos o convenientes (o necesarios) para muchos propósitos. Una alternativa mucho más común es crear un flujo de números que parecen estar distribuidos aleatoriamente en algún intervalo utilizando un algoritmo informático. Estos algoritmos no son realmente impredecibles y, por lo tanto, se les conoce como generadores de números pseudoaleatorios (PRNG).

Finalmente, las secuencias cuasialeatorias son una colección finita de números que están destinados a ser representativos de un espacio muestral de alguna manera. Por ejemplo, la media de la secuencia puede ser la misma (o muy similar) a la media conocida de la población. Si bien las secuencias cuasialeatorias son interesantes y pueden ser útiles, no son el foco de este artículo y no se discutirán más a fondo.

The Standard Uniform Distribution

Por lo general, la salida de un gran número de valores de un generador de números pseudoaleatorios está pensada para aproximarse a la distribución uniforme estándar (SUD) que cubre el rango de 0 a 1. Sin embargo, existe cierta variación en cuanto a si se incluyen uno o ambos puntos finales. En el mundo conceptual de las matemáticas de las distribuciones continuas, básicamente no hay diferencia entre la distribución uniforme entre [0,1] (incluye 0 y 1) y la distribución uniforme entre (0,1) (excluye 0 y 1). En el mundo real de los números de coma flotante, con solo un número finito de valores posibles entre 0 y 1, la diferencia es real y podría ser potencialmente problemática. Uno podría, por ejemplo, querer usar el número generado dentro de la función de logaritmo natural Math.log.

La generación de un número aleatorio para otra distribución suele ser "sólo" cuestión de utilizar uno o más números de un PRNG SUD para producir un valor apropiado a partir de la distribución de interés. Dependiendo de la distribución final deseada, esto puede implicar una línea de código o algo bastante complejo. Durante el resto de este artículo, me limitaré a discutir la generación de números a partir de un SUD PRNG.

Period

Un PRNG útil debe tener un período grande, es decir, debe ser capaz de producir un gran número de números sin repetirse. Por ejemplo, el PRNG de Wichmann Hill de 1982 (más sobre esto más adelante) tiene un período de casi 7 billones de números, mientras que el extremadamente popular Mersenne Twister PRNG tiene un período de 2 ^19937-1 números. El primero se considera bastante corto para los estándares modernos.

¿Qué le pasa a Math.random?

Puede usar el Math.random incorporado de JavaScript con regularidad y no tener problemas con él. Sin embargo, tiene una gran limitación: su salida no es reproducible. Ejecute código que utilice Math.random una y otra vez y obtendrá un conjunto diferente de resultados cada vez. En muchos casos, eso realmente no es un problema. De hecho, en muchos (la mayoría, probablemente) de los casos será exactamente lo que quieres. La imprevisibilidad (al menos para un humano sentado mirando la salida) es exactamente lo que se requiere. Pero a veces queremos ver el mismo conjunto de resultados.

Alejándote de JavaScript por un momento, considera la posibilidad de ejecutar un experimento de simulación para un trabajo que desees publicar. Tal vez estés usando C++ o Java o R o... Quieres que tus resultados sean reproducibles. Estos lenguajes (y muchos otros) ofrecen una forma de "sembrar" el estado inicial de sus PRNGs. Estableces la semilla de una forma u otra y obtienes la misma secuencia de números "aleatorios". Math.random también requiere una semilla, simplemente no hay forma de configurarla usted mismo. La especificación de​ ​Math.random también es bastante abierta, lo que permite a los proveedores de navegadores utilizar "un algoritmo dependiente de la implementación" siempre que la salida sea aproximadamente uniforme en el rango [0,1].

Desde una perspectiva personal, soy un gran admirador de la visualización interactiva de datos basada en el navegador para comunicar datos y conceptos. Esto podría incluir simulación; Hay límites a lo que es práctico en un navegador, pero los trabajadores web pueden ayudar. La simulación suele requerir números aleatorios. Si los números aleatorios no son reproducibles, las condiciones de una simulación no se pueden volver a ejecutar. También hay muchos otros casos de uso, como una animación repetible, y JavaScript ya no es solo el lenguaje de programación del navegador.

PRNGs problemáticos

Hasta ahora me he saltado cómo funcionan los PRNG de distribución uniforme. Todo ha sido una especie de caja negra: llamas a una función una o más veces, posiblemente estableciendo una semilla, y luego salen algunos números pseudoaleatorios. El problema es que crear un buen PRNG es difícil. Hay miles de artículos sobre el tema y múltiples métodos. Y múltiples casos en los que personas que saben mucho más sobre este tema que yo parecen haberse equivocado. Por ejemplo...

RANDU

RANDU es un "generador congruente lineal" (LCG) desarrollado por IBM en la década de 1950. Los LCG utilizan una relación de recurrencia de la siguiente forma para generar nuevos números pseudoaleatorios:

En el caso de RANDU, c es 0, a es 65,539 y m es 2 ³¹. Debido a que c es 0, RANDU es miembro de un subconjunto de LCG llamados "generadores congruentes multiplicativos" (MCG). Para obtener un número en el rango de 0 a 1 (como se desea para un reemplazo de Math.random), solo se necesita dividir el resultado de la relación de recurrencia RANDU por m. Una implementación de JavaScript (¡que definitivamente no deberías usar!) podría tener un aspecto similar al siguiente:

var randu = function(seed){

   "use strict";
   
   if(!isFinite(seed)){
      throw new Error("Seed not a finite number");
   }
		   
   var x = Math.round(seed);
   var a = 65539;
   var m = Math.pow(2, 31);

   if(x<1 || x≥m){
      throw new Error("Seed out of bounds");
   }

   return function(){
      x = (a*x)%m;
      return x/m;
   };
    
};

La paridad del valor generado por la relación de recurrencia en RANDU nunca cambia. Es decir, una semilla impar da lugar solo a valores impares de x, mientras que una semilla par da lugar solo a valores pares de x. Esta no es exactamente una propiedad deseable, pero hay problemas más grandes.

El período de un LCG es como máximo m, pero para RANDU es mucho menor que eso y depende de la paridad de la semilla. En el caso de las semillas impares es de más de 536 millones, pero en el caso de las semillas pares puede ser tan solo 16.384.

Hay otra razón para no molestarse con una semilla par: un método común y simple para evaluar la aleatoriedad de un generador es trazar pares de valores sucesivos como un diagrama de dispersión. Un buen PRNG debe llenar un cuadrado de 1 por 1 de manera bastante uniforme. Con 10.000 números aleatorios, 5.000 puntos y una semilla de 1, todo parece razonable. (Puede pensar en "x" como refiriéndose a los valores en posiciones de índice par en una matriz (indexada 0) de 10.000 números aleatorios. Es decir, los índices 0, 2, 4, 6... 9,996, 9,998. Los puntos en el diagrama de dispersión se forman haciendo coincidir con el siguiente índice impar (1, 3, 5, 7... 9,997, 9999) valor "y").

Con algunas semillas incluso tenemos algo bastante diferente. A continuación se muestra un diagrama de dispersión para la semilla 32,768.

Está claro que no solo tenemos un déficit de puntos en el caso de las cabezas de serie. En algunos casos, tenemos relaciones inequívocas entre valores vecinos.

Sería bastante simple adaptar la función randu anterior para rechazar incluso las semillas, dando un mensaje de error apropiado. Desafortunadamente, las semillas de probabilidades también muestran estructura. Para ver esto, solo necesitamos extender la idea del diagrama de dispersión a tres dimensiones observando tripletes de números aleatorios sucesivos. Los diagramas de dispersión 3D suelen ser bastante inútiles. Los datos de RANDU proporcionan una especie de excepción a esta regla. (Aquí los índices de los valores "x" son 0, 3, 6, 9... 9.993, 9.996, los índices de los valores "y" son 1, 4, 7, 10... 9,994, 9997 y los índices para los valores "z" son 2, 5, 8, 11... 9,995, 9,998.)

En lugar de llenar la caja de manera aproximadamente uniforme, los tripletes de números se encuentran todos en uno de los 15 planos, ¡independientemente de la semilla! (En realidad, para la semilla par 32,768 es peor que esto). Podemos comparar esto con los resultados de Math.random (usé Chrome para esto); La diferencia es marcada.

Un problema general con los diagramas de dispersión 3D es que la visibilidad de la estructura en el gráfico puede depender del ángulo de visión. Desde ciertos ángulos, la estructura de la trama RANDU está oculta. Este podría ser el caso de Math.random. Para ayudar con este problema, creé una versión interactiva que le permite elegir un PRNG (y, cuando corresponda, una o más semillas) y visualice los resultados usando WebGL. Esta demostración se puede encontrar aquí y la caja de números aleatorios se puede girar (usando el mouse) y ver desde diferentes ángulos. Todavía no he encontrado signos obvios de estructura al usar Math.random en varios navegadores (Chrome, Firefox, Maxthon, IE, Edge y Opera en el escritorio y Safari en iOS).

La aparición de estructuras reticular en 3 o más dimensiones existe para todos los MCG, pero es particularmente mala para RANDU. Se conoce desde la década de 1960. A pesar de esto, RANDU todavía se usaba en la década de 1970 y algunos resultados de simulación de esa época deberían, tal vez, ser vistos con escepticismo.

Sobresalir

Quizás se pregunte si los problemas con los PRNG se limitaron a las décadas de 1960 y 1970. La respuesta corta a esta pregunta es "no". Después de las críticas a su antiguo generador de números aleatorios, Microsoft cambió al Wichmann-Hill PRNG por Excel 2003. El generador WH (publicado por primera vez en 1982) combina tres MCG para superar algunas de las deficiencias de los MCG individuales (como un período relativamente corto y los planos de red e hiperplanos que se ven al observar grupos de valores vecinos). Una implementación rápida de JavaScript de WH podría ser similar a la siguiente:

var wh = function(seeds){
  
   "use strict";

   if(seeds.length<3){
      throw new Error("Not enough seeds");
   }

   var xA = Math.round(seeds[0]);
   var aA = 171;
   var mA = 30269;

   var xB = Math.round(seeds[1]);
   var aB = 172;
   var mB = 30307;

   var xC = Math.round(seeds[2]);
   var aC = 170;
   var mC = 30323;
   
   if(!isFinite(xA) || !isFinite(xB) || !isFinite(xC)){
      throw new Error("Seed not a finite number");
   }

   if(Math.min(xA,xB,xC)<1 || xA≥mA || xB≥mB || xC≥mC){
      throw new Error("Seed out of bounds");
   }  

   return function(){
      xA = (aA*xA)%mA;
      xB = (aB*xB)%mB;
      xC = (aC*xC)%mC;
      return (xA/mA + xB/mB + xC/mC) % 1;
   };
	  
};

De nuevo, podemos buscar la estructura al trazar conjuntos de valores vecinos en dos o tres dimensiones:

Si bien esto claramente no es suficiente para decir si tenemos o no un buen generador de números aleatorios, los gráficos anteriores al menos parecen razonables. (También puede marcar la casilla tridimensional en la demostración de WebGL mencionada anteriormente). Sin embargo, la implementación original del algoritmo WH para la función RAND en Excel ocasionalmente arrojaba números negativos.

El algoritmo WH falla una serie de pruebas más modernas y estrictas de PRNG, y parece que Microsoft ha pasado a usar el popular (pero bastante más complejo) algoritmo Mersenne Twister.

V8

Anteriormente, utilicé la salida de la implementación de Chrome de Math.random para ilustrar cómo debería verse la distribución de tripletes de números aleatorios cuando se traza como un diagrama de dispersión tridimensional. Sin embargo, recientemente se demostró que el algoritmo utilizado por V8, el motor JavaScript de Chrome, era defectuoso. Específicamente, reprodujo las mismas cadenas de caracteres "aleatorios" con una frecuencia mucho mayor de la que debería, como se describe en este artículo largo pero informativo. Los desarrolladores de V8 cambiaron rápidamente el algoritmo utilizado y el problema parece haberse solucionado en Chrome desde la versión 49.

Speed

Otra consideración antes de intentar "hacer crecer su propio" PRNG de JavaScript es la velocidad. Uno debe esperar que Math.random esté altamente optimizado. Por ejemplo, algunas pruebas muy aproximadas con varios navegadores mostraron que Math.random es ~ 3 veces más rápido en la producción de 100,000 números aleatorios que la implementación simple de WH anterior. Habiendo dicho esto, todavía estamos hablando del orden de solo decenas de milisegundos (al menos en Chrome y Firefox en mi computadora portátil), por lo que esto puede no ser un cuello de botella, incluso si requiere una gran cantidad de números aleatorios. Por supuesto, los PRNG más complejos con mejores propiedades estadísticas pueden ser más lentos.

Conclusiones

Apenas he tocado la superficie aquí. Solo he mirado un par de PRNG simples y he demostrado que aún pueden ser problemáticos. Existen algoritmos mucho más complicados para los PRNG, algunos de los cuales han pasado un gran número de pruebas estadísticas bastante estrictas. Y algunos de estos ya tienen implementaciones de JavaScript de código abierto.

Si no necesita reproducibilidad, Math.random puede estar bien para todas sus necesidades de números aleatorios. De cualquier manera, si la confiabilidad de su generador de números aleatorios es crítica para el funcionamiento de su sitio, entonces debe realizar las verificaciones pertinentes. En el caso de Math.random, esto significa verificar en todos los navegadores de destino, ya que la especificación de JavaScript no especifica un algoritmo en particular que los proveedores deban usar.

Pruebe nuestros controles HTML5 de JavaScript para sus aplicaciones web y aproveche de inmediato sus impresionantes capacidades de visualización de datos. Descargue la versión de prueba gratuita hoy mismo.