numero - random number generator several

¿Cómo probar números aleatorios? (10)

He escrito en matlab, un programa, que se supone para generar números aleatorios entre 0 y 1. Lo he probado solo con la prueba de ejecución en Matlab, y el resultado es que la secuencia es aleatoria. También he visto los histogramas y tienen una distribución beta. Quiero probar esta prueba con otra prueba, como diehard, ent o nist, pero no sé cómo. ¿Puede alguien explicar cómo usarlos o sugerirme algunas otras pruebas de aleatoriedad? gracias

@Anna He tenido la misma pregunta que tú y ahora he descubierto a Diehard gracias a algunas de las otras respuestas.

La situación con mi RNG es que crea 1 y 0 y los almacena en un archivo ASCII. Al intentar cargar este archivo a pruebas de aleatoriedad en línea, falló, probablemente porque los datos deben estar en formato binario.

Y ese es realmente el caso con Diehard. Si instala Diehard, encontrará un archivo llamado DIEHARD.DOC que le DIEHARD.DOC los pasos de cómo convertir su archivo ASCII en los archivos binarios requeridos (junto con algunos otros cambios que pueda necesitar realizar en su programa).

Estos son mis primeros pasos, de todos modos. Espero que esto ayude a alguien.

Aquí puede encontrar programas de prueba y un código fuente para diferentes sistemas operativos. Otro buen enlace podría ser este .

Con la mayoría de las pruebas puede suministrar un archivo grande de números aleatorios (entero o punto flotante) y ejecutar varias pruebas en ese archivo de muestra. DIEHARD trabajó de esa manera, si recuerdo correctamente y otros lo hacen, también. Si realmente quieres ver que tu generador falle, podrías probar usar TestU01 de Pierre L''Ecuyer, que tiene pruebas suficientes para que casi todos los generadores fallen al menos una prueba :-)

Aún así, para la mayoría de las suites de prueba hay una extensa documentación, al menos esto lo sé por DIEHARD , el conjunto de pruebas de NIST SP 800-22 , así como DieHarder y TestU01 (los enlaces van a los documentos). Los métodos para el suministro de números aleatorios para probar son generalmente diferentes, pero se mencionan en la documentación respectiva.

Confine el resultado a un rango específico (posiblemente usando el operador de mod), ejecute su código unos pocos millones de veces y cuente cuántas veces ve cada número en el rango. Asegúrese de que los recuentos sean más o menos iguales y de que no tenga un sesgo para ningún valor específico.

De hecho, estoy buscando una prueba similar, esperaba encontrarla aquí pero no lo hice. Voy a probar math..com donde probablemente pueda preguntarlo ya que la respuesta es estadística.

Mi conocimiento de estadísticas es lo suficientemente moderado como para saber lo que está buscando sin poder proporcionar los detalles exactos.

Básicamente, estás realizando una prueba de regresión para ver si tus números se ajustan a una distribución uniforme. Entonces podemos crear un modelo chi-cuadrado (creo). Llevará a obtener un t-stat y un p-value. Una t-estadística más alta y un valor p más bajo significan que no se ajusta a la distribución (por lo tanto, rechazamos la hipótesis nula). El valor de p estará entre 0 y 1. Si es decir 0.06, entonces podemos rechazar la hipótesis nula con una confianza del 94%.

Y para responder a aquellos que dicen "no deberíamos crear números aleatorios", quizás no números aleatorios reales, pero podemos obtener datos y desear probar si se ajusta a una distribución uniforme, y para los programadores podemos probar si un hash -function produce una distribución uniforme a través de un gran número de instancias aleatorias de los objetos que estamos mezclando.

En cuanto a algunos códigos para las pruebas NIST, hay algunos aquí:

http://sourceforge.net/projects/randomanalysis/

que puede darte lo que quieres.

Hay muchas cosas para probar si quiere probar su RNG por su cuenta. Aquí hay algunas características básicas que pueden revelar que la secuencia numérica no es realmente aleatoria o puede ser indistinguible de lo aleatorio.

