testing - sorteos - Cómo probar un generador aleatorio
numeros pseudoaleatorios ejemplos (13)
Necesito probar un generador de números aleatorios que produce números aleatoriamente. Cómo asegurarse de que los números generados sean aleatorios.
Cómo asegurarse de que los números generados sean aleatorios.
No se puede asegurar , no hay manera de distinguir con certeza cualquier función de un generador de números aleatorios usando un número finito de pruebas. Pero puedes hacer un Análisis estadístico :
Entonces, si es imposible probar definitivamente la aleatoriedad, ¿qué podemos hacer? El enfoque pragmático es tomar muchas secuencias de números aleatorios de un generador dado y someterlos a una batería de pruebas estadísticas. A medida que las secuencias superan la mayoría de las pruebas, la confianza en la aleatoriedad de los números aumenta y también aumenta la confianza en el generador. Sin embargo, debido a que esperamos que algunas secuencias parezcan no aleatorias (como los diez rollos de seis en nuestro dado), deberíamos esperar que algunas de las secuencias fallen al menos algunas de las pruebas. Sin embargo, si muchas secuencias fallan las pruebas, deberíamos sospechar. Esta es también la forma en que probarías intuitivamente un dado para ver si está cargado: Hazlo rodar muchas veces, y si ves demasiadas secuencias del mismo valor que surgen, deberías sospechar.
Consulte la sección del estudio de Charmaine Kenny para obtener más detalles sobre las pruebas que puede ejecutar.
A menos que tenga acceso al generador de números aleatorios y pueda usarlo para generar números a voluntad, no puede probar si una secuencia de números es aleatoria. Piénselo: tiene un generador de números aleatorios. Digamos que es un generador de números aleatorios uniforme, generando enteros aleatorios en el rango [0,9]. Dada una secuencia:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
¿Puedes decir si es aleatorio? Existe una probabilidad finita 10 -10 , de que nuestro generador de números aleatorios uniformes generará esta secuencia exacta. De hecho, dada cualquier secuencia de longitud 10, tenemos la misma probabilidad de que nuestro generador de números aleatorios uniformes genere esa secuencia. Por lo tanto, por definición, no puede determinar si una secuencia dada es aleatoria.
Si tiene acceso al generador y puede usarlo para generar secuencias múltiples, entonces tiene sentido "verificar la aleatoriedad". Para esto, miraría las pruebas de Diehard . Hay varias implementaciones.
A menudo, si tiene su generador dibujar puntos en ubicaciones al azar en un mapa de bits, cualquier no aleatoriedad será fácilmente discernible a simple vista como aglutinación, bandas o líneas.
Aquí hay una explicación detallada de cómo comenzar. La prueba preliminar para cualquier RNG es la prueba Monobit utilizada por el NIST que simplemente cuenta el número de 1s y 0s. http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html
Una nota sobre la prueba de un generador de números aleatorios: en realidad no necesitamos demasiadas pruebas de RNG porque muchos se "subsumen" entre sí.
Dicho esto, aquí se describe una nueva prueba de frecuencia ordenada efectiva para bits. Esta prueba incluye cualquier prueba de frecuencia que espera 50-50 porque es más estricta.
Definiciones: t = lanzamientos / ensayos b = bins / urnas s = sesiones de lanzamientos n = series de sesiones
Debido a que los lanzamientos de monedas generalmente no son 50-50, esta nueva prueba se puede utilizar con gran efectividad utilizando un conjunto de 40,000,000 de bits.
Cuando las monedas se voltean 100 veces, los valores esperados son 53.9795 de uno y 46.0205 del otro, a veces más cabezas, a veces más colas. 50-50 no es el valor esperado de los contenedores ordenados, por lo que esta prueba es superior a cualquier prueba de frecuencia que, en cambio, espera 50-50.
Paso 1: Elección del tamaño de la muestra: 100 lanzamientos / bits.
Paso 2: Elección del número de sesiones: 50 sesiones nunca es suficiente, incluso con grandes tamaños de muestra en millones. 400 es usualmente suficiente. 2000 converge bien, por lo que se utilizan 2000 muestras diferentes de 100 lanzamientos. La ganancia mínima se produce por encima de 2000.
Valores esperados para 2000 sesiones de 100 lanzamientos: 50-50 159.1784748 (Observe que 50-50 ocurre solo el 7.96% del tiempo.) 51-49 312.1146564 52-48 294.1080416 53-47 266.362 54-46 231.8335926 55-45 193.8971865 56 -44 155.8102392 57-43 120.2745706 58-42 89.16907819 59-41 63.47629295 60-40 43.37546685 61-39 28.4429291 62-38 17.89152 63-37 10.79171042 64-36 6.238957586 65-35 3.455422663
66-34 1.832421109 67 o más 1.747439674
La ecuación para obtener los porcentajes exactos para los contenedores b = 2 y arroja t = 100 es: para 100-0, las probabilidades son 1 / (2 ^ 99) = 1 / (2 ^ (t-1)) Luego, construyendo desde allí, para 99-1 anterior multiplicado por 100 (t) divida por 1 para 98-2 anterior multiplicado por 99 (t-1) divida por 2 para 97-3 anterior multiplicado por 98 (t-2) divida por 3. .. omitir ... para 51-49 anterior multiplicado por 52 (t-48) dividir por 49 para 50-50 anterior multiplicado por 51 (t-49) dividir por 50, luego dividir de nuevo por 2.
Esta ecuación funciona con cualquier cantidad de lanzamientos.
Paso 3: se toma una chi-cuadrado en estos 18 valores con 17 grados de libertad, dando un valor de p resultante.
los valores p por encima de 0.999 están cerca de la perfección. ¿Puede un RNG estar demasiado cerca de la perfección con demasiada frecuencia? Sí, siendo demasiado predecible. Por debajo de 0.001 es donde generalmente ocurren problemas definidos. Un banco de pruebas considera 300 ceros a la derecha del decimal como infinitesimalmente malo y 10-14 como fallas. Algunos consideran 6 ceros lo suficientemente malos como para calificar como una clara falla definitiva. Algunos, por razones de seguridad, consideran 1 o 2 ceros lo suficiente y están en error. Por lo tanto, en lugar de un único valor de p para un solo conjunto que a veces proporciona un valor de p menor de 0.01 para un excelente RNG, se toman muchos conjuntos de sesiones.
Paso 4: Los valores de p se alimentan a una prueba de Kolmogorov-Smirnov en línea recta 0-1.0. Diferentes expertos recomiendan que la cantidad de entradas para la prueba KS sea de 10 a 1000. 100 no es suficiente. 200 está bien. 500 es ligeramente agresivo.
Aquí hay un pseudocódigo para obtener la diferencia máxima de KS:
Set low := 0; Set n := 200;
Set ansForward := 0; Set ansBack := 0;
sort( pval [n] );
for (j := 0; j < n; j := j+1)
{ Set Kback := pval [ j ] - low;
Set low := low +1 / n; { Ranges from 0 to 1 }
Set Kforward := low - pval [ j ];
if (Kforward > ansForward) Set ansForward := Kforward;
if (Kback > ansBack) Set ansBack := Kback;
}
{ Separate analysis can perhaps be made here on ansForward and ansBack. Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
return ansForward;
else
return ansBack; ∎
La respuesta KS no tiene un valor ap y no debe exceder 0,115 para valores de 200 p. 0.03 a 0.08 es normal para un buen RNG. 0.115 a 0.13 es sospechoso.
La prueba KS es muy simple. También es bastante efectiva.
Se muestra arriba una nueva prueba de frecuencia ordenada superior. Cualquier RNG que no supere esta prueba no se debe probar más y se debe reemplazar inmediatamente. Pero, ¿qué sigue?
El OFTest no incluye la prueba LOR. Se recomienda la prueba de longitud de carreras con un tamaño de muestra de 200,000 con 15 grados de libertad alimentados en la prueba KS 200 veces. (Tenga en cuenta que el total esperado del contenedor LOR más pequeño para "más que j" es igual al j-ésimo cubo).
¿Y entonces que? Para muchos juegos, estas dos pruebas son todo lo que necesitas. Hay una propensión de elecciones de NIST, Diehard, Dieharder, Crusher. (Nota: La prueba de Sumas superpuestas Diehard es inferior y defectuosa, no una interpretación fiel del código Fortran original de Marsaglia).
Resultados de algunos RNG con n = 200.
LCG 134775813x + 1 mod 2 ^ 31 semilla = 11111: Alto bit: OFT KS: 0.0841 Pase. LOR KS: 0.04786 Pase. Monobit de los primeros 200,000: -189 Pase. Bit 16: OFT KS: 0.5477 Error. Monobit de los primeros 200,000: 114 Pass. Todos los bits del 0 al 15 fallan el OFT, pero pasan la prueba Monobit.
El menudo y difamado LCG Randu: 65539x + 0 mod 2 ^ 31 semilla = 11111:
Alto bit: OFT KS: 0.03567 LOR KS: 0.07709. Monobit de los primeros 200,000: -165 Bit 18: OFT KS: 0,15143 Monobit de los primeros 200,000: +204 Todos los bits del 0 al 17 fallan el OFT.LCG 69069x + 1 mod 2 ^ 32 semilla = 11111: bit alto: OFT KS: 0.05547 LOR KS: 0.0456 Monobit de 200,000: -290 Bit 17: OFT KS: 0.1467 Monobit de 200,000: -193 Todos los bits del 0 al 13 fallan A MENUDO.
LCG 3141592653x + 2718281829 mod 2 ^ 35 semilla = 11111: Alto bit: OFT KS: 0.02868 LOR KS: 0.06117 Monobit de 200,000: -69 Bit 16: OFT KS: 0.240 Monobit de 200,000: -13 Todos los bits del 0 al 15 fallan A MENUDO.
LCG 23x + 0 mod 2 ^ 27 semilla = 11111: Alto bit: OFT KS: 0.5368 Monobit de 200,000: -235 Todos los bits fallan el OFT.
Observe que los bits bajos de cualquier LCG deben descartarse del resultado devuelto.
Una nota de aproximadamente 2 ^ 35: este es el período mínimo y la importancia para cualquier generador de números aleatorios porque se activan las monedas y los dados, y esas cosas pueden suceder 30 veces seguidas, pero no se espera que ocurra 35. Un período de 2 ^ 32 es insuficiente, demasiado pequeño para situaciones de la vida real.
LWAP
Cree un archivo de registro que contendrá el número aleatorio para al menos 500 instancias y auditará la aleatoriedad. También eche un vistazo al enlace a continuación,
Depende de cuán severo sea tu requerimiento de aleatoriedad. Si no es demasiado severo, lo que hago es generar una gran cantidad de números aleatorios, encontrar sus frecuencias y luego usar las frecuencias para trazar un gráfico usando un spreadshhet como ese en Open Office. Si la distribución se ve bien, entonces estoy listo para ir.
Es una cosa muy difícil.
Puede probar ENT desde Fourmilab y compararlo con los resultados contra su RNG, HotBits . También es posible que Random.org revisar Random.org .
Esto también parece interesante: pruebas duras (aunque no he trabajado con eso).
Hay una buena herramienta para este alumno: http://www.phy.duke.edu/~rgb/General/dieharder.php
por ejemplo, puedes probar el build-in urandom
cat /dev/random | dieharder -a -g 200
O escriba su propio script que creará un archivo con números aleatorios
dieharder -a -g 202 -f random.txt
Muéstralo a una habitación llena de desarrolladores.
No puede asegurarse de que los números sean aleatorios simplemente porque los números aleatorios son, bueno, aleatorios .
Las posibilidades de obtener una cadena de un millón de 9 consecutivos es lo mismo que obtener cualquier otra secuencia específica de un millón de años. Lo único que puede verificar es la distribución correcta en un gran conjunto de muestras. Ejecute una prueba considerable y resuelva las ocurrencias relativas de cada resultado posible.
En una muestra lo suficientemente grande, deberían ser aproximadamente iguales.
Otra posibilidad es probar la no repetibilidad. Idealmente, los números aleatorios no deberían depender de los números que vinieron antes. Los PRNG muy sencillos (congruencia lineal) le darán la misma secuencia de números con el tiempo, pero a lo largo de un conjunto lo suficientemente grande que probablemente no le importe (a menos que sea serio acerca de la aleatoriedad).
No puede generar aleatoriedad real mediante ningún algoritmo, por lo tanto, trate de visualizar sus resultados y compruebe los patrones con sus propios ojos. Ninguno generador aleatorio (por algoritmo) crearía algunos patrones que usted mismo puede juzgar. Aquí hay una demostración de esa idea: http://www.alife.co.uk/nonrandom/
Solo se puede probar la aleatoriedad estadística de todos modos, y eso no prueba si la secuencia numérica es criptográficamente fuerte. Probar estadísticamente un PRNG requiere bastante (10 o incluso 100 Gbytes) de los bits generados.
Dieharder es una muy buena suite de pruebas.
http://www.phy.duke.edu/~rgb/General/dieharder.php
Y TestU01 también es muy conocido.
Use la prueba de chi-cuadrado. Qué idioma estás usando? Puedo ofrecer un ejemplo de C ++. Básicamente
- Coloque números al azar en cubos (muchas veces).
- La cantidad de cubos menos uno son los grados de libertad .
- Compare los recuentos de cubo con los recuentos "esperados", produciendo un resultado de chi-cuadrado.
- Use una calculadora de chi-cuadrado para ver la probabilidad de obtener esos resultados.