stringtranslate.com

Pruebas intransigentes

Las pruebas incondicionales 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] En 2006, las pruebas intransigentes originales se ampliaron a las dieharderpruebas. [2]

Historia

En la primera edición de 1969 de The Art of Computer Programming de 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 luego suplantadas por las pruebas Diehard (1995) de George Marsaglia, que constan de quince pruebas diferentes. La imposibilidad de modificar los parámetros de la prueba o agregar nuevas pruebas llevó al desarrollo de la biblioteca TestU01 , introducida en 2007 por Pierre L'Ecuyer y Richard Simard de la Universidad de Montreal .

Descripción general de la prueba

Espaciados de cumpleaños
Elija puntos aleatorios en un intervalo grande. Los espacios entre los puntos deben estar distribuidos asintóticamente exponencialmente . [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 cantidad de bits de una cantidad de números aleatorios para formar una matriz sobre {0,1}, luego determine el rango de la matriz. Cuente las filas.
Pruebas de monos
Trate las secuencias de una cierta cantidad de 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 .
contar 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 aleatoriamente círculos unitarios en un cuadrado de 100 × 100. Un círculo se estaciona exitosamente si no se superpone a uno existente estacionado exitosamente. Después de 12.000 intentos, el número de círculos aparcados con éxito debería seguir una determinada distribución normal .
Prueba de distancia mínima
Coloque aleatoriamente 8000 puntos en un cuadrado de 10000 × 10000 y luego encuentre la distancia mínima entre los pares. El cuadrado de esta distancia debe estar distribuido exponencialmente con una media determinada.
Prueba de esferas aleatorias
Elija aleatoriamente 4000 puntos en un cubo de arista 1000. Centre una esfera en cada punto, cuyo radio sea la distancia mínima a otro punto. El volumen de la esfera más pequeña debe distribuirse exponencialmente con una media determinada.
La prueba del apretón
Multiplica 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 distribución determinada.
Prueba de sumas superpuestas
Genere una secuencia larga de flotadores aleatorios en ( 0,1 ). Añade secuencias de 100 flotadores consecutivos. Las sumas deben distribuirse normalmente con media y varianza características.
Prueba de ejecución
Genere una secuencia larga de flotadores aleatorios en ( 0,1 ). Cuente las carreras ascendentes y descendentes. Los recuentos deben seguir una determinada distribución.
la prueba de dados
Juega 200.000 partidas de dados , contando las victorias y el número de tiros por partida. Cada conteo debe seguir una distribución determinada.

Descripciones de pruebas

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 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 considera 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 del 1 al 24 (contando desde la izquierda) de números enteros en el archivo especificado. Luego el expediente se cierra y se vuelve a abrir. A continuación, los bits 2 a 25 se utilizan para indicar los cumpleaños, 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 un KSTEST.
La prueba de las 5 permutaciones superpuestas
Esta es la prueba OPERM5. Observa una secuencia de un millón de enteros aleatorios de 32 bits. Cada conjunto de cinco números enteros consecutivos puede estar en uno de 120 estados, ¡para el 5! Posibles ordenamientos de cinco números. Por lo tanto, cada uno de los números 5, 6, 7, ... proporciona un estado. Como se observan miles de transiciones de estados, se hacen 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 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 especificada (asintóticamente) con la matriz de covarianza de 120 × 120 especificada (con rango 99). ). Esta versión utiliza 1000000 enteros, dos veces. Esta prueba puede tener errores no resueltos que resulten en valores p consistentemente bajos. [4]
La 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 del 0 al 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 de este tipo 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 entero aleatorio de 32 bits. El rango está determinado. Ese rango puede ser de 0 a 32, los rangos inferiores 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 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 del 0 al 6, pero los rangos 0, 1, 2, 3 son raros; sus recuentos se combinan con los del rango 4. Los rangos se encuentran para 100.000 matrices aleatorias y se realiza una prueba de chi cuadrado en 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. Llámelos 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. Así, 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 x 21 palabras de 20 letras superpuestas. Hay 2 20 posibles palabras de 20 letras. Para una cadena verdaderamente aleatoria de 2 21 + 19 bits, el número de palabras faltantes j debería estar (muy cerca) de una distribución normal con media 141,909 y sigma 428. Por lo tanto ( j −141909) / 428 debería 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 ADN
OPSO significa 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 (superpuestas) palabras de 2 letras (a partir 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 la secuencia completa. Ese recuento debería estar muy cerca de la distribución normal con media 141909, sigma 290. Por lo tanto (missingwrds-141909)/290 debería 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 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, cuyos elementos se suponen enteros aleatorios de 32 bits. El número medio de palabras que faltan 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 extensa. 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 prueba. Considera palabras de 10 letras, de modo que al igual que 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 mediante simulación. (Sigma para OPSO, 290, es el valor verdadero (hasta tres lugares), no determinado por simulación.
La prueba de contar 1 en un flujo de bytes
Considere el archivo bajo prueba como una secuencia de bytes (cuatro por entero de 32 bits). Cada byte puede contener desde ninguno hasta ocho unos, con probabilidades de 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Ahora deje que el flujo de bytes proporcione una cadena de palabras de 5 letras superpuestas, cada una " letra" tomando los valores A, B, C, D, E. Las letras están determinadas por el número de unos en un byte 0, 1 o 2 producen A, 3 produce B, 4 produce C, 5 produce D y 6, 7 u 8 produce E. Por lo tanto, tenemos un mono frente a 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, a partir de una cadena de 256 000 palabras de 5 letras (superpuestas), se cuentan las frecuencias de cada palabra. La forma cuadrática en el inverso débil de la matriz de covarianza de los recuentos de celdas proporciona una prueba de chi cuadrado Q5-Q4, la diferencia de las simples sumas de Pearson de (OBS-EXP) 2 / EXP en recuentos para recuentos de celdas de 5 y 4 letras. .
La prueba de contar los 1 para bytes específicos
Considere el archivo bajo prueba como una secuencia de enteros de 32 bits. De cada número 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 unos, con probabilidades de 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Ahora deje que los bytes especificados de números enteros sucesivos proporcionen una cadena de palabras de 5 letras (superpuestas), cada "letra" tomando 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 frente a 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, a partir de una cadena de 256 000 palabras de 5 letras (superpuestas), se cuentan las frecuencias de cada palabra. La forma cuadrática en el inverso débil de la matriz de covarianza de los recuentos de celdas proporciona una prueba de chi cuadrado Q5 – Q4, la diferencia de las simples sumas de Pearson de (OBS − EXP) 2 / EXP en recuentos para recuentos de celdas de 5 y 4 letras. .
La prueba del estacionamiento
En un cuadrado de lado 100, "estaciona" aleatoriamente un automóvil, un círculo de radio 1. Luego intenta estacionar un segundo, un tercero, y así sucesivamente, estacionando cada vez "de oído". Es decir, si un intento de estacionar un automóvil provoca un choque con uno ya estacionado, vuelva a intentarlo en una nueva ubicación aleatoria. (Para evitar problemas en el camino, considere estacionar helicópteros en lugar de automóviles). Cada intento conduce a un accidente o a un éxito, este último seguido de un incremento en la lista de automóviles ya estacionados. Si trazamos n : el número de intentos, versus k el número de estacionamientos exitosos, obtenemos una curva que debería ser similar a las proporcionadas por un generador de números aleatorios perfectos. La teoría del comportamiento de tal curva aleatoria parece fuera de alcance, y como 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 exitosamente 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 entrada a un KSTEST basado 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 uniformes verdaderamente independientes, entonces d 2 , el cuadrado de la distancia mínima debería estar (muy cerca de) distribuido exponencialmente con una media de 0,995. Por lo tanto, 1 − exp(− d 2 / 0,995) debe ser uniforme en [0,1) y un KSTEST sobre los 100 valores resultantes sirve como prueba de uniformidad para puntos aleatorios en el cuadrado. Se imprimen los 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 arista 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 elevado al cubo conduce a una variable uniforme mediante 1 − exp(− r 3 / 30) , luego se realiza un KSTEST en los 20 valores p .
La prueba del apretón
Los números enteros aleatorios se hacen flotar 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, usando la reducción k = techo ( k × U ), con U proporcionada por enteros flotantes del archivo que se está probando. Dichos j s se encuentran 100000 veces, luego se utilizan los recuentos del número de veces que j fue ≤ 6, 7, ..., 47, ≥ 48 para proporcionar una prueba de chi-cuadrado para las frecuencias celulares.
La prueba de sumas superpuestas
Los números enteros se hacen flotar para obtener una secuencia U (1), U (2), ... de variables uniformes [0,1). Luego se forman sumas superpuestas, S (1) = U (1) + ... + U (100), S (2) = U (2) + ... + U (101), .... Los S s son prácticamente normales con una determinada 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 asigna otro KSTEST.
la prueba de carreras
Cuenta las ejecuciones ascendentes y descendentes en una secuencia de variables uniformes [0,1), obtenidas haciendo flotar los enteros de 32 bits en el archivo especificado. Este ejemplo muestra cómo se cuentan los tramos: 0,123, 0,357, 0,789, 0,425, 0,224, 0,416, 0,95 contiene un tramo ascendente de longitud 3, un tramo descendente de longitud 2 y un tramo 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 longitud 10000. Esto se hace diez veces. Luego repitió.
la prueba de dados
Juega 200.000 juegos de dados, calcula el número de victorias y el número de tiros necesarios para finalizar cada juego. El número de victorias debe ser (muy cercano a) normal con una media de 200000 p y 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 los recuentos para todos > 21 se agrupan con 21. Se realiza una prueba de chi-cuadrado en el recuento de celdas del número de lanzamientos. Cada entero de 32 bits del archivo de prueba proporciona el valor del 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 supuesta de la variable aleatoria muestral X , a menudo normal. Pero eso supone que F es sólo 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 una secuencia de bits realmente FALLA GRANDE, obtendrá ps de 0 o 1 a seis o más lugares. Dado que hay muchas pruebas, no es improbable que p < 0,025 o p > 0,975 signifique que el RNG "no pasó la prueba en el nivel 0,05". Esperamos que ocurran varios eventos de este tipo entre los cientos de eventos que produce DIEHARD, incluso condicionados a que el generador de números aleatorios sea perfecto.

Ver también

Referencias

  1. ^ "El CDROM de números aleatorios de Marsaglia que incluye la batería incondicional de pruebas de aleatoriedad". Universidad Estatal de Florida . 1995. Archivado desde el original el 25 de enero de 2016.
  2. ^ Brown, Robert G. "más acérrimo" . Consultado el 25 de septiembre de 2023 .
  3. ^ Renyi, 1953, p194
  4. ^ "Página de herramientas generales de Robert G. Brown". Archivado desde el original el 3 de julio de 2017.

Otras lecturas

enlaces externos