stringtranslate.com

Pruebas a prueba de fuego

Las pruebas de rigor son una batería de pruebas estadísticas para medir la calidad de un generador de números aleatorios . Fueron desarrolladas por George Marsaglia a lo largo de varios años y publicadas por primera vez en 1995 en un CD-ROM de números aleatorios. [1] En 2006, las pruebas de rigor originales se ampliaron a las dieharderpruebas. [2]

Historia

En la primera edición de 1969 de The Art of Computer Programming (El arte de la programación informática ), Donald Knuth (volumen 2, capítulo 3.3: Pruebas estadísticas), se sugirió una batería inicial de pruebas de aleatoriedad para los RNG. Las pruebas de Knuth fueron sustituidas por las pruebas Diehard de George Marsaglia (1995), que consistían en quince pruebas diferentes. La imposibilidad de modificar los parámetros de las pruebas o añadir nuevas pruebas llevó al desarrollo de la biblioteca TestU01 , introducida en 2007 por Pierre L'Ecuyer y Richard Simard de la Université de Montréal .

Descripción general de la prueba

Espaciamiento entre cumpleaños
Elija puntos aleatorios en un intervalo grande. Los espacios entre los puntos deben distribuirse de forma exponencial asintótica . [3] El nombre se basa en la paradoja del cumpleaños .
Permutaciones superpuestas
Analizar secuencias de cinco números aleatorios consecutivos. Los 120 ordenamientos posibles deberían ocurrir con probabilidad estadísticamente igual.
Rangos de matrices
Seleccione una cierta cantidad de bits de una cierta cantidad de números aleatorios para formar una matriz sobre {0,1}, luego determine el rango de la matriz. Cuente los rangos.
Pruebas de mono
Trate las secuencias de cierta cantidad de bits como "palabras". Cuente las palabras superpuestas en un flujo. La cantidad de "palabras" que no aparecen debe seguir una distribución conocida. El nombre se basa en el teorema del mono infinito .
Cuenta los 1s
Cuente los bits 1 de cada byte sucesivo o elegido. Convierta los recuentos en "letras" y cuente las ocurrencias de "palabras" de cinco letras.
Prueba de estacionamiento
Coloque círculos unitarios al azar en un cuadrado de 100×100. Un círculo se considera estacionado correctamente si no se superpone a otro ya estacionado correctamente. Después de 12 000 intentos, la cantidad de círculos estacionados correctamente debería seguir una determinada distribución normal .
Prueba de distancia mínima
Colocar aleatoriamente 8000 puntos en un cuadrado de 10000×10000 y luego hallar la distancia mínima entre los pares. El cuadrado de esta distancia debe estar distribuido exponencialmente con una media determinada.
Prueba de esferas aleatorias
Elige al azar 4000 puntos en un cubo de 1000 aristas. Centra en cada punto una esfera cuyo radio sea la distancia mínima a otro punto. El volumen de la esfera más pequeña debe estar distribuido exponencialmente con una media determinada.
La prueba de compresión
Multiplica 2 31 por números de punto flotante aleatorios en ( 0,1 ) hasta llegar a 1. Repite esto 100000 veces. La cantidad de números de punto flotante necesarios para llegar a 1 debe seguir una distribución determinada.
Prueba de sumas superpuestas
Generar una secuencia larga de números flotantes aleatorios en ( 0,1 ). Agregar secuencias de 100 números flotantes consecutivos. Las sumas deben estar distribuidas normalmente con media y varianza características.
Ejecuta prueba
Generar una secuencia larga de números flotantes aleatorios en ( 0,1 ). Contar las ejecuciones ascendentes y descendentes. Los conteos deben seguir una distribución determinada.
La prueba de dados
Juegue 200.000 partidas de dados , contando las ganancias y la cantidad de lanzamientos por partida. Cada conteo debe seguir una distribución determinada.

Descripciones de pruebas

