Una prueba de aleatoriedad (o prueba de aleatoriedad ), en la evaluación de datos, es una prueba que se utiliza para analizar la distribución de un conjunto de datos para ver si puede describirse como aleatorio (sin patrón). En el modelado estocástico , como en algunas simulaciones por computadora , la aleatoriedad esperada de los datos de entrada potenciales se puede verificar, mediante una prueba formal de aleatoriedad, para demostrar que los datos son válidos para su uso en ejecuciones de simulación. En algunos casos, los datos revelan un patrón no aleatorio obvio, como ocurre con las llamadas "ejecuciones en los datos" (como esperar un 0-9 aleatorio pero encontrar "4 3 2 1 0 4 3 2 1..." y rara vez yendo por encima de 4). Si un conjunto seleccionado de datos no supera las pruebas, entonces se pueden cambiar los parámetros o se pueden utilizar otros datos aleatorios que pasen las pruebas de aleatoriedad.
La cuestión de la aleatoriedad es una cuestión filosófica y teórica importante. Se pueden utilizar pruebas de aleatoriedad para determinar si un conjunto de datos tiene un patrón reconocible, lo que indicaría que el proceso que lo generó es significativamente no aleatorio. En su mayor parte, el análisis estadístico, en la práctica, se ha preocupado mucho más por encontrar regularidades en los datos que por probar la aleatoriedad. Muchos "generadores de números aleatorios" que se utilizan hoy en día están definidos por algoritmos y, por lo tanto, en realidad son generadores de números pseudoaleatorios . Las secuencias que producen se denominan secuencias pseudoaleatorias. Estos generadores no siempre generan secuencias que sean suficientemente aleatorias, sino que pueden producir secuencias que contienen patrones. Por ejemplo, la infame rutina RANDU falla dramáticamente en muchas pruebas de aleatoriedad, incluida la prueba espectral .
Stephen Wolfram utilizó pruebas de aleatoriedad en el resultado de la Regla 30 para examinar su potencial para generar números aleatorios, [1] aunque se demostró que tiene un tamaño de clave efectivo mucho menor que su tamaño real [2] y que funciona mal en un chip. prueba al cuadrado . [3] El uso de un generador de números aleatorios mal concebido puede poner en duda la validez de un experimento al violar supuestos estadísticos. Aunque existen técnicas de prueba estadística de uso común, como los estándares NIST, Yongge Wang demostró que los estándares NIST no son suficientes. Además, Yongge Wang [4] diseñó técnicas de prueba basadas en estadísticas basadas en distancias y en la ley del logaritmo iterado. Utilizando esta técnica, Yongge Wang y Tony Nicol [5] detectaron la debilidad en generadores pseudoaleatorios de uso común, como la conocida versión Debian del generador pseudoaleatorio OpenSSL que se solucionó en 2008.
En la práctica se ha utilizado un número bastante pequeño de diferentes tipos de generadores de números (pseudo)aleatorios. Se pueden encontrar en la lista de generadores de números aleatorios y han incluido:
Estos diferentes generadores tienen distintos grados de éxito a la hora de pasar los conjuntos de pruebas aceptados. Varios generadores ampliamente utilizados no pasan las pruebas más o menos gravemente, mientras que otros generadores "mejores" y anteriores (en el sentido de que pasaron todas las baterías de pruebas actuales y ya existían) han sido en gran medida ignorados.
Existen muchas medidas prácticas de aleatoriedad para una secuencia binaria . Estos incluyen medidas basadas en pruebas estadísticas , transformaciones y complejidad o una combinación de ellas. Una colección de pruebas muy conocida y ampliamente utilizada fue la Diehard Battery of Tests , introducida por Marsaglia; L'Ecuyer y Simard ampliaron esto a la suite TestU01 . El uso de la transformada de Hadamard para medir la aleatoriedad fue propuesto por S. Kak y desarrollado por Phillips, Yuen, Hopkins, Beth y Dai, Mund y Marsaglia y Zaman. [6]
Varias de estas pruebas, que son de complejidad lineal, proporcionan medidas espectrales de aleatoriedad. T. Beth y ZD. Dai pretendió demostrar que la complejidad de Kolmogorov y la complejidad lineal son prácticamente las mismas, [7] aunque Y. Wang demostró más tarde que sus afirmaciones son incorrectas. [8] Sin embargo, Wang también demostró que para las secuencias aleatorias de Martin-Löf , la complejidad de Kolmogorov es esencialmente la misma que la complejidad lineal.
Estas pruebas prácticas permiten comparar la aleatoriedad de las cadenas . Desde el punto de vista probabilístico, todas las cadenas de una longitud determinada tienen la misma aleatoriedad. Sin embargo, diferentes cuerdas tienen diferente complejidad de Kolmogorov. Por ejemplo, considere las siguientes dos cadenas.
01010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110La cadena 1 admite una breve descripción lingüística: "32 repeticiones de '01'". Esta descripción tiene 22 caracteres y se puede construir de manera eficiente a partir de algunas secuencias básicas. [ se necesita aclaración ] La cadena 2 no tiene una descripción simple obvia aparte de escribir la cadena en sí, que tiene 64 caracteres, [ se necesita aclaración ] y no tiene una representación de función base comparablemente eficiente . Utilizando pruebas espectrales lineales de Hadamard (ver Transformada de Hadamard ), se encontrará que la primera de estas secuencias es mucho menos aleatoria que la segunda, lo que concuerda con la intuición.