¿Es pi un buen generador de números aleatorios?

Question

Parte de lo que hago es estudiar el comportamiento típico de las grandes estructuras combinatorias observando instancias pseudoaleatorias. Pero muchos generadores de números pseudoaleatorios disponibles en el mercado tienen defectos conocidos, lo que me lleva a preguntarme si debería utilizar simplemente los dígitos (o bits) de $\pi$ .

Un colega mío dice que "leyó en alguna parte" que los dígitos de $\pi$ no son un buen generador de números aleatorios. Quizás esté pensando en el artículo "Un estudio sobre la aleatoriedad de los dígitos de $\pi$ "por Shu-Ju Tu y Ephraim Fischbach. ¿Alguien conoce este artículo? Algunos de los medios de comunicación que ha recibido (véase, por ejemplo http://news.uns.purdue.edu/html4ever/2005/050426.Fischbach.pi.html ) lo hizo sonar como $\pi$ no era una buena fuente de aleatoriedad, pero el resumen del propio artículo (ver http://adsabs.harvard.edu/abs/2005IJMPC..16..281T ) sugiere lo contrario.

¿Alguien sabe de problemas con el uso de $\pi$ de esta manera? Por supuesto, si se utilizan los dígitos de $\pi$ debes tener cuidado de no reutilizar dígitos que ya hayas usado en otra parte de tu experimento.

Mi opinión es que hay que utilizar los dígitos de $\pi$ para las simulaciones de Monte Carlo. Si utilizas un RNG comercial y te lleva a publicar conclusiones falsas, has perdido el tiempo y has engañado a tus colegas. Si utiliza $\pi$ y te lleva a publicar conclusiones falsas, igual has perdido el tiempo y has engañado a tus colegas, pero también has encontrado un patrón en los dígitos de $\pi$ ¡!

Answer 1

Tenga en cuenta que el análisis de Tu y Fischbach fue cuestionado - no sé si estas preocupaciones son válidas. Véase más abajo

Refutación de afirmaciones como "Pi es menos aleatorio de lo que pensábamos". George Marsaglia Profesor emérito Universidad Estatal de Florida

http://interstat.statjournals.net/YEAR/2006/articles/0601001.pdf

Answer 2

Como han señalado otros, $\pi$ obviamente no es realmente aleatorio, ya que sus dígitos son fijos para siempre.

Pero, ¿son los dígitos "tan buenos como el azar"? La respuesta breve es que, por lo que se sabe, la respuesta parece ser empíricamente afirmativa (véase el artículo de Marsaglia Sobre la aleatoriedad de Pi y otras expansiones decimales ). Es decir, no se conocen formas en las que los dígitos de $\pi$ se comportan sistemáticamente a diferencia de un número aleatorio.

Hay otras respuestas que creo que son confusas en este punto. Permítanme explicar por qué algunas de las afirmaciones hechas por otras respuestas (a pesar de ser técnicamente correctas y en ciertos aspectos muy perspicaces) no refutan la afirmación de que los dígitos de $\pi$ son tan buenos como el azar.

• Una respuesta señala que existe $n_0$ tal que para todo $n > n_0$ El $n$ -a través de $8n$ -enésimos bits de $\pi$ no son todos cero. Sin embargo, esta propiedad también es cierta para cualquier cadena de bits aleatoria (con probabilidad $1$ ). Así que el hecho de que la propiedad se mantenga es en realidad una prueba de la aleatoriedad de $\pi$ .
• Otra respuesta señala que $\pi$ no parece equidistribuir tan uniformemente como, por ejemplo, $e$ . Esto sólo significa que si miras los números $i \pi - \lfloor i\pi \rfloor$ para $i \in \{1, 2, \ldots, 10000\}$ y se redondea cada número al múltiplo más cercano de $0.05$ el resultado es menos suave que si se hace lo mismo con el número $e$ . Pero las cantidades que se grafican aquí sólo dependen de los seis primeros dígitos de $\pi$ . No pretenden decirnos nada significativo sobre la aleatoriedad de los dígitos de $\pi$ son.
• Finalmente, otra respuesta señala correctamente que los dígitos de $\pi$ no cumplen la definición estándar de teoría de la complejidad de un generador de números pseudoaleatorios. Pero eso se debe principalmente a un desajuste de tipo: ninguna cadena de bits individual $x$ puede encajar en la definición de un generador de números pseudoaleatorios. (De hecho, cualquier algoritmo que conozca los primeros, digamos, 10 bits de $x$ puede distinguir fácilmente $x$ a partir de una cadena de bits aleatoria). En general, para construir un generador de números pseudoaleatorios, lo que se necesita formalmente es un conjunto $S$ de cadenas de bits con la propiedad de que ningún algoritmo rápido (es decir, ningún algoritmo con un tiempo de ejecución sustancialmente menor que $|S|$ ) puede distinguir un elemento aleatorio de $S$ a partir de una cadena de bits realmente aleatoria (con probabilidad al menos, digamos, $2/3$ ). Podríamos empalmar fácilmente $\pi$ en múltiples cadenas de bits $S = \{x_1, \ldots, x_k\}$ donde cada $x_i$ consiste en el $i$ -a, $(i + k)$ -a, $(i + 2k)$ etc., trozos de $\pi$ y no veo ninguna razón a priori para pensar que esto no daría un generador de números pseudoaleatorios perfectamente bueno.

Answer 3

El problema obvio aquí es que un buen generador de números pseudoaleatorios generará una secuencia diferente cada vez que se ejecute, mientras que nunca se ha observado que los dígitos de pi cambien.

Answer 4

En realidad, no se ha demostrado que pi sea un número normal, y ese es seguramente el requisito mínimo para su uso como "número aleatorio".

Answer 5

Los PRNG criptográficos son el estándar de oro, ya que si tienes una forma práctica de detectar la más mínima falta de aleatoriedad en la salida, eso se considera una ruptura contra el generador, y un resultado de investigación significativo (en el criptoanálisis) si el PRNG se consideraba bueno (digamos que si estaba basado en AES, el Estándar de Encriptación Avanzado, de alguna forma sensata). Es fácil hacerlos deterministas: para cualquier clave K, basta con tomar los cifrados E(0), E(1), E(2), ... donde E es la función de cifrado.

Los ordenadores x86 recientes tienen una instrucción de hardware para el cifrado AES, por lo que es muy rápido. No me sorprendería que AES utilizando la instrucción de hardware sea más rápido que Mersenne Twister implementado en software.

En la primera edición de "Numerical Recipes" se hablaba del uso de DES (predecesor de AES) como RNG, aunque lo quitaron de las ediciones posteriores.