Sequência algoritmicamente aleatória

Intuitivamente, uma sequência algoritmicamente aleatória (ou 'sequência aleatória' ) é uma sequência infinita de dígitos binários que parece aleatória para qualquer algoritmo. O conceito pode ser aplicado analogamente para as sequências em qualquer alfabeto finito (por exemplo, dígitos decimais). Sequências aleatórias são objetos-chave de estudo em teoria algorítmica da informação.

Como os diferentes tipos de algoritmos são considerados às vezes, variando de algoritmos com limitantes específicos sobre o seu tempo de execução para algoritmos que podem fazer perguntas de um oráculo, existem diferentes noções de aleatoriedade. O mais comum deles é conhecido como 'aleatoriedade de Martin-Löf ' (ou '1-aleatoriedade' ), mas outras formas mais fortes e mais fracas da aleatoriedade também existem. O termo "aleatório" utilizado para se referir a uma sequência sem esclarecimento é geralmente considerado como significando "aleatório Martin-Löf " (definido a seguir).

Pelo fato de sequências infinitas de dígitos binários poderem ser identificadas com números reais no intervalo unitário, sequências binárias aleatórias são freqüentemente chamadas de 'números reais aleatórios' . Além disso, as sequências binárias infinitas correspondem às funções características de conjuntos de números naturais; portanto, essas sequências podem ser vistas como conjuntos de números naturais.

A classe de todas as sequências aleatórias Martin-Löf (binária) é denotada por RAND ou MLR.

História

A primeira definição adequada de uma seqüência aleatória foi dada por Per Martin-Löf em 1966. Pesquisadores anteriores, como Richard von Mises tentaram formalizar a noção de um [teste de aleatoriedade [| teste de aleatoriedade] ], a fim de definir uma sequência aleatória como uma que passasse em todos os testes de aleatoriedade; no entanto, a noção precisa de um teste de aleatoriedade foi deixada vaga. A percepção-chave de Martin-Löf era usar a teoria da computação para definir formalmente a noção de um teste de aleatoriedade. Isto contrasta com a ideia de aleatoriedade na probabilidade; em que na teoria, qualquer elemento particular de um espaço de amostra pode ser considerado aleatório.

Já foi mostrado que a aleatoriedade de Martin-Löf admite muitas caracterizações equivalentes - em termos de compressão, testes de aleatoriedade, e apostas - que carregam pouca semelhança para fora, para a definição original, mas cada um dos quais satisfaz a nossa noção intuitiva das propriedades que as sequências aleatórias devem ter: sequências aleatórias devem ser incompressíveis, elas devem passar por testes estatísticos de aleatoriedade, e deve ser difícil fazer dinheiro apostando sobre elas. A existência destas múltiplas definições de aleatoriedade de Martin-Löf, e a estabilidade dessas definições sob diferentes modelos de computação, dá provas de que a aleatoriedade de Martin-Löf é uma propriedade fundamental da matemática e não um acidente de um determinado modelo de Martin-Löf. A tese de que a definição de Martin-Löf captura "corretamente" a noção intuitiva de aleatoriedade tem sido chamada de 'Tese de Martin-Löf-Chaitin ' ; e é um pouco semelhante à tese de Church-Turing .

Três definições equivalentes

A definição original de Martin-Löf para uma seqüência aleatória foi dada em termos de coberturas construtivas nulas; ele definiu que para uma seqüência ser aleatória, ela não pode estar contida em qualquer cobertura. Leonid Levin e Claus-Peter Schnorr provaram uma caracterização em termos de complexidade de Kolmogorov: uma sequência é aleatória, se houver um limite uniforme na compressibilidade dos seus segmentos iniciais. Schnorr deu uma terceira definição equivalente em termos de martingales (um tipo de estratégia de apostas). O livro de Li e Vitanyi, Uma Introdução à Complexidade de Kolmogorov e suas aplicações é a introdução padrão para essas ideias.

• Complexidade de Kolmogorov (Schnorr 1973; Levin, 1973): complexidade de Kolmogorov pode ser considerada como um limite inferior na compressibilidade algorítmica de uma sequência finita (de caracteres ou dígitos binários). Ele atribui a cada tal sequência um número natural 'w' K (w) que, intuitivamente, mede a duração mínima de um programa de computador (escrito em alguma linguagem de programação fixa), que não recebe nenhuma entrada e retorna “w” como saída quando é executado. Dado um número natural c e uma sequência w , dizemos que w é 'c' '- incompressível' se $K(w)\geq |w|-c$.

Uma sequência infinita S é Martin-Löf aleatória se e somente se existe uma constante c de tal forma que todos os prefixos finitos de S são c -. incompressíveis

