¿La mejor manera de determinar si una lista de bytes es aleatoria?

¿Existe algún algoritmo que pueda devolver algún valor que indique un nivel de aleatoriedad? Creo que se llama Data Entropy .

Recientemente leí este artículo: http://faculty.rhodes.edu/wetzel/random/mainbody.html

¿Su enfoque de analizar lanzamientos de monedas se aplicaría a bytes? ¿Debería desplegarme al nivel de bits donde es verdadero / falso nuevamente o hay una manera de determinar en función del valor de byte completo?

¿Son sus mejores análisis que este artículo?

En TCS, otro enfoque para este problema ha sido a través de la prueba de propiedad de las distribuciones , donde uno debe distinguir si una distribución es (verdaderamente) distribución uniforme o "ni siquiera está cerca" de ser uniforme (de manera formal). Aquí se obtienen límites precisos sobre la cantidad de muestras necesarias para decidir sobre la pregunta.

Consulte, por ejemplo, la Sección 6 del siguiente tutorial: http://people.csail.mit.edu/ronitt/papers/icm.ps

En particular, se puede decidir si una distribución en es verdaderamente uniforme o es ε -lejos (en distancia total variación ) de ser uniforme con O ( $[n]$$\epsilon$consultas / muestras de dicha distribución. (Esto también es estricto en el sentido de queΩ($O(\sqrt{n}/\epsilon^4)$se necesitan muestras)$\Omega(\sqrt{n})$

No existe un único algoritmo correcto para medir la aleatoriedad. Varias pruebas estadísticas son un enfoque posible, como los otros ya han dicho. Otra posibilidad es comprimir la secuencia de bytes y ver qué sucede. Si obtiene aproximadamente 8 bits / byte (o más), la secuencia es aleatoria con respecto al modelo de datos subyacente al compresor.

De los métodos de compresión estándar, PPM utiliza un modelo estadístico explícito para predecir el siguiente carácter basado en el contexto anterior. Su principal debilidad es que no puede utilizar repetitividad a gran escala, como repeticiones idénticas de una secuencia aleatoria larga.

Los métodos de compresión basados ​​en el análisis LZ77 o la Transformación Burrows-Wheeler (BWT) funcionan bien, cuando hay muchas subcadenas repetidas en la secuencia. Sin embargo, muchas implementaciones prácticas tienen un tamaño de bloque / ventana limitado para ahorrar memoria, por lo que tampoco pueden utilizar la repetitividad a gran escala.

En lugar de comprimir la secuencia, también podría calcular alguna medida relacionada con el modelo de datos del compresor: entropía empírica de alto orden para PPM, el número de corridas de letras iguales en el BWT o el número de frases en el análisis LZ77. En los primeros dos casos, 8 bits de entropía por byte o n (1 - 1/256) se ejecutan para una secuencia de longitud n significa datos totalmente aleatorios.

De random.org:

Curiosamente, es teóricamente imposible demostrar que un generador de números aleatorios es realmente aleatorio. Más bien, analiza una cantidad cada vez mayor de números producidos por un generador dado, y dependiendo de los resultados, su confianza en el generador aumenta (o disminuye, según sea el caso)

Más información se puede encontrar aquí

http://www.phy.duke.edu/~rgb/General/dieharder.php

La complejidad de Kolmogorov es una forma de medir la aleatoriedad de las cadenas y es algorítmicamente incuestionable. Usando esta noción, es imposible medir la aleatoriedad de todas las cadenas. La existencia de dicho algoritmo podría usarse para resolver el problema de detención.

Como se mencionó en otras respuestas, la versión de decisión de este problema (como el problema de detención y una serie de otros problemas como el problema de mosaico) es indecidible. Sin embargo, creo que está preguntando sobre formas prácticas de medir la aleatoriedad de una colección de bits.

La práctica estándar aquí es ejecutar los datos a través de una serie de pruebas de aleatoriedad, como la prueba de Chi-cuadrado.

$i_p$$(i_1/n,\ldots,i_k/n)$

En la práctica, no hay una prueba universal para la aleatoriedad de la transmisión, en su lugar hay una serie de pruebas, y si su transmisión prueba k de las mejores pruebas y las supera todas, podemos estar razonablemente seguros de que es aleatoria ... hasta que alguien invente k + 1 ' st prueba que lo rompe.

Esto es lo que Knuth dice al respecto en "Art of Computer Algorithms, Vol 2"

"Si una secuencia se comporta aleatoriamente con respecto a las pruebas T1, T2, ..., Tn, no podemos estar seguros en general de que no será una falla miserable cuando se somete a una prueba adicional T (n + 1). Sin embargo cada prueba nos da más y más confianza en la aleatoriedad de la secuencia. En la práctica, aplicamos alrededor de media docena de diferentes tipos de pruebas estadísticas a una secuencia, y si las pasa satisfactoriamente consideramos que es aleatoria, entonces se presume inocente hasta que se demuestre lo contrario ".

Recomiendo leer la sección 3.1 "El arte de los algoritmos informáticos" de Knuth para una introducción general a la pseudoaleatoriedad y 3.3 sobre pruebas estadísticas para transmisiones.

Hice un conjunto de pruebas bastante débil que, sin embargo, fue muy útil para mí e indicativo de la naturaleza de las pruebas de aleatoriedad en general:

1. generar una estadística para "datos aleatorios buenos conocidos" (matemática o empíricamente)
2. generar la misma estadística para sus datos de muestra (es de esperar que tenga al menos 30 muestras más o menos)
3. obtener un valor p para la diferencia (hipótesis: estas son de diferentes distribuciones)
4. repetir para N estadísticas
5. bonferonni corrige los resultados (divide por N)

La fuente está aquí: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py