Secuencia aleatoria algorítmica

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 (con o sin prefijo) . Esta noción puede aplicarse de forma análoga a secuencias en cualquier alfabeto finito (por ejemplo, dígitos decimales). Las secuencias aleatorias son objetos de estudio clave en la teoría de la información algorítmica .

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

Dado que a veces se consideran diferentes tipos de algoritmos, desde algoritmos con límites específicos en su tiempo de ejecución hasta algoritmos que pueden consultar a una máquina oráculo , existen diferentes nociones de aleatoriedad. La más común se conoce como aleatoriedad de Martin-Löf ( aleatoriedad K o 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 particular (finita o infinita) sin aclaración, generalmente se entiende como "incompresible" o, en el caso de que la secuencia sea infinita y se anteponga el prefijo "algorítmicamente aleatorio" (es decir, K-incompresible), "aleatoriedad de Martin-Löf-Chaitin".

Desde su concepción, se ha demostrado que la aleatoriedad de Martin-Löf admite numerosas caracterizaciones equivalentes —en términos de compresión , pruebas de aleatoriedad y apuestas— que guardan poca semejanza con la definición original, pero que satisfacen nuestra noción intuitiva de las propiedades que deberían tener las secuencias aleatorias: deberían ser incompresibles, superar pruebas estadísticas de aleatoriedad y ser difícil obtener ganancias apostando por ellas. La existencia de estas múltiples definiciones de la aleatoriedad de Martin-Löf, y la estabilidad de estas definiciones bajo diferentes modelos de computación, evidencian que la aleatoriedad de Martin-Löf es natural y no una consecuencia del modelo particular de Martin-Löf.

Es importante diferenciar 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), la aleatoriedad estocástica se suele definir como una propiedad de una secuencia que se sabe a priori que es generada por (o es el resultado de) un proceso estocástico independiente , idénticamente distribuido y equiprobable .

Dado que las secuencias infinitas de dígitos binarios pueden identificarse con números reales en el intervalo unitario, las secuencias binarias aleatorias suelen denominarse (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, dichas secuencias pueden considerarse 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 una prueba de aleatoriedad para definir una secuencia aleatoria como aquella que superaba todas las pruebas de aleatoriedad. Definió un "colectivo" ( kollektiv ) como una cadena binaria infinita. $x_{1:\infty }$ definido de tal manera que

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

Para seleccionar una subsecuencia , primero seleccione una función binaria. $\phi$ , de tal manera que dada cualquier cadena binaria $x_{1:k}$ , produce un resultado de 0 o 1. Si produce 1, entonces añadimos $x_{k+1}$ a la subsecuencia, de lo contrario continuamos. En esta definición, algunas reglas admisibles podrían abstenerse indefinidamente en algunas secuencias y, por lo tanto, no lograr seleccionar una subsecuencia infinita. Solo consideramos aquellas que sí seleccionan una subsecuencia infinita.

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

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

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

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

Teorema ( Abraham Wald , 1936, 1937) ^{[ 3 ]} Si solo hay una cantidad numerable de reglas admisibles, entonces casi cualquier secuencia es un colectivo.

Bosquejo de la demostración: Utilice la probabilidad basada en la teoría de la medida.

Fije una regla admisible. Muestre una secuencia aleatoria del espacio de Bernoulli. Con probabilidad 1 (usando martingalas), la subsecuencia elegida por la regla admisible aún tiene $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$ . Ahora agregue todas las reglas numerables. Con probabilidad 1, cada subsecuencia elegida por cada regla todavía tiene $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$ .

Sin embargo, se descubrió que esta definición no era lo suficientemente fuerte. Intuitivamente, el promedio a largo plazo de una secuencia aleatoria debería oscilar a ambos lados de $p$ , como si un paseo aleatorio debiera cruzar el origen infinitas veces. Sin embargo, Jean Ville demostró que, incluso con un número numerable de reglas, existe una secuencia binaria que tiende a $p$ fracción de unos, pero, para cada prefijo finito, la fracción de unos es menor que $p$ . ^{[ 4 ]}

La construcción de Ville (Jean Ville, 1939) Existe un colectivo con un número numerable de reglas admisibles tales que, para todo $n$ , ${\frac {1}{n}}\sum _{k=1}^{n}x_{k}\leq p$ . ^{[ 5 ]}

Por Martin-Löf

La construcción 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, la construcción de Ville no satisface una de las leyes del logaritmo iterado : $\limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1$ Ingenuamente, se 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 $y_{1:\infty }\in 2^{\mathbb {N} }$ , tenemos una ley de aleatoriedad que $x_{1:\infty }\neq y_{1:\infty }$ , lo que lleva a la conclusión de que no existen secuencias aleatorias.

( Per Martin-Löf , 1966) ^{[ 6 ]} definió la "aleatoriedad de Martin-Löf" al permitir únicamente leyes de aleatoriedad que sean computables por una máquina de Turing. En otras palabras, una secuencia es aleatoria si y solo si supera todas las pruebas de aleatoriedad computables por una máquina 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 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 por máquinas de Turing» refleja la noción intuitiva de que una función sea «computable». Así como la computabilidad de Turing tiene muchas definiciones equivalentes, la aleatoriedad de Martin-Löf también las tiene. Véase la siguiente sección.

Tres definiciones equivalentes

La definición original de Martin-Löf de una secuencia aleatoria se basaba en cubiertas nulas constructivas; definía una secuencia como aleatoria si no estaba contenida en ninguna de dichas cubiertas. 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 una cota uniforme para la compresibilidad de sus segmentos iniciales. Schnorr ofreció una tercera definición equivalente en términos de martingalas . El libro de Li y Vitanyi, «Una 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 una cota inferior de la compresibilidad algorítmica de una secuencia finita (de caracteres o dígitos binarios). 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 fijo) que no recibe entrada y produce w como salida al ejecutarse. Dado un número natural c y una secuencia w , decimos que w es c- incompresible si $K(w)\geq |w|-c$ .