• Coberturas construtivas nulas (Martin-Löf 1966): Esta é a definição original de Martin-Löf. Para uma cadeia binária finita w dizemos que 'C _w ' 'denota o cilindro gerado por w . Este é o conjunto de todas as sequências infinitas começando com w , que é um conjunto aberto básico no espaço de Cantor. A 'medida produto' μ ( C _w ) do cilindro gerado por w é definida como sendo 2 ^{- | w |} . Cada subconjunto aberto do espaço de Cantor é a união de uma sequência contável de conjuntos abertos básicos disjuntos, e a medida de um conjunto aberto é a soma das medidas de tal sequência. Um conjunto aberto eficaz é um conjunto aberto que é a união da seqüência de conjuntos abertos básicos determinados por uma sequência de cadeias binárias recursivamente enumeráveis . A Cobertura construtiva nula ou medida eficaz 0 conjunto é uma sequência recursivamente enumerável ​​$U_{i}$ de conjuntos abertos eficazes tal que $U_{i+1}\subseteq U_{i}$ e $\mu (U_{i})\leq 2^{-i}$ para cada número natural i . Cada cobertura nula eficaz determina um conjunto $G_{\ }delta$ de medida 0, ou seja, a intersecção dos conjuntos $U_{i}$.

A seqüência é definida para ser Martin-Löf aleatória, se não for contida em qualquer $G_{\ }delta$ conjunto determinado por uma cobertura construtiva nula.

• Martingales construtivas' (Schnorr 1971): A martingale é uma função $d:\{0,1\}^{*}\to [0,\infty )$ tal que, para todas as cadeias finitas w, $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$, onde $a^{\smallfrown }b$ é a concatenação das cadeias a e b. Isso é chamado de "condição de justiça"; um martingale é visto como uma estratégia de aposta, e as condições abaixo requerem que o melhor jogue contra probabilidades justas. Um martingale d é dito suceder numa sequência S se $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ onde $S\upharpoonright n$ são os primeiros n bits de S. Um martingale d é construtivo (também conhecido como fracamente computável ou subcomputável) se existe uma função computável ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ tal que, para todas as cadeias binárias finitas w

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

Uma sequência é Martin-Löf aleatória se e somente se não há martingale construtivo que sucede nela.

(Note que a definição de martingale usada aqui é um pouco diferente da utilizado em teoria da probabilidade . Essa definição da martingale tem uma condição de justiça semelhante, que também estabelece que o valor esperado após alguma observação é o mesmo que o valor antes da observação, dada a história prévia de observações. a diferença é que na teoria das probabilidades, a história prévia de observações apenas se refere à história de capital, visto que aqui a história refere-se à sequência exata de 0’s e 1’s na cadeia.).

Interpretações das definições

A caracterização da complexidade de Kolmogorov transmite a intuição de que uma sequência aleatória é incompressível: nenhum prefixo pode ser produzido por um programa muito mais curto do que o prefixo.

A caracterização da cobertura nula transmite a intuição de que um número real aleatório não deve ter qualquer propriedade que é "incomum". Cada conjunto de medida 0 pode ser pensado como uma propriedade incomum. Não é possível para uma seqüência cair em conjuntos de medida 0, porque cada conjunto de um ponto tem medida 0. A idéia de Martin-Löf era limitar a definição de conjuntos de medida 0 que são efetivamente descritíveis; a definição de uma cobertura efetiva nula determina uma coleção contável de conjuntos de medida 0 efetivamente descritíveis e define uma sequência a ser aleatória, se ele não está em qualquer destes conjuntos de medida 0 especiais. Desde que a união de uma coleção contável de conjuntos de medida 0 tem medida 0, essa definição leva imediatamente para o teorema de que existe um conjunto de medida 1 de sequências aleatórias. Note que se nós identificarmos o espaço de Cantor de sequências binárias com o intervalo [0,1] de números reais, a medida no espaço de Cantor concorda com a medida de Lebesgue.

A caracterização de martingale transmite a intuição de que nenhum procedimento eficaz deve ser capaz de fazer dinheiro apostando contra uma seqüência aleatória. Uma martingale d é uma estratégia de apostas. d lê uma cadeia finita w e aposta dinheiro no próximo bit. Aposta-se alguma fração do seu dinheiro que o próximo bit será 0, e depois restante do seu dinheiro que o próximo bit será 1. d dobra o dinheiro que foi colocado no bit que realmente ocorreu, e ele perde o resto do dinheiro. d ( w ) é a quantidade de dinheiro que ele tem depois de ver a cadeia w . Uma vez que a aposta foi feita depois de ver a cadeia w pode ser calculado a partir dos valores”d” ( w ), d ( w0), e “d ( w1), calculando a quantidade de dinheiro que tem é equivalente para calcular a aposta. A caracterização martingale diz que nenhuma estratégia de apostas implementável por qualquer computador (mesmo no sentido fraco de estratégias construtivas, que não são necessariamente computáveis) pode ganhar dinheiro apostando em uma seqüência aleatória.

