Secuencia algorítmicamente aleatoria

Secuencia de dígitos binarios que parece aleatoria para cualquier algoritmo que se ejecute en una máquina de Turing universal

Intuitivamente, una secuencia algorítmicamente aleatoria (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 prefijos o no) . La noción se puede aplicar de manera análoga a secuencias de cualquier alfabeto finito (por ejemplo, dígitos decimales). Las secuencias aleatorias son objetos clave de estudio en la teoría algorítmica de la información .

En la teoría de la probabilidad de la teoría de la medida , introducida por Andrey Kolmogorov en 1933, no existe una secuencia aleatoria. Por ejemplo, considere lanzar una moneda justa infinitas veces. Cualquier secuencia particular, ya sea o , tiene la misma probabilidad de ser exactamente cero. No hay forma de afirmar que una secuencia es "más aleatoria" que otra secuencia, utilizando el lenguaje de la probabilidad de la teoría de 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 Oracle , existen diferentes nociones de aleatoriedad. El más común de ellos se conoce como aleatoriedad de Martin-Löf ( aleatoriedad K o aleatoriedad 1 ), pero también existen formas de aleatoriedad más fuertes y más débiles. Cuando el término "algorítmicamente aleatorio" se utiliza para referirse a una secuencia única (finita o infinita) particular sin aclaración, generalmente se entiende que significa "incompresible" o, en el caso de que la secuencia sea infinita y tenga el prefijo algorítmicamente aleatorio (es decir, K -incompresible), "Martin-Löf-Chaitin aleatorio".

Desde sus inicios, se ha demostrado que la aleatoriedad de Martin-Löf admite muchas caracterizaciones equivalentes (en términos de compresión , pruebas de aleatoriedad y juegos de azar ) que guardan poca semejanza exterior con la definición original, pero cada una de las cuales satisface nuestra noción intuitiva de las propiedades que definen al azar. Las secuencias deberían tener: las secuencias aleatorias deberían ser incompresibles, deberían pasar pruebas estadísticas de aleatoriedad y debería 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 cálculo 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 eliminar la ambigüedad 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), generalmente se dice que la aleatoriedad estocástica es una propiedad de una secuencia que a priori se sabe que es generada por (o es el resultado de) una secuencia estocástica equiprobable independiente e idénticamente distribuida . proceso.

Debido a que se pueden identificar secuencias infinitas de dígitos binarios 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 tal 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 . A este principio lo llamó " 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 elija una función binaria , de modo que dada cualquier cadena binaria , genere 0 o 1. Si genera 1, entonces agregamos a la subsecuencia; de lo contrario, continuamos. En esta definición, algunas reglas admisibles podrían abstenerse para siempre de algunas secuencias y, por tanto, no seleccionar una subsecuencia infinita. Sólo consideramos aquellos que 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 que tiene un jugador de decidir cuándo hacer apuestas. Un colectivo es un juego de lanzamiento de moneda en el que no hay forma de que un jugador lo haga mejor que otro a largo plazo. Es decir, no existe ningún 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 aún 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 otra computable . ^[1] Aquí, "Church" se refiere a Alonzo Church , cuyo artículo de 1940 proponía utilizar 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: utilice la probabilidad teórica de la medida.

Fije una regla admisible. Muestreo de una secuencia aleatoria del espacio de Bernoulli. Con probabilidad 1 (use martingalas), la subsecuencia elegida por la regla admisible todavía tiene . Ahora agregue todas las reglas contables. Con probabilidad 1, cada subsecuencia elegida por cada regla todavía 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 para todos . ${\displaystyle {\frac {1}{n}}\sum _{k=1}^{n}x_{k}\geq p}$ ${\displaystyle n}$

