Secuencia aleatoria algorítmica

Secuencia binaria

Intuitivamente, una secuencia aleatoria algorítmica (o secuencia aleatoria ) es una secuencia de dígitos binarios que parece aleatoria para cualquier algoritmo que se ejecute en una máquina de Turing universal (sin prefijo o no) . La noción se puede aplicar de forma análoga a las secuencias de cualquier alfabeto finito (por ejemplo, dígitos decimales). Las secuencias aleatorias son objetos clave de estudio en la teoría de la información algorítmica .

En la teoría de la probabilidad basada en la medida , introducida por Andrey Kolmogorov en 1933, no existe una secuencia aleatoria. Por ejemplo, considere lanzar una moneda al aire infinitas veces. Cualquier secuencia particular, ya sea o , tiene una probabilidad exactamente cero. No hay forma de afirmar que una secuencia es "más aleatoria" que otra secuencia, utilizando el lenguaje de la probabilidad basada en la medida. Sin embargo, es intuitivamente obvio que parece más aleatorio que . La teoría de la aleatoriedad algorítmica formaliza esta intuición. ${\displaystyle 0000\dots }$ ${\displaystyle 011010\dots }$ ${\displaystyle 011010\dots }$ ${\displaystyle 0000\dots }$

Como a veces se consideran diferentes tipos de algoritmos, que van desde algoritmos con límites específicos en su tiempo de ejecución hasta algoritmos que pueden hacer preguntas a una máquina oráculo , existen diferentes nociones de aleatoriedad. La más común de ellas se conoce como aleatoriedad de Martin-Löf ( aleatoriedad K o aleatoriedad 1 ), pero también existen formas más fuertes y más débiles de aleatoriedad. Cuando se utiliza el término "algorítmicamente aleatorio" para referirse a una secuencia única particular (finita o infinita) sin aclaración, generalmente se toma como "incompresible" o, en el caso de que la secuencia sea infinita y se anteponga algorítmicamente aleatorio (es decir, K-incompresible), "aleatorio de Martin-Löf–Chaitin".

Desde su creación, se ha demostrado que la aleatoriedad de Martin-Löf admite muchas caracterizaciones equivalentes (en términos de compresión , pruebas de aleatoriedad y apuestas ) que tienen poco parecido exterior con la definición original, pero que satisfacen nuestra noción intuitiva de las propiedades que deben tener las secuencias aleatorias: las secuencias aleatorias deben ser incompresibles, deben pasar pruebas estadísticas de aleatoriedad y debe ser difícil ganar dinero apostando por ellas. La existencia de estas múltiples definiciones de aleatoriedad de Martin-Löf y la estabilidad de estas definiciones bajo diferentes modelos de computación dan evidencia de que la aleatoriedad de Martin-Löf es una propiedad fundamental de las matemáticas y no un accidente del modelo particular de Martin-Löf.

Es importante distinguir entre aleatoriedad algorítmica y aleatoriedad estocástica. A diferencia de la aleatoriedad algorítmica, que se define para procesos computables (y por lo tanto deterministas), se suele decir que la aleatoriedad estocástica es una propiedad de una secuencia que se sabe a priori que es generada por (o es el resultado de) un proceso estocástico equiprobable independiente distribuido de manera idéntica .

Debido a que las secuencias infinitas de dígitos binarios se pueden identificar con números reales en el intervalo unitario, las secuencias binarias aleatorias a menudo se denominan (algorítmicamente) números reales aleatorios . Además, las secuencias binarias infinitas corresponden a funciones características de conjuntos de números naturales; por lo tanto, esas secuencias podrían verse como conjuntos de números naturales.

La clase de todas las secuencias aleatorias (binarias) de Martin-Löf se denota por RAND o MLR.

Historia

Richard von Mises

Richard von Mises formalizó la noción de prueba de aleatoriedad para definir una secuencia aleatoria como aquella que pasa todas las pruebas de aleatoriedad. Definió un "colectivo" ( kollektiv ) como una cadena binaria infinita definida de tal manera que ${\displaystyle x_{1:\infty }}$

