tipos simulacion que pseudoaleatorios pruebas programacion numeros numero metodo los lineal importancia generadores congruencial aleatorios aleatorio aleatoriedad aditivo unit-testing random
http://csrc.nist.gov/groups/ST/toolkit/rng/documents/sts-2.1.1.zip

unit testing - simulacion - ¿Cómo probar un generador de números pseudo aleatorio?



que es un numero aleatorio en programacion (13)

A menos que esté implementando un algoritmo PNRG dado, no hay manera de decir 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, verifique que los primeros miles de números coincidan 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 demostrar matemáticamente que una secuencia de números es aleatoria ...

XKCD

DILBERT

Se modded abajo ...

Tengo una clase de generador de números pseudoaleatorios (PRNG) que quiero probar en una unidad. 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 prefieres y por qué?

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

Creo que su primer punto (n. ° 1) hace más para probar la calidad de los números aleatorios generados, que está dictado por el algoritmo que se utiliza. El segundo punto (n. ° 2) se usa más para 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.

De regreso a 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.

Tuve 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).

Ajusté el PRNG para eliminar las estriaciones y las explosiones que aparecían en el gráfico, luego tracé (log (x), log (y)) para una perspectiva completamente nueva y repetí 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.

Estrictamente, no hay manera de probar si el generador aleatorio es realmente aleatorio :-) El primer enfoque le da el conocimiento de la distribución de keed apropiada o no para una cantidad fija de muestras solamente, 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 puedes hacer: usa ambos.

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 sobre 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 verdadera, no 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.

Me imagino que en última instancia querrías ambas pruebas, porque quieres estar seguro de que las dos siguientes son ciertas:

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

Tal vez la primera prueba solo podría ejecutarse ocasionalmente, mientras que la segunda podría usarse para verificar que cualquier cambio de código no haya roto el algoritmo.

Obtenga otra implementación del mismo algoritmo PRNG, genere una pequeña cantidad 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 es necesario probar si la salida es aleatoria, ya que muchos otros investigadores han hecho más investigaciones sobre el algoritmo de las que son capaces de reproducir.

Si ha inventado su propio algoritmo PRNG, entonces tiene un problema bastante diferente, porque además 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ía una basura.

Para probar un PRNG, usaría ENT que es un conjunto de pruebas estadísticas que le indicarán qué tan bien funciona su PRNG. Supongo que este es el enfoque 1.

Plesae tenga en cuenta: si ha "inventado" su PRNG, probablemente lo haya equivocado y haya producido algo que no se haya distribuido de forma óptima. La prueba básica de cuán aleatorio es tu generador es la prueba de Chi-Cuadrado

Puede encontrar útiles algunas de las respuestas a esta pregunta .

Básicamente, no puede "probar" 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 las esperadas .

Un método es canalizar su salida a PractRand .

Si PractRand dice que la salida de un PRNG está bien, ¿el PRNG está realmente bien? 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.