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 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 puede verificarse, 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 obvio no aleatorio, como con las llamadas "corridas en los datos" (como esperar 0-9 aleatorios pero encontrar "4 3 2 1 0 4 3 2 1 ..." y rara vez yendo por encima de 4). Si un conjunto de datos seleccionado no supera las pruebas, se pueden cambiar los parámetros o se pueden utilizar otros datos aleatorios que superen las pruebas de aleatoriedad.
Fondo
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 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 de los "generadores de números aleatorios" en uso hoy en día son definidos por algoritmos, por lo que son en realidad pseudo-aleatorios generadores de números. Las secuencias que producen se denominan secuencias pseudoaleatorias. Estos generadores no siempre generan secuencias 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 usó 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 más pequeño que su tamaño real [2] y un rendimiento deficiente 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 los supuestos estadísticos. Aunque existen técnicas de prueba estadísticas 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.
Pruebas específicas de aleatoriedad
Ha habido un número bastante pequeño de diferentes tipos de generadores de números (pseudo) aleatorios utilizados en la práctica. Se pueden encontrar en la lista de generadores de números aleatorios y han incluido:
- Generador de congruencia lineal y lineal con realimentación registro de desplazamiento
- Generador de Fibonacci generalizado
- Generadores criptográficos
- Generador congruencial cuadrático
- Generadores de autómatas celulares
- Secuencia binaria pseudoaleatoria
Estos diferentes generadores tienen distintos grados de éxito al aprobar las suites de prueba aceptadas. Varios generadores ampliamente utilizados fallan las pruebas más o menos mal, mientras que otros generadores "mejores" y anteriores (en el sentido de que pasaron todas las baterías de pruebas actuales y ya existían) se han ignorado en gran medida.
Hay 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 estos. Una colección de pruebas bien conocida y ampliamente utilizada fue la Batería de Pruebas Diehard , presentada por Marsaglia; L'Ecuyer y Simard extendieron 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 pretendía mostrar que la complejidad de Kolmogorov y la complejidad lineal son prácticamente lo mismo, [7] aunque Y. Wang más tarde demostró 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 las cadenas . Por motivos probabilísticos, todas las cadenas de una longitud determinada tienen la misma aleatoriedad. Sin embargo, las diferentes cadenas tienen una complejidad de Kolmogorov diferente. Por ejemplo, considere las siguientes dos cadenas.
- Cadena 1: 010101010101010101010101010101010101010101010101010101010101010101
- Cadena 2: 1100100001100001110111101110110011111010010000100101011110010110
La 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 de base. [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 . Usando 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.
Implementaciones de software notables
- Intransigente
- PruebaU01
- utilidad ent de Fourmilab
- Conjunto de pruebas estadísticas del NIST (Publicación especial 800-22 Revisión 1a)
Ver también
Notas
- ^ Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media, Inc. págs. 975–976 . ISBN 978-1-57955-008-0.
- ^ Willi Meier; Othmar Staffelbach (1991), "Análisis de secuencias pseudoaleatorias generadas por autómatas celulares", Avances en Criptología: Proc. Taller de Teoría y Aplicación de Técnicas Criptográficas, EUROCRYPT '91. Notas de clase en Ciencias de la Computación 547 : 186
- ^ Moshe Sipper; Marco Tomassini (1996), "Generación de generadores de números aleatorios paralelos mediante programación celular", International Journal of Modern Physics C , 7 (2): 181-190, CiteSeerX 10.1.1.21.870 , doi : 10.1142 / S012918319600017X.
- ^ Yongge Wang. Sobre el diseño de pruebas LIL para (pseudo) generadores aleatorios y algunos resultados experimentales, http://webpages.uncc.edu/yonwang/ , 2014
- ^ Yongge Wang; Tony Nicol (2014), "Propiedades estadísticas de secuencias pseudoaleatorias y experimentos con PHP y Debian OpenSSL", Esorics 2014, Lncs 8712 : 454–471
- ^ Terry Ritter, "Pruebas de aleatoriedad: una encuesta de literatura", página web: CBR-rand .
- ^ Beth, T. y ZD. Dai. 1989. Sobre la complejidad de las secuencias pseudoaleatorias, o si puede describir una secuencia, no puede ser aleatoria. Avances en Criptología - EUROCRYPT '89. 533-543. Springer-Verlag
- ^ Yongge Wang 1999. Complejidad lineal versus pseudoaleatoriedad: sobre el resultado de Beth y Dai. En: Proc. Asiacrypt 99, páginas 288-298. LNCS 1716, Springer Verlag
enlaces externos
- Pruebas de aleatoriedad incluidas en el kit de herramientas criptográficas de NIST
- George Marsaglia , Wai Wan Tsang (2002), " Algunas pruebas de aleatoriedad difíciles de aprobar ", Journal of Statistical Software , Volumen 7, Número 3
- DieHarder: A Random Number Test Suite por Robert G. Brown, Universidad de Duke
- Análisis generador de números aleatorios en línea de CAcert.org