Una secuencia infinita S es aleatoria de Martin-Löf si y solo si existe una constante c tal que todos los prefijos finitos de S son c- incompresibles. De forma más concisa, $K(w)\geq |w|-O(1)$ .

Recubrimientos nulos constructivos (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 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. Un recubrimiento nulo constructivo o conjunto de medida efectiva 0 es una secuencia recursivamente enumerable $U_{i}$ de conjuntos abiertos efectivos tales que $U_{i+1}\subseteteq U_{i}$ y $\mu (U_{i})\leq 2^{-i}$ para cada número natural i . Cada cobertura nula efectiva determina una $G_{\delta }$ conjunto de medida 0, es decir, la intersección de los conjuntos $U_{i}$ .

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

Martingalas constructivas (Schnorr 1971): Una martingala es una función $d:\{0,1\}^{*}\a [0,\infty )$ de tal manera que, para todas las cadenas finitas w , $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$ , dónde $a^{\smallfrown }b$ es la concatenación de las cadenas a y b . Esto se denomina "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 $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ dónde $S\upharpoonright n$ 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. ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ de tal manera que, para todas las cadenas binarias finitas w

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

Una secuencia es aleatoria de Martin-Löf si y solo si ninguna martingala constructiva tiene éxito sobre 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 la 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 pensarse como una propiedad poco común. No es posible que una secuencia se encuentre en ningún conjunto de medida 0, porque cada conjunto de un punto tiene medida 0. La idea de Martin-Löf fue limitar la definición a conjuntos de medida 0 que son efectivamente descriptibles; la definición de una cobertura nula efectiva determina una colección numerable de conjuntos de medida 0 efectivamente descriptibles y define una secuencia como aleatoria si no se encuentra en ninguno de estos conjuntos particulares de medida 0. Dado que la unión de una colección numerable 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 coincide con la medida de Lebesgue .

Un conjunto de medida efectiva 0 puede interpretarse como una máquina de Turing capaz de determinar, dada una cadena binaria infinita, si la cadena parece aleatoria a niveles de significancia estadística . El conjunto es la intersección de conjuntos decrecientes. $U_{1}\supset U_{2}\supset U_{3}\supset \cdots$ y puesto que cada conjunto $U_{n}$ se especifica mediante una secuencia enumerable de prefijos, dada cualquier cadena binaria infinita, si está en $U_{n}$ , entonces la máquina de Turing puede decidir en tiempo finito que la cadena cae dentro $U_{n}$ Por lo tanto, puede "rechazar la hipótesis de que la cadena es aleatoria a un nivel de significancia $2^{-n}$ "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 indefinidamente sin ser rechazada en algún nivel de significancia. ^{[ 8 ]}

La caracterización de la martingala transmite la intuición de que ningún procedimiento efectivo debería poder ganar dinero apostando contra una secuencia aleatoria. Una martingala d es una estrategia de apuestas. d lee una cadena finita w y apuesta dinero al siguiente bit. Apuesta una fracción de su dinero a que el siguiente bit será 0, y el resto a que será 1. d duplica el dinero apostado al 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 la martingala afirma que ninguna estrategia de apuestas implementable por ninguna computadora (incluso en el sentido débil de estrategias constructivas, que no son necesariamente computables ) puede ganar dinero apostando a 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 lo tiene 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 supere esta única prueba de aleatoriedad superará todas las pruebas de aleatoriedad. (Martin-Löf 1966) Intuitivamente, esta prueba universal de aleatoriedad afirma: «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. —véase la siguiente sección.

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

Superar pruebas de aleatoriedad

Si una secuencia no supera una prueba de aleatoriedad algorítmica, entonces es compresible algorítmicamente. Por el contrario, si es compresible algorítmicamente, 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, a continuación, codificando la posició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 compresible, entonces, según el principio del palomar , solo una fracción ínfima de secuencias son así, por lo que podemos definir una nueva prueba de aleatoriedad: «tiene una compresión mediante esta máquina de Turing universal». Cabe mencionar que esta es la prueba universal de aleatoriedad.

Por ejemplo, consideremos una secuencia binaria muestreada IID de la distribución de Bernoulli . Después de tomar un gran número $N$ de muestras, deberíamos tener aproximadamente $M\approx pN$ unos. Podemos codificar esta secuencia como "Generar todas las secuencias binarias con longitud $N$ , y $M$ los. De esos, el $i$ -ésima secuencia en orden lexicográfico.".

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

Imposibilidad de un sistema de apuestas

Si una mesa de ruleta genera una secuencia aleatoria mediante un algoritmo, entonces no hay forma de vencer al crupier. Si no es así, entonces sí hay una forma.

Consideremos un casino que ofrece probabilidades justas en la ruleta. La mesa genera una secuencia de números aleatorios. Si esta secuencia es aleatoria algorítmicamente, no existe una estrategia semicomputable inferior para ganar, lo que implica que no existe una estrategia computable para ganar. Es decir, para cualquier algoritmo de juego, la ganancia logarítmica a largo plazo es cero (ni positiva ni negativa). Por el contrario, si esta secuencia no es aleatoriamente algorítmicamente, existe una estrategia semicomputable inferior para ganar.

Ejemplos

La probabilidad de parada 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 por Turing que satisface una secuencia 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 existen una cantidad numerable de recubrimientos nulos constructivos, y una unión numerable 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 una $\Sigma _{2}^{0}$ subconjunto del espacio de Cantor, donde $\Sigma _{2}^{0}$ 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 existe algún conjunto abierto en la cobertura nula efectiva universal que no contiene a S ; esta propiedad puede verse definida por una $\Sigma _{2}^{0}$ fórmula.
Hay una secuencia aleatoria que es $\Delta _{2}^{0}$ , es decir, computable en relación con un oráculo para el problema de la parada. (Schnorr 1971) La Ω de Chaitin es un ejemplo de tal secuencia.
Ninguna secuencia aleatoria es decidible , computablemente enumerable o co-computablemente enumerable . Dado que estas corresponden a la $\Delta _{1}^{0}$ , $\Sigma _{1}^{0}$ , y $\Pi _{1}^{0}$ niveles de la jerarquía aritmética , esto significa que $\Delta _{2}^{0}$ es el nivel más bajo en la jerarquía aritmética donde se pueden encontrar secuencias aleatorias.
Toda secuencia es Turing reducible a alguna secuencia aleatoria. (Kučera 1985/1989, Gács 1986). Por lo tanto, existen secuencias aleatorias de grado 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 preguntarse naturalmente qué es computable por una máquina 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 de computabilidad con respecto a A (por ejemplo, ninguna martingala que sea constructiva con respecto al oráculo A tiene éxito en B ) se dice que es aleatoria con respecto a A. Dos secuencias, aunque aleatorias en sí mismas, pueden contener información muy similar y, por lo tanto, ninguna será aleatoria con respecto a la otra. Siempre que haya una reducción de Turing de una secuencia a otra, la segunda secuencia no puede ser aleatoria con respecto a la primera, al igual que las secuencias computables no son aleatorias en sí mismas; en particular, esto significa que Ω de Chaitin no es aleatorio con respecto al problema de la parada .

Un resultado importante relacionado con la aleatoriedad relativa es el teorema de van Lambalgen , que establece que si C es la secuencia compuesta a partir de A y B intercalando 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 aleatoria si y solo si A es algorítmicamente aleatoria, y B es algorítmicamente aleatoria 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 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 relativas al oráculo A. Los oráculos importantes que se suelen considerar son el problema de la parada, $\emptyset '$ y el oráculo del enésimo salto , $\emptyset ^{(n)}$ , 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. $\emptyset ^{(n-1)}$ Se denomina n -aleatorio; 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 denomina aleatoria aritmética. Las secuencias n -aleatorias a veces surgen al considerar propiedades más complicadas. Por ejemplo, solo hay una cantidad numerable de $\Delta _{2}^{0}$ conjuntos, por lo que uno podría pensar que estos deberían ser no aleatorios. Sin embargo, la probabilidad de parada Ω es $\Delta _{2}^{0}$ y 1-aleatorio; solo después de alcanzar la 2-aleatoriedad es imposible que un conjunto aleatorio sea $\Delta _{2}^{0}$ .

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

Además, existen varias nociones de aleatoriedad más débiles que la aleatoriedad de Martin-Löf. Algunas de ellas son la aleatoriedad débil de orden 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. Asimismo, se sabe que la aleatoriedad de Kolmogorov-Loveland no es más fuerte que la aleatoriedad de Martin-Löf, pero se desconoce si en realidad es más débil.

En el extremo opuesto del espectro de aleatoriedad está la noción de un conjunto K-trivial . Estos conjuntos son antialeatorios en el sentido de que todo segmento inicial es logarítmicamente compresible (es decir, $K(w)\leq K(|w|)+b$ para cada segmento inicial w), pero no son computables.

Véase también

Referencias

↑ 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.
↑ Copeland, Arthur H. (junio de 1940). "Alonzo Church. Sobre el concepto de secuencia aleatoria. Boletín de la Sociedad Matemática Americana , vol. 46 (1940), págs. 130–135". The Journal of Symbolic Logic (Revisión). 5 (2): 71– 72. doi : 10.2307/2266178 . ISSN 0022-4812 . JSTOR 2266178. S2CID 124646586 .
^ 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
^ Ville, J. (1939). Estudio crítico de la noción colectiva , Monographies des Probabilités, Calcul des Probabilités et ses Applications , Gauthier-Villars.
↑ Lieb, Elliott H.; Osherson, Daniel; Weinstein, Scott (2006-07-11). "Prueba elemental de un teorema de Jean Ville". arXiv : cs/0607054 .
↑ Martin-Löf, Per (1966-12-01). "La definición de secuencias aleatorias" . Information and Control . 9 (6): 602– 619. doi : 10.1016/S0019-9958(66)80018-9 . ISSN 0019-9958 .
↑ Jean-Paul Delahaye , Aleatoriedad, imprevisibilidad y ausencia de orden , en Filosofía de la probabilidad , págs. 145-167, Springer 1993.
↑ Li, Vitányi, Sección 2.4
↑ Cover, T. (enero de 1973). "Codificación enumerativa de fuentes". IEEE Transactions on Information Theory . 19 (1): 73– 77. doi : 10.1109/TIT.1973.1054929 . ISSN 0018-9448 .
1 2 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, NJ: Wiley-Interscience. ISBN 978-0-471-24195-9.
↑ Yongge Wang: Aleatoriedad y complejidad. Tesis doctoral, 1996, http://webpages.uncc.edu/yonwang/papers/thesis.pdf

Lecturas adicionales

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, Rod; Hirschfeldt, Denis R.; Nies, André; Terwijn, Sebastiaan A. (2006). "Calibrating Randomness" . The Bulletin of Symbolic Logic . 12 (3/4): 411– 491. CiteSeerX 10.1.1.135.4162 . doi : 10.2178/bsl/1154698741 . Archivado del original el 2 de febrero de 2016.
Gács, Péter (1986). "Cada secuencia es reducible a una aleatoria" (PDF) . Information and Control . 70 (2/3): 186–192 . doi : 10.1016/s0019-9958(86)80004-3 . Archivado del original (PDF) el 4 de marzo de 2016. Consultado el 2 de septiembre de 2015 .
Kučera, A. (1985). "Medida, clases Π ⁰₁ y extensiones completas de PA". Semana de la Teoría de la Recursión . Notas de clase en matemáticas. Vol. 1141. Springer-Verlag. pp. 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 en lógica y fundamentos de las matemáticas . Vol. 129. North-Holland. pp. 219–239 .
Levin, L. (1973). "Sobre la noción de una 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". Information and 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". Mathematical Systems Theory . 5 (3): 246– 258. doi : 10.1007/BF01694181 . S2CID 8931514 .
Schnorr, Claus P. (1973). "Complejidad de procesos y pruebas aleatorias efectivas" . Journal of Computer and System Sciences . 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" . Journal of the 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.

[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 Matemática Americana , vol. 46 (1940), págs. 130–135". The Journal of Symbolic Logic (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 colectiva , Monographies des Probabilités, Calcul des Probabilités et ses Applications , Gauthier-Villars.

[5] Lieb, Elliott H.; Osherson, Daniel; Weinstein, Scott (2006-07-11). "Prueba elemental de un teorema de Jean Ville". arXiv : cs/0607054 .

[6] Martin-Löf, Per (1966-12-01). "La definición de secuencias aleatorias" . Information and 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ágs. 145-167, Springer 1993.

[8] Li, Vitányi, Sección 2.4

[9] Cover, T. (enero de 1973). "Codificación enumerativa de fuentes". IEEE Transactions on Information Theory . 19 (1): 73– 77. doi : 10.1109/TIT.1973.1054929 . ISSN 0018-9448 .

[:0-10] 1 2 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, NJ: 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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 11 ]