¿Puedes usar Pi como un generador de números aleatorios crudo?

30

Hace poco vi esta pregunta en matemáticas. Me hizo pensar. ¿Podría Pi utilizarse como un generador de números aleatorios en bruto? Quiero decir que los resultados son bien conocidos (¿hasta cuándo se ha calculado pi ahora?) Pero, Pi parece ser bastante aleatorio cuando se toma 1 dígito a la vez.

¿Tiene esto algún sentido?

Earlz
fuente
¿Dónde se utilizarán estos números aleatorios?
NullUserException
2
Teóricamente podría ser, pero probablemente sería menos óptimo que los métodos actuales. Solo instintos sobre eso, pero parece que el grupo aleatorio es más grande de esta manera con menos sobrecarga.
Aparejo
@NullUserException No estoy seguro ... Me preguntaba si podrían usarse en absoluto. Sin embargo, supongo que esto definitivamente no sería para la criptografía '
Earlz
3
@FrustratedWithFormsDesigner: es parte del paquete ent. Utiliza los números aleatorios para calcular el área de un círculo inscrito dentro de un cuadrado y a partir de eso, se puede calcular pi. Usando los bits de pi como números aleatorios, hay una cierta elegancia en usar esos datos para calcular pi.
1
@FrustratedWithFormsDesigner ent es un conjunto de códigos para analizar la seudoaleatoriedad de un montón de bytes. Una prueba dentro de él es un Monte Carlo para calcular pi y comparar el cálculo aleatorio con el valor real para ver qué tan aleatorio es.

Respuestas:

50

Excavando desde http://www.befria.nu/elias/pi/binpi.html para obtener el valor binario de pi (para que fuera más fácil convertirlo en bytes en lugar de intentar usar dígitos decimales) y luego ejecutarlo a través de ent Obtengo lo siguiente para un análisis de la distribución aleatoria de los bytes:

Entropía = 7.954093 bits por byte.

La compresión óptima reduciría el tamaño de este archivo de 4096 bytes en un 0 por ciento.

La distribución de chi cuadrado para 4096 muestras es 253.00, y aleatoriamente excedería este valor el 52.36 por ciento de las veces.

El valor medio aritmético de los bytes de datos es 126.6736 (127.5 = aleatorio).

El valor de Monte Carlo para Pi es 3.120234604 (error 0.68 por ciento).

El coeficiente de correlación serial es 0.028195 (totalmente no correlacionado = 0.0).

Entonces, sí, usar pi para datos aleatorios le daría datos bastante aleatorios ... al darse cuenta de que son datos aleatorios bien conocidos.


De un comentario arriba ...

Dependiendo de lo que esté haciendo, pero creo que puede usar los decimales de la raíz cuadrada de cualquier número primo como generador de números aleatorios. Estos deberían tener al menos dígitos distribuidos uniformemente. - Paxinum

Entonces, calculé la raíz cuadrada de 2 en binario para resolver el mismo conjunto de problemas. Usando la iteración de Wolfram, escribí un simple script en perl

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }   

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

Ejecutar esto durante los primeros 10 A095804 coincide, así que estaba seguro de que tenía la secuencia. El valor v n como cuando se escribe en binario con el punto binario colocado después del primer dígito da una aproximación de la raíz cuadrada de 2.

El uso de ent contra estos datos binarios produce:

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).

fuente
Exactamente el tipo de respuesta que estaba buscando. No tengo idea de cómo calcular todo este tipo de cosas
Earlz
Incluso si la distribución de números es bastante aleatoria, ¿no tiene que encontrar una manera de seleccionar aleatoriamente una parte de ella?
Blumer
1
@Blumer no. La aleatoriedad se mide en una secuencia de números. Se dice que la secuencia de dígitos pi es aleatoria. Ver en.wikipedia.org/wiki/Statistical_randomness
Simon Bergot el
11
Absolutamente correcto. Y debido a que son datos aleatorios bien conocidos, nunca te atrevas a usarlos para fines criptográficos.
Falcon
3
+1 para "datos aleatorios bien conocidos". Si necesita datos aleatorios que alguien no puede adivinar, pi no es para usted, si solo necesita un montón de números aleatorios por alguna razón, funciona bien.
jmoreno
5

