Sequência algoritmicamente aleatória - Algorithmically random sequence

Intuitivamente, uma sequência algorítmica aleatória (ou sequência aleatória ) é uma sequência de dígitos binários que parece aleatória para qualquer algoritmo executado em uma máquina de Turing universal (sem prefixo ou não) . A noção pode ser aplicada analogamente a sequências em qualquer alfabeto finito (por exemplo, dígitos decimais). As sequências aleatórias são objetos-chave de estudo na teoria da informação algorítmica .

Como diferentes tipos de algoritmos são às vezes considerados, desde algoritmos com limites específicos em seu tempo de execução até algoritmos que podem fazer perguntas a uma máquina oráculo , existem diferentes noções de aleatoriedade. O mais comum deles é conhecido como aleatoriedade de Martin-Löf ( aleatoriedade K ou aleatoriedade 1 ), mas também existem formas mais fortes e fracas de aleatoriedade. Quando o termo "algoritmicamente aleatório" é usado para se referir a uma determinada sequência única (finita ou infinita) sem esclarecimento, geralmente significa "incompressível" ou, no caso de a sequência ser infinita e prefixar algoritmicamente aleatório (ou seja, K -incompressível), "Martin-Löf – Chaitin random".

É importante eliminar a ambigüidade da aleatoriedade algorítmica com a aleatoriedade estocástica. Ao contrário da aleatoriedade algorítmica, que é definida para processos computáveis ​​(e, portanto, determinísticos), a aleatoriedade estocástica é geralmente considerada uma propriedade de uma sequência que é a priori conhecida por ser gerada (ou é o resultado de) por um estocástico independente e equiprovável distribuído de forma idêntica processar.

Como as sequências infinitas de dígitos binários podem ser identificadas com números reais no intervalo da unidade, as sequências binárias aleatórias são freqüentemente chamadas de números reais aleatórios (algoritmicamente) . Além disso, sequências binárias infinitas correspondem a 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 (binárias) de Martin-Löf é denotada por RAND ou MLR.

História

A primeira definição adequada de uma sequê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 para definir uma sequência aleatória como aquela que passou em todos os testes para aleatoriedade; no entanto, a noção precisa de um teste de aleatoriedade foi deixada vaga. O insight principal de Martin-Löf foi usar a teoria da computação para definir formalmente a noção de um teste de aleatoriedade. Isso contrasta com a ideia de aleatoriedade na probabilidade ; nessa teoria, nenhum elemento particular de um espaço amostral pode ser considerado aleatório.

Desde o seu início, a aleatoriedade de Martin-Löf demonstrou admitir muitas caracterizações equivalentes - em termos de compressão , testes de aleatoriedade e jogos de azar - que têm pouca semelhança externa com a definição original, mas cada uma das quais satisfaz nossa noção intuitiva de propriedades que aleatórias as sequências devem ter: sequências aleatórias devem ser incompressíveis, devem passar por testes estatísticos de aleatoriedade e deve ser difícil ganhar dinheiro apostando nelas. A existência dessas múltiplas definições de aleatoriedade de Martin-Löf e a estabilidade dessas definições sob diferentes modelos de computação dão evidências de que a aleatoriedade de Martin-Löf é uma propriedade fundamental da matemática e não um acidente do modelo particular de Martin-Löf. A tese de que a definição de aleatoriedade de Martin-Löf "corretamente" captura a noção intuitiva de aleatoriedade foi chamada de Tese de Martin-Löf-Chaitin ; é um tanto semelhante à tese de Church-Turing .

Três definições equivalentes