• Existe un límite . ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{i}=p\in (0,1)}$
• Para cualquier regla "admisible", tal que seleccione una subsecuencia infinita de la cadena, todavía tenemos . Llamó a este principio " imposibilidad de un sistema de juego ". ${\displaystyle (x_{m_{i}})_{i}}$ ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$

Para seleccionar una subsecuencia, primero se elige una función binaria que, dada cualquier cadena binaria , dé como resultado 0 o 1. Si da como resultado 1, entonces sumamos a la subsecuencia; de lo contrario, continuamos. En esta definición, algunas reglas admisibles podrían abstenerse para siempre en algunas secuencias y, por lo tanto, no lograr seleccionar una subsecuencia infinita. Solo consideramos aquellas que sí eligen una subsecuencia infinita. ${\displaystyle \phi }$ ${\displaystyle x_{1:k}}$ ${\displaystyle x_{k+1}}$

Dicho de otra manera, cada cadena binaria infinita es un juego de lanzamiento de moneda, y una regla admisible es una forma en la que el jugador decide cuándo hacer apuestas. Un juego colectivo es un juego de lanzamiento de moneda en el que no hay forma de que un jugador obtenga mejores resultados que otro a largo plazo. Es decir, no existe un sistema de apuestas que funcione para el juego.

La definición se generaliza del alfabeto binario al alfabeto contable:

• La frecuencia de cada letra converge a un límite mayor que cero.
• Para cualquier regla "admisible", tal que seleccione una subsecuencia infinita de la cadena, la frecuencia de cada letra en la subsecuencia todavía converge al mismo límite. ${\displaystyle (x_{m_{i}})_{i}}$

Por lo general, las reglas admisibles se definen como reglas computables por una máquina de Turing, y requerimos . Con esto, tenemos las secuencias aleatorias de Mises–Wald–Church . Esto no es una restricción, ya que dada una secuencia con , podemos construir secuencias aleatorias con cualquier otro computable . ^[1] Aquí, "Church" se refiere a Alonzo Church , cuyo artículo de 1940 propuso usar reglas computables por Turing. ^[2] ${\displaystyle p=1/2}$ ${\displaystyle p=1/2}$ ${\displaystyle p\in (0,1)}$

Teorema. ( Abraham Wald , 1936, 1937) ^[3] Si sólo hay un número contable de reglas admisibles, entonces casi cualquier secuencia es un colectivo.

Bosquejo de prueba: utilizar la probabilidad teórica de la medida.

Corrija una regla admisible. Tome una muestra de una secuencia aleatoria del espacio de Bernoulli. Con probabilidad 1 (use martingalas), la subsecuencia elegida por la regla admisible aún tiene . Ahora sume todas las reglas contables. Con probabilidad 1, cada subsecuencia elegida por cada regla aún tiene . ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$ ${\displaystyle \lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p}$

Contraejemplo. (Jean Ville, 1939) ^[4] Si sólo hay un número contable de reglas admisibles, entonces existe un colectivo con para todos los . ${\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}x_{k}\geq p}$ ${\displaystyle n}$

Prueba: Véase. ^[5]

Intuitivamente, el promedio a largo plazo de una secuencia aleatoria debería oscilar en ambos lados de , de la misma manera que un paseo aleatorio debería cruzar el origen infinitas veces. El contraejemplo sugiere que la definición de von Mises no es lo suficientemente sólida. ${\displaystyle p}$

Por Martin-Löf

