Prueba de algoritmos de generación de variables aleatorias

¿Qué métodos se utilizan para probar algoritmos de generación de variables aleatorias?

El conjunto de pruebas de Duro de pelar es algo parecido a un estándar de oro para probar los generadores de números aleatorios. Incluye una serie de pruebas en las que un buen generador de números aleatorios debe producir un resultado distribuido de acuerdo con alguna distribución conocida con la que se puede comparar el resultado utilizando el generador probado.

EDITAR

Tengo que actualizar esto ya que no estaba exactamente en lo cierto: Diehard todavía podría usarse mucho, pero ya no se mantiene y ya no es lo más avanzado. NIST ha presentado un conjunto de pruebas mejoradas desde entonces.

Solo para agregar un poco a la respuesta de bocinazo, el Diehard Test Suite (desarrollado por George Marsaglia) son las pruebas estándar para PRNG.

Hay una bonita biblioteca Diehard C que le da acceso a estas pruebas. Además de las pruebas estándar de Diehard, también proporciona funciones para algunas otras pruebas PRNG que involucran (entre otras cosas) verificar el orden de bits. También hay una facilidad para probar la velocidad del RNG y escribir sus propias pruebas.

Hay una interfaz R para la biblioteca Dieharder, llamada RDieHarder :

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

Esto muestra que el generador RANDU RNG falla la prueba de distancia mínima / 2dsphere.

Para probar los números producidos por generadores de números aleatorios, las pruebas de Diehard son un enfoque práctico. Pero esas pruebas parecen algo arbitrarias y uno puede preguntarse si deberían incluirse más o si hay alguna forma de verificar realmente la aleatoriedad.

El mejor candidato para la definición de una secuencia aleatoria parece ser la aleatoriedad de Martin-Löf . La idea principal para este tipo de aleatoriedad, desarrollada maravillosamente en Knuth, sección 3.5 , es probar la uniformidad para todos los tipos de subsecuencias de la secuencia de números aleatorios. Conseguir que todo tipo de definición de subsecuencias sea correcto resultó ser realmente difícil incluso cuando uno usa nociones de computabilidad.

Las pruebas de Diehard son solo algunas de las subsecuencias posibles que uno puede considerar y su fracaso excluiría la aleatoriedad de Martin-Löf.

No puedes probar, porque es imposible; solo puede verificar si no hay autocorrelaciones o perturbaciones de distribución vergonzosas, y de hecho, Diehard es un estándar para ello. Esto es para estadísticas / física, los criptógrafos también verificarán principalmente (entre otras cosas) qué tan difícil es ajustar el generador a los datos para obtener los valores futuros.

Pequeña corrección a la publicación de Colin: el paquete CRAN RDieHarder es una interfaz para DieHarder , la reescritura / extensión / revisión Diehard realizada por Robert G. Brown (quien amablemente me enumera como coautor basado en mis envoltorios RDieHarder) con la reciente contribución de David Bauer.

Entre otras cosas, DieHarder incluye la batería de pruebas NIST mencionadas en la publicación de Mark, así como algunas nuevas. Esta es una investigación en curso y lo ha sido por un tiempo. Di una charla en useR! 2007 sobre RDieHarder que puede obtener desde aquí .

Rara vez es útil concluir que algo es "aleatorio" en abstracto. Con mayor frecuencia desea probar si tiene un cierto tipo de estructura aleatoria. Por ejemplo, es posible que desee probar si algo tiene una distribución uniforme, con todos los valores en un cierto rango igualmente probable. O quizás desee probar si algo tiene una distribución normal, etc. Para probar si los datos tienen una distribución particular, puede usar una prueba de bondad de ajuste, como la prueba de chi cuadrado o la prueba de Kolmogorov-Smirnov.

Hay dos partes para probar un generador de números aleatorios. Si solo le preocupa probar un generador uniforme, entonces sí, algo como el conjunto de pruebas DIEHARD es una buena idea.

Pero a menudo necesita probar una transformación de un generador uniforme. Por ejemplo, puede usar un generador uniforme para crear valores distribuidos de manera exponencial o normal. Es posible que tenga un generador uniforme de alta calidad, digamos que tiene una implementación confiable de un algoritmo conocido como Mersenne Twister, pero debe probar si la salida transformada tiene la distribución correcta. En ese caso, debe realizar algún tipo de prueba de bondad de ajuste, como Kolmogorov-Smirnov. Pero para empezar, puede verificar que la media y la varianza de la muestra tengan los valores que espera.

La mayoría de la gente no escribe, y no debería, escribir su propio generador uniforme de números aleatorios desde cero. Es difícil escribir un buen generador y es fácil engañarse pensando que ha escrito uno bueno cuando no lo ha hecho. Por ejemplo, Donald Knuth cuenta la historia en el volumen 2 de TAOCP de un generador de números aleatorios que escribió que resultó horrible. Pero es común que las personas tengan que escribir su propio código para producir valores aleatorios a partir de una nueva distribución.

El NIST publica una lista de pruebas estadísticas con una implementación de referencia en C.

También hay TestU01 de algunas personas inteligentes, incluido el respetado investigador de PRNG Pierre L'Ecuyer. Nuevamente, hay una implementación de referencia en C.

Como señalaron otros comentaristas, estos son para probar la generación de bits pseudoaleatorios. Si transforma estos bits en una variable aleatoria diferente (por ejemplo, la transformación de Box-Muller de uniforme a normal), necesitará pruebas adicionales para confirmar la corrección del algoritmo de transformación.