Echa un vistazo a:

La distribución : ya has hecho algunos análisis sobre tu distribución. Desea que cada número posible tenga la misma probabilidad de ocurrir.
Comportamiento cíclico : ¿la misma secuencia se repite una y otra vez? La secuencia repetitiva puede ser bastante larga.
La aparición de duplicados (... CBBAF F ...), trillizos (... CBAAA F ...) etc. Estadísticamente en una secuencia de números aleatorios tiene una cierta probabilidad de dulplicados (el mismo número generado dos veces seguidas ), trillizos, etc. Calcule esta probabilidad y verifique si su secuencia de números pseudoaleatorios tiene la misma probabilidad de que se produzcan duplicados.

Tenga en cuenta que para la mayoría de estas pruebas debe tener una secuencia bastante larga de números aleatorios para poder obtener resultados precisos y precisos del análisis estadístico.

Supuse secuencias de número entero aleatorias de números enteros, que se fijan fácilmente multiplicando sus números [0, 1] por una constante adecuada.

He estado mirando este problema durante el último año, y he llegado a la conclusión de que no existe una forma estándar de probar la aleatoriedad en el mundo real. Creo que es justo lo que te hace sentir cómodo. No puede probar que una secuencia es aleatoria, y no puede demostrar fácilmente que una secuencia no es aleatoria.

(Estoy descartando secuencias aleatorias que realmente no son al azar, como 0123456789 ... repitiendo).

user3535668 enumera algunas pruebas ampliamente conocidas y una lista completa de problemas con ellas. Puedo agregar otros. Diehard: ¿cuán grande debería ser el archivo de entrada, y debería consistir solo en enteros de 32 bits? ENT: solo parece adecuado para errores graves, pero la prueba de chi es útil. El manual de usuario de NIST tiene> 100 páginas, buena suerte. TestU01: los mismos problemas de compilación. Y una vez que lo calzaste en tu computadora, ¿funciona correctamente? ¿Cómo puedes entonces confiar en la salida? ¿Y cómo sabes si una prueba ha fallado? ¿Qué nivel de p o KS se considera demasiado extremo?

Además, agregaría que debería considerar el desarrollo de suites de prueba de aleatoriedad en relación con la política real. Es en interés propio de un académico desarrollar pruebas que desacrediten a los generadores de números aleatorios. Después de todo, no obtienes ningún tipo de financiación que produzca resultados que digan "todo está bien, nada encontrado, no se requiere más investigación".

Los lectores estarán en desacuerdo con esta premisa, pero sugiero que consideren lo que sucede en el mundo real en el que vivimos, no en la biblioteca de un académico. No hay una prueba estándar. Considerar:-

Random.org: usó una licenciatura para realizar algunas pruebas caseras para una tesis. Y esencialmente cuente el número de 1 y 0. ENT hace similar.

Hotbits: defiende el ENT simplista y una versión pirateada de Dieharder que a la mayoría de la gente le resultará difícil ejecutar, sin importar que intentes comprender miles de inicializadores de prueba.

Papeles de generador académico: mucho recurso a los escritos de Knuth y técnicas caseras. Algunos usan algunas de las herramientas anteriores. Algunos luego aceptan una serie de fallas de prueba dentro de esas suites.

El único ejemplo que he encontrado hasta ahora en el universo de este hombre que parece tener algún peso real (es decir, si falla, vas a un tipo de peso de prisión) es la certificación de Playtech PLC, un proveedor de software de apuestas del Reino Unido. Ofrecen algunas de las mayores compañías de apuestas en línea donde el dinero real cambia de manos. Aún así, usan pruebas homebrew y la prueba Diehard.

Personalmente me gusta:

convierta el archivo sujeto en un mapa de bits para verlo
comprimirlo con 7z en la configuración Ultra para ver si se vuelve más pequeño
haz una carrera de Diehard y busca ps y KS estúpidos.

