Sequência aleatória - Random sequence

O conceito de sequência aleatória é essencial na teoria da probabilidade e na estatística . O conceito geralmente se baseia na noção de uma seqüência de variáveis ​​aleatórias e muitas discussões estatísticas começam com as palavras "sejam X 1 , ..., X n variáveis ​​aleatórias independentes ...". No entanto, como DH Lehmer afirmou em 1951: "Uma sequência aleatória é uma noção vaga ... na qual cada termo é imprevisível para os não iniciados e cujos dígitos passam em um certo número de testes tradicionais com estatísticos".

A teoria de probabilidade axiomática evita deliberadamente a definição de uma sequência aleatória. A teoria de probabilidade tradicional não afirma se uma sequência específica é aleatória, mas geralmente prossegue discutindo as propriedades de variáveis ​​aleatórias e sequências estocásticas assumindo alguma definição de aleatoriedade. A escola Bourbaki considerou a afirmação "consideremos uma sequência aleatória" um abuso de linguagem .

História antiga

Émile Borel foi um dos primeiros matemáticos a abordar formalmente a aleatoriedade em 1909. Em 1919, Richard von Mises deu a primeira definição de aleatoriedade algorítmica, que foi inspirada pela lei dos grandes números, embora tenha usado o termo coletivo em vez de sequência aleatória. Usando o conceito da impossibilidade de um sistema de jogo , von Mises definiu uma sequência infinita de zeros e uns como aleatória se não for enviesada por ter a propriedade de estabilidade de frequência, ou seja, a frequência dos zeros vai para 1/2 e cada sub-sequência nós pode selecionar a partir dele por um método "adequado" de seleção também não é tendencioso.

O critério de seleção de subseqüência imposto por von Mises é importante, porque embora 0101010101 ... não seja tendencioso, ao selecionar as posições ímpares, obtemos 000000 ... que não é aleatório. Von Mises nunca formalizou totalmente sua definição de uma regra de seleção apropriada para subseqüências, mas em 1940 Alonzo Church a definiu como qualquer função recursiva que, tendo lido os primeiros N elementos da seqüência, decide se deseja selecionar o elemento número  N  + 1. Church foi um pioneiro no campo das funções computáveis, e a definição que ele fez baseou-se na Tese de Church Turing para computabilidade. Esta definição é freqüentemente chamada de aleatoriedade de Mises-Church .

Abordagens modernas

Durante o século 20, várias abordagens técnicas para definir sequências aleatórias foram desenvolvidas e agora três paradigmas distintos podem ser identificados. Em meados dos anos 1960, AN Kolmogorov e DW Loveland propuseram independentemente uma regra de seleção mais permissiva. Na visão deles, a definição da função recursiva de Church era muito restritiva, pois lia os elementos em ordem. Em vez disso, eles propuseram uma regra baseada em um processo parcialmente computável que, tendo lido quaisquer N elementos da sequência, decide se deseja selecionar outro elemento que ainda não foi lido. Essa definição é freqüentemente chamada de estocasticidade de Kolmogorov-Loveland . Mas este método foi considerado muito fraco por Alexander Shen, que mostrou que existe uma sequência estocástica de Kolmogorov-Loveland que não se conforma com a noção geral de aleatoriedade.

Em 1966, Per Martin-Löf introduziu uma nova noção que agora é geralmente considerada a noção mais satisfatória de aleatoriedade algorítmica . Sua definição original envolvia a teoria da medida, mas mais tarde foi mostrado que ela pode ser expressa em termos de complexidade de Kolmogorov . A definição de Kolmogorov de uma string aleatória era que ela é aleatória se não tiver uma descrição mais curta do que ela mesma por meio de uma máquina de Turing universal .

Três paradigmas básicos para lidar com sequências aleatórias surgiram agora:

  • A abordagem teórica de frequência / medida . Essa abordagem começou com o trabalho de Richard von Mises e Alonzo Church. Na década de 1960, Per Martin-Löf notou que os conjuntos que codificam tais propriedades estocásticas baseadas em frequência são um tipo especial de conjuntos de zero de medida , e que uma definição mais geral e suave pode ser obtida considerando todos os conjuntos de zero de medida efetivamente.
  • A abordagem de complexidade / compressibilidade . Este paradigma foi defendido por AN Kolmogorov junto com contribuições de Leonid Levin e Gregory Chaitin . Para sequências finitas, Kolmogorov define a aleatoriedade de uma string binária de comprimento n como a entropia (ou complexidade de Kolmogorov ) normalizada pelo comprimento n . Em outras palavras, se a complexidade de Kolmogorov da string for próxima de n , ela é muito aleatória; se a complexidade estiver muito abaixo de n , não é tão aleatória. O conceito duplo de aleatoriedade é compressibilidade - quanto mais aleatória uma sequência, menos compressível e vice-versa.
  • A abordagem da previsibilidade . Este paradigma é devido a Claus P. Schnorr e usa uma definição ligeiramente diferente de martingales construtivos do que os martingales usados ​​na teoria de probabilidade tradicional. Schnorr mostrou como a existência de uma estratégia de apostas seletivas implicava a existência de uma regra de seleção para uma subseqüência enviesada. Se alguém requer apenas um martingale recursivo para ter sucesso em uma sequência, em vez de ter sucesso construtivamente em uma sequência, então obtém-se o conceito de aleatoriedade recursiva. Yongge Wang mostrou que o conceito de aleatoriedade recursiva é diferente do conceito de aleatoriedade de Schnorr.

Na maioria dos casos, teoremas relacionando os três paradigmas (freqüentemente equivalência) foram provados.

Veja também

Referências

Notas

links externos