7 votos

Monos y máquinas de Escribir

Supongamos que hay una especie de antología de obras de teatro que es de N símbolos de largo en el siguiente sentido: "símbolo" es una de las 26 letras del alfabeto, con un salto de línea, punto, espacio, o de colon; en otras palabras, hay 30 posibles símbolos.

Si "un mono" al azar "tipos" 1 de estos 30 símbolos a un ritmo de uno por segundo, ¿cuánto tiempo tardará M monos trabajando a este ritmo, en promedio, uno de ellos al azar para escribir este símbolo N largo obras completas?

Para mayor claridad, permítanme decir que estoy suponiendo que cada mono incesantemente tipos de símbolos al azar, a este ritmo, y a menos que un mono inmediatamente tipos de cosas, las obras completas será precedido por un galimatías.

9voto

Martin OConnor Puntos 116

Por desgracia, una respuesta exacta dependerá de la secuencia específica de los $N$ símbolos. Para ver por qué, tomar un ejemplo sencillo en el que sólo tiene dos posibles símbolos, a y B, con a $N = 2$, y sólo uno de los monos. Comparar los tiempos de espera hasta que el mono tipos de la secuencia de AA vs la secuencia de BA. A menos que el mono tipos de AA en el principio (con una probabilidad de $\frac{1}{4}$), la primera vez que aparezca AA BA secuencia debe haber ocurrido ya. Así que la última secuencia tendrá el menor tiempo de espera.

Hay un montón de este tipo de resultados intuitivo acerca de la probabilidad de que aparezca una determinada secuencia antes de que otra secuencia determinada y sobre el tiempo de espera hasta que una secuencia es visto por primera vez. Para obtener más información, consulte MathWorld la entrada de la Moneda de Tirar, o, incluso para más información, ver el artículo "Penney Ante" que apareció en la UMAP Diario.

Ahora, si $N$ es grande y los símbolos son asumidos para ser distribuido uniformemente en la secuencia de destino, tal vez usted puede evitar los problemas con los dos-símbolo y distribuido de forma desigual ejemplo que les he dado aquí. O, si la fuerza de cada mono a parar después de escribir exactamente $N$ símbolos, comprobar para ver si ellos han escrito la secuencia de destino, y luego pídales que empezar de nuevo desde cero si no lo tienen, entonces usted puede evitar estos problemas. (Para más información sobre esto, véase este artículo de "Infinite Monkey Business".)

1voto

John Fouhy Puntos 759

Vamos a calcular la probabilidad de un "genérico" de la cadena. El número de apariciones de la cadena en cualquier mono de salida es de aproximadamente distribuidos de Poisson con $\lambda = 30^{-N}$. El tiempo hasta el primer evento sucede es, pues, aproximadamente, distribuido exponencialmente con la tasa de $\lambda = 30^{-N}$. El mínimo de $M$ estos procesos también se distribuye exponencialmente con la tasa de $\lambda = M/30^N$. Por lo tanto el tiempo de espera es de aproximadamente el $30^N/M$.

El mismo cálculo se puede obtener si se calcula el número esperado de las apariencias. El número esperado de las apariencias en cualquier mono de flujo para la primera $t+M-1$ personajes es $t/30^N$. Para $M$ monos, es $tM/30^N$. Esto es$1$$t = 30^N/M$, y esto da una estimación aproximada de la real expectativa.

De hecho, suponiendo que la cadena "no se superponen con sí mismo", podemos obtener una expresión exacta para la expectativa (dependiendo únicamente de la $N$$M$) utilizando el Teorema 1.1 en la "Cadena de la solapa, la coincidencia de patrones, y no transitiva de los juegos" (Guibas y Odlyzko '81), lo que da una generación de función de la probabilidad de que un mono no se hace después de la $t$ pasos.

El documento también da una expresión para los "no-genérico" cadenas y para varias cadenas, pero las obras no se van a solapar a sí mismos; incluso si lo hacen, es probable que sólo tienen un ligero efecto sobre las probabilidades.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X