¿Cómo se prueba un generador de números pseudoaleatorios?

Question

Tengo una clase de generador de números pseudoaleatorios (PRNG) que deseo probar unitario. Hay dos enfoques:

1. escriba un caso de prueba que tome una gran cantidad de muestras y compruebe si están distribuidas correctamente. Este enfoque puede conducir a un tiempo de ejecución bastante largo para el caso de prueba;
2. calcule una pequeña serie de muestras 'a mano' y verifique si el algoritmo PRNG la reproduce. Este enfoque puede conducir a que se genere una secuencia no aleatoria sin que se note;

Yo diría que el primer enfoque no es realmente la prueba unitaria porque no realiza una prueba de caja blanca del generador, pero por otro lado, prueba adecuadamente la responsabilidad de la clase. El segundo enfoque es más como una prueba de unidad real, centrándose en el algoritmo, pero no proporciona tanta evidencia como si la clase cumple con su responsabilidad.

¿Qué enfoque prefiere y por qué?

---

Answer 1

Obtenga otra implementación del mismo algoritmo PRNG, genere un número pequeño de casos de prueba largos basados ​​en semillas conocidas y verifique que su implementación del algoritmo coincida con las implementaciones de los demás. Cuantos más datos pruebes, más posibilidades tendrás. Si quiere hablar en serio, investigue cómo se realiza la validación FIPS para el algoritmo.

No hay necesidad de probar si la salida es aleatoria, ya que otros investigadores han realizado mucha más investigación sobre el algoritmo de la que usted es capaz de reproducir.

Si ha inventado su propio algoritmo PRNG, entonces tiene un problema bastante diferente, porque aparte de probar su código también necesita probar su nuevo algoritmo. Hay varias cosas que hacer, creo que las más importantes son las pruebas estadísticas en el resultado y la revisión por otros criptógrafos. Básicamente, sin embargo, si diseñara un algoritmo de PRNG sin tener suficiente conocimiento en el campo para saber cómo probarlo, entonces será una basura.

Answer 2

para probar un PRNG, me gustaría utilizar ENT que es una suite de pruebas estadísticas que le dirá qué tan bien realiza PRNG. Supongo que este es el enfoque 1.

Answer 3

Me imagino que en última instancia le gustaría que ambas pruebas - porque usted quiere estar seguro de que tanto los siguientes son ciertas:

(1) los números están adecuadamente distribuidos y (2) el algoritmo específico está funcionando como se esperaba.

Quizás la primera prueba solo se podía ejecutar de vez en cuando, mientras que la segunda se podría usar para verificar que los cambios de código no hayan roto el algoritmo.

Answer 4

Creo que su primer punto (n. ° 1) se basa más en probar la calidad de los números aleatorios generados, que es dictado por el algoritmo que se utiliza. El segundo punto (n. ° 2) obtiene más resultados al probar la implementación del algoritmo. Si diseñó el algoritmo, ambas pruebas son importantes. Si implementó un algoritmo de rendimiento demostrado, el # 2 debería ser suficiente. Aunque, probablemente probaría más que unas pocas semillas y las secuencias que resultaron usando algún conocimiento de la estructura de su generador particular.

Answer 5

Estrictamente, no hay forma de comprobar si el generador aleatorio es realmente aleatorio :-) El primer enfoque le da el conocimiento de la distribución correcta o no para una cantidad fija de muestras, sin importar cuán grande sea esta cantidad . El segundo enfoque puede respaldar el conocimiento de si se comporta como un algoritmo, pero nuevamente para una cantidad fija de muestras.

Lo mejor que puede hacer: use ambos.

Answer 6

Plesae tenga en cuenta: Si ha 'inventado' su PRNG, probablemente lo haya equivocado y haya producido algo que tiene una distribución inferior a la óptima. La prueba básica para saber qué tan aleatorio es tu generador es la prueba de Chi-Cuadrado

Answer 7

A menos que estés implementando un algoritmo PNRG dado, no hay forma de saber que los números son aleatorios, esa es la naturaleza de la aleatoriedad. sí, en promedio, a medida que su generador de números va hacia el infinito, se igualará, pero no va a probar un número infinito de iteraciones.