A definição original de Martin-Löf de uma sequência aleatória era em termos de coberturas nulas construtivas; ele definiu uma sequência como aleatória se não estiver contida em qualquer capa. Gregory Chaitin , Leonid Levin e Claus-Peter Schnorr provaram uma caracterização em termos de complexidade algorítmica : uma sequência é aleatória se houver um limite uniforme na compressibilidade de seus segmentos iniciais. Schnorr deu uma terceira definição equivalente em termos de martingales . O livro de Li e Vitanyi, Uma introdução à complexidade de Kolmogorov e suas aplicações, é a introdução padrão a essas idéias.

  • Complexidade algorítmica (Chaitin 1969, Schnorr 1973, Levin 1973): A complexidade algorítmica (também conhecida como complexidade de Kolmogorov (sem prefixo) ou complexidade do tamanho do programa) 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 sequência w um número natural K (w) que, intuitivamente, mede o comprimento mínimo de um programa de computador (escrito em alguma linguagem de programação fixa) que não recebe entrada e produzirá w quando executado. A complexidade deve ser livre de prefixo: O programa (uma sequência de 0 e 1) é seguido por uma string infinita de 0s, e o comprimento do programa (assumindo que ele pare) inclui o número de zeros à direita do programa que a máquina de Turing universal lê. O requisito adicional é necessário porque podemos escolher um comprimento de forma que o comprimento codifique as informações sobre a substring. Dado um número natural ce uma sequência w , dizemos que w é c -incompressível se .
Uma sequência infinita S é Martin-Löf aleatória se e somente se houver uma constante c tal que todos os prefixos finitos de S sejam c- incompressíveis.
  • Coberturas nulas construtivas (Martin-Löf 1966): Esta é a definição original de Martin-Löf. Para uma string binária finita w , deixamos C w denotar 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 do produto μ ( C w ) do cilindro gerado por w é definida como 2 - | w | . Cada subconjunto aberto do espaço 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 qualquer sequência. Um conjunto aberto efetivo é um conjunto aberto que é a união da sequência de conjuntos abertos básicos determinados por uma sequência recursivamente enumerável de cadeias binárias. Uma cobertura nula construtiva ou conjunto de medida efetiva 0 é uma sequência recursivamente enumerável de conjuntos abertos efetivos de modo que e para cada número natural i . Cada cobertura nula efetiva determina um conjunto de medida 0, ou seja, a interseção dos conjuntos .
Uma sequência é definida como Martin-Löf aleatória se não estiver contida em nenhum conjunto determinado por uma cobertura nula construtiva.
  • Martingais construtivas (Schnorr 1971): Uma martingala é uma função de tal modo que, para todas as cadeias finitas w , , onde é a concatenação das cordas um e b . Isso é chamado de "condição de justiça": se um martingale for visto como uma estratégia de aposta, a condição acima exige que o apostador jogue contra probabilidades justas. Um martingala d é dito ter sucesso em uma sequência S se onde é os primeiros n bits do S . Um martingale d é construtivo (também conhecido como fracamente computável , semicomputável inferior ) se existe uma função computável tal que, para todas as cadeias binárias finitas w
  1. para todos os inteiros positivos t ,
