¿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

Estrictamente hablando, hay algunos patrones conocidos en los dígitos de $\pi$ . Hay algunos resultados conocidos sobre lo bien que $\pi$ pueden ser aproximados por los racionales, lo que implica (por ejemplo) que sabemos a priori que el próximo $n$ dígitos aún no calculados de $\pi$ no pueden ser todos cero (para algún valor explícito de $n$ que me da pereza calcular ahora mismo). En la práctica, sin embargo, estos "patrones" son tan débiles que no afectarán a ningún experimento de Monte Carlo.

La principal limitación de utilizar los dígitos de $\pi$ puede ser la velocidad de cálculo. Dependiendo de la cantidad de dígitos aleatorios que necesites, el cálculo de dígitos frescos de $\pi$ puede convertirse en un cuello de botella computacional. Cuanto más se aleje, más difícil será computar más dígitos de $\pi$ .

Si le preocupa la calidad de los dígitos aleatorios que está obteniendo, puede utilizar criptográfico generadores de números aleatorios. Por ejemplo, encontrar un patrón en el generador de números aleatorios Blum-Blum-Shub probablemente daría lugar a un nuevo algoritmo para factorizar números enteros grandes. Los generadores de números aleatorios criptográficos funcionarán más lentamente que los generadores de números aleatorios "comerciales" de los que hablas, pero seguro que puedes encontrar algunos que generen dígitos más rápido que los algoritmos para calcular $\pi$ lo hará.

Answer 2

También es relevante la fórmula Bailey-Borwein-Plouffe

$$ \pi = \sum_{i=0}^{\infty} \frac1{16^i}\left( \frac{4}{8i+1}-\frac{2}{8i+4}-\frac{1}{8i+5}-\frac{1}{8i+6}\right),$$

lo que indica una cierta previsibilidad en los dígitos de base-16 de $\pi$ .

Answer 3

En un sentido técnico, no. Un buen generador de números pseudoaleatorios sería aquel que se puede conectar a cualquier algoritmo aleatorio y esperar ver el mismo comportamiento que tendría un generador de números aleatorios real. Una forma de hacer una definición técnica de esto es decir que el generador de números pseudoaleatorios no puede distinguirse del verdaderamente aleatorio (con probabilidad acotada lejos de 1/2) por cualquier prueba de tiempo polinómico.

Pero los dígitos de π pueden distinguirse claramente del azar mediante una prueba de tiempo polinómico, es decir, una prueba que calcule los dígitos de π y los compare con su supuesta secuencia aleatoria.

Por la misma razón, ninguna secuencia totalmente determinista puede ser una buena secuencia aleatoria. En su lugar, para ajustarse a esta definición, es necesario utilizar un generador de números pseudoaleatorios que tome algún número n de bits verdaderamente aleatorios como semilla de entrada y genere a partir de ellos una secuencia más larga (polinómica en n) de bits pseudoaleatorios que no pueda distinguirse del azar mediante un algoritmo de tiempo polinómico.

Answer 4

Creo que depende de su aplicación.

Yo diría que no si estás usando los números aleatorios para generar claves criptográficas, entonces te abres inmediatamente a los ataques, porque el atacante puede probablemente imitar tu generador de números aleatorios, y así añades un eslabón débil en la cadena.

Answer 5

Se sabe que $\pi$ no equidistribuye muy bien . No estoy seguro de lo que esto dice (si es que dice algo) sobre la "aleatoriedad" de sus dígitos, pero podría sugerir el uso de la proporción áurea o la constante de Euler-Mascheroni sobre $\pi$ .