Propriedades e exemplos de seqüências aleatórias de Martin-Löf

• A probabilidade de parada de Chaitin Ω é um exemplo de uma sequência aleatória.

• RAND ^c (o complemento da RAND) é um subconjunto de medida 0 do conjunto de todas as sequências infinitas. Isso está implícito pelo fato de que cada cobertura construtiva nula abrange um conjunto de medida 0, existem apenas uma quantidade contável de coberturas nulas, e uma união contável de conjuntos de medida 0 tem medida 0. Isto implica que RAND é um subconjunto de medida 1 do conjunto de todas as sequências infinitas.

• Cada seqüência aleatória é Normal.

• Existe uma cobertura construtiva nula da RAND ^c . Isto significa que todos os testes eficazes para a aleatoriedade (isto é, cobertura construtiva nula) são, em certo sentido, subsumido por este teste “universal” para aleatoriedade, uma vez que qualquer seqüência que passa neste único teste de aleatoriedade vai passar em todos os testes para aleatoriedade . (Martin-Löf 1966)

• Existe um martingale construtivo “universal“ d. Este martingale é universal no sentido de que, dado qualquer martingale construtivo d , se d sucede em uma seqüência, então,d sucede nessa sequência também. Assim, d sucede em cada seqüência na RAND ^c (mas, uma vez que d é construtivo, ele não sucede em nenhuma sequência em RAND). (Schnorr 1971)

• A classe RAND é um $\ Sigma_{2}^{0}$ subconjunto do espaço de Cantor, onde $\ Sigma_{2}^{0}$ refere-se ao segundo nível da hierarquia aritmética. Isso ocorre porque uma seqüência S está em RAND se e somente se existe algum conjunto aberto na cobertura nula eficaz universal que não contém S ; esta propriedade pode ser vista para ser definível por uma $\ Sigma_{2}^{0}$ fórmula.

• Há uma seqüência aleatória que é $\ Delta_{2}^{0}$, ou seja, computável em relação a um oráculo para o problema da parada. (Schnorr 1971). A constante Ω de Chaitin é um exemplo de uma tal sequência.

• Nenhuma seqüência aleatória é decidível, computavelmente enumerável ou co-computavelmente-enumerável. Uma vez que estas correspondem aos $\ Delta_{1}^{0}$, $\ Sigma_{1}^{0}$ e $\ Pi_{1}^{0}$ níveis da hierarquia aritmética , isso significa que $\ Delta_{2}^{0}$ é o nível mais baixo da hierarquia aritmética onde seqüências aleatórias podem ser encontradas.

• Toda sequência é Turing redutível para uma sequência aleatória. (Kučera 1985/1989, GaCS 1986). Assim, existem sequências aleatórias de grau Turing arbitrariamente elevado.

Aleatoriedade Relativa

Como cada uma das definições equivalentes de uma seqüência aleatória de Martin-Löf é baseada no que é computável por alguma máquina de Turing, pode-se, naturalmente, perguntar o que é computável por uma máquina oráculo de Turing. Para um oráculo fixo A , uma sequência B , que não é apenas aleatória, mas na verdade, satisfaz as definições equivalentes para a computabilidade relativa à A (por exemplo, nenhum martingale que é construtivo em relação ao Oráculo A sucede em B ) é dito ser aleatório em relação à A . Duas sequências, enquanto elas próprias forem aleatórias, podem conter informações muito semelhantes, e, portanto, não vai ser aleatória em relação à outra. Sempre que há uma redução de Turing a partir de uma sequência para outra, a segunda sequência não pode ser aleatória em relação à primeira, assim como sequências computáveis ​​são, eles próprios, não aleatórios; em particular, isto significa que a constante Ω de Chaitin não é aleatória em relação ao problema da parada.

Um resultado importante, relacionado à aleatoriedade relativa é o teorema de van Lambalgen, que afirma que se C é a seqüência composta de A e B intercalando o primeiro bit de A , o primeiro bit de B , o segundo bit de A , o segundo bit de B , e assim por diante, em seguida, C é algoritmicamente aleatória se e somente se A é algoritmicamente aleatória, e B é algoritmicamente aleatória em relação à A . Uma consequência estreitamente relacionada é que se A e B são ambas aleatórias, então, A é aleatória em relação à B se e somente se B é aleatória em relação à A .