Uma sequência Martin-Löf é aleatória se, e somente se, nenhum martingale construtivo for bem-sucedido.

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 de cobertura nula transmite a intuição de que um número real aleatório não deve ter nenhuma propriedade que seja "incomum". Cada conjunto de medida 0 pode ser considerado uma propriedade incomum. Não é possível para uma sequência estar em nenhum conjunto de medida 0, porque cada conjunto de um ponto tem medida 0. A ideia de Martin-Löf era limitar a definição para medir 0 conjuntos que são efetivamente descritíveis; a definição de uma cobertura nula efetiva determina uma coleção contável de conjuntos de medida 0 efetivamente descritíveis e define uma sequência como aleatória se não estiver em nenhum desses conjuntos de medida 0 em particular. Como a união de uma coleção contável de conjuntos de medida 0 tem medida 0, essa definição leva imediatamente ao teorema de que existe um conjunto de medida 1 de sequências aleatórias. Observe que se 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 do martingale transmite a intuição de que nenhum procedimento eficaz deve ser capaz de ganhar dinheiro apostando contra uma sequência aleatória. Um martingale d é uma estratégia de aposta. d lê uma string finita w e aposta dinheiro no próximo bit. Ele aposta uma fração de seu dinheiro que o próximo bit será 0, e o restante de seu dinheiro que o próximo bit será 1. d dobra o dinheiro que colocou no bit que realmente ocorreu e perde o resto. d ( w ) é a quantidade de dinheiro que ele possui depois de ver a string w . Uma vez que a aposta feita depois de ver a seqüência w pode ser calculada a partir dos valores d ( w ), d ( w 0) e d ( w 1), calcular a quantidade de dinheiro que ela possui é equivalente a calcular a aposta. A caracterização do martingale diz que nenhuma estratégia de aposta 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 sequência aleatória.

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

  • A probabilidade de parada de Chaitin Ω é um exemplo de sequência aleatória.
  • RAND c (o complemento de RAND) é um subconjunto de medida 0 do conjunto de todas as sequências infinitas. Isso está implícito no fato de que cada cobertura nula construtiva cobre um conjunto de medida 0, há apenas muitas coberturas nulas construtivas contáveis ​​e uma união contável de conjuntos de medida 0 tem medida 0. Isso implica que RAND é um subconjunto de medida 1 do conjunto de todas as sequências infinitas.
  • Cada sequência aleatória é normal .
  • Há uma cobertura nula construtiva de RAND c . Isso significa que todos os testes eficazes de aleatoriedade (ou seja, coberturas nulas construtivas) são, em certo sentido, subsumidos por esse teste universal de aleatoriedade, uma vez que qualquer sequência que passe nesse único teste de aleatoriedade passará em todos os testes de aleatoriedade. (Martin-Löf 1966)
  • Existe um martingale construtivo universal d . Esse martingale é universal no sentido de que, dado qualquer martingale construtivo d , se d é bem-sucedido em uma sequência, então d também é bem-sucedido nessa sequência. Assim, d é bem-sucedido em todas as sequências no RAND c (mas, como d é construtivo, ele não tem sucesso em nenhuma sequência no RAND). (Schnorr 1971)
  • A classe RAND é um subconjunto do espaço Cantor, onde se refere ao segundo nível da hierarquia aritmética . Isso ocorre porque uma sequência S está em RAND se e somente se houver algum conjunto aberto na cobertura nula efetiva universal que não contenha S ; esta propriedade pode ser definida por uma fórmula.
  • Existe uma sequência aleatória que é , isto é, computável em relação a um oráculo para o problema de Halting. (Schnorr 1971) O Ω de Chaitin é um exemplo de tal sequência.
  • Nenhuma sequência aleatória é decidível , computavelmente enumerável ou co-computavelmente enumerável . Uma vez que estes correspondem a , , e os níveis da hierarquia aritmética , isto significa que é o nível mais baixo na hierarquia aritmética onde sequências aleatórias podem ser encontradas.
  • Cada sequência é Turing redutível a alguma sequência aleatória. (Kučera 1985/1989, Gács 1986). Assim, existem sequências aleatórias de grau de Turing arbitrariamente alto .

Aleatoriedade relativa

Como cada uma das definições equivalentes de uma sequê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 de fato, satisfaz as definições equivalentes para computabilidade em relação a A (por exemplo, nenhum martingale que seja construtivo em relação ao oráculo A é bem-sucedido em B ) é considerado aleatório em relação para um . Duas sequências, embora sejam aleatórias, podem conter informações muito semelhantes e, portanto, nenhuma será aleatória em relação à outra. Sempre que há uma redução de Turing de uma sequência para outra, a segunda sequência não pode ser aleatória em relação à primeira, da mesma forma que as sequências computáveis ​​são elas mesmas não aleatórias; em particular, isso significa que o Ω de Chaitin não é aleatório em relação ao problema da parada .