Prueba: Ver. ^[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 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 :

$${\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" permitiendo únicamente leyes de aleatoriedad que sean computables por Turing. En otras palabras, una secuencia es aleatoria si pasa todas las pruebas de aleatoriedad computables por Turing.

La tesis de que la definición de aleatoriedad de Martin-Löf captura "correctamente" la noción intuitiva de aleatoriedad se ha denominado 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".

Al igual que la computabilidad de Turing tiene muchas definiciones equivalentes, la aleatoriedad de Martin-Löf también tiene muchas definiciones equivalentes. Consulte la siguiente sección.

Tres definiciones equivalentes

La definición original de Martin-Löf de una secuencia aleatoria estaba en términos de coberturas nulas constructivas; definió una secuencia como aleatoria si no está contenida en ninguna cubierta de este tipo. 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 prefijos) 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 estas secuencias w un número natural K(w) que, intuitivamente, mide la longitud mínima de un programa de computadora (escrito en algún lenguaje de programación fijo) que no recibe ninguna entrada y generará w cuando se ejecute. Se requiere que la complejidad esté libre de prefijos: el programa (una secuencia de 0 y 1) es seguido por una cadena infinita de ceros, y la longitud del programa (suponiendo que se detenga) incluye el número 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 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 de Martin-Löf si y sólo si hay una constante c tal que todos los prefijos finitos de S sean 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, dejamos que C _w denote 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 |} . Cada subconjunto abierto del espacio de Cantor es la unión de una secuencia contable 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 un conjunto de medida efectiva 0 es una secuencia recursivamente enumerable de conjuntos abiertos efectivos tales que y para cada número natural i . Cada 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 "condición de equidad": si se considera una martingala como una estrategia de apuestas, entonces la condición anterior requiere que el apostante juegue contra probabilidades justas. Se dice que una martingala d tiene éxito en una secuencia S si donde están 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 de Martin-Löf si y sólo si no tiene éxito ninguna martingala constructiva.

Interpretaciones de las definiciones.

La caracterización de la complejidad de Kolmogorov transmite la intuición de que una secuencia aleatoria es incompresible: un programa mucho más corto que el prefijo no puede producir ningún prefijo.

La caracterización de cobertura nula transmite la intuición de que un número real aleatorio no debe 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 se encuentre en conjuntos 0 sin medida, porque cada conjunto de un punto tiene medida 0. La idea de Martin-Löf era limitar la definición a medir 0 conjuntos que sean efectivamente descriptibles; la definición de una cobertura nula efectiva determina una colección contable de conjuntos de medidas 0 efectivamente descriptibles y define una secuencia como aleatoria si no se encuentra en ninguno de estos conjuntos de medidas 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 secuencias aleatorias de medida 1. Tenga en cuenta 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 está especificado por una secuencia enumerable de prefijos, dada cualquier cadena binaria infinita, si está en , entonces la máquina de Turing puede decidir en un tiempo finito que la cadena cae dentro . Por 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 aquella que, para cada prueba de aleatoriedad computable por Turing, logra permanecer para siempre sin ser rechazada 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 eficaz debería poder generar 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 apostó 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 equivale a calcular la apuesta. La caracterización 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 generar 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 también tiene éxito en esa secuencia. Por lo tanto, d tiene éxito en cada secuencia en RAND ^c (pero, dado que d es constructivo, no tiene éxito en ninguna secuencia en RAND). (Schnorr 1971)

Hay una cobertura nula constructiva de RAND ^c . Esto significa que todas las pruebas efectivas de aleatoriedad (es decir, 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". (consulte la siguiente sección).

Croquis de construcción: Enumerar las coberturas nulas efectivas como . La enumeración también es eficaz (enumerada mediante 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}}$

Pasar pruebas de aleatoriedad

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

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

Por el contrario, si la secuencia es comprimible, entonces, según el principio del casillero, sólo una fracción extremadamente pequeña de secuencias es así, por lo que podemos definir una nueva prueba de aleatoriedad como "tiene una compresión mediante esta máquina universal de Turing". Por cierto, ésta es la prueba universal de aleatoriedad.

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

Por aproximación de Stirling , ¿ dónde está la función de entropía binaria ? Por tanto, el número de bits en esta descripción es: ${\displaystyle \log _{2}{\binom {N}{pN}}\approx NH(p)}$ ${\displaystyle H}$

$${\displaystyle 2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)}$$