Mais forte do que a aleatoriedade de Martin-Löf

Aleatoriedade Relativa nos dá a primeira noção que é mais forte do que a aleatoriedade de Martin-Löf, que é a aleatoriedade em relação a algum oráculo fixo A . Para qualquer oráculo, isto é, pelo menos, tão forte, e para a maioria dos oráculos, é estritamente mais forte, uma vez que haverá sequências aleatórias de Martin-Löf que não são aleatórios relativamente ao oráculo A . Oráculos importantes muitas vezes considerados são o problema da parada, $\ emptyset'$, e o oráculo do n-ésimo pulo, $\ emptyset^{(n)}$, uma vez que estes oráculos são capazes de responder a perguntas específicas que surgem naturalmente. Uma sequência que é aleatória em relação ao oráculo $\ emptyset^{(n-1)}$ é chamada de n - aleatória; uma sequência é 1-aleatória, portanto, se, e somente se for Martin-Löf aleatória. Uma sequência que é n - aleatória para cada n é chamada de aritmeticamente aleatória. As sequências n - aleatórias às vezes surgem quando se consideram propriedades mais complicadas. Por exemplo, existem apenas $\ Delta_{2}^{0}$ conjuntos muito contáveis, então pode-se pensar que estes devem ser não-aleatórios. No entanto, a probabilidade de parada Ω é $\ Delta_{2}^{0}$ e 1-aleatório; é só depois que a 2-aleatoriedade é alcançada que é impossível para um conjunto aleatório de ser $\ Delta_{2}^{0}$.

Mais fraco do que a aleatoriedade de Martin-Löf

Além disso, existem várias noções de aleatoriedade que são mais fracas do que a aleatoriedade de Martin-Löf. Algumas delas são 1-aleatoriedade fracas, aleatoriedade de Schnorr, aleatoriedade computável, aleatoriedade parcialmente computável. Adicionalmente, a aleatoriedade de Kolmogorov-Loveland é conhecida por ser mais forte do que a aleatoriedade de Martin-Löf, mas não se sabe se é realmente mais fraca. <! - Se alguém quer definir estes, eles podem ir em frente. ->

No extremo oposto do espectro da aleatoriedade existe a noção de um conjunto K-trivial. Estes conjuntos são anti -aleatórios, em que todos segmentos iniciais tem a menor K-complexidade de acordo com uma constante b. Ou seja, $K(w)\ leqK(|w|)+b$ para cada segmento inicial w.

Ver também

• Random sequence
• Gregory Chaitin
• Estocástico
• Método de Monte Carlo
• K-trivial set

Referências

• Downey, Rod; Denis R. (1 de setembro de 2006). «Calibrating Randomness». Bulletin of Symbolic Logic. 12 (03): 411–491. ISSN 1943-5894. doi:10.2178/bsl/1154698741 

• Gács, Péter (1 de agosto de 1986). «Every sequence is reducible to a random one». Information and Control. 70 (2–3): 186-192. doi:10.1016/S0019-9958(86)80004-3 </ref>

• Kučera, A. (1985). «Measure, Π₁⁰-classes and complete extensions of PA». Recursion Theory Week. Lecture Notes in Mathematics 1141, Springer-Verlag. pp. 245–259 

• Kučera, A. (1989). «On the use of diagonally nonrecursive functions». Studies in Logic and the Foundations of Mathematics. 129. North-Holland. pp. 219–239 

• Levin, L. (1973). «On the notion of a random sequence». Soviet Mathematics Doklady. 14: 1413–1416 

• Li, M.; Vitanyi, P. M. B. (1997). An Introduction to Kolmogorov Complexity and its Applications Second ed. Berlin: Springer-Verlag  !CS1 manut: Nomes múltiplos: lista de autores (link)

• Martin-Löf, Per. «The definition of random sequences». Information and Control. 9 (6): 602-619. doi:10.1016/s0019-9958(66)80018-9 

• Nies, André (2009). Computability and randomness. Col: Oxford Logic Guides. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034 

• Schnorr, C. P. (1971). «A unified approach to the definition of a random sequence». Mathematical Systems Theory. 5 (3): 246–258. doi:10.1007/BF01694181 

• Schnorr, C.P. «Process complexity and effective random tests». Journal of Computer and System Sciences. 7 (4): 376-388. doi:10.1016/s0022-0000(73)80030-3 

• Ville, J. (1939). Etude critique de la notion de collectif. Paris: Gauthier-Villars