El contraejemplo de Ville sugiere que el sentido de aleatoriedad de Mises-Wald-Church no es lo suficientemente bueno, porque algunas secuencias aleatorias no satisfacen algunas leyes de aleatoriedad. Por ejemplo, el contraejemplo de Ville no satisface una de las leyes del logaritmo iterado : Ingenuamente, uno puede solucionar esto exigiendo que una secuencia satisfaga todas las leyes de aleatoriedad posibles, donde una "ley de aleatoriedad" es una propiedad que satisfacen todas las secuencias con probabilidad 1. Sin embargo, para cada secuencia infinita , tenemos una ley de aleatoriedad que , lo que lleva a la conclusión de que no hay secuencias aleatorias. $${\displaystyle \limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1}$$ ${\displaystyle y_{1:\infty }\in 2^{\mathbb {N} }}$ ${\displaystyle x_{1:\infty }\neq y_{1:\infty }}$

( Per Martin-Löf , 1966) ^[6] definió la "aleatoriedad de Martin-Löf" al permitir únicamente leyes de aleatoriedad que sean computables mediante el método de Turing. En otras palabras, una secuencia es aleatoria si pasa todas las pruebas de aleatoriedad computables mediante el método de Turing.

La tesis de que la definición de aleatoriedad de Martin-Löf captura "correctamente" la noción intuitiva de aleatoriedad se ha llamado tesis de Martin-Löf-Chaitin ; es algo similar a la tesis de Church-Turing . ^[7]

Tesis de Martin-Löf–Chaitin. El concepto matemático de “aleatoriedad de Martin-Löf” captura la noción intuitiva de que una secuencia infinita es “aleatoria”. Tesis de Church–Turing. El concepto matemático de “computable mediante máquinas de Turing” captura la noción intuitiva de que una función es “computable”.

Así como la computabilidad de Turing tiene muchas definiciones equivalentes, la aleatoriedad de Martin-Löf también tiene muchas definiciones equivalentes. Véase la siguiente sección.

Tres definiciones equivalentes

La definición original de Martin-Löf de una secuencia aleatoria se daba en términos de coberturas nulas constructivas; definió una secuencia como aleatoria si no está contenida en ninguna de esas coberturas. Gregory Chaitin , Leonid Levin y Claus-Peter Schnorr demostraron una caracterización en términos de complejidad algorítmica : una secuencia es aleatoria si existe un límite uniforme en la compresibilidad de sus segmentos iniciales. Schnorr dio una tercera definición equivalente en términos de martingalas . El libro de Li y Vitanyi Introducción a la complejidad de Kolmogorov y sus aplicaciones es la introducción estándar a estas ideas.

• Complejidad algorítmica (Chaitin 1969, Schnorr 1973, Levin 1973): La complejidad algorítmica (también conocida como complejidad de Kolmogorov (sin prefijo) o complejidad del tamaño del programa) puede considerarse como un límite inferior de la compresibilidad algorítmica de una secuencia finita (de caracteres o dígitos binarios). Asigna a cada una de esas secuencias 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 fijo) que no acepta ninguna entrada y que dará como salida w cuando se ejecute. Se requiere que la complejidad no tenga prefijo: el programa (una secuencia de 0 y 1) va seguido de una cadena infinita de 0, y la longitud del programa (suponiendo que se detiene) incluye la cantidad de ceros a la derecha del programa que lee la máquina universal de Turing. El requisito adicional es necesario porque podemos elegir una longitud tal que la longitud codifique información sobre la subcadena. 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 aleatoria según el método de Martin-Löf si y solo si existe una constante c tal que todos los prefijos finitos de S son c -incompresibles. Más sucintamente, ${\displaystyle K(w)\geq |w|-O(1)}$ .

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

Una secuencia se define como aleatoria de Martin-Löf si no está contenida en ningún conjunto determinado por una cobertura nula constructiva. ${\displaystyle G_{\delta }}$

