¿Cómo debo probar la aleatoriedad?

No creo que las pruebas unitarias sean la herramienta correcta para probar la aleatoriedad. Una prueba de unidad debe llamar a un método y probar el valor devuelto (o el estado del objeto) contra un valor esperado. El problema con la aleatoriedad de las pruebas es que no hay un valor esperado para la mayoría de las cosas que le gustaría probar. Puedes probar con una semilla dada, pero eso solo prueba la repetibilidad . No le proporciona ninguna manera de medir cuán aleatoria es la distribución, o incluso si es aleatoria en absoluto.

Afortunadamente, hay muchas pruebas estadísticas que puedes ejecutar, como la Batería de pruebas imprevista . Véase también:

1. ¿Cómo realizar la prueba unitaria de un generador de números pseudoaleatorios?

   • Steve Jessop recomienda que encuentre una implementación probada del mismo algoritmo RNG que está utilizando y compare su resultado con las semillas seleccionadas. en contra de su propia implementación.
   • Greg Hewgill recomienda el ENT conjunto de pruebas estadísticas.
   • John D. Cook refiere a los lectores a su artículo de CodeProject Generación de números aleatorios simples , que incluye una implementación de la prueba de Kolmogorov-Smirnov mencionada en el volumen 2 de Donald Knuth, Algoritmos seminuméricos.
   • Varias personas recomiendan probar que la distribución de los números generados es uniforme, la prueba de Chi cuadrado y que la media y la desviación estándar estén dentro del rango esperado. (Tenga en cuenta que probar la distribución por sí solo no es suficiente. [1,2,3,4,5,6,7,8,8] es una distribución uniforme, pero ciertamente no es aleatoria).

2. Pruebas de unidad con funciones que devuelven resultados aleatorios

   • Brian Genisio señala que burlarse de su RNG es una opción para hacer que sus pruebas sean repetibles, y proporciona un código de muestra de C #.
   • Nuevamente, varias personas más señalan el uso de valores de semilla fijos para la repetibilidad y pruebas simples para la distribución uniforme, Chi cuadrado, etc.

3. Randomness de pruebas de unidad es un artículo de wiki que habla sobre muchos de los desafíos que ya se tocaron al intentar probar lo que Es, por su naturaleza, no repetible. Una parte interesante que obtuve de esto fue la siguiente:

     

   He visto Winzip utilizado como una herramienta para medir la aleatoriedad de un archivo de valores (obviamente, cuanto más pequeño puede comprimir el archivo, menos aleatorio es).

1. Prueba unitaria tu algoritmo

Para la primera pregunta, construiría una clase falsa en la que alimentarías una secuencia de números aleatorios para los que conoces el resultado de tu algoritmo. De esa manera, te aseguras de que el algoritmo que construyas en la parte superior de tu función aleatoria funcione. Así que algo a lo largo de las líneas de:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Mira si tu función aleatoria tiene sentido

A la prueba unitaria, debe agregar una prueba que se ejecute varias veces y afirme que los resultados

• están dentro de los límites que estableciste (por lo tanto, una tirada de dados está entre 1 y 6) y
• muestre una distribución sensible (haga varias ejecuciones de prueba y vea si la distribución está dentro del x% de lo que esperaba, por ejemplo, para la tirada de dados debería ver que un 2 sube entre el 10% y el 20% (1/6 = 16.67%) del tiempo dado que lo tiraste 1000 veces).

3. Prueba de integración para el algoritmo y la función aleatoria

¿Con qué frecuencia espera que su matriz se clasifique en la clasificación original? Ordena un par de cientos de veces y afirma que solo el x% del tiempo no cambia la clasificación.

Esto ya es una prueba de integración, estás probando el algoritmo junto con la función aleatoria. Una vez que esté utilizando la función aleatoria real, ya no podrá salir con las pruebas de ejecución únicas.

Por experiencia (escribí un algoritmo genético), diría que combinando la prueba unitaria de su algoritmo, la prueba de distribución de su función aleatoria y la prueba de integración es el camino a seguir.

Un aspecto de los PRNG que parece olvidado es que todas sus propiedades son de naturaleza estadística: no se puede esperar que al mezclar una matriz se produzca una permutación diferente de la que empezaste. Básicamente, si estás usando un PRNG normal, lo único que tienes garantizado es que no usa un patrón simple (con suerte) y que tiene una distribución uniforme entre el conjunto de números que devuelve.

