Las pruebas intransigentes son una batería de pruebas estadísticas para medir la calidad de un generador de números aleatorios . Fueron desarrollados por George Marsaglia durante varios años y publicados por primera vez en 1995 en un CD-ROM de números aleatorios. [1]
Resumen de la prueba
- Espacios de cumpleaños : elija puntos aleatorios en un intervalo grande. Los espacios entre los puntos deben estar distribuidos asintóticamente y exponencialmente . [2] El nombre se basa en la paradoja del cumpleaños .
- Permutaciones superpuestas : analiza secuencias de cinco números aleatorios consecutivos. Los 120 ordenamientos posibles deben ocurrir con una probabilidad estadísticamente igual.
- Rangos de matrices : seleccione un número de bits de un número de números aleatorios para formar una matriz sobre {0,1}, luego determine el rango de la matriz. Cuente las filas.
- Pruebas de mono : trate las secuencias de algunos bits como "palabras". Cuente las palabras superpuestas en una secuencia. El número de "palabras" que no aparecen debe seguir una distribución conocida. El nombre se basa en el teorema del mono infinito .
- Cuente los 1 : cuente los 1 bits en cada uno de los bytes sucesivos o elegidos. Convierta los recuentos en "letras" y cuente las apariciones de "palabras" de cinco letras.
- Prueba de estacionamiento : coloque círculos unitarios al azar en un cuadrado de 100 × 100. Un círculo se estaciona correctamente si no se superpone a uno existente estacionado correctamente. Después de 12.000 intentos, el número de círculos aparcados correctamente debe seguir una cierta distribución normal .
- Prueba de distancia mínima : coloque aleatoriamente 8000 puntos en un cuadrado de 10000 × 10000, luego encuentre la distancia mínima entre los pares. El cuadrado de esta distancia debe distribuirse exponencialmente con una determinada media.
- Prueba de esferas aleatorias: elija 4000 puntos al azar en un cubo de borde 1000. Centre una esfera en cada punto, cuyo radio es la distancia mínima a otro punto. El volumen de la esfera más pequeña debe distribuirse exponencialmente con una determinada media.
- La prueba de compresión : Multiplique 2 31 por flotadores aleatorios en (0,1) hasta llegar a 1. Repita esto 100000 veces. El número de flotadores necesarios para llegar a 1 debe seguir una determinada distribución.
- Prueba de sumas superpuestas : Genere una secuencia larga de flotantes aleatorios en (0,1). Agregue secuencias de 100 flotadores consecutivos. Las sumas deben distribuirse normalmente con media y varianza características.
- Prueba de rachas : genera una secuencia larga de flotantes aleatorios en (0,1). Cuente carreras ascendentes y descendentes. Los recuentos deben seguir una determinada distribución.
- La prueba de los dados : Juega 200000 partidas de dados , contando las ganancias y el número de lanzamientos por juego. Cada recuento debe seguir una determinada distribución.
Descripciones de prueba
- La prueba de espaciamiento de cumpleaños : elija m cumpleaños en un año de n días. Enumere los espacios entre los cumpleaños. Si j es el número de valores que ocurren más de una vez en esa lista, entonces j tiene una distribución de Poisson asintóticamente con una media m 3 ÷ (4 n ). La experiencia muestra que n debe ser bastante grande, digamos n ≥ 2 18 , para comparar los resultados de la distribución de Poisson con esa media. Esta prueba usa n = 2 24 y m = 2 9 , de modo que la distribución subyacente de j se toma como Poisson con λ = 2 27 ÷ 2 26 = 2. Se toma una muestra de 500 j s y se obtiene un chi-cuadrado La prueba de bondad de ajuste proporciona un valor p . La primera prueba usa los bits 1–24 (contando desde la izquierda) de enteros en el archivo especificado. Luego, el archivo se cierra y se vuelve a abrir. A continuación, los bits 2–25 se utilizan para proporcionar cumpleaños, luego 3–26 y así sucesivamente para los bits 9–32. Cada conjunto de bits proporciona un valor p , y los nueve valores p proporcionan una muestra para un KSTEST.
- La prueba de 5 permutación superpuesta : esta es la prueba OPERM5. Observa una secuencia de un millón de enteros aleatorios de 32 bits. Cada conjunto de cinco enteros consecutivos puede estar en uno de 120 estados, ¡para el 5! posibles ordenamientos de cinco números. Por lo tanto, los números 5, 6, 7, ... cada uno proporciona un estado. Como se observan muchos miles de transiciones de estado, se realizan recuentos acumulativos del número de ocurrencias de cada estado. Luego, la forma cuadrática en el inverso débil de la matriz de covarianza 120 × 120 produce una prueba equivalente a la prueba de razón de verosimilitud de que los 120 recuentos de células provienen de la distribución normal especificada (asintóticamente) con la matriz de covarianza 120 × 120 especificada (con rango 99 ). Esta versión usa 1000000 enteros, dos veces. Esta prueba puede tener errores no resueltos que resulten en valores p consistentemente bajos. [3]
- Prueba de rango binario para matrices de 31 × 31 : Los 31 bits más a la izquierda de 31 enteros aleatorios de la secuencia de prueba se utilizan para formar una matriz binaria de 31 × 31 sobre el campo {0,1}. El rango está determinado. Ese rango puede ser de 0 a 31, pero los rangos <28 son raros, y sus recuentos se combinan con los del rango 28. Los rangos se encuentran para 40000 matrices aleatorias y se realiza una prueba de chi-cuadrado en los recuentos de los rangos 31, 30 , 29 y ≤ 28.
- La prueba de rango binario para matrices de 32 × 32 : Se forma una matriz binaria aleatoria de 32 × 32, cada fila es un número entero aleatorio de 32 bits. El rango está determinado. Ese rango puede ser de 0 a 32, los rangos menores a 29 son raros y sus recuentos se combinan con los del rango 29. Los rangos se encuentran para 40000 matrices aleatorias de este tipo y se realiza una prueba de chi cuadrado en los recuentos de los rangos 32, 31, 30 y ≤ 29.
- La prueba de rango binario para matrices de 6 × 8 : de cada uno de los seis números enteros aleatorios de 32 bits del generador bajo prueba, se elige un byte específico y los seis bytes resultantes forman una matriz binaria de 6 × 8 cuyo rango se determina. Ese rango puede ser de 0 a 6, pero los rangos 0, 1, 2, 3 son raros; sus recuentos se combinan con los del rango 4. Los rangos se encuentran para 100000 matrices aleatorias y se realiza una prueba de chi cuadrado en los recuentos de los rangos 6, 5 y ≤ 4.
- La prueba del flujo de bits : el archivo bajo prueba se ve como un flujo de bits. Llámalos b 1 , b 2 , .... Considere un alfabeto con dos "letras", 0 y 1, y piense en el flujo de bits como una sucesión de "palabras" de 20 letras, superpuestas. Por tanto, la primera palabra es b 1 b 2 ... b 20 , la segunda es b 2 b 3 ... b 21 , y así sucesivamente. La prueba de flujo de bits cuenta el número de palabras de 20 letras (20 bits) que faltan en una cadena de 2 21 palabras superpuestas de 20 letras. Hay 2 20 palabras posibles de 20 letras. Para una cadena verdaderamente aleatoria de 2 21 + 19 bits, el número de palabras faltantes j debe estar (muy cerca de) distribuido normalmente con una media de 141,909 y sigma 428. Por lo tanto, ( j -141909) ÷ 428 debe ser una variable normal estándar ( z puntuación) que conduce a un valor p uniforme [0,1) . La prueba se repite veinte veces.
- Las pruebas OPSO, OQSO y DNA : OPSO significa ocupación escasa de pares superpuestos. La prueba OPSO considera palabras de 2 letras de un alfabeto de 1024 letras. Cada letra está determinada por diez bits específicos de un entero de 32 bits en la secuencia que se va a probar. OPSO genera 2 21 palabras de 2 letras (superpuestas) (de 2 21 + 1 "pulsaciones de teclas") y cuenta el número de palabras que faltan, es decir, palabras de 2 letras que no aparecen en toda la secuencia. Ese recuento debe estar muy cerca de la distribución normal con media 141909, sigma 290. Por lo tanto (missingwrds-141909) ÷ 290 debe ser una variable normal estándar. La prueba OPSO toma 32 bits a la vez del archivo de prueba y usa un conjunto designado de diez bits consecutivos. Luego reinicia el archivo para los siguientes 10 bits designados, y así sucesivamente. OQSO significa ocupación-escasa-cuádruple-superpuesta. La prueba OQSO es similar, excepto que considera palabras de 4 letras de un alfabeto de 32 letras, cada letra determinada por una cadena designada de 5 bits consecutivos del archivo de prueba, elementos de los cuales se asumen números enteros aleatorios de 32 bits. El número medio de palabras faltantes en una secuencia de 2 21 palabras de cuatro letras, (2 21 + 3 "pulsaciones de teclas"), es de nuevo 141909, con sigma = 295. La media se basa en la teoría; sigma proviene de una extensa simulación. La prueba de ADN considera un alfabeto de 4 letras C, G, A, T, determinado por dos bits designados en la secuencia de números enteros aleatorios que se están probando. Considera palabras de 10 letras, de modo que, como en OPSO y OQSO, hay 2 28 palabras posibles, y el número medio de palabras faltantes de una cadena de 2 21 (superpuestas) palabras de 10 letras (2 21 + 9 "pulsaciones de teclas" ) es 141909. La desviación estándar sigma = 339 se determinó como para OQSO por simulación. (Sigma para OPSO, 290, es el valor real (a tres lugares), no determinado por simulación.
- La prueba del conteo de 1 en un flujo de bytes : considere el archivo bajo prueba como un flujo de bytes (cuatro por entero de 32 bits). Cada byte puede contener de ninguno a ocho 1, con probabilidades 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Ahora deje que el flujo de bytes proporcione una cadena de palabras superpuestas de 5 letras, cada una " letra "tomando los valores A, B, C, D, E. Las letras están determinadas por el número de 1 en un byte 0, 1 o 2 dan como resultado A, 3 dan como resultado B, 4 dan como resultado C, 5 dan como resultado D y 6, 7 u 8 producen E. Así tenemos un mono en una máquina de escribir presionando cinco teclas con varias probabilidades (37, 56, 70, 56, 37 sobre 256). Hay 5 5 palabras posibles de 5 letras, y de una cadena de 256000 (superpuestas) palabras de 5 letras, se realizan recuentos en las frecuencias de cada palabra. La forma cuadrática en el inverso débil de la matriz de covarianza de los recuentos de células proporciona una prueba de qui-cuadrado Q5-Q4, la diferencia de las sumas ingenuas de Pearson de (OBS-EXP) 2 ÷ EXP en los recuentos de recuentos de células de 5 y 4 letras .
- La prueba del recuento de 1 para bytes específicos : considere el archivo bajo prueba como una secuencia de enteros de 32 bits. De cada entero, se elige un byte específico, digamos los bits más a la izquierda del 1 al 8. Cada byte puede contener de 0 a 8 1s, con probabilidades 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Ahora deje que los bytes especificados de enteros sucesivos proporcionen una cadena de palabras de 5 letras (superpuestas), cada "letra" toma los valores A, B, C, D, E. Las letras están determinadas por el número de unos, en ese byte 0 , 1, o 2 → A, 3 → B, 4 → C, 5 → D, y 6, 7 u 8 → E. Así tenemos un mono en una máquina de escribir presionando cinco teclas con varias probabilidades 37, 56, 70, 56 , 37 sobre 256. Hay 5 5 palabras posibles de 5 letras, y de una cadena de 256000 (superpuestas) palabras de 5 letras, se realizan recuentos en las frecuencias de cada palabra. La forma cuadrática en el inverso débil de la matriz de covarianza de los recuentos de células proporciona una prueba de chi cuadrado Q5 - Q4, la diferencia de las sumas ingenuas de Pearson de (OBS - EXP) 2 ÷ EXP en los recuentos de recuentos de células de 5 y 4 letras .
- La prueba del estacionamiento : En un cuadrado del lado 100, "estacione" aleatoriamente un automóvil - un círculo de radio 1. Luego intente estacionar un segundo, un tercero, y así sucesivamente, cada vez que estacione "de oído". Es decir, si un intento de estacionar un automóvil provoca un choque con uno ya estacionado, intente nuevamente en una nueva ubicación aleatoria. (Para evitar problemas en la ruta, considere estacionar helicópteros en lugar de automóviles). Cada intento conduce a un accidente o un éxito, este último seguido de un incremento en la lista de automóviles ya estacionados. Si graficamos n : el número de intentos, versus k el número estacionado exitosamente, obtenemos una curva que debería ser similar a las proporcionadas por un generador de números aleatorios perfecto. La teoría del comportamiento de una curva tan aleatoria parece fuera de alcance y, dado que no hay pantallas gráficas disponibles para esta batería de pruebas, se utiliza una caracterización simple del experimento aleatorio: k , el número de automóviles estacionados con éxito después de n = 12000 intentos. La simulación muestra que k debería promediar 3523 con sigma 21.9 y está muy cerca de la distribución normal. Por lo tanto, ( k - 3523) ÷ 21,9 debería ser una variable normal estándar, que, convertida en una variable uniforme, proporciona una entrada a un KSTEST basado en una muestra de 10.
- La prueba de distancia mínima : Hace esto 100 veces, elija n = 8000 puntos aleatorios en un cuadrado de lado 10000. Encuentre d , la distancia mínima entre los ( n 2 - n ) ÷ 2 pares de puntos. Si los puntos son uniformes verdaderamente independientes, entonces d 2 , el cuadrado de la distancia mínima debe estar (muy cerca de) distribuido exponencialmente con una media de 0,995. Por tanto, 1 - exp (- d 2 ÷ 0,995) debe ser uniforme en [0,1) y una prueba KST en los 100 valores resultantes sirve como prueba de uniformidad para puntos aleatorios en el cuadrado. Se imprimen números de prueba = 0 mod 5, pero el KSTEST se basa en el conjunto completo de 100 opciones aleatorias de 8000 puntos en el cuadrado de 10000 × 10000.
- La prueba de las esferas 3D : Elija 4000 puntos aleatorios en un cubo de borde 1000. En cada punto, centre una esfera lo suficientemente grande como para llegar al siguiente punto más cercano. Entonces, el volumen de la esfera más pequeña está (muy cerca de) distribuido exponencialmente con una media de 120 π ÷ 3. Por lo tanto, el radio al cubo es exponencial con una media de 30. (La media se obtiene mediante una simulación extensa). La prueba de esferas 3D genera 4000 esferas de este tipo 20 veces. Cada radio mínimo al cubo conduce a una variable uniforme por medio de 1 - exp (- r 3 ÷ 30), luego se realiza una KSTEST en los 20 valores p .
- La prueba de compresión : los números enteros aleatorios se flotan para obtener uniformes en [0,1). Comenzando con k = 2 31 = 2147483648, la prueba encuentra j , el número de iteraciones necesarias para reducir k a 1, utilizando la reducción k = techo ( k × U ), con U proporcionado por enteros flotantes del archivo que se está probando. Tales j s se encuentran 100000 veces, luego se cuenta el número de veces que j fue ≤ 6, 7, ..., 47, ≥ 48 se utilizan para proporcionar una prueba de chi-cuadrado para las frecuencias de las células.
- La prueba de sumas superpuestas : los enteros se flotan para obtener una secuencia U (1), U (2), ... de variables uniformes [0,1). Entonces se forman las sumas superpuestas, S (1) = U (1) + ... + U (100), S (2) = U (2) + ... + U (101), .... Los S son virtualmente normales con una determinada matriz de covarianza. Una transformación lineal de los S s los convierte en una secuencia de normales estándar independientes, que se convierten en variables uniformes para un KSTEST. Los valores p de diez KSTEST reciben todavía otro KSTEST.
- La prueba de corridas : cuenta las corridas hacia arriba y hacia abajo, en una secuencia de variables uniformes [0,1), obtenidas flotando los enteros de 32 bits en el archivo especificado. Este ejemplo muestra cómo se cuentan las corridas: 0.123, 0.357, 0.789, 0.425, 0.224, 0.416, 0.95 contiene una corrida ascendente de longitud 3, una corrida descendente de longitud 2 y una corrida ascendente de (al menos) 2, dependiendo en los siguientes valores. Las matrices de covarianza para las subidas y bajadas son bien conocidas, lo que lleva a pruebas de chi-cuadrado para formas cuadráticas en las inversas débiles de las matrices de covarianza. Las ejecuciones se cuentan para secuencias de 10000 de longitud. Esto se realiza diez veces. Luego repitió.
- La prueba de los dados : Juega 200000 juegos de dados, encuentra el número de victorias y el número de lanzamientos necesarios para finalizar cada juego. La cantidad de victorias debe ser (muy cercana a) una normal con una media de 200000 py una varianza de 200000 p (1 - p ), con p = 244 ÷ 495. Los lanzamientos necesarios para completar el juego pueden variar de 1 a infinito, pero cuenta para todos> 21 se agrupan con 21. Se realiza una prueba de chi-cuadrado en el conteo de celdas de número de tiros. Cada entero de 32 bits del archivo de prueba proporciona el valor para el lanzamiento de un dado, flotando a [0,1), multiplicando por 6 y tomando 1 más la parte entera del resultado.
La mayoría de las pruebas en DIEHARD devuelven un valor p , que debería ser uniforme en [0,1) si el archivo de entrada contiene bits aleatorios verdaderamente independientes. Esos valores de p se obtienen mediante p = F ( X ), donde F es la distribución supuesta de la variable aleatoria de muestra X , a menudo normal. Pero ese supuesto F es solo una aproximación asintótica, para la cual el ajuste será peor en las colas. Por lo tanto, no debería sorprenderse con valores p ocasionales cercanos a 0 o 1, como 0,0012 o 0,9983. Cuando un flujo de bits realmente FALLA GRANDE, obtendrá p s de 0 o 1 a seis o más lugares. Dado que hay muchas pruebas, no es improbable que una p <0.025 op > 0.975 signifique que el RNG ha "fallado la prueba al nivel 0.05". Esperamos que ocurran varios de estos eventos p s entre los cientos de eventos que DIEHARD produce, incluso condicionados a que el generador de números aleatorios sea perfecto.
Ver también
Notas
- ^ "El CDROM de números aleatorios de Marsaglia que incluye la batería de pruebas de aleatoriedad" . Universidad Estatal de Florida . 1995. Archivado desde el original el 25 de enero de 2016.
- ↑ Renyi, 1953, p194
- ^ https://webhome.phy.duke.edu/~rgb/General/dieharder.php
enlaces externos
- "El CDROM de números aleatorios de Marsaglia, incluida la batería de pruebas de aleatoriedad" . Universidad Estatal de Florida . 1995. Archivado desde el original el 25 de enero de 2016.
- Robert G. Brown. "Dieharder: una suite de prueba de números aleatorios" .
- Rényi, Alfréd (1953). "Sobre la teoría de la estadística de orden". Acta Mathematica Academiae Scientiarum Hungaricae . Acta Mathematica Hungarica. 4 (3–4): 191–231. doi : 10.1007 / BF02127580 . hdl : 10338.dmlcz / 102650 .