Si está implementando un algoritmo conocido, compruebe que los primeros miles coinciden con los resultados que proporcionan dado un conjunto de semillas. sin embargo, no hay forma de estar seguros ya que la cantidad de semillas posibles es infinita.

Ni siquiera se puede proove mathmatically que una secuencia de números es aleatoria ...

xkcd

DILBERT

obtiene modded abajo ..

Answer 8

La "aleatoriedad" en un generador de números pseudoaleatorios generalmente se expresa como el número promedio de iteraciones antes de que se repita un número. Existen numerosos algoritmos que tienen diferentes "aleatoriedad" y rendimiento. Random.org tiene una buena explicación de algunos análisis realizados en sus algoritmos. Mira las fotos a la mitad de la página. Es fácil ver en las imágenes estáticas qué tan aleatorios son los dos algoritmos.

Una característica de un PRNG (una característica real, no es un error disfrazado como una característica) es que es predecible. Para una semilla dada, se debe producir la misma secuencia de números. Esto es extremadamente importante y necesario para probar y depurar programas que usan métodos estocásticos (es decir, aleatorios).

La secuencia numérica debe aproximarse a cierta distribución estadística. Pruebe su PRNG generando una secuencia grande (digamos 10^6 números) y realice varias pruebas estadísticas en la secuencia, particularmente la prueba Chi-Squared (si la distribución es normal). Haga un histograma de su muestra y vea si se ve como espera.

Si controla cómo se establece la semilla, la secuencia generada debe ser la misma cada vez, lo que es adecuado para hacer pruebas de caja blanca. Al hacer sus pruebas, también es una buena idea "calentar" el generador ejecutándolo durante 100 iteraciones más o menos antes de recoger su muestra.

Answer 9

Puede encontrar algunas de las respuestas a this question útiles.

Básicamente, no puede "demostrar" que el RNG es aleatorio, pero puede realizar varias pruebas para mejorar su confianza. Estas pruebas varían en complejidad.Diehard es completo, pero en realidad no ofrece una respuesta de sí/no, más bien como un par de cientos de "maybes". En el otro extremo del espectro, es bastante simple generar una secuencia de valores (10,000 como mínimo) y luego verificar si la media y la desviación/varianza estándar son as expected.

Answer 10

Aquí hay un CodeProject article que incluye una implementación de la prueba de Kolmogorov-Smirnov mencionada en el volumen 2, Algoritmos Seminumerical de Donald Knuth. Como InSciTek Jeff mencionó anteriormente, hay dos problemas: probar el algoritmo y probar su implementación del algoritmo. La prueba K-S es probable que encuentre errores en la implementación, y es un buen comienzo para probar la calidad del algoritmo en sí.

Answer 11

De regreso en la escuela, estaba desarrollando un generador de números aleatorios para una tarea de simulación, y necesitaba alguna forma de identificar la no aleatoriedad.

Tengo la brillante idea de tomar dos números aleatorios y graficarlos (x, y). Es sorprendente cómo el cerebro humano puede detectar patrones no aleatorios. ("Patrón Aleatorio" es un oxímoron.)

Pellizqué el PRNG para eliminar las estriaciones y destellos que aparecían en el gráfico, luego tracé (log (x), log (y)) para una perspectiva completamente nueva y repitió el proceso.

Más tarde, me vi obligado a tomar estadísticas y aprendí que puedes hacer cálculos extraños para cuantificar la aleatoriedad.

Answer 12

Random.org utiliza este traje de prueba: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

Puede descargar el software (UNIX y Mac OS X) en: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/sts-2.1.1.zip

La documentación está aquí: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

Answer 13

Un método consiste en pipe su salida a PractRand.

Si PractRand dice que la salida de un PRNG está bien, ¿realmente está bien el PRNG? No estoy calificado para juzgar, pero lo que puedo decir es que PRNG es lo suficientemente exigente como para juzgar insatisfactorio el resultado de varios algoritmos LFSR y xor-y-shift que encontré en la literatura o en línea, y consideraba correcto el resultado de xorgens de RP Brent.