• Martingalas constructivas (Schnorr 1971): Una martingala es una función tal que, para todas las cadenas finitas w , , donde es la concatenación de las cadenas a y b . Esto se llama la "condición de equidad": si una martingala se considera una estrategia de apuestas, entonces la condición anterior requiere que el apostador juegue contra probabilidades justas. Se dice que una martingala d tiene éxito en una secuencia S si donde son los primeros n bits de S . Una martingala d es constructiva (también conocida como débilmente computable , semicomputable inferior ) si existe una función computable tal que, para todas las cadenas binarias finitas w ${\displaystyle d:\{0,1\}^{*}\to [0,\infty )}$ ${\displaystyle d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2}$ ${\displaystyle a^{\smallfrown }b}$ ${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$ ${\displaystyle S\upharpoonright n}$ ${\displaystyle {\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }}$

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).}$

Una secuencia es aleatoria Martin-Löf si y sólo si ninguna martingala constructiva tiene éxito en ella.

Interpretaciones de las definiciones

La caracterización de la complejidad de Kolmogorov transmite la intuición de que una secuencia aleatoria es incompresible: ningún 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 debería tener ninguna propiedad que sea "poco común". Cada conjunto de medida 0 puede considerarse como una propiedad poco común. No es posible que una secuencia no se encuentre en ningún conjunto de medida 0, porque cada conjunto de un punto tiene medida 0. La idea de Martin-Löf era limitar la definición a conjuntos de medida 0 que sean efectivamente descriptibles; la definición de una cobertura nula efectiva determina una colección contable de conjuntos de medida 0 efectivamente descriptibles y define una secuencia como aleatoria si no se encuentra en ninguno de estos conjuntos de medida 0 particulares. Dado que la unión de una colección contable de conjuntos de medida 0 tiene medida 0, esta definición conduce inmediatamente al teorema de que existe un conjunto de medida 1 de secuencias aleatorias. Nótese que si identificamos el espacio de Cantor de secuencias binarias con el intervalo [0,1] de números reales, la medida en el espacio de Cantor concuerda con la medida de Lebesgue .

Un conjunto de medida efectiva 0 puede interpretarse como una máquina de Turing que es capaz de decir, dada una cadena binaria infinita, si la cadena parece aleatoria en niveles de significancia estadística. El conjunto es la intersección de conjuntos que se reducen y, dado que cada conjunto se especifica mediante una secuencia enumerable de prefijos, dada cualquier cadena binaria infinita, si está en , entonces la máquina de Turing puede decidir en tiempo finito que la cadena cae dentro de . Por lo tanto, puede "rechazar la hipótesis de que la cadena es aleatoria en el nivel de significancia ". Si la máquina de Turing puede rechazar la hipótesis en todos los niveles de significancia, entonces la cadena no es aleatoria. Una cadena aleatoria es una que, para cada prueba de aleatoriedad computable por Turing, logra permanecer para siempre sin rechazar en algún nivel de significancia. ^[8] ${\displaystyle U_{1}\supset U_{2}\supset U_{3}\supset \cdots }$ ${\displaystyle U_{n}}$ ${\displaystyle U_{n}}$ ${\displaystyle U_{n}}$ ${\displaystyle 2^{-n}}$

La caracterización de martingala transmite la intuición de que ningún procedimiento efectivo debería ser capaz de ganar dinero apostando contra una secuencia aleatoria. Una martingala d es una estrategia de apuestas. d lee una cadena finita w y apuesta dinero en el siguiente bit. Apuesta una fracción de su dinero a que el siguiente bit será 0, y luego el resto de su dinero a que el siguiente bit será 1. d duplica el dinero que puso en el bit que realmente ocurrió, y pierde el resto. d ( w ) es la cantidad de dinero que tiene después de ver la cadena w . Dado que la apuesta realizada después de ver la cadena w se puede calcular a partir de los valores d ( w ), d ( w 0) y d ( w 1), calcular la cantidad de dinero que tiene es equivalente a calcular la apuesta. La caracterización de martingala dice que ninguna estrategia de apuestas implementable por cualquier computadora (incluso en el sentido débil de estrategias constructivas, que no son necesariamente computables ) puede ganar dinero apostando en una secuencia aleatoria.

Propiedades y ejemplos de secuencias aleatorias de Martin-Löf

