Pruebas de aleatoriedad

En estadística y análisis preliminar de datos, las pruebas de aleatoriedad (o test de aleatoriedad), son pruebas estadísticas usadas para decidir si una determinada muestra o conjuntos de datos responde a un patrón o puede considerarse aleatoria. En modelización estocástica, y algunas ciencia de la computación, es deseable que algunos datos de entrada sean aleatorios y que dicha aleatoriedad pueda ser verificada por una prueba cuantitativa de aleatoriedad, para mostrar que la simulación se realizó usando datos aleatorios y por tanto representativos de una cierta distribución. En algunos casos, los datos muestran un patrón claramente no aleatorio (por ejemplo si una variable debe presentar valores aleatorios que sean enteros entre 0 y 9, la secuencia "4 3 2 1 0 4 3 2 1..." es poco probable ya que en ningún caso los valores exceden el valor 4). Si un conjunto de datos no pasa la prueba de aleatoriedad, entonces puede ser sustituida por otra serie de datos aleatorizados que pase el test de aleatoriedad.

Existen muchas medidas prácticas de aleatoriedad para una secuencia binaria. Estas medidas incluyen las pruebas estadísticas, la transformada de Hadamard y la complejidad o una mezcla de mediadas del tipo anterior. El uso de la transformada de Hadamard para medir la aleatoriedad fue propuesto por S. Kak y fue desarrollado por Phillips, Yuen, Hopkins, Beth and Dai, Mund y Marsaglia & Zaman.^[1]

Introducción

El asunto de la aleatoriedad es una cuestión importante tanto desde el punto de vista teórico y como filosófico. Muchos generadores de números aleatorios actualmente en uso general lo que se llama "secuencias aleatorias" pero de hecho son el resultado de algoritmos deterministas, por lo que técnicamente se los denomina generadores de números pseudoaleatorios. Estos generadores no siempre general secuencias que exhiben una aleatoriedad suficiente y generan patrones muy repetitivos, que no pasan muchas pruebas de aleatoriedad. El uso de generadores de números aleatorios mal concebidos puede dar lugar a experimentos no válidos, debido a esa falta de aleatoriedad.

Las pruebas de aleatoriedad nos reducen a analizar el resultado de un generador de números pseudoaleatorios, también pueden usarse para determinar si un conjunto de datos es explicable mediante un patrón reconocible. Por ejemplo, Wolfram usaba pruebas de aleatoriedad para examinar el resultado de la Regla 30 para examinar su capacidad para generar números aleatorios,^[2] aunque demostró tener un tamaño clave efectivo bastante más pequeño que su tamaño real^[3] y tener un desempeño pobre en una Prueba χ².^[4]

Pruebas de aleatoriedad particulares

Muchos de las pruebas de aleatoriedad existentes, son de complejidad lineal, proporcionan medidas espectrales de aleatoriedad. T. Beth and Z-D. Dai^[5] demostraron que la complejidad de Kolmogorov y la complejidad lineal son muy similares en la práctica.

Estas pruebas prácticas hacen posible comparar y verificar la aleatoriedad de una cadena de datos. Sobre una base probabilística, todas las cadenas, por ejemplo de longitud 64, tienen la misma aleatoriedad sin embargo cuando se consideran las dos cadenas siguientes:

cadena 1: 0101010101010101010101010101010101010101010101010101010101010101

cadena 2: 1100100001100001110111101110110011111010010000100101011110010110

Estas tienen complejidades de Kolmogorov diferentes. La primera cadena admite una simple descripción lingüística, "32 repeticiones de '01'", que contiene 20 caracteres, y puede construirse efectivamente a partir de una secuencia base corta. La segunda no admite ninguna descripción simple que salte a simple vista, aparte de reescribir la propia secuencia, que tiene 64 caracteres, y ninguna representación en términos de secuencias más pequeñas que sea simple. Usando las pruebas de Hadamard espectrales (ver transformada de Hadamard), la primera cadena tiene una aleatoriedad menor que la segunda, lo cual concuerda con la intuición.

Véase también

Referencias

↑ Terry Ritter, "Randomness tests: a literature survey", webpage: CBR-rand.
↑ Wolfram, Stephen (mayo de 2002). A New Kind of Science. Wolfram Media. pp. 975–976. ISBN 1-57955-008-8.
↑ Willi Meier; Othmar Staffelbach (1991), «Analysis of pseudo random sequences generated by cellular automata», Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547 (Springer-Verlag.): 186. .
↑ Moshe Sipper; Marco Tomassini (1996), «Generating parallel random number generators by cellular programming», International Journal of Modern Physics C 7 (2): 181-190, doi:10.1142/S012918319600017X ..
↑ Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology -- EUROCRYPT '89. 533-543. Springer-Verlag

Enlaces externos

George Marsaglia, Wai Wan Tsang, Some Difficult-to-pass Tests of Randomness, Journal of Statistical Software, Volume 7, 2002, Issue 3.
DieHarder: A Random Number Test Suite
Online randomness test

Datos: Q13560113

[Rit-1] Terry Ritter, "Randomness tests: a literature survey", webpage: CBR-rand.

[2] Wolfram, Stephen (mayo de 2002). A New Kind of Science. Wolfram Media. pp. 975–976. ISBN 1-57955-008-8.

[3] Willi Meier; Othmar Staffelbach (1991), «Analysis of pseudo random sequences generated by cellular automata», Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547 (Springer-Verlag.): 186. .

[4] Moshe Sipper; Marco Tomassini (1996), «Generating parallel random number generators by cellular programming», International Journal of Modern Physics C 7 (2): 181-190, doi:10.1142/S012918319600017X ..

[5] Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology -- EUROCRYPT '89. 533-543. Springer-Verlag

[1]

[2]

[3]

[4]

[5]