Creo que si un archivo supera mi 1 - 3 personal, tendrá dificultades para demostrar lo contrario. Me parece un punto de partida tan bueno como cualquier ...

La ruta que probablemente tomaría sería hacer un análisis visual de los resultados. El código para esto es bastante simple, como se muestra en el siguiente código de psudo basado en su artículo .

1. Create an image of size x by y 2. For ndx = 0 to x 3. For ndy = 0 to y 4. Let random be a random number between 0 and 1 5. If random = 1, set the image point at ndx, ndy as black 6. Display the generated image

Además, Random.org tiene más información sobre el análisis estadístico de algoritmos, pero también usan el artículo mencionado anteriormente como su ejemplo de análisis visual.

Las pruebas disponibles son:

Dieharder - http://www.phy.duke.edu/~rgb/General/dieharder.php

TestU01 - http://simul.iro.umontreal.ca/testu01/tu01.html

RaBiGeTe - http://cristianopi.altervista.org/RaBiGeTe_MT/

NIST STS - http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

PractRand - http://pracrand.sourceforge.net/

Cualquiera de ellos puede probar bits de un archivo. Algunos (PractRand, Dieharder, no estoy seguro acerca de TestU01) pueden probar los datos canalizados en la entrada estándar. Algunos también admiten el enlace de su PRNG directamente al banco de pruebas, dinámicamente (solo RaBiGeTe ofrece soporte real para vincular dinámicamente su PRNG) o estáticamente.

La calidad no es igual Si tiene muchos bits de salida de PRNG, PractRand puede encontrar la mayor variedad de sesgos de la forma más rápida (completo: escribí PractRand), seguido de TestU01. Si no tienes muchos bits, RaBiGeTe podría hacerlo mejor. NIST STS y Dieharder generalmente tienen un rendimiento inferior.

La comodidad de la interfaz tampoco es igual. PractRand y Dieharder están configurados para la automatización de línea de comando. PractRand y TestU01 tienden a tener el resultado más fácil de interpretar en mi opinión. Dieharder no está mal en ese sentido. RaBiGeTe y NIST STS, bueno ... ambos promueven lo que me parece una visualización demasiado complicada e inútil de las distribuciones de los resultados de las pruebas.

Además, NIST STS y Dieharder tienen problemas falsos positivos.

También hay ENT, no puede encontrar un enlace para él en este momento ... tiene una interfaz bastante conveniente IIRC pero no es muy buena para encontrar el sesgo.

Para su caso de uso particular, recomiendo anotar los números 0 y 1 generados por su rng como caracteres en un archivo y luego usar ese archivo como datos de entrada para el programa de conjunto de pruebas.

Tenga en cuenta que la secuencia debe tener al menos 1000 caracteres de largo para ser probado por STS.

Cuando lo ejecute, no se olvide de usar el indicador -F ''a'' , para decirle al programa que el archivo de entrada está hecho de ASCII 0 y 1 caracteres.

También recomiendo probar esta versión no oficial de NIST Statistical Test Suite, donde he jugueteado con el código fuente original de NIST e intenté optimizarlo.

Para su comodidad, aquí está el comando que sugeriría que use para ejecutar las pruebas con él (después de haber compilado el programa desde las fuentes con $ make ):

$ ./sts -v 1 -i 32 -I 1 -w . -F ''a'' /path/to/input/file

Es posible que desee aumentar la cantidad de flujos de bits probados (indicados por el -i ) a uno más grande para utilizar más datos de la entrada. Por ejemplo, puedes elegir:

number of bitstreams = (number of 1 and 0 bits you generated) / 1048576

Una vez que se hayan ejecutado todas las pruebas, el programa generará un informe en un archivo llamado result.txt , que puede usar para evaluar la calidad de su rng.

Tenga en cuenta que este programa no es NIST-oficial sin embargo. Además, nuestras modificaciones de la suite de pruebas no se sometieron a pruebas de terceros; entonces es AS-IS sin garantías de ningún tipo.