Universalidad

Existe una martingala constructiva universal d . Esta martingala es universal en el sentido de que, dada cualquier martingala constructiva d , si d tiene éxito en una secuencia, entonces d tiene éxito también en esa secuencia. Por lo tanto, d tiene éxito en todas las secuencias de RAND ^c (pero, dado que d es constructiva, no tiene éxito en ninguna secuencia de RAND). (Schnorr 1971)

Existe una cobertura nula constructiva de RAND ^c . Esto significa que todas las pruebas efectivas de aleatoriedad (es decir, las coberturas nulas constructivas) están, en cierto sentido, subsumidas por esta prueba universal de aleatoriedad, ya que cualquier secuencia que pase esta única prueba de aleatoriedad pasará todas las pruebas de aleatoriedad. (Martin-Löf 1966) Intuitivamente, esta prueba universal de aleatoriedad dice "Si la secuencia tiene prefijos cada vez más largos que pueden comprimirse cada vez mejor en esta máquina de Turing universal", entonces no es aleatoria." - ver la siguiente sección.

Esquema de construcción: Enumere las coberturas nulas efectivas como . La enumeración también es efectiva (enumerada por una máquina de Turing universal modificada). Ahora tenemos una cobertura nula efectiva universal por diagonalización: . ${\displaystyle ((U_{m,n})_{n})_{m}}$ ${\displaystyle (\cup _{n}U_{n,n+k+1})_{k}}$

Pasando pruebas de aleatoriedad

Si una secuencia no supera una prueba de aleatoriedad algorítmica, entonces es algorítmicamente comprimible. Por el contrario, si es algorítmicamente comprimible, entonces no supera una prueba de aleatoriedad algorítmica.

Esquema de construcción: supongamos que la secuencia no supera una prueba de aleatoriedad, entonces se puede comprimir enumerando lexicográficamente todas las secuencias que no superan la prueba y luego codificar la ubicación de la secuencia en la lista de todas esas secuencias. Esto se llama "codificación de fuente enumerativa". ^[9]

Por el contrario, si la secuencia es comprimible, entonces, según el principio del casillero, solo una fracción minúscula de secuencias lo son, por lo que podemos definir una nueva prueba de aleatoriedad como "tiene una compresión por esta máquina de Turing universal". Por cierto, esta es la prueba universal de aleatoriedad.

Por ejemplo, considere una secuencia binaria muestreada IID de la distribución de Bernoulli. Después de tomar una gran cantidad de muestras, deberíamos tener alrededor de unos. Podemos codificar para esta secuencia como "Generar todas las secuencias binarias con longitud , y unos. De ellas, la secuencia -ésima en orden lexicográfico". ${\displaystyle N}$ ${\displaystyle M\approx pN}$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle i}$

Por aproximación de Stirling , donde es la función de entropía binaria . Por lo tanto, el número de bits en esta descripción es: El primer término es para codificar con prefijo los números y . El segundo término es para codificar con prefijo el número . (Use la codificación omega de Elias .) El tercer término es para codificar con prefijo el resto de la descripción. Cuando es grande, esta descripción tiene solo bits, y por lo tanto es comprimible, con una relación de compresión . En particular, la relación de compresión es exactamente uno (incompresible) solo cuando . (Ejemplo 14.2.8 ^[10] ) ${\displaystyle \log _{2}{\binom {N}{pN}}\approx NH(p)}$ ${\displaystyle H}$ $${\displaystyle 2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)}$$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle N}$ ${\displaystyle \sim H(p)N}$ ${\displaystyle \sim H(p)}$ ${\displaystyle p=1/2}$

Imposibilidad de un sistema de juego

Si una mesa de ruleta genera una secuencia aleatoria algorítmica, no hay forma de vencer al crupier. Si no es así, hay una forma.