la codificación omega de Elias^[10] ${\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 algorítmicamente aleatoria, entonces no hay forma de vencer al crupier. Si no es así, entonces hay una manera.

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

Ejemplos

• La probabilidad de detención Ω de Chaitin es un ejemplo de secuencia aleatoria.
• Toda secuencia aleatoria no es computable.
• Cada 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 uniformemente aleatorios. (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 está implícito en el hecho de que cada cubierta nula constructiva cubre un conjunto de medida 0, solo hay un número contable de cubiertas nulas constructivas 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 ALEATORIO si y sólo si hay algún conjunto abierto en la cobertura nula efectiva universal que no contiene S ; Se puede considerar que esta propiedad se puede definir mediante una fórmula. ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \Sigma _{2}^{0}}$
• Hay una secuencia aleatoria que es , es decir, computable en relación con un oráculo para el problema de detención. (Schnorr 1971) Ω de Chaitin es un ejemplo de tal 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 de 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}}$
• Cada secuencia es reducible por Turing a alguna secuencia aleatoria. (Kučera 1985/1989, Gács 1986). Por tanto, existen secuencias aleatorias de 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, naturalmente uno puede preguntarse qué es computable por una máquina oráculo de Turing . Para un oráculo fijo A , una secuencia B que no sólo es aleatoria sino que, de hecho, satisface las definiciones equivalentes de 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 relativa. a A.​ Dos secuencias, aunque sean aleatorias, 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, del mismo modo que las secuencias computables no son aleatorias en sí mismas; 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 entrelazando 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 sólo 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 aleatorios, entonces A es aleatorio con respecto a B si y sólo si B es aleatorio con respecto a 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 igual de 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 son 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 enésimo salto, ya que estos oráculos son capaces de 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 sólo si es aleatoria de Martin-Löf. Una secuencia que es n -aleatoria para cada n se llama aritméticamente aleatoria. Las n -secuencias aleatorias surgen a veces cuando se consideran propiedades más complicadas. Por ejemplo, sólo hay un número contable de conjuntos, por lo que se podría pensar que no deberían ser aleatorios. Sin embargo, la probabilidad de parada Ω es 1 aleatoria; sólo después de alcanzar la aleatoriedad 2 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. Algunos de estos son aleatoriedad 1 débil, aleatoriedad de Schnorr, aleatoriedad computable, 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 la aleatoriedad está la noción de conjunto K-trivial . Estos conjuntos son antialeatorios porque todos los segmentos iniciales son comprimibles logarítmicamente (es decir, para cada segmento inicial w), pero no son computables. ${\displaystyle K(w)\leq K(|w|)+b}$

Ver también

• Secuencia aleatoria
• Gregorio Chaitin
• Estocásticos
• Método Montecarlo
• Conjunto K-trivial
• Probabilidad de universalidad
• Aleatoriedad estadística

Referencias

1. Li, Ming; Vitányi, PM (2019). "1.9 Aleatoriedad". Una introducción a la complejidad de Kolmogorov y sus aplicaciones (Cuarta ed.). Cham: Springer. ISBN 978-3-030-11298-1.
2. Copeland, Arthur H. (junio de 1940). "Alonzo Church. Sobre el concepto de secuencia aleatoria. Boletín de la Sociedad Estadounidense de Matemáticas , vol. 46 (1940), págs. 130-135". La revista de lógica simbólica (revisión). 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 colectividad , 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 (1 de diciembre de 1966). "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. 145–167, Springer 1993.
8. Li, Vitányi, sección 2.4
9. Portada, T. (enero de 1973). "Codificación de fuente enumerativa". Transacciones IEEE sobre teoría de la información . 19 (1): 73–77. doi :10.1109/TIT.1973.1054929. ISSN  0018-9448.
10. Portada, Thomas M.; Thomas, Joy A. (18 de julio de 2006). Elementos de la teoría de la información, segunda 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

Otras lecturas

• 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, Universidad de Stanford , consultado el 28 de enero de 2024.
• Downey, varilla; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A. (2006). "Calibración de la aleatoriedad". El Boletín de Lógica Simbólica . 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, Peter (1986). "Cada secuencia se puede reducir 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". Semana de la teoría de la recursión . Apuntes de conferencias sobre 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 la noción 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 ed.). Berlín: Springer-Verlag.
• Martín-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 . Guías de lógica de Oxford. vol. 51. Oxford: Prensa de la Universidad de Oxford. 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 del proceso 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 duración 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.