Una prueba de aleatoriedad (o prueba de aleatoriedad ), en la evaluación de datos, es una prueba utilizada para analizar la distribución de un conjunto de datos para ver si se puede describir 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 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 superar el 4). Si un conjunto seleccionado de datos no pasa las pruebas, se pueden cambiar los parámetros o se pueden utilizar otros datos aleatorios que sí pasen las pruebas de aleatoriedad.
La cuestión de la aleatoriedad es una cuestión filosófica y teórica importante. Las pruebas de aleatoriedad se pueden utilizar 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 la práctica, en su mayor parte, el análisis estadístico se ha preocupado mucho más por encontrar regularidades en los datos que por comprobar su aleatoriedad. Muchos "generadores de números aleatorios" que se utilizan hoy en día se definen mediante algoritmos y, por lo tanto, son en realidad 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 contengan patrones. Por ejemplo, la infame rutina RANDU no supera muchas pruebas de aleatoriedad de forma espectacular, incluida la prueba espectral .
Stephen Wolfram utilizó pruebas de aleatoriedad en la salida 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 tiene un rendimiento deficiente en una prueba de chi-cuadrado . [3] El uso de un generador de números aleatorios mal concebido puede poner en duda la validez de un experimento al violar los 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 la distancia estadística y la ley del logaritmo iterado. Usando esta técnica, Yongge Wang y Tony Nicol [5] detectaron la debilidad en los generadores pseudoaleatorios de uso común, como la conocida versión Debian del generador pseudoaleatorio OpenSSL que se corrigió en 2008.
Se han utilizado en la práctica una cantidad bastante pequeña de diferentes tipos de generadores de números (pseudo)aleatorios. Se pueden encontrar en la lista de generadores de números aleatorios e incluyen:
Estos diferentes generadores tienen distintos grados de éxito a la hora de pasar las pruebas aceptadas. Varios generadores ampliamente utilizados no superan las pruebas con mayor o menor éxito, 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 ignorados en gran medida.
Existen muchas medidas prácticas de aleatoriedad para una secuencia binaria . Estas incluyen medidas basadas en pruebas estadísticas , transformadas y complejidad o una mezcla de estas. Una colección de pruebas bien conocida y ampliamente utilizada fue la Diehard Battery of Tests , introducida por Marsaglia; esta fue extendida a la suite TestU01 por L'Ecuyer y Simard. El uso de la transformada de Hadamard para medir la aleatoriedad fue propuesto por S. Kak y desarrollado aún más 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 pretendieron demostrar que la complejidad de Kolmogorov y la complejidad lineal son prácticamente iguales, [7] aunque Y. Wang demostró posteriormente que sus afirmaciones son incorrectas. [8] No obstante, 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 cadenas . Desde el punto de vista probabilístico, todas las cadenas de una longitud dada tienen la misma aleatoriedad. Sin embargo, cadenas diferentes tienen una complejidad de Kolmogorov diferente. Por ejemplo, considere las dos cadenas siguientes.
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 base. [ aclaración necesaria ] La cadena 2 no tiene una descripción simple obvia más allá de escribir la cadena misma, que tiene 64 caracteres, [ aclaración necesaria ] y no tiene una representación de función base comparablemente eficiente . Usando pruebas espectrales de Hadamard lineales (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.