Um resultado importante relacionado à aleatoriedade relativa é o teorema de van Lambalgen , que afirma que se C é a sequê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, então C é algoritmicamente aleatório, se e apenas se um é algoritmicamente aleatória, e B é algoritmicamente aleatório em relação à Um . Uma consequência estreitamente relacionado é que, se A e B são ambos aleatório-se, em seguida, uma é aleatório em relação ao B se e somente se B é aleatória em relação ao um .

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

Aleatoriedade relativa nos dá a primeira noção que é mais forte do que Martin-Löf aleatoriedade, que é a aleatoriedade em relação a algum oráculo fixo A . Para qualquer Oracle, isto é, pelo menos, tão forte, e para a maioria dos oráculos, é estritamente mais forte, uma vez que haverá sequências aleatórias Martin-Löf que não são aleatórios relativamente ao oráculo Uma . Oráculos importantes muitas vezes considerados são o problema da parada, eo n º oráculo salto, como estes oráculos são capazes de responder a questões específicas que surgem naturalmente. Uma sequência que é aleatória em relação ao oráculo é chamada de n- aleatória; uma sequência é 1-aleatória, portanto, se e somente se for aleatória de Martin-Löf. Uma sequência que é n- aleatória para cada n é chamada aritmeticamente aleatória. As sequências n- aleatórias às vezes surgem ao considerar propriedades mais complicadas. Por exemplo, existem apenas muitos conjuntos contáveis , então pode-se pensar que eles não devem ser aleatórios. No entanto, a probabilidade de parada Ω é 1-aleatória; é somente depois que a aleatoriedade 2 é alcançada que é impossível que um conjunto aleatório o seja .

Mais fraco 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. Alguns deles são 1-aleatoriedade fraca, aleatoriedade Schnorr, aleatoriedade computável, aleatoriedade computável parcial. Yongge Wang mostrou que a aleatoriedade de Schnorr é diferente da aleatoriedade computável. Além disso, sabe-se que a aleatoriedade de Kolmogorov-Loveland não é mais forte do que a aleatoriedade de Martin-Löf, mas não se sabe se é realmente mais fraca.

Na extremidade oposta do espectro de aleatoriedade, há a noção de um conjunto K-trivial . Esses conjuntos são anti-aleatórios em que todo o segmento inicial é logaritmicamente compressível (ou seja, para cada segmento inicial w), mas eles não são computáveis.

Veja também

Referências

Leitura adicional

  • Downey, Rod; Hirschfeldt, Denis R .; Nies, André; Terwijn, Sebastiaan A. (2006). "Calibrando a aleatoriedade" . O Boletim de Lógica Simbólica . 12 (3/4): 411–491. CiteSeerX  10.1.1.135.4162 . doi : 10.2178 / bsl / 1154698741 . Arquivado do original em 02/02/2016.
  • Gács, Péter (1986). "Cada sequência é redutível a uma sequência aleatória" (PDF) . Informação e controle . 70 (2/3): 186–192. doi : 10.1016 / s0019-9958 (86) 80004-3 .
  • Kučera, A. (1985). "Medir, Π0
    1
    -classes e extensões completas de PA ". Recursion Theory Week . Lecture Notes in Mathematics. 1141. Springer-Verlag. pp. 245–259. doi : 10.1007 / BFb0076224 . ISBN . 978-3-540-39596-6.
  • Kučera, A. (1989). “Sobre o uso de funções não recursivas diagonalmente”. Estudos em lógica e os fundamentos da matemática . 129 . Holanda do Norte. pp. 219–239.
  • Levin, L. (1973). “Sobre a noção de uma sequência aleatória”. Matemática Soviética - Doklady . 14 : 1413–1416.
  • Li, M .; Vitanyi, PMB (1997). Uma introdução à complexidade de Kolmogorov e suas aplicações (segunda ed.). Berlim: Springer-Verlag.
  • Ville, J. (1939). Etude critique de la notion de collectif . Paris: Gauthier-Villars.