Pseudoness de generadores de números pseudoaleatorios

Question

¿Es que una prueba estadística razonable uno puede hacer para estándar generadores de números aleatorios (decir, uno de los que vienen construido en libs Python) que demuestra que no son realmente aleatorios?

(Por razonable me refiero a excluir cosas tontas como «generar una lista laaarga y ver que es periódico»)

Más tarde: Aviso que estoy en busca de una prueba falla en los generadores estándar.

Answer 1

El estándar de referencia es Knuth, el Arte de La Programación de computadoras, Volumen 2, Seminumerical Los algoritmos. Cualquier persona con un serio interés en este tema debe leer Knuth de la extensa exposición aquí. Además de la discusión teórica, se presenta a las pruebas, incluida la frecuencia, de serie, gap, de poker, bonos de coleccionista, permutación, ejecutar, máximo-de-t, colisión de cumpleaños, espaciamientos, y la correlación serial.

Marsaglia del DIEHARD suite de prueba estadística incluye cumpleaños espaciamientos, la superposición de las permutaciones, los rangos de 31x31 y 32x32 matrices, los rangos de 6x8 matrices, mono pruebas en 20 bits de Palabras,mono pruebas de vis máxima (opso), OQSO, ADN, contar el 1 en una secuencia de bytes, contar el 1 en bytes, estacionamiento, a una distancia mínima de, al azar de las esferas, exprimir, la superposición de sumas, corre, y el juego de dados.

El NIST Prueba Estadística Suite incluye la frecuencia, el bloque de frecuencia acumulativa de sumas de dinero, carreras, carreras largas,Marsaglia del rango espectral (basado en la transformada de Fourier Discreta), que no se solapan plantilla de elecciones, la superposición de plantilla de elecciones, Maurer universal de estadística, entropía aproximada (basada en la obra de Pincus, Cantante y Kalman), al azar excursiones (debido a Baron y Rukhin), Lempel-Ziv complejidad, complejidad lineal, y de serie.

Como de las pruebas que fallan, como Knuth menciona cuando se habla de un generador típico en la sección 3.6 p. 188 "Precaución: Los números generados por ran_array fallar el cumpleaños de espaciamientos de prueba de la Sección 3.3.2 J, y tienen otras deficiencias que a veces se muestran en alta resolución de las simulaciones (vea los ejercicios 3.3.2-31 y 3.3.2-35)".

Answer 2

Búsquedas de Marsaglia (George), trabaja por él o sobre su PRNG pruebas, sería descubrir una gran cantidad de información. por ejemplo,

http://en.wikipedia.org/wiki/Diehard_tests

se encontró buscando "marsaglia test".

Answer 3

PRNGs en la mayoría de los modernos programas informáticos destinados a hacer seria la simulación han sido examinados para asegurarse de que pase diversas suites de pruebas, por lo que son raro encontrar un caso donde uno de ellos falla.

Históricamente, un famoso fallo es el PRNG llamado 'RANDU'. Cuando tríadas de tres valores sucesivos de este generador son trazados en la unidad de cubo, uno puede ver que todos los puntos de la trama de la mentira en un pequeño número de muy separadas de los planos paralelos (Lewis, Orav y Uribe, 1986), mientras que un generador satisfactoria iba a colocar puntos en consonancia con la selección al azar de todo el cubo.

Esto no quiere decir que todas las simulaciones de realizar a la perfección. Normalmente, PRNGs generar valores de UNIF(0,1). Es posible abuso de los valores de un excelente generador de cuando el intento de transformar a muestras aleatorias de otras distribuciones, pero esto es un fallo de la programación-no de los valores generados.

Ejemplo: un Moderno software que utiliza la Caja-Muller de transformación para obtener dos precisamente aleatoria normal estándar de las variables de dos uniforme queridos a través de registro y funciones trigonométricas. Pero antes de hacer trascendental de la aritmética era como rápido como lo es hoy, un método de obtención de una normal estándar de 12 uniforme de la suma y la resta se $Z = U_1, \dots, U_{12} - 6$. Este método, que no puede producir valores de $|Z| > 6$ (raro, pero posible), aún persiste en algunos textos y software de la herencia.

El siguiente programa en R se usa este método para generar un cientos de muestras aleatorias de tamaño 5000 de un "estándar normal" de distribución, de los cuales 15 sanples fallar la de Shapiro-Wilk 5% de nivel de prueba de la normalidad. (R utiliza el "Mersenne-Twister" PRNG debido a Matsumoto y Nishimura (1998), que se ejecuta a través de $2^{19937} - 1$ valores antes de repetirse a sí misma y ha sido validada en pruebas de la participación de hasta 624 dimensiones sin encontrar resultados inconsistentes con un comportamiento aleatorio.)

conjunto.semilla(1234); m = 100; p.val = numeric(m); n = 5000

for(i in 1:m) { z = rowSums(matriz(runif(n*12), nrow=n))-6

p.val[i] = shapiro.de prueba(z)$p.valor }

suma(p.val < .05)