Sobre el problema del mono que escribe caracteres al azar Luis Rinc´on Departamento de Matem´aticas Facultad de Ciencias UNAM Circuito Exterior de CU 04510 M´exico DF [email protected] Septiembre 2004 Resumen Se expone y se comenta la soluci´on al problema de encontrar la probabilidad de que un mono que escribe caracteres al azar, escriba las obras completas de Shakespeare.

1. Planteamiento del problema El problema es simple. Un mono escribe caracteres completamente al azar en una m´aquina de escribir. ¿Cu´al es la probabilidad de que eventualmente el mono escriba exactamente y sin ning´ un error las obras completas de Shakespeare? Este es un problema te´orico contextualizado en una situaci´on real. Se asume idealmente que tenemos el escenario de un mono eterno que escribe permanentemente caracteres al azar en una m´aquina de escribir. La m´aquina nunca se descompone y la tira de papel nunca termina. La soluci´on que se expone en este art´ıculo no aparece en la mayor´ıa de los textos de probabilidad, pero ciertamente no es nueva pues el problema aparece planteado y resuelto en el excelente libro de probabilidad de 1

Ghahramani [1], como una aplicaci´on de la ley fuerte de los grandes n´ umeros. Nuestro objetivo es exponer con mayor detalle la soluci´on, efectuar algunos c´alculos num´ericos y hacer comentarios respecto a este problema de insospechadas consecuencias. Empecemos pues por recordar brevemente la ley de los grandes n´ umeros. 2. Ley de los grandes n´ umeros Este resultado es uno de los pilares de la teor´ıa de la probabilidad y una primera versi´on fue demostrada por primera vez en 1713 por el matem´atico suizo James Bernoulli en la cuarta parte de su obra Ars Conjectandi. La versi´on que enunciamos a continuaci´on ser´a adecuada para nuestros prop´ositos. Sea X1 , X2 , . . . una sucesi´on infinita de variables aleatorias independientes todas con la misma distribuci´on con esperanza µ y con cierta varianza finita. La ley d´ebil de los grandes n´ umeros establece que para cualquier  > 0, n

lim P ( |

n→∞

1X Xk − µ| ≥  ) = 0. n k=1

P Esto quiere decir que la variable aleatoria promedio n1 nk=1 Xk converge en probabilidad a la constante µ. La ley fuerte establece un tipo de convergencia ´ m´as fuerte. Esta dice que n

