Hay muchas razones por las que podemos necesitar números aleatorios. Por ejemplo, si queremos hacer simulaciones realistas de sucesos naturales como el clima, si necesitamos tomar muestras aleatorias de un conjunto grande (del que sería poco práctico examinar todos los casos), si tenemos que tomar una decisión imparcial sobre algo, si estamos programando un juego que necesite desde lanzar una moneda o un dado, hasta generar niveles en forma aleatoria o producir eventos tipo “20% de posibilidades de hacer un golpe crítico”, etc, etc.
Incluso, los números aleatorios pueden usarse simplemente para crear cosas bonitas. Por ejemplo, la imagen de este post fué generada utilizando números aleatorios (mas abajo está el código que se usó para eso).
¿Cómo podemos generar números aleatorios?
¿Podemos usar Software?
¿Puede una computadora generar números realmente aleatorios usando un algoritmo?
Después de todo, si tenemos un algoritmo que genere los números determinísticamente, ya estamos violando una de las afirmaciones sobre los números aleatorios, que nos dice que los números son obtenidos al azar de forma independiente. Siempre podríamos saber cuál va a ser el número siguiente de la secuencia si tenemos el algoritmo que la genera y lo ejecutamos con las mismas entradas, por lo que los números no habrían sido obtenidos realmente al azar. ¿Y si no podemos saber de ninguna forma cuáles fueron las entradas para volver a ejecutar el algoritmo? Entonces significa que las entradas habrán sido aleatorias, entonces ¿Cómo hicimos para obtenerlas? (estamos en la misma).
En definitiva, este problema lo va a tener cualquier algoritmo. Por lo tanto (al parecer) no podemos hacer demasiado usando Software. Entonces, si no podemos procesar los números, ¿Qué tal si los obtenemos de otra forma y los guardamos para usarlos después?
Podríamos construir una tabla gigante con números generados usando eventos aleatorios, por ejemplo números obtenidos al azar (a mano) de reportes de censos o tirando un dado un montón (pero un montón) de veces, y cargarla en la computadora. Los programas entonces irían extrayendo los números de ahí. Y si no se nos ocurre de dónde sacar los números para la tabla, bueno, hay algunos libros que tienen justamente eso:
El problema de esto es que quizás la tabla no sea lo suficientemente grande (esperemos que alcance con cargar todo el libro), además del tiempo que nos llevaría ingresarla en la computadora, la memoria que ocuparía, y en general la molestia de estar preparando y manteniendo la tabla…
Entonces, ¿Qué otra forma puede haber para obtener los números (que no sea una tabla que haya que cargar)?. Bueno, podríamos pensar algo para generar los números usando Hardware.
Intentando generar los números con Hardware
Por ejemplo, podemos conectarle a la computadora algún dispositivo físico que sirva como fuente de eventos aleatorios, desde un sensor de ruido térmico o atmosférico, hasta un robot que lance un dado y lea el resultado. En Wikipedia podemos encontrar una lista comparando algunos de estos generadores.
Pero bueno, usar un dispositivo Hardware tiene sus inconvenientes, porque pueden ser caros, no generar los números con velocidad suficiente, o ser frágiles. Para colmo, los fallos son bastante difíciles de detectar (¿Cómo podríamos detectar, dadas las secuencias aleatorias que genera la máquina, si tiene alguna falla?).
Además, si bien resolvemos el problema de obtener los números al azar, para que los números nos sean útiles tenemos que conocer su distribución. Entonces ¿Cuál es la distribución de los eventos aleatorios que se producen? ¿Y se mantiene constante, o varía con el tiempo (por ejemplo, cambia a medida que se desgasta el dispositivo)?.
Obviamente, todas estas cuestiones van a depender del dispositivo, pero son solucionables. Y después de todo, al final vamos a tener un generador posta de números aleatorios.
Pero ¿Vale la pena? Bueno, si estamos generando claves criptográficas aleatorias, realmente no queremos que nadie pueda adivinarlas. En esos casos sí se justifica un generador que utilice Hardware. Pero si lo que queremos es simular un dado para un juego, ¿Necesitamos tanta seguridad? Aparte, ¿Vamos a estar comprando un generador de números para conectarle a la compu solamente porque queremos hacer un jueguito que use un dado?
Lo que realmente necesitamos
Lo que nos gustaría tener para hacer simulaciones es un generador de números que parecerían ser aleatorios, pero que no necesariamente lo son. A estos números los denominamos pseudoaleatorios.
Esto hace que las limitaciones que encontramos en la generación de los números usando Software ya no tengan importancia. Generar los números usando un algoritmo nos da ventajas en simplicidad y velocidad de generación con respecto a las soluciones que usaban Hardware. Aparte, como los números son generados en forma determinística, podemos regenerar una secuencia ya generada anteriormente (teniendo los valores de entrada que se usaron para generarla), lo que nos puede ser útil para realizar pruebas y depurar nuestros programas.
Entonces, hagamos un bosquejo de los Requerimientos que necesitamos para nuestro generador de números “aleatorios” (pseudoaleatorios realmente):
- El generador va a generar los números respetando siempre una distribución específica. Vamos a optar por la distribución uniforme para la generación.
- El período del generador debe ser grande. Esto es, si el generador, habiendo ya generado $k$ números, empieza a repetir toda o parte de la secuencia, $k$ debe ser grande.
- Se debe poder guardar el estado del generador, para poder repetir los números generados si se desea (por ejemplo, para ejecutar una prueba del programa).
- El generador debe ser eficiente en cuanto al tiempo de generación. No nos interesa un generador que se demore un mes para darnos el primer número.
- El generador debe ser eficiente en cuanto al uso de la memoria. Si ya decidimos no cargar toda una tabla, más vale que el generador utilice menos memoria que eso.
Podemos ver que estos requerimientos no son precisos (por ejemplo, qué significa que $k$ “debe ser grande”, o qué es ser “eficiente en el tiempo de generación”), pero al menos nos dan una pauta general sobre qué es lo que necesitamos.
Ahora que nos decidimos a usar Software para la generación, y teniendo una idea sobre lo que queremos, en el próximo post vamos a empezar a ver algunos algoritmos para generar números aleatorios.
Referencias
- Donald E. Knuth (1997) The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3ra edición).
- James E. Gentle (2005) Random Number Generation and Monte Carlo Methods (2da edición).
- Universidad Autónoma de Madrid (2008) Curso de Estadística, Tema 10: Simulación de Variables Aleatorias
- Colaboradores de Wikipedia (2015) Applications of randomness, Wikipedia, La enciclopedia libre.
- Colaboradores de Wikipedia (2015) Hardware Random Number Generator, Wikipedia, La enciclopedia libre.
Código de la imagen del post
Aquí está el código que escribí para generar la imagen del post. Cada vez que se ejecuta genera una imagen diferente. El color, tamaño y posición de los triángulos se obtienen de forma aleatoria.