Teorema do macaco infinito

Um macaco escrevendo indefinidamente acabará quase certamente por escrever uma peça de Shakespeare

O teorema do macaco infinito afirma que um macaco digitando aleatoriamente em um teclado por um intervalo de tempo infinito irá quase certamente criar um texto qualquer escolhido, como por exemplo a obra completa de William Shakespeare.

Pode-se também pensar que, com infinitos macacos infinitos, algum deles irá quase certamente criar um texto qualquer escolhido como primeiro texto a ser digitado.

Neste contexto, "quase certamente" é um termo matemático com um significado preciso, enquanto que o "macaco" é apenas uma imagem, não um símio verdadeiro; trata-se de uma metáfora para um dispositivo abstracto que produza uma sequência aleatória de letras ad infinitum. O teorema ilustra os perigos do raciocínio sobre o infinito ao imaginar um número muito grande mas finito, e vice versa. A idade do universo é diminuída relativamente pelo tempo que levaria a um macaco para obter um texto igual ao Hamlet, de modo que num sentido físico tal nunca aconteceria.

Variantes do teorema incluem múltiplos dispositivos de escrita, e o texto pode variar entre uma biblioteca inteira e uma simples e pequena frase. O problema apareceu pela primeira vez no artigo chamado Mécanique Statistique et Irréversibilité do matemático Émile Borel no ano de 1913.

Solução

Prova Direta

Há uma prova direta desse teorema. Se dois eventos são estatisticamente independentes (isto é, um não afeta o resultado do outro), então a probabilidade de que ambos aconteçam é igual ao produto das probabilidades de que cada um aconteça independentemente. Exemplo: se a chance de chover em Sydney num certo dia é de 0,3 e a chance de um terremoto ocorrer em São Francisco é de 0,008, então a chance de que os dois aconteçam ao mesmo tempo é de 0.3 × 0.008 = 0.0024.

Suponha que uma máquina de escrever tenha 50 teclas, e a palavra a ser escrita seja "banana". Teclando-se aleatoriamente, a chance de a primeira letra teclada ser b é 1/50, e a chance de a segunda ser a é também 1/50, e assim por diante, porque os eventos são independentes. Então a chance de as seis letras formarem banana é

(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50)⁶. Ou seja, 1 em 15625000000 (uma em quinze bilhões e seiscentos e vinte e cinco milhões).

Pela mesma razão, a chance de que as 6 próximas letras formem banana é também (1/50)⁶, e assim por diante.

Disto, a chance de não ser escrito banana num dado bloco de 6 letras é 1 − (1/50)⁶. Como cada bloco é feito independentemente, a chance X_n de não ser escrito banana em qualquer dos primeiros n blocos de 6 letras é

$X_{n}=\left(1-{\frac {1}{50^{6}}}\right)^{n}.$

Quando n aumenta, X_n diminui. Para um n de um milhão, X_n é 99.99%, mas para um n de 10 bilhões X_n é 53% e para um n de 100 bilhões é 0.17%. Quando n se aproxima do infinito, a probabilidade X_n se aproxima de zero; isto é, tendo-se um n grande o suficiente, X_n pode ser tão pequeno quanto se deseje.

O mesmo argumento mostra por que pelo menos um dos infinitamente muitos macacos irá (quase certamente) produzir um texto tão rapidamente quanto o seria por um digitador humano perfeitamente sem erros copiando do original. Nesse caso X_n = (1 − (1/50)⁶)ⁿ onde X_n representa a probabilidade de nenhum dos primeiros n macacos escrever banana corretamente na primeira tentativa. Quando consideramos 100 bilhões de macacos, a probabilidade cai para 0.17%, e aumentando-se o número de macacos n ao infinito o valor de X_n — a probabilidade de os macacos não reproduzirem o texto dado — cai para zero. Isso equivale a afirmar que a probabilidade de um ou mais de infinitos de macacos produzirá um texto dado na primeira tentativa é de 100%, ou que é quase certo que fará.

Cadeias infinitas

As duas afirmações acima podem ser explicadas mais geral e compactamente em termos de cadeias, que são sequências de caracteres escolhidos de algum alfabeto finito:

• Dada uma cadeia infinita onde cada caractere é escolhido uniforme e aleatoriamente, qualquer cadeia finita dada quase certamente ocorre como uma subcadeia em alguma posição (e, de fato, infinitas posições).
• Dada uma sequência infinita de cadeias infinitas, onde cada caractere de cada cadeia é escolhido uniforme e aleatoriamente, qualquer cadeia finita quase certamente ocorre como um prefixo de uma dessas cadeias (e, de fato, como um prefixo de infinitamente muitas dessas cadeias na sequência).

Ambos são deduzidos facilmente do segundo Lema de Borel-Cantelli. Para o segundo teorema, seja E_k o evento no qual a k-ésima cadeia começa com o texto dado. Por ter uma probabilidade fixa diferente de zero p de ocorrer, E_k é independente, e a soma abaixo diverge,

$\sum _{i=1}^{\infty }P(E_{k})=\sum _{i=1}^{\infty }p=\infty ,$

a probabilidade de infinitamente muitos dos E_k ocorrerem é 1. O primeiro teorema é demonstrado de forma similar; pode-se dividir a cadeia aleatória pelos blocos não sobrepostos que correspondem ao texto desejado, e fazer E_k o evento onde o k-ésimo bloco é igual à cadeia desejada.

Probabilidades

Ignorando pontuação, espaçamento e diferença entre maiúsculas e minúsculas, um macaco escrevendo letras de maneira uniforme e aleatória tem uma chance em 26 de digitar corretamente a primeira letra de Hamlet. Ele tem uma chance em 676 (26 × 26) de digitar as primeiras duas letras. Devido ao fato da probabilidade encolher exponencialmente, para 20 letras já se terá apenas uma chance em 26²⁰ = 19.928.148.895.209.409.152.340.197.376, equivalente à probabilidade de se comprar 4 bilhetes de loteria consecutivamente e ganhar o prêmio principal de cada vez.

Ligações externas

• «The Parable of the Monkeys»