La prueba del espaciamiento entre 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 aparecen más de una vez en esa lista, entonces j tiene una distribución asintótica de Poisson con media m 3 / (4 n ) . La experiencia muestra que n debe ser bastante grande, digamos n ≥ 2 18 , para comparar los resultados con la distribución de Poisson con esa media. Esta prueba utiliza n = 2 24 y m = 2 9 , de modo que la distribución subyacente para j se toma como Poisson con λ = 2 27 / 2 26 = 2 . Se toma una muestra de 500 j s, y una prueba de bondad de ajuste de chi-cuadrado proporciona un valor p . La primera prueba utiliza los bits 1–24 (contando desde la izquierda) de números enteros en el archivo especificado. Luego, el archivo se cierra y se vuelve a abrir. A continuación, se utilizan los bits 2 a 25 para proporcionar fechas de nacimiento, luego los bits 3 a 26 y así sucesivamente hasta los bits 9 a 32. Cada conjunto de bits proporciona un valor p y los nueve valores p proporcionan una muestra para una prueba KSTEST.
La prueba de 5 permutaciones superpuestas
Esta es la prueba OPERM5. Examina una secuencia de un millón de números enteros aleatorios de 32 bits. Cada conjunto de cinco números enteros consecutivos puede estar en uno de los 120 estados, para los 5! posibles ordenamientos de cinco números. Por lo tanto, el quinto, sexto, séptimo, ... números proporcionan cada uno un estado. Como se observan miles de transiciones de estado, se realizan recuentos acumulativos del número de ocurrencias de cada estado. Luego, la forma cuadrática en la inversa débil de la matriz de covarianza de 120 × 120 produce una prueba equivalente a la prueba de razón de verosimilitud de que los recuentos de 120 celdas provienen de la distribución normal (asintóticamente) especificada con la matriz de covarianza de 120 × 120 especificada (con rango 99). Esta versión utiliza 1000000 números enteros, dos veces. Esta prueba puede tener errores sin resolver que resulten en valores p consistentemente deficientes. [4]
La prueba de rango binario para matrices de 31×31
Los 31 bits más a la izquierda de 31 números enteros aleatorios de la secuencia de prueba se utilizan para formar una matriz binaria de 31×31 sobre el campo {0,1}. Se determina el rango. Ese rango puede ser de 0 a 31, pero los rangos < 28 son raros y sus conteos se agrupan con los del rango 28. Se encuentran los rangos para 40000 de esas matrices aleatorias y se realiza una prueba de chi-cuadrado sobre los conteos de los rangos 31, 30, 29 y ≤ 28.
Prueba de rango binario para matrices de 32×32
Se forma una matriz binaria aleatoria de 32×32, cada fila es un entero aleatorio de 32 bits. Se determina el rango. Ese rango puede ser de 0 a 32, los rangos menores a 29 son raros y sus conteos se agrupan con los del rango 29. Se encuentran los rangos para 40000 de esas matrices aleatorias y se realiza una prueba de chi cuadrado sobre los conteos para 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 en 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 y 3 son poco frecuentes; sus recuentos se agrupan con los del rango 4. Se encuentran los rangos de 100 000 matrices aleatorias y se realiza una prueba de chi cuadrado sobre los recuentos de los rangos 6, 5 y ≤ 4.
La prueba de flujo de bits
El archivo bajo prueba se ve como un flujo de bits. Llamémoslos 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 lo 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 la cantidad de palabras de 20 letras (20 bits) faltantes en una cadena de 2 21 palabras superpuestas de 20 letras. Hay 2 20 posibles palabras de 20 letras. Para una cadena verdaderamente aleatoria de 2 21 + 19 bits, la cantidad de palabras faltantes j debería tener una distribución (muy cercana a la normal) con una media de 141 909 y una sigma de 428. Por lo tanto, ( j −141 909) / 428 debería ser una variable normal estándar ( puntuación z ) que conduzca a un valor p uniforme [0,1) . La prueba se repite veinte veces.
Las pruebas OPSO, OQSO y DNA
OPSO significa overlapping-pairssparse-occupancy (ocupación dispersa 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) (a partir de 2 21 + 1 "pulsaciones de teclas") y cuenta la cantidad de palabras faltantes, es decir, palabras de 2 letras que no aparecen en toda la secuencia. Ese recuento debe estar muy cerca de una 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 utiliza un conjunto designado de diez bits consecutivos. Luego, reinicia el archivo para los siguientes 10 bits designados, y así sucesivamente. OQSO significa ocupación dispersa por superposición de cuadruplicaciones. 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, cuyos elementos se suponen enteros aleatorios de 32 bits. La media del número de palabras faltantes en una secuencia de 2 21 palabras de cuatro letras (2 21 + 3 "pulsaciones de teclas") es nuevamente 141909, con sigma = 295. La media se basa en la teoría; sigma proviene de una simulación exhaustiva. La prueba de ADN considera un alfabeto de 4 letras C, G, A, T, determinado por dos bits designados en la secuencia de enteros aleatorios que se está probando. Se consideran palabras de 10 letras, de modo que, como en OPSO y OQSO, hay 2 · 20 palabras posibles y la cantidad media de palabras faltantes de una cadena de 2 · 21 palabras (superpuestas) de 10 letras (2 · 21 + 9 "pulsaciones de teclas") es 141909. La desviación estándar sigma = 339 se determinó como para OQSO mediante simulación. (Sigma para OPSO, 290, es el valor verdadero (hasta tres lugares), no determinado por simulación.
La prueba de contar los 1 en un flujo de bytes
Considere el archivo bajo prueba como un flujo de bytes (cuatro por cada entero de 32 bits). Cada byte puede contener desde ninguno hasta ocho 1, con probabilidades 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Ahora dejemos que el flujo de bytes proporcione una cadena de palabras superpuestas de 5 letras, cada "letra" tomando los valores A, B, C, D, E. Las letras están determinadas por la cantidad de 1 en un byte: 0, 1 o 2 dan A, 3 da B, 4 da C, 5 da D y 6, 7 u 8 dan E. Por lo tanto, tenemos un mono en una máquina de escribir presionando cinco teclas con varias probabilidades (37, 56, 70, 56, 37 sobre 256). Hay 5 posibles palabras de 5 letras y, a partir de una cadena de 256 000 palabras de 5 letras (superpuestas), se realizan recuentos de las frecuencias de cada palabra. La forma cuadrática en la inversa débil de la matriz de covarianza de los recuentos de celdas 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 celdas de 5 y 4 letras.
La prueba de contar los 1 para bytes específicos
Considere el archivo bajo prueba como un flujo de números 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 1, con probabilidades 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Ahora, dejemos que los bytes especificados de enteros sucesivos proporcionen una cadena de palabras de 5 letras (superpuestas), cada "letra" tomando los valores A, B, C, D, E. Las letras están determinadas por la cantidad de 1, en ese byte 0, 1 o 2 → A, 3 → B, 4 → C, 5 → D y 6, 7 u 8 → E. Por lo tanto, 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 posibles Palabras de 5 letras y, a partir de una cadena de 256 000 palabras de 5 letras (superpuestas), se realizan recuentos de las frecuencias de cada palabra. La forma cuadrática en la inversa débil de la matriz de covarianza de los recuentos de celdas 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 celdas de 5 y 4 letras.
La prueba del estacionamiento
En un cuadrado de 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 estacionando "de oído". Es decir, si un intento de estacionar un automóvil causa un choque con uno que ya está estacionado, intente nuevamente en una nueva ubicación aleatoria. (Para evitar problemas de ruta, considere estacionar helicópteros en lugar de automóviles). Cada intento conduce a un choque o a un éxito, este último seguido por un incremento en la lista de automóviles que ya están estacionados. Si graficamos n : el número de intentos, versus k el número de estacionados exitosamente, obtenemos una curva que debería ser similar a las proporcionadas por un generador de números aleatorios perfecto. La teoría para el comportamiento de una curva aleatoria de este tipo parece estar fuera de alcance, y como no hay representaciones 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 exitosamente después de n = 12000 intentos. La simulación muestra que k debería tener un promedio de 3523 con sigma 21,9 y que está muy cerca de una 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 datos de entrada para una prueba KSTEST basada en una muestra de 10.
La prueba de distancia mínima
Hace esto 100 veces elige n = 8000 puntos aleatorios en un cuadrado de lado 10000. Encuentra d , la distancia mínima entre los ( n 2 − n ) / 2 pares de puntos. Si los puntos son verdaderamente independientes uniformes, entonces d 2 , el cuadrado de la distancia mínima debería estar (muy cerca de) distribuido exponencialmente con media 0.995. Por lo tanto, 1 − exp(− d 2 / 0.995) debería ser uniforme en [0,1) y un KSTEST 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 elecciones aleatorias de 8000 puntos en el cuadrado de 10000×10000.
La prueba de las esferas 3D
Elija 4000 puntos aleatorios en un cubo de arista 1000. En cada punto, centre una esfera lo suficientemente grande como para alcanzar el siguiente punto más cercano. Entonces, el volumen de la esfera más pequeña de este tipo se distribuye (muy cerca de) exponencialmente con media 120 π / 3. Por lo tanto, el radio al cubo es exponencial con media 30. (La media se obtiene mediante simulación extensiva). La prueba de esferas 3D genera 4000 de estas esferas 20 veces. Cada radio mínimo al cubo conduce a una variable uniforme por medio de 1 − exp(− r 3 / 30) , luego se realiza un KSTEST en los 20 valores p .
La prueba de compresión
Los números enteros aleatorios se convierten en números flotantes 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 proporcionada por números enteros flotantes del archivo que se está probando. Dichos j se encuentran 100000 veces, luego se utilizan los recuentos para el número de veces que j fue ≤ 6, 7, ..., 47, ≥ 48 para proporcionar una prueba de chi-cuadrado para frecuencias de celdas.
La prueba de las sumas superpuestas
Los números enteros se convierten en flotantes para obtener una secuencia U (1), U (2), ... de variables uniformes [0,1). Luego se forman las sumas superpuestas, S (1) = U (1) + ... + U (100), S (2) = U (2) + ... + U (101), .... Las S son virtualmente normales con una cierta matriz de covarianza. Una transformación lineal de las S las convierte en una secuencia de normales estándar independientes, que se convierten en variables uniformes para un KSTEST. A los valores p de diez KSTEST se les da otro KSTEST.
La prueba de carreras
Cuenta las ejecuciones ascendentes y descendentes en una secuencia de variables uniformes [0,1), obtenidas haciendo flotantes los enteros de 32 bits en el archivo especificado. Este ejemplo muestra cómo se cuentan las ejecuciones: 0,123, 0,357, 0,789, 0,425, 0,224, 0,416, 0,95 contiene una ejecución ascendente de longitud 3, una ejecución descendente de longitud 2 y una ejecución ascendente de (al menos) 2, dependiendo de los siguientes valores. Las matrices de covarianza para las ejecuciones ascendentes y descendentes 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 longitud 10000. Esto se hace diez veces. Luego se repite.
La prueba de dados
Juega 200000 juegos de dados, encuentra el número de victorias y el número de lanzamientos necesarios para terminar cada juego. El número de victorias debe ser (muy cercano a) un normal con media 200000 p y varianza 200000 p (1 − p ) , con p = 244 / 495 . Los lanzamientos necesarios para completar el juego pueden variar de 1 a infinito, pero los conteos para todos > 21 se agrupan con 21. Se realiza una prueba de chi-cuadrado en los recuentos de celdas de número de lanzamientos. 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 p se obtienen mediante p = F ( X ), donde F es la distribución asumida de la variable aleatoria de muestra X , a menudo normal. Pero esa F asumida es solo una aproximación asintótica, para la cual el ajuste será peor en las colas. Por lo tanto, no debería sorprenderle que ocasionalmente aparezcan valores p cercanos a 0 o 1, como 0,0012 o 0,9983. Cuando un flujo de bits realmente FALLA EN GRANDES, obtendrá valores p de 0 o 1 a seis o más lugares. Dado que hay muchas pruebas, no es improbable que un p < 0,025 o p > 0,975 signifique que el RNG "ha fallado la prueba en el nivel 0,05". Esperamos que ocurran varios de estos eventos entre los cientos de eventos que produce DIEHARD, incluso si el generador de números aleatorios es perfecto.

Véase también

Referencias

  1. ^ "El CD-ROM de números aleatorios de Marsaglia que incluye la batería de pruebas de aleatoriedad más completa". Universidad Estatal de Florida . 1995. Archivado desde el original el 25 de enero de 2016.
  2. ^ Brown, Robert G. "dieharder" . Consultado el 25 de septiembre de 2023 .
  3. ^ Renyi, 1953, pág. 194
  4. ^ "Página de herramientas generales de Robert G. Brown". Archivado desde el original el 3 de julio de 2017.

Lectura adicional

Enlaces externos