Teorema de la mona infinita

Teorema de la mona infinita

D'acort en el segon enunciat Borel-Cantelli, en suficient temps, un chimpansé escrivint a l'encert podria escriure una obra de Shakespeare (o qualsevol atre text).

La teorema de la mona infinita afirma que un mona pulsant tecles a l'encert sobre un teclat durant un periodo de temps indefinit podrà escriure finalment qualsevol text donat. En el món angloparlante, se sol utilisar el Hamlet de Shakespeare com a eixemple, mentres en el món hispanohablante s'utilisa el Quixot de Cervantes.

En este context, el terme casi segurament és un terme matemàtic en un sentit precís i el "mona" no és en realitat una mona, sino que es tracta d'una metàfora de la creació d'una seqüència aleatòria de lletres ad infinitum.

L'idea original va ser plantejada per Émile Borel, en 1913, en el seu llibre Mécanique Statistique et Irréversibilité. Borel va dir que si un milló de mones mecanografiaran dèu hores al dia era extremadament improvable que pogueren produir alguna cosa que fora igual a lo contingut en els llibres de les biblioteques més riques del món i aixina i tot, en comparació, seria encara més inverosímil que les lleis de l'estadística anaren violades, siquiera someramente. Per a Borel, el propòsit de la metàfora de les mones era ilustrar la magnitut d'un acontenyiment extraordinàriament improvable.

Despuix de 1970, la popular image de les mones es va estendre fins al infinit, convertint-se en que si un infinit número de mones mecanografiaran per un interval indefinit de temps produirien text llegible. Insistir en abdós infinits és, esperem, excessiu. Una sola mona immortal que eixecutara infinitament teclejos sobre una màquina d'escriure podria escriure qualsevol text donat, ademés, el text seria produït un infinit número de voltes.

Bosqueig intuïtiu de la teorema

La teorema de la mona infinita és directament demostradora, inclús sense necessitat de resultats més alvançats. Si dos acontenyiments són estadísticament independents, volent dir açò que cap d'ells afecta al resultat de l'atre, llavors, la provabilitat de que abdós succeïxquen és igual al producte de les provabilitats individuals de que succeïxca cada u. Per eixemple, si les provabilitats de pluja en Sídney en un dia en particular és 0,3 i la provabilitat de que eixe mateix dia hi haja un terremot en Sant Francisco és d'un 0,8, llavors, la provabilitat de que abdós succeïxquen el mateix dia és 0,3x0,8=0,24.

Ara, suponent que un teclat tinga 50 tecles i la paraula a ser escrita és “banana”, mecanografiando a l'encert, la provabilitat de que la primera lletra escrita siga b és 1/50, de que la segona siga a és 1/50, etc. Dits events són estadísticament independents, aixina que la provabilitat de que les sis primeres lletres escrites siguen “banana” és 1/50⁶.

Ara, les provabilitats de no escriure “banana” en cada bloc de 6 lletres és 1-1/50⁶. Ya que cada bloc deu ser considerat independentment, la provabilitat X de no escriure “banana” en els n primers de 6 lletres és X=(1-1/50⁶)ⁿ. A mida que n aumenta, X es reduïx. Per a n=1.000.000, X=99.99%, pero per a un n igual a 10 000 millons, X=53% i per a una n=100 000 millons és un 0,17%. A mida que n s'acosta a infinit, la provabilitat de X tendix a zero. Açò és, fent n lo suficientment gran, X pot ser tan chicotet com un vullga (sense que aplegue a zero). Si consideràrem les voltes que s'escriuria “banana” entre blocs de 6 lletres, X tendiria a 0 inclús més ràpidament. El mateix argument s'aplica si la mona estiguera escrivint qualsevol atra cadena de caràcters de qualsevol tamany.

Esta demostració mostra per qué infinites mones podrien (en casi tota provabilitat) produir un text tan ràpidament com poguera ser escrit per un mecanografiador humà copiant-ho des de l'original. En este cas X=(1-1/50⁶)ⁿ, a on X representa la provabilitat de que cap dels primers n mones escriguera banana a la primera. Quan considerem 100 000 millons de mones, la provabilitat cau al 0,17% i a mida que n aumenta, X (la provabilitat de que totes les mones fallen en escriure un text donat) tendix a 0, pero mai conseguix alcançar-ho.

Enunciat formal

A pesar de que la teorema de la mona infinita és a sovint expressat de manera informal, un enunciat formal del mateix clarificaria el seu significat exacte. És més fàcil d'expressar en les cadenes de text de la ciència de computadoras, que són seqüències finitas de caràcters d'un determinat alfabet. En este estat, les dos sentències superiors podrien ser expressades formalment com:

• Donada una cadena infinita a on cada caràcter és elegit de manera aleatòria, qualsevol cadena finita casi segurament (provabilitat 1) ocorre com a subcadena de la primera en alguna posició (de fet, en infinites posicions).

• Donada una infinita seqüència d'infinites cadenes iguals a la primera, a on cada caràcter de cada cadena és elegit de forma aleatòria, qualsevol cadena finita casi segurament ocorre com un prefix d'una d'eixes cadenes infinites (de fet, com a prefix d'infinites de dites cadenes en la seqüència).

Abdós sentències s'extrauen senzillament del segon lema de Borel-Cantelli. Suponent que el nostre text desijat té una llongitut n, per a la segona teorema, I_k és el succés de que la k-ésima cadena comence en el text donat. Ya que açò té la provabilitat p no zero d'ocórrer, l'I_k és independent i la suma inferior divergix, la provabilitat de que infinites I_k ocórreguen és 1. La primera teorema és igual, llevat que dividim la cadena aleatòria en blocs no sobreposts de n caràcters cada u i fem I_k l'event en que el bloc k-ésimo iguala la cadena desijada.

$\sum _{i=1}^{\mathrm{\infty }}P(E_k)=\sum _{i=1}^{\mathrm{\infty }}p=\mathrm{\infty }.$

De fet, inclús anant a infinit pot ser excessiu. Si l'alfabet té un tamany a, llavors pot ser demostrat que la provabilitat de que una de les primeres aⁿ ocórrega és a lo manco 1/2. Llavors, 20aⁿ intents podrien ser suficients per a escriure el text donat en una provabilitat molt pròxima a 1. El problema inclús fa paralelisme be: k mones poden escriure el text k voltes més ràpit. Per a un n chicotet no és massa mal. Per eixemple, mil mones escrivint lletres a l'encert a un ritme de 100 caràcters per minut podrien provablement escriure la paraula «banana» en unes sis semanes.

Esta teorema és una instància de la Llei Zero-U de Kolmogórov.

Vore també

• La biblioteca de Babel (pàgina d'Internet)

Bibliografia

• (2015).Lliçons inaugurals de l'Universitat Complutense de Madrit.Consultat el 16 de setembre de 2016.