Una prueba adecuada para un PRNG implicará ejecutarlo al menos 100 veces y luego verificar la distribución de la salida (que es una respuesta directa a la segunda parte de la pregunta).

Una respuesta a la primera pregunta es casi la misma: ejecute la prueba aproximadamente 100 veces con {1, 2, ..., n} y cuente el número de veces que cada elemento ha estado en cada posición. Deben ser aproximadamente iguales si el método de reproducción aleatoria es bueno.

Un asunto completamente diferente es cómo probar los PRNG de grado criptográfico. Este es un asunto en el que probablemente no deba detenerse, a menos que realmente sepa lo que está haciendo. Se sabe que las personas destruyen (lea: abrir agujeros catastróficos en) buenos criptosistemas con solo algunas 'optimizaciones' o ediciones triviales .

EDITAR: He releído completamente la pregunta, la respuesta principal y la mía. Mientras que los puntos que sostengo siguen en pie, secundaría la respuesta de Bill The Lizard. Las pruebas unitarias son de naturaleza booleana: o bien fracasan o tienen éxito, y por lo tanto no son adecuadas para probar "qué tan buenas" son las propiedades de un PRNG (o un método que usa un PRNG), ya que cualquier respuesta a esta pregunta sería cuantitativa , en lugar de polar.

Hay dos partes en esto: probar la aleatorización y probar cosas que usan la aleatorización.

La aleatorización de las pruebas es relativamente sencilla. Usted verifica que el período del generador de números aleatorios sea el esperado (para algunas muestras que usan un poco de semillas aleatorias, dentro de algún umbral) y que la distribución de la salida en un tamaño de muestra grande es como espera que sea (dentro de algún umbral).

La mejor manera de realizar pruebas de cosas que utilizan la aleatorización es con un generador de números psuedo-aleatorios determinista. Dado que la salida de la aleatorización se conoce en función de la semilla (sus entradas), entonces puede realizar una prueba de unidad como normal en base a las entradas frente a las salidas esperadas. Si su RNG es no determinista, entonces se burla de él con uno que es determinista (o simplemente no aleatorio). Pruebe la aleatorización en forma aislada del código que la consume.

Deje que se ejecute un montón de veces y visualice sus datos .

Aquí hay un ejemplo de un orden aleatorio de Coding Horror , usted Puede ver que el algoritmo está bien o no:

Es fácil ver que cada elemento posible se devuelve al menos una vez (los límites son correctos) y que la distribución es correcta.

Los punteros generales que he encontrado útiles al tratar con un código que toma entradas aleatorias: Verifique los casos de borde de aleatoriedad esperada (valores máximo y mínimo, y los valores máximo + 1 y mínimo-1 si corresponde). Verifique los lugares (en, arriba y abajo) donde los números tienen puntos de inflexión (es decir, -1, 0, 1, o mayor que 1, menor que 1 y no negativo para los casos en que un valor fraccionario puede estropear la función). Compruebe algunos lugares completamente fuera de la entrada permitida. Revisa algunos casos típicos. También puede agregar una entrada aleatoria, pero para una prueba unitaria que tiene el efecto secundario indeseable de que no se está probando el mismo valor cada vez que se ejecuta la prueba (aunque puede funcionar un enfoque de semilla, pruebe los primeros 1,000 números aleatorios de semilla) S o somesuch).

Para probar la salida de una función aleatoria, es importante identificar el objetivo. En el caso de las tarjetas, ¿el objetivo es probar la uniformidad del generador aleatorio 0-1, para determinar si las 52 tarjetas aparecen en el resultado, o algún otro objetivo (quizás toda esta lista y más)?

En el ejemplo específico, debes asumir que tu generador de números aleatorios es opaco (al igual que no tiene sentido realizar una prueba unitaria del sistema operativo syscall o malloc, a menos que escribas sistemas operativos). Puede ser útil medir el generador de números aleatorios, pero su objetivo no es escribir un generador aleatorio, solo para ver que obtiene 52 tarjetas cada vez, y que cambian de orden.

Es un largo camino para decir que realmente hay dos tareas de prueba aquí: probar que el RNG está produciendo la distribución correcta, y verificar que el código de barajado de su tarjeta esté usando ese RNG para producir resultados aleatorios. Si está escribiendo el RNG, use el análisis estadístico para probar su distribución, si está escribiendo el barajador de tarjetas, asegúrese de que haya 52 tarjetas no repetidas en cada salida (es un caso mejor para la prueba por inspección que esté usando el RNG).