Bueno, entre otras propiedades de un generador de números aleatorios, es probable que desee que sea un número normal . Y varias respuestas en la pregunta de matemáticas. SE que inspiraron su pregunta señalan que actualmente se cree que pi es normal, pero no se ha demostrado.

psr
fuente
2

Dicho generador sería un generador de pseudo números, es decir, dada la misma semilla, el resultado siempre sería el mismo. Dicho esto, en la mayoría de los marcos, cuando usa el generador de números aleatorios estándar, existe el mismo problema de ser pseudoaleatorio.

La distribución de los dígitos parece ser bastante similar a la de los generadores de números aleatorios estándar¹, por lo que los dígitos de π pueden usarse para escenarios de generación de números aleatorios ordinarios.

El problema es que el algoritmo probablemente será muy lento, en comparación con los generadores de números aleatorios comunes, por lo que no es muy útil en la práctica.


¹ Creo que es verdad, pero no tengo ninguna prueba. Sería interesante (y no complicar) hacer una comparación basada en una gran cantidad de números.

Arseni Mourzenko
fuente
55
@NullUserException: No, algunos generadores de números aleatorios usan una fuente de entropía. Esto puede hacerse a través de hardware especializado (el enfoque adoptado por random.org ) o mediante el uso de fuentes existentes de entropía (fluctuaciones medibles dentro de los sensores de hardware existentes, ciertos tipos de interacciones del usuario, micro variaciones en ciertos tipos de pruebas de rendimiento, etc. )
Brian
1
@NullUserException: existen PRNG criptográficamente seguros, que siguen siendo pseudoaleatorios. Luego están RNG real, que se basa en la información del mundo real: la desintegración radiactiva, ruido, etc.
Arseni Mourzenko
2
@MainMa Pero incluso entonces, la aleatoriedad de la desintegración radiactiva, el ruido atmosférico, derivado de la entrada del usuario, etc. es discutible. El hecho de que no reconozcamos un patrón no significa que no exista.
NullUserException
1
@NullUserException: el año pasado, Colbeck / Renner publicó un artículo que pretende demostrar: "Ninguna extensión de la teoría cuántica puede haber mejorado el poder predictivo". Suponiendo que esto se mantenga, puede haber una fuente de entropía que es realmente impredecible, en lugar de simplemente imposible de predecir.
Brian
1
@MainMa: aún realizaría pruebas matemáticas de aleatoriedad. Aunque la física subyacente es aleatoria (según nuestro conocimiento), no significa que la medición lo sea. Los detectores de todo tipo tienen un comportamiento "interesante" en el mundo real
Martin Beckett
2

La aleatoriedad de los dígitos de pi (o para cualquier otra secuencia) se puede probar mediante las llamadas 'pruebas de batería'. Una prueba de batería popular es la Prueba de batería dura de George Marsaglia . También hay una publicación especial NIST 800-22 que describe varias de estas pruebas y los resultados de aplicar estas pruebas a una serie de constantes físicas, que incluyen - lo y he aquí - pi por más de un millón de bits. El resultado de pi se da en el Apéndice B del informe y se ve así:

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

¿Es pi un buen generador de secuencia aleatoria? Mire los resultados anteriores (o busque los significados de la variable de la columna izquierda, si no tiene idea de lo que significan), y verifique si satisface su necesidad.

sm535
fuente
1
La lectura de Diehard dice que necesita alrededor de 10-12 megabytes de datos binarios (lo mejor que pude encontrar es 32 kilobytes). Si lo ejecutó contra los datos ascii, la prueba estaría muy lejos de lo que la aplicación espera.
Mi respuesta fue para la pregunta OP y la pregunta original sobre Math.SE, ninguna de las cuales mencionó nada sobre ascii versus datos binarios o la longitud de la muestra. Sin un conjunto de muestras lo suficientemente grande, ¿cómo se puede determinar la aleatoriedad estadística de cualquier secuencia?
sm535