Consideremos un casino que ofrece probabilidades justas en una mesa de ruleta. La mesa de ruleta genera una secuencia de números aleatorios. Si esta secuencia es aleatoria desde el punto de vista algorítmico, entonces no existe una estrategia semicomputable inferior para ganar, lo que a su vez implica que no existe una estrategia computable inferior para ganar. Es decir, para cualquier algoritmo de juego, el logaritmo de la recompensa a largo plazo es cero (ni positivo ni negativo). Por el contrario, si esta secuencia no es aleatoria desde el punto de vista algorítmico, entonces existe una estrategia semicomputable inferior para ganar.

Ejemplos

• La probabilidad de detención de Chaitin Ω es un ejemplo de una secuencia aleatoria.
• No toda secuencia aleatoria es computable.
• Toda secuencia aleatoria es normal , satisface la ley de los grandes números y satisface todas las propiedades computables de Turing satisfechas por un flujo IID de números aleatorios uniformes. (Teorema 14.5.2 ^[10] )

Relación con la jerarquía aritmética

• RAND ^c (el complemento de RAND) es un subconjunto de medida 0 del conjunto de todas las secuencias infinitas. Esto se deduce del hecho de que cada recubrimiento nulo constructivo cubre un conjunto de medida 0, solo hay un número contable de recubrimientos nulos constructivos y una unión contable de conjuntos de medida 0 tiene medida 0. Esto implica que RAND es un subconjunto de medida 1 del conjunto de todas las secuencias infinitas.
• La clase RAND es un subconjunto del espacio de Cantor, donde se refiere al segundo nivel de la jerarquía aritmética . Esto se debe a que una secuencia S está en RAND si y solo si hay algún conjunto abierto en la cobertura nula efectiva universal que no contenga a S ; se puede ver que esta propiedad se puede definir mediante una fórmula. ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \Sigma _{2}^{0}}$
• Existe una secuencia aleatoria que es , es decir, computable en relación con un oráculo para el problema de Halting. (Schnorr 1971) El Ω de Chaitin es un ejemplo de dicha secuencia. ${\displaystyle \Delta _{2}^{0}}$
• Ninguna secuencia aleatoria es decidible , computablemente enumerable o co-computablemente enumerable . Dado que estos corresponden a los niveles , , y de la jerarquía aritmética , esto significa que es el nivel más bajo en la jerarquía aritmética donde se pueden encontrar secuencias aleatorias. ${\displaystyle \Delta _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$
• Toda secuencia es reducible por el método de Turing a una secuencia aleatoria (Kučera 1985/1989, Gács 1986). Por lo tanto, existen secuencias aleatorias con un grado de Turing arbitrariamente alto .

Aleatoriedad relativa

Como cada una de las definiciones equivalentes de una secuencia aleatoria de Martin-Löf se basa en lo que es computable por alguna máquina de Turing, uno puede naturalmente preguntar qué es computable por una máquina de oráculo de Turing . Para un oráculo fijo A , una secuencia B que no solo es aleatoria sino que, de hecho, satisface las definiciones equivalentes para computabilidad relativa a A (por ejemplo, ninguna martingala que sea constructiva en relación con el oráculo A tiene éxito en B ) se dice que es aleatoria en relación con A. Dos secuencias, aunque aleatorias en sí mismas, pueden contener información muy similar y, por lo tanto, ninguna será aleatoria en relación con la otra. Cada vez que hay una reducción de Turing de una secuencia a otra, la segunda secuencia no puede ser aleatoria en relación con la primera, así como las secuencias computables son en sí mismas no aleatorias; en particular, esto significa que el Ω de Chaitin no es aleatorio en relación con el problema de detención .

Un resultado importante relacionado con la aleatoriedad relativa es el teorema de van Lambalgen , que establece que si C es la secuencia compuesta de A y B al intercalar el primer bit de A , el primer bit de B , el segundo bit de A , el segundo bit de B , y así sucesivamente, entonces C es algorítmicamente aleatorio si y solo si A es algorítmicamente aleatorio, y B es algorítmicamente aleatorio en relación con A . Una consecuencia estrechamente relacionada es que si A y B son ambos aleatorios en sí mismos, entonces A es aleatorio en relación con B si y solo si B es aleatorio en relación con A .

Más fuerte que la aleatoriedad de Martin-Löf

La aleatoriedad relativa nos da la primera noción que es más fuerte que la aleatoriedad de Martin-Löf, que es la aleatoriedad relativa a algún oráculo fijo A . Para cualquier oráculo, esto es al menos tan fuerte, y para la mayoría de los oráculos, es estrictamente más fuerte, ya que habrá secuencias aleatorias de Martin-Löf que no sean aleatorias en relación con el oráculo A . Los oráculos importantes que a menudo se consideran son el problema de la detención, , y el oráculo del n -ésimo salto, , ya que estos oráculos pueden responder preguntas específicas que surgen naturalmente. Una secuencia que es aleatoria en relación con el oráculo se llama n -aleatoria; una secuencia es 1-aleatoria, por lo tanto, si y solo si es aleatoria de Martin-Löf. Una secuencia que es n -aleatoria para cada n se llama aritméticamente aleatoria. Las secuencias n -aleatorias a veces surgen cuando se consideran propiedades más complicadas. Por ejemplo, solo hay una cantidad contable de conjuntos, por lo que uno podría pensar que estos deberían ser no aleatorios. Sin embargo, la probabilidad de detención Ω es 1-aleatoria; solo después de alcanzar la 2-aleatoriedad es imposible que un conjunto aleatorio sea . ${\displaystyle \emptyset '}$ ${\displaystyle \emptyset ^{(n)}}$ ${\displaystyle \emptyset ^{(n-1)}}$ ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$

Más débil que la aleatoriedad de Martin-Löf

Además, existen varias nociones de aleatoriedad que son más débiles que la aleatoriedad de Martin-Löf. Algunas de ellas son la aleatoriedad débil 1, la aleatoriedad de Schnorr, la aleatoriedad computable y la aleatoriedad computable parcial. Yongge Wang demostró ^[11] que la aleatoriedad de Schnorr es diferente de la aleatoriedad computable. Además, se sabe que la aleatoriedad de Kolmogorov-Loveland no es más fuerte que la aleatoriedad de Martin-Löf, pero no se sabe si en realidad es más débil.

En el extremo opuesto del espectro de aleatoriedad existe la noción de un conjunto K-trivial . Estos conjuntos son antialeatorios en el sentido de que todos los segmentos iniciales son logarítmicamente compresibles (es decir, para cada segmento inicial w), pero no son computables. ${\displaystyle K(w)\leq K(|w|)+b}$

Véase también

• Secuencia aleatoria
• Gregorio Chaitin
• Estocástico
• Método de Monte Carlo
• Conjunto k-trivial
• Probabilidad de universalidad
• Aleatoriedad estadística

Referencias

1. Li, Ming; Vitányi, PM (2019). "1.9 Aleatoriedad". Introducción a la complejidad de Kolmogorov y sus aplicaciones (cuarta edición). Cham: Springer. ISBN 978-3-030-11298-1.
2. Copeland, Arthur H. (junio de 1940). "Alonzo Church. Sobre el concepto de una secuencia aleatoria. Boletín de la American Mathematical Society , vol. 46 (1940), págs. 130-135". The Journal of Symbolic Logic (Reseña). 5 (2): 71-72. doi :10.2307/2266178. ISSN  0022-4812. JSTOR  2266178. S2CID  124646586.
3. Wald, A. (1936). Sur la noción de colectivo en el cálculo de probabilidades. Comptes Rendus des Seances de l'Académie des Sciences, 202, 180-183. Wald, A. (1937). Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung. Ergebnisse eines Mathematischen Kolloquiums, 8, 38–72
4. Ville, J. (1939). Estudio crítico de la noción de colectivo , Monographies des Probabilités, Calcul des Probabilités et ses Applications , Gauthier-Villars.
5. Lieb, Elliott H.; Osherson, Daniel; Weinstein, Scott (11 de julio de 2006). "Demostración elemental de un teorema de Jean Ville". arXiv : cs/0607054 .
6. Martin-Löf, Per (1966-12-01). "La definición de secuencias aleatorias". Información y Control . 9 (6): 602–619. doi :10.1016/S0019-9958(66)80018-9. ISSN  0019-9958.
7. Jean-Paul Delahaye , Aleatoriedad, imprevisibilidad y ausencia de orden, en Filosofía de la probabilidad , pág. 145-167, Springer 1993.
8. Li, Vitányi, Sección 2.4
9. Cover, T. (enero de 1973). "Codificación de fuentes enumerativas". IEEE Transactions on Information Theory . 19 (1): 73–77. doi :10.1109/TIT.1973.1054929. ISSN  0018-9448.
10. Cover, Thomas M.; Thomas, Joy A. (18 de julio de 2006). Elementos de la teoría de la información, 2.ª edición (2.ª ed.). Hoboken, Nueva Jersey: Wiley-Interscience. ISBN 978-0-471-24195-9.
11. Yongge Wang: Aleatoriedad y complejidad. Tesis doctoral, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

Lectura adicional

• Eagle, Antony (2021), "Chance versus Randomness", en Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (edición de primavera de 2021), Metaphysics Research Lab, Stanford University , consultado el 28 de enero de 2024
• Downey, Rod; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A. (2006). "Calibración de la aleatoriedad". The Bulletin of Symbolic Logic . 12 (3/4): 411–491. CiteSeerX  10.1.1.135.4162 . doi :10.2178/bsl/1154698741. Archivado desde el original el 2 de febrero de 2016.
• Gács, Péter (1986). "Toda secuencia es reducible a una aleatoria" (PDF) . Información y Control . 70 (2/3): 186–192. doi : 10.1016/s0019-9958(86)80004-3 .
• Kučera, A. (1985). "Medida, Π⁰
  ₁-clases y extensiones completas de PA". Recursion Theory Week . Apuntes de clase en matemáticas. Vol. 1141. Springer-Verlag. págs. 245–259. doi :10.1007/BFb0076224. ISBN 978-3-540-39596-6.
• Kučera, A. (1989). "Sobre el uso de funciones diagonalmente no recursivas". Estudios de lógica y fundamentos de las matemáticas . Vol. 129. Holanda Septentrional. págs. 219–239.
• Levin, L. (1973). "Sobre el concepto de secuencia aleatoria". Matemáticas soviéticas - Doklady . 14 : 1413–1416.
• Li, M.; Vitanyi, PMB (1997). Introducción a la complejidad de Kolmogorov y sus aplicaciones (segunda edición). Berlín: Springer-Verlag.
• Martin-Löf, P. (1966). "La definición de secuencias aleatorias". Información y Control . 9 (6): 602–619. doi :10.1016/s0019-9958(66)80018-9.
• Nies, André (2009). Computabilidad y aleatoriedad . Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1.Zbl 1169.03034  .
• Schnorr, CP (1971). "Un enfoque unificado para la definición de una secuencia aleatoria". Teoría de sistemas matemáticos . 5 (3): 246–258. doi :10.1007/BF01694181. S2CID  8931514.
• Schnorr, Claus P. (1973). "Complejidad de procesos y pruebas aleatorias efectivas". Revista de Ciencias de la Computación y de Sistemas . 7 (4): 376–388. doi : 10.1016/s0022-0000(73)80030-3 .
• Chaitin, Gregory J. (1969). "Sobre la longitud de los programas para calcular secuencias binarias finitas: consideraciones estadísticas". Revista de la ACM . 16 (1): 145–159. doi : 10.1145/321495.321506 . S2CID  8209877.
• Ville, J. (1939). Estudio crítico de la noción de colectivo . París: Gauthier-Villars.