¿Cómo podemos comprobar la Aleatoriedad?

Question

Imaginemos un hombre que pretende poseer una máquina que puede cada vez que producen una completamente al azar serie de 0/1 dígitos (por ejemplo,$1,0,0,1,1,0,1,1,1,...$). Y cada vez que se genera uno, usted puede mantener pidiéndole la $n$-ésimo dígito y él te dirá lo que corresponda.

Entonces, ¿cómo verificar si su serie es realmente completamente al azar?

Si sólo tenemos en comprobar si el $n$-ésimo dígito está distribuida de manera uniforme, entonces él puede hacer trampa usando:

$0,0,0,0,...$
$1,1,1,1,...$
$0,0,0,0,...$
$1,1,1,1,...$
$...$

Si queremos comprobar si la secuencia se distribuye de manera uniforme, entonces él puede hacer trampa usando:

$(0,)(1,)(0,0,)(0,1,)(1,0,)(1,1,)(0,0,0,)(0,0,1,)...$
$(1,)(0,)(1,1,)(1,0,)(0,1,)(0,0,)(1,1,1,)(1,1,0,)...$
$...$

Me pueden dar otra posible la comprobación de los procesos, pero tal y como yo lo de la lista, cada uno de ellos tiene defectos que puede ser engañado con un preparado de serie regular.

¿Cómo podemos comprobar si una serie es realmente aleatorio? O es la aleatoriedad de un concepto filosófico que no puede ser fácilmente definido en Matemáticas?

Answer 1

Todas las secuencias que ha mencionado tienen una muy baja complejidad de Kolmogorov, porque fácilmente se puede describir en muy corto espacio. Una secuencia aleatoria (según la definición habitual) tiene una alta complejidad de Kolmogorov, que significa que no hay instrucciones más corta que la propia cadena que puede describir o reproducir la cadena. Por supuesto la longitud de la descripción depende del sistema formal (lenguaje) que se utiliza para describir esto, pero si la longitud de la cadena es mucho mayor que la de los axiomas de sus sistemas formales, a continuación, la prueba de Kolmogorov-la complejidad de una cadena aleatoria se vuelve independiente de su elección de sistema.

Por suerte, bajo la tesis de Church-Turing, sólo hay 1 modelo de cálculo,(a menos que la máquina utiliza aún por descubrir las leyes de la física), por lo que sólo hay 1 lenguaje de la máquina puede hablar de que tenemos que revisar.

Así que para comprobar si una cadena es al azar, sólo tenemos que la fuerza bruta de verificación de la longitud de la menor de Turing-programa de salidas de los primeros n bits correctamente. Si la longitud finalmente se convierte proporcional a n, entonces podemos estar bastante seguros de que tenemos una secuencia al azar, pero para estar 100% tenemos que revisar el conjunto (infinito) de la cadena. (Según la definición de azar).

Answer 2

Dejando de lado el aspecto teórico de la cuestión, también hay pragmática respuestas porque no son del mundo real utiliza para la alta calidad de generadores aleatorios (ya sea de hardware o de algoritmos). Para usos estadísticos, "aleatoriedad estadística" es un usado. Por ejemplo, usted puede utilizar estos "diehard pruebas" o TestU01.

Answer 3

Esto se explica muy bien en el Volumen 2 de Knuth el Arte De La Programación de computadoras. El resumen ejecutivo es que el azar es un concepto matemático que puede ser definida en matemáticas, pero no fácilmente.