Hispanopedia Wiki
Articulo de referencia

Prueba de aleatoriedad

En la evaluación de datos, una prueba de aleatoriedad (o prueba de aleatoriedad ) se utiliza para analizar la distribución de un conjunto de datos y determinar si puede describi...

Hispanopedia WikiContenido en espanolLectura gratuita

En la evaluación de datos, una prueba de aleatoriedad (o prueba de aleatoriedad ) se utiliza para analizar la distribución de un conjunto de datos y determinar si puede describirse como aleatoria (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 simulaciones. En algunos casos, los datos revelan un patrón no aleatorio evidente, como ocurre con las llamadas "rachas en los datos" (por ejemplo, esperar valores aleatorios entre 0 y 9, pero encontrar "4 3 2 1 0 4 3 2 1..." y rara vez superar el 4). Si un conjunto de datos seleccionado no supera las pruebas, se pueden modificar los parámetros o utilizar otros datos aleatorios que sí las superen.

Fondo

La cuestión de la aleatoriedad es una importante cuestión filosófica y teórica. Las pruebas de aleatoriedad pueden utilizarse 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, el análisis estadístico se ha centrado mucho más en encontrar regularidades en los datos que en probar la aleatoriedad. Muchos "generadores de números aleatorios" que se utilizan hoy en día se definen mediante algoritmos, por lo que en realidad son generadores de números pseudoaleatorios . 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 estrepitosamente en muchas pruebas de aleatoriedad, 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 tenía un tamaño de clave efectivo mucho menor que su tamaño real [ 2 ] y que se desempeñaba mal 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 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 en la ley del logaritmo iterado. Utilizando 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 para la aleatoriedad

En la práctica se han utilizado relativamente pocos tipos diferentes de generadores de números (pseudo)aleatorios. Estos se pueden encontrar en la lista de generadores de números aleatorios e incluyen:

Estos distintos generadores tienen diversos grados de éxito al superar las pruebas estandarizadas. Varios generadores de uso generalizado no superan las pruebas con la suficiente contundencia, mientras que otros generadores "mejores" y anteriores (en el sentido de que superaron todas las series de pruebas actuales y ya existían) han sido prácticamente ignorados.

Existen numerosas medidas prácticas de aleatoriedad para una secuencia binaria . Estas incluyen medidas basadas en pruebas estadísticas , transformaciones y complejidad , o una combinación de ambas. Una colección de pruebas muy conocida y ampliamente utilizada fue la Diehard Battery of Tests , introducida por Marsaglia; esta fue ampliada al conjunto de pruebas TestU01 por L'Ecuyer y Simard. El uso de la transformada de Hadamard para medir la aleatoriedad fue propuesto por S. Kak y desarrollado posteriormente 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 afirmaron 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 ] Sin embargo, Wang también demostró que, para 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 un punto de vista probabilístico, todas las cadenas de una longitud dada tienen la misma aleatoriedad. Sin embargo, distintas cadenas tienen una complejidad de Kolmogorov diferente. Por ejemplo, consideremos las dos cadenas siguientes.

Cadena 1:0101010101010101010101010101010101010101010101010101010101010101
Cadena 2:1100100001100001110111101110110011111010010000100101011110010110

La cadena 1 admite una breve descripción lingüística: "32 repeticiones de '01'". Esta descripción tiene 22 caracteres y puede construirse eficientemente a partir de secuencias base. La cadena 2 no tiene una descripción simple obvia, aparte de escribir la cadena misma, que tiene 64 caracteres, y no tiene una representación de función base comparablemente eficiente . Mediante pruebas espectrales lineales de Hadamard (véase la transformada de Hadamard ), se encontrará que la primera de estas secuencias es mucho menos aleatoria que la segunda, lo cual concuerda con la intuición.

Implementaciones de software destacadas

Véase también

Notas

  1. ↑ Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media, Inc. págs. 975–976 . ISBN  978-1-57955-008-0.
  2. ↑ Willi Meier; Othmar Staffelbach (1991). «Análisis de secuencias pseudoaleatorias generadas por autómatas celulares». Avances en criptología — EUROCRYPT '91 . Notas de clase en informática. Vol. 547. págs. 186–199 . doi : 10.1007/3-540-46416-6_17 . ISBN   978-3-540-54620-7.
  3. ↑ 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. Bibcode : 1996IJMPC...7..181S . CiteSeerX 10.1.1.21.870 . doi : 10.1142/S012918319600017X . .
  4. ↑ Yongge Wang. Sobre el diseño de pruebas LIL para generadores (pseudo)aleatorios y algunos resultados experimentales, http://webpages.uncc.edu/yonwang/ , 2014
  5. ↑ Wang, Yongge; Nicol, Tony (2014). "Propiedades estadísticas de secuencias pseudoaleatorias y experimentos con PHP y Debian OpenSSL". Seguridad informática - ESORICS 2014. Notas de clase en ciencias de la computación. Vol. 8712. págs. 454–471 . doi : 10.1007/978-3-319-11203-9_26 . ISBN   978-3-319-11202-2.
  6. ↑ Terry Ritter, "Pruebas de aleatoriedad: una revisión de la literatura", página web: CBR-rand .
  7. ↑ Beth, Thomas; Dai, Zong-Duo (1990). "Sobre la complejidad de las secuencias pseudoaleatorias - o: Si puedes describir una secuencia, no puede ser aleatoria". Avances en criptología — EUROCRYPT '89 . Notas de clase en ciencias de la computación. Vol. 434. págs. 533–543 . doi : 10.1007/3-540-46885-4_51 . ISBN   978-3-540-53433-4.
  8. ↑ Wang, Yongge (1999). "Complejidad lineal frente a pseudoaleatoriedad: Sobre el resultado de Beth y Dai". Avances en criptología - ASIACRYPT'99 . Notas de clase en ciencias de la computación. Vol. 1716. págs. 288–298 . doi : 10.1007/978-3-540-48000-6_23 . ISBN   978-3-540-66666-0.
  9. ↑ ENT: Un programa de prueba de secuencias de números pseudoaleatorios , Fourmilab, 2008.
  10. ↑ Un conjunto de pruebas estadísticas para generadores de números aleatorios y pseudoaleatorios para aplicaciones criptográficas , Publicación especial 800-22 Revisión 1a, Instituto Nacional de Estándares y Tecnología , 2010.
  11. ↑ Implementación del conjunto de pruebas estadísticas del NIST
  • Pruebas de aleatoriedad incluidas en el kit de herramientas criptográficas del NIST.
  • George Marsaglia , Wai Wan Tsang (2002), " Algunas pruebas de aleatoriedad difíciles de superar ", Journal of Statistical Software , Volumen  7, Número  3
  • DieHarder: Un conjunto de pruebas de números aleatorios por Robert G. Brown, Universidad de Duke
  • Análisis de generadores de números aleatorios en línea de CAcert.org