Secuencia algorítmicamente aleatoria

Intuitivamente, una secuencia algorítmicamente aleatoria (o secuencia aleatoria) es una secuencia infinita de dígitos binarios que aparece aleatoria a cualquier algoritmo. La definición no puede aplicarse igualmente bien a las secuencias en cualquier conjunto finito de caracteres, pero ingenuamente aplica en la práctica. Las secuencias aleatorias son los objetos principales de estudio en la teoría algorítmica de la información.

Como los diferentes tipos de algoritmos se consideran a veces, que van desde algoritmos con límites específicos en el tiempo de recorrido a los algoritmos que pueden hacer preguntas de un oráculo, existen distintas nociones de aleatoriedad. El más común de ellos es conocido como aleatoriedad Martin-Löf (o 1-azar), pero las formas más fuertes y más débiles de la aleatoriedad también existen. El término "azar" se utiliza para referirse a una secuencia sin aclaración se toma generalmente para significar "Martin-Löf azar" (que se define más adelante).

Debido a secuencias infinitas de dígitos binarios pueden ser identificados con números reales en el intervalo de unidad, secuencias aleatorias binarias son a menudo llamados números reales aleatorios. Adicionalmente, las secuencias infinitas binarios corresponden a funciones características de conjuntos de números naturales; por lo que dichas secuencias puede ser visto como un conjunto de números naturales.

La clase de aleatoria de secuencias de Martin-Löf (binario) se denota por RAND o MLR.

Historia

Véase también: Tesis de Church-Turing

La primera definición adecuada de una secuencia aleatoria fue propuesta por Per Martin-Löf en 1966. Investigadores anteriores tales como Richard von Mises había tratado de formalizar la noción de una prueba de aleatoriedad a fin de definir una secuencia aleatoria como uno que pasaron todas las pruebas de aleatoriedad, sin embargo, la noción precisa de una prueba de aleatoriedad se dejó vago. Idea clave Martin-Löf era utilizar la teoría de la computación para definir formalmente la noción de una prueba de aleatoriedad. Esto contrasta con la idea de aleatoriedad en probabilidad; que en teoría, no hay ningún elemento particular de un espacio de la muestra puede ser dicho para ser al azar.

La aleatoriedad Martin-Löf desde entonces se ha demostrado que admitir muchas caracterizaciones equivalentes - en términos de compresión, tests de aleatoriedad y juegos de azar - que se parecen poco hacia afuera a la definición original, pero cada uno de los cuales satisfacer nuestra noción intuitiva de las propiedades que las secuencias aleatorias deben tiene: secuencias aleatorias debe ser incompresible, deben pasar las pruebas estadísticas de aleatoriedad, y debe ser difícil ganar dinero apostando a ellos. La existencia de estos múltiples definiciones de Martin-Löf aleatoriedad y la estabilidad de estas definiciones bajo diferentes modelos de computación, dan evidencia de que Martin-Löf aleatoriedad es una propiedad fundamental de las matemáticas y no un accidente de la modelo en particular Martin-Löf de. La tesis de que la definición de Martin-Löf aleatoriedad "correctamente" captura la noción intuitiva de aleatoriedad que se ha denominado la Tesis de Martin-Löf-Chaitin, sino que es algo similar a la tesis de Church-Turing.[1]​

Tres definiciones equivalentes

Véanse también: Complejidad de Kolmogorov y Martingala.

La definición original de Martin-Löf de una secuencia aleatoria fue en términos de las cubiertas nulas constructivas; él define que una secuencia será aleatoria si no está contenido en ningún dicha cobertura. Leonid Levin y Claus-Peter Schnorr demostraron una caracterización en términos de la complejidad de Kolmogorov: una secuencia es aleatoria si hay una cota uniforme sobre la compresibilidad de sus segmentos iniciales. Schnorr dio una definición equivalente tercero en términos de martingalas (un tipo de estrategia de apuestas). El libro de Li y Vitanyi de "Introducción a la complejidad de Kolmogorov y sus aplicaciones" es la introducción estándar a estas ideas.