1X Xk = µ ) = 1, P ( lim n→∞ n k=1 es decir, la convergencia es casi segura. No es dif´ıcil demostrar que la convergencia casi segura de variables aleatorias implica la convergencia en probabilidad y por ende los adjetivos de d´ebil y fuerte para estos resultados [2]. Es interesante observar, por otro lado, que esta ley justifica la definici´on frecuentista de probabilidad. Usaremos la versi´on fuerte de la ley de los grandes n´ umeros para dar respuesta a la pregunta inicialmente planteada. 3. Soluci´ on Imaginemos entonces que un mono escribe caracteres al azar en una m´aquina de escribir y que lo hace de manera continua generando una sucesi´on 2

lineal de caracteres. Sea m el total de caracteres disponibles y sea N el total de caracteres de los que constan la obras completas de Shakespeare. Por el momento no necesitamos especificar exactamente los valores de m y N . Segmentamos el arreglo lineal de caracteres generados por el mono en bloques de N caracteres, uno despu´es de otro y observamos si alg´ un bloque contiene las obras de Shakespeare. Xku · · · aT s} hwW · · · pzq Ot · · · | {z {z } | N

N

Para cada n´ umero natural k defina el evento Ak correspondiente a que el k-´esimo bloque contiene exactamente y sin error alguno la obras completas de Shakespeare. Observe que los eventos Ak son independientes pues los bloques no se sobreponen. Sea p = P (Ak ). Ahora defina la variable aleatoria indicadora de estos eventos, es decir, sea  1 si Ak ocurre, Xk = 0 si Ak no ocurre. Entonces Xk tiene distribuci´on Bernoulli con par´ametro p. Por lo tanto  N 1 = p. E(Xk ) = P (Ak ) = m Tenemos entonces una sucesi´on X1 , X2 , . . . de variables aleatorias independientes con id´entica distribuci´on Bernoulli(p). Consideremos la suma X1 + X2 + · · · + Xn . Si para alg´ un valor de n esta suma es positiva significa que alguno de los sumandos es distinto de cero y por lo tanto que el mono ha tenido ´exito. Pero esto es justamente lo que garantiza la ley de los grandes n´ umeros pues  N n 1 1X Xk = ) = 1. (1) P ( lim n→∞ n m k=1 Es decir, con probabilidad uno la suma de la ecuaci´on (1) es positiva. Esto implica que debe existir un valor de k tal que Xk = 1 y esto a su vez significa que en el k-´esimo bloque ¡el mono ha tenido ´exito! M´as a´ un, para que el promedio que aparece en la ecuaci´on (1) sea positivo necesariamente la suma debe ser infinita y por lo tanto deben existir una infinidad de valores de k tal que Xk = 1. Esto quiere decir que con probabilidad uno ¡el mono escribir´a tantas veces como uno desee las obras de Shakespeare! 3

Una vez que uno se ha repuesto de la incredulidad del resultado, es natural hacerse la siguiente pregunta. ¿Cu´anto tiempo le tomar´a al mono obtener las obras de Shakespeare? Lamentablemente s´olo podemos responder a esta pregunta en t´erminos de promedios. Cada bloque de N caracteres puede considerarse como un ensayo Bernoulli en donde la probabilidad de obtener ´exito es p y la probabilidad de obtener fracaso es 1 − p. Si T es la variable aleatoria que cuenta el n´ umero de ensayos (bloques) hasta obtener el primer ´exito entonces T tiene una distribuci´on geom´etrica con par´ametro p y es f´acil comprobar que 1 E(T ) = . p Es decir, en promedio se necesitan 1/p bloques de N caracteres para obtener las obras de Shakespeare. En t´erminos de caracteres se necesitan en promedio N/p caracteres al azar para obtener el texto. 4. Probabilidades peque˜ nas y tiempos de espera grandes Suponga que el total de caracteres distintos incluyendo letras may´ usculas y min´ usculas, punto, coma, espacio y otros s´ımbolos es m = 80. Asuma tambi´en que el total de caracteres N en las obras completas de Shakespeare es de seis millones 1 . Estas cantidades revelan que la probabilidad de que el mono tenga ´exito en un bloque cualquiera es  6,000,000 1 . p= 80 Al ritmo pausado de imprimir un caracter por segundo, el tiempo promedio de espera, medido en sgundos, para obtener ´exito es entonces E(T ) = 806,000,000 . Como cada a˜ no de 365 dias tiene 31, 536, 000 segundos, el tiempo de espera en a˜ nos para obtener ´exito es 806,000,000 >> 106,000,000 . 31, 536, 000 1

(2)

Una versi´ on de las obras completas contiene 1230 p´aginas, en donde cada p´agina contiene 65 lineas con un promedio de 80 caracteres por linea. Estos datos arrojan un total de 1230 × 65 × 80 = 6, 396, 000 caracteres.

4

La cota inferior sugerida es conservadora pero proporciona una idea del n´ umero de a˜ nos promedio de espera para observar un ´exito en este experimento. Unos segundos de reflexi´on revelan que este n´ umero de a˜ nos es desmesuradamente grande. Es el d´ıgito 1 seguido de seis millones de ceros. Comp´arese por ejemplo con la edad del universo que es aproximadamente de 15 billones2 de a˜ nos, es decir, 15 × 109 = 15, 000, 000, 000 a˜ nos, mientras que la edad de la tierra y del resto del sistema solar es de 4.5 billones de a˜ nos, es decir, 4.5 × 109 = 4, 500, 000, 000 a˜ nos. Estas cantidades son insignificantes cuando se les compara con (2). Asi pues, los tiempos de espera para observar un ´exito en este experimento parecen ser demasiado largos. Cualquier incremento razonable en la velocidad de escritura e incluso del n´ umero de monos que pudieran ponerse a trabajar a un mismo tiempo, no parece suficiente para reducir significativamente el tiempo esperado promedio. No obstante estas consideraciones, pueden encontrarse en internet algunos simuladores por computadora de este experimento3 . 5. Comentarios El esquema bajo el cual se ha planteado el problema del mono puede f´acilmente pensarse en forma general. Suponga que se tiene una sucesi´on de ensayos independientes en cada uno de los cuales puede observarse un evento A con la misma probabilidad p > 0. Nuevamente se define la variable aleatoria Xk que indica si en el k-´esimo ensayo se observa el evento A. La ley fuerte de los grandes n´ umeros garantiza que con probabilidad uno el evento A ocurrir´a eventualmente y no solamente una vez sino una infinidad de veces. Lo importante aqui es la condici´on p > 0 y que el experimento aleatorio puede efectuarse bajo las mismas condiciones iniciales tantas veces como sea necesario. El aspecto dram´atico en el problema del mono es que la probabilidad p es peque˜ n´ısima pero positiva y el contexto ayuda a pensar que es punto menos que imposible imaginar realmente que un mono escribe las obras de Shakespeare. Sin embargo hemos probado probabilisticamente que esto es posible. Hist´oricamente este resultado ha sido contextualizado en la obtenci´on 2 3

Un bill´ on son mil millones seg´ un el sistema norteamericano. Escriba por ejemplo las palabras ”typing monkey” en alg´ un buscador.

5

de diversos escritos. Thomas Huxley en 1860 sugiri´o que de forma aleatoria pod´ıa obtenerse el Salmo 23, mientras que su sobrino Julian Huxley repiti´o la analog´ıa para un texto menos puntilloso, las obras completas de Shakespeare. Stephen Hawking tambi´en se˜ nala en su libro ”A brief history of time” que dada una manada de monos escribiendo al azar ”very ocassionally by pure chance they will type out one of Shakespeare’s sonnets”. El resultado tambi´en ha sido aplicado al caso de obtener una secuencia de ADN, lo cual apoyar´ıa a la teor´ıa de la generaci´on espont´anea y a la teor´ıa de la evoluci´on. En [3] pueden encontrarse algunas opiniones y argumentos en contra. A pesar de los grandes tiempos de espera involucrados en esta interesante aplicaci´on de la ley de los grandes n´ umeros e imaginando la remota ocurrencia de un evento muy favorable, no puedo evitar recordar el conocido proverbio ”El que persevera alcanza”.

Bibliograf´ıa [1] Ghahramani S. (1999) Fundamentals of probability (2nd. edition). Prentice Hall. [2] Grinstead C. M. y Snell J. L. (1997) Introduction to probability. AMS. [3] Smart, Laurence D. Those typing monkeys don’t prove evolution. [www.unmaskingevolution.com]

6