Puede confiar en generadores de números aleatorios seguros

Acabo de tener un pensamiento horrible: no estás escribiendo tu propio generador de números aleatorios, ¿verdad?

Suponiendo que no lo esté, entonces debería probar el código del que es responsable , no el código de otras personas (como la implementación SecureRandom para su marco).

Probando tu código

Para probar que su código responde correctamente, es normal usar un método de baja visibilidad para producir los números aleatorios de modo que una clase de prueba unitaria pueda anularlos fácilmente. Este método anulado imita efectivamente al generador de números aleatorios y le da un control completo sobre lo que se produce y cuándo. En consecuencia, puede ejercer plenamente su código, que es el objetivo de las pruebas unitarias.

Obviamente, comprobará las condiciones de los bordes y se asegurará de que la ordenación aleatoria tenga lugar exactamente como lo dicta su algoritmo dadas las entradas apropiadas.

Probando el generador seguro de números aleatorios

Si no está seguro de que el generador seguro de números aleatorios para su idioma no sea realmente aleatorio o esté lleno de errores (proporcione valores fuera de rango, etc.), debe realizar un análisis estadístico detallado de la producción durante varios cientos de millones de iteraciones. Grafique la frecuencia de ocurrencia de cada número y debería aparecer con igual probabilidad. Si los resultados se desvían de una manera u otra, debe informar sus hallazgos a los diseñadores del marco. Definitivamente estarán interesados en solucionar el problema, ya que los generadores de números aleatorios seguros son fundamentales para muchos algoritmos de cifrado.

Bueno, nunca estarás 100% seguro, por lo que lo mejor que puedes hacer es que es probable que los números sean aleatorios. Elija una probabilidad: digamos que una muestra de números o elementos aparecerá x veces si se obtiene un millón de muestras, dentro de un margen de error. Ejecutar la cosa un millón de veces, y ver si está dentro del margen. Afortunadamente, las computadoras hacen este tipo de cosas fáciles de hacer.

Para probar que una fuente de números aleatorios está generando algo que al menos tiene la apariencia de aleatoriedad, haría que la prueba generara una secuencia bastante grande de bytes, los escribiera en un archivo temporal y luego los enviara a Herramienta ent de Fourmilab. Dé a ent el conmutador -t (terso) para que genere un CSV fácil de analizar. Luego revisa los distintos números para ver si son "buenos".

Para decidir qué números son buenos, use una fuente conocida de aleatoriedad para calibrar su prueba. La prueba casi siempre debe pasar cuando se le da un buen conjunto de números aleatorios. Debido a que incluso una secuencia verdaderamente aleatoria tiene una probabilidad de generar una secuencia que parece no ser aleatoria, no se puede obtener una prueba que sea segura para pasar. Simplemente selecciona umbrales que hacen que sea improbable que una secuencia aleatoria cause una falla en la prueba. ¿No es divertido el azar?

Nota: No puede escribir una prueba que muestre que un PRNG genera una secuencia "aleatoria". Solo puede escribir una prueba que, si pasa, indica alguna probabilidad de que la secuencia generada por el PRNG sea "aleatoria". ¡Bienvenido a la alegría de la aleatoriedad!

Caso 1: Probando un shuffle:

Considere una matriz [0, 1, 2, 3, 4, 5], mezclelo, ¿qué puede salir mal? Lo habitual: a) no barajar, b) barajando 1-5 pero no 0, barajando 0-4 pero no 5, barajando, y generando siempre el mismo patrón, ...

Una prueba para atraparlos a todos:

Mezcla 100 veces, agrega los valores en cada ranura. La suma de cada ranura debe ser similar a cada otra ranura. Avg / Stddev puede ser calculado. (5 + 0) /2=2.5, 100 * 2.5 = 25. El valor esperado es de alrededor de 25, por ejemplo.

Si los valores están fuera de rango, existe una pequeña posibilidad de que tengas un falso negativo. Puedes calcular qué tan grande es esa posibilidad. Repita la prueba. Bueno, por supuesto, hay una pequeña posibilidad de que la prueba falle 2 veces seguidas. Pero no tiene una rutina que elimine automáticamente su fuente, si la prueba de unidad falla, ¿verdad? ¡Corre de nuevo!

¿Puede fallar 3 veces seguidas? Tal vez deberías probar suerte en la lotería.

Caso 2: tira un dado

La pregunta de tirar dados es la misma pregunta. Lanza los dados 6000 veces.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;