• Complejidad de Kolmogorov (Schnorr 1973, Levin 1973): se puede considerar como un límite inferior sobre la compresibilidad algorítmica de una secuencia finita (de caracteres o dígitos binarios). Se asigna a cada secuencia w un número natural K(w) que, intuitivamente, mide la longitud mínima de un programa informático (escrito en algún lenguaje de programación fija) que no tiene entrada y salida W cuando se ejecuta. Dado un número natural c y una secuencia w, decimos que W es C- incompresible si

${\displaystyle K(w)\geq |w|-c}$

Una secuencia infinita S es una aleatoriedad Martin-Löf si y sólo si existe una constante c tal que todos los prefijos finito S son c- incompresibles.

• Cubiertas nulas constructivas (Martin-Löf 1966): Esta es la definición original de Martin-Löf. Para una cadena finita binaria w dejamos Cw denote que el cilindro es generado por w. Este es el conjunto de todas las secuencias infinitas que comienzan con w, que es un conjunto de base abierta en Cantor espacio. La medida μ producto (Cw) del cilindro generado por w se define como 2^-| W |. Cada subconjunto abierto de Cantor espacio es la unión de una secuencia numerable de abiertos disjuntos conjuntos básicos, y la medida de un conjunto abierto es la suma de las medidas de cualquier secuencia de este tipo. Un conjunto abierto efectiva es un conjunto abierto que es la unión de la secuencia de conjuntos abiertos básicos determinados por una secuencia recursivamente numerable de cadenas binarias. Una cubierta constructivo nulo o conjunto eficaz medida 0 es una sucesión recursivamente enumerable ${\displaystyle U_{i}}$ de eficaces conjuntos abiertos tales que ${\displaystyle U_{i+1}\subseteq U_{i}}$ y ${\displaystyle \mu (U_{i})\leq 2^{-i}}$ para cada número natural i. Cada cobertura nula efectiva determina un ${\displaystyle G_{\delta }}$ conjunto de medida 0, es decir, la intersección de los conjuntos ${\displaystyle U_{i}}$.

Una secuencia se define para ser aleatoria Martin-Löf si no está contenido en ningún ${\displaystyle G_{\delta }}$ establecer determinados por una cobertura nula constructiva.

• Martingala constructivas (Schnorr 1971): Una martingala es una función ${\displaystyle d:\{0,1\}^{*}\to [0,\infty )}$ de tal manera que, para todas las cadenas finitas W, , ${\displaystyle d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2}$, donde ${\displaystyle a^{\smallfrown }b}$ es la concatenación de las cadenas a y b.

Esto se llama la "condición de equidad"; una martingala es visto como una estrategia de apuestas, y requiere la condición anterior que desempeña mejor contra probabilidades justas. Una martingala d, se dice que sucede en una secuencia S si ${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$ donde ${\displaystyle S\upharpoonright n}$ es la primera n bits de S. Una martingala d es "constructiva" (o también conocido como "débilmente computable", "inferior semi-computable" o, "subcomputable") si existe una función computable ${\displaystyle {\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }}$ de modo que, para todas las cadenas binarias finitas W

1. ${\displaystyle {\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),}$ para todos los enteros positivos t,
2. ${\displaystyle \lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).}$

Tengáse en cuenta que la definición de martingala utilizada aquí es ligeramente diferente de la utilizada en la teoría de la probabilidad.[2]​ Esta definición de martingala tiene una condición de equidad similares, lo que también indica que el valor esperado después de algún observación es el mismo que el valor antes de la observación, dado el historial previo de observaciones. La diferencia es que en la teoría de probabilidades, la historia previa de observaciones sólo se refiere a la historia de capital, mientras que aquí la historia se refiere a la secuencia exacta de 0 y 1 en la cadena.)

Interpretaciones de las definiciones

La caracterización de la complejidad de Kolmogorov transmite la intuición de que una secuencia aleatoria es incompresible: sin prefijo puede ser producido por un programa mucho más corto que el prefijo.

La caracterización de cobertura nula transmite la intuición de que un número real aleatorio no debe tener ninguna propiedad que es "poco frecuente". Cada conjunto 0 medida se puede considerar como una propiedad común. No es posible para una secuencia que se encuentran en ninguna medida 0 conjuntos, porque cada conjunto de un punto tiene una medida de 0. La idea de Martin-Löf era limitar la definición para medir 0 conjuntos que son efectivamente descriptibles, la definición de una cobertura nula efectiva determina una colección numerable de medida efectivamente descriptible 0 conjuntos y define una secuencia para ser aleatorio si no se encuentra en ninguna de estos conjuntos particulares medida 0. Desde la unión de una colección numerable de conjuntos de medida 0 tiene medida 0, esta definición lleva inmediatamente al teorema de que no es una medida un conjunto de secuencias aleatorias. Tenga en cuenta que si identificamos el espacio de Cantor de secuencias binarias con el intervalo [0,1] de los números reales, la medida en espacio Cantor está de acuerdo con la medida de Lebesgue.

La caracterización martingala transmite la intuición de que no existe un procedimiento eficaz debe ser capaz de hacer dinero apostando en contra de una secuencia aleatoria. La martingala d es una estrategia de apuestas. d lee una cadena finita w de dinero y las apuestas en el siguiente bit. Apuesta alguna fracción de su dinero que el siguiente bit será 0, y luego el resto de su dinero que el siguiente bit sea 1. d duplica el dinero que se coloca en la parte que realmente ocurrió, y se pierde el resto. d(w) es la cantidad de dinero que tiene después de ver la cadena w. Dado que la apuesta después de ver la cadena w se puede calcular a partir de la d valores (w), d(w0), y d(w1), el cálculo de la cantidad de dinero que ha es equivalente a calcular la apuesta. La caracterización martingala dice que no implementable estrategia de apuestas por cualquier equipo (incluso en el sentido débil de estrategias constructivas, que no son necesariamente computable) se puede ganar dinero apostando en una secuencia aleatoria.

Véase también

• Sucesión aleatoria
• Estocástico
• Método de Montecarlo

Referencias

1. Jean-Paul Delahaye. Randomness, Unpredictability and Absence of Order Philosophy of Probability, p. 145-167, Springer 1993.
2. John M. Hitchcock y Jack H. Lutz. "Why computational complexity requires stricter martingales", Theory of Computing Systems, 2006.

Bibliografía

• Rod Downey, Denis R. Hirschfeldt, Andre Nies, Sebastiaan A. Terwijn (2006). "Calibrating Randomness". The Bulletin of Symbolic Logic 12 (3/4): 411–491. doi:10.2178/bsl/1154698741
• Gács, P. (1986). "Every sequence is reducible to a random one". Information and Control 70 (2/3): 186–192. doi:10.1016/S0019-9958(86)80004-3
• Kučera, A. (1985). "Measure, Π10-classes and complete extensions of PA". Recursion Theory Week. Lecture Notes in Mathematics 1141, Springer-Verlag. pp. 245–259.
• Kučera, A. (1989). "On the use of diagonally nonrecursive functions". Studies in Logic and the Foundations of Mathematics. 129. North-Holland. pp. 219–239.
• Levin, L. (1973). "On the notion of a random sequence". Soviet Mathematics Doklady 14: 1413–1416.
• Li, M.; Vitanyi, P. M. B. (1997). An Introduction to Kolmogorov Complexity and its Applications (Second ed.). Berlín: Springer-Verlag.
• Martin-Löf, P. (1966). "The definition of random sequences". Information and Control 9 (6): 602–619. doi:10.1016/S0019-9958(66)80018-9
• Schnorr, C. P. (1971). "A unified approach to the definition of a random sequence". Mathematical Systems Theory 5 (3): 246–258. doi:10.1007/BF01694181
• Schnorr, C. P. (1973). "Process complexity and effective random tests". Journal of Computer and System Sciences 7 (4): 376–388. doi:10.1016/S0022-0000(73)80030-3
• Ville, J. (1939). Etude critique de la notion de collectif. Paris: Gauthier-Villars.

• Datos: Q612552