¿Hay alguna prueba de que una secuencia de dígitos finita dada debe existir en algún lugar dentro de una secuencia de dígitos infinitamente larga y aleatoria?

Supuesto: por “generado aleatoriamente”, quiere decir “extraído independientemente de la distribución uniforme en el alfabeto”.

Teorema: con probabilidad 1, una secuencia [matemática] \ vec s = s_1s_2 \ ldots s_k \ in \ Sigma ^ k [/ math] aparecerá en una cadena de letras independientes uniformemente distribuidas [matemática] S \ in \ Sigma ^ \ omega [/matemáticas].

Prueba: considere [math] S [/ math] como una serie de [math] k [/ math] -grams. La probabilidad de que cualquier [math] k [/ math] -gram sea [math] \ vec s [/ math] es [math] | \ Sigma | ^ {- k} [/ math]; la probabilidad de que ninguno de los primeros [math] n [/ math] -grams sea [math] \ vec s [/ math] es
[matemáticas] \ prod_ {i = 1} ^ n \ text {Pr} (\ text {the} i \ text {th} k \ text {-gram is} \ vec s) [/ math]
[matemáticas] = \ prod_ {i = 1} ^ n | \ Sigma | ^ {- k} = | \ Sigma | ^ {- nk} [/ matemáticas].

Entonces, como [math] n \ to \ infty [/ math], [math] \ text {Pr} (\ text {none of the} n \ text {first} k \ text {-grams are} \ vec s) \ to0 [/ matemáticas].

Corolario: con probabilidad 1, [math] \ vec s [/ math] aparece un número infinito de veces.

Para resumir la respuesta de Ross de una manera libre de anotaciones, imagine dibujar mosaicos de letras para formar una cadena de letras al azar infinitamente larga. Suponga que para cada sorteo, cada letra tiene la misma probabilidad de ser sorteada, y cada sorteo es independiente de todas las demás.

Suponga que quiere ver la palabra “flapjack” aparecer en algún lugar de esa secuencia. Supongamos, en aras de la contradicción, que esto no sucede con probabilidad positiva.

Hay una probabilidad pequeña pero positiva de que “flapjack” aparezca como las primeras ocho letras. Si no, entonces mira las siguientes ocho letras, números del 9 al 16. Nuevamente, tienes la misma probabilidad de ver la palabra, y el evento de que aparezca en el segundo bloque de ocho caracteres es independiente de si apareció en el primer bloquear.

Continuando de esta manera, la probabilidad de que no hayamos visto la palabra que estamos buscando en los primeros 100 bloques, por ejemplo, es la probabilidad de que no aparezca en el primer bloque a la potencia número 100. La probabilidad de que no aparezca en los primeros 1000 bloques es el mismo número que 1000, y así sucesivamente. Dado que la probabilidad de “flapjack” no aparece en el primer bloque es menor que 1, esta probabilidad aumentada a potencias cada vez más altas se acerca arbitrariamente a cero. Esto contradice la hipótesis de que el “flapjack” no aparece en ninguna parte con alguna probabilidad positiva. Entonces aparece con probabilidad 1.

Esencialmente, la misma prueba funciona para cualquier secuencia finita de caracteres con cualquier alfabeto.

Digamos que la cadena de dígitos tiene N dígitos de longitud. La probabilidad de obtener todos los N dígitos seguidos es 1/10 ^ N.

Pero supongamos que observa una cadena de dígitos N * (10 ^ N) de largo. (Sí, es un número grande, pero infinitamente se adapta a CUALQUIER número finito). Eso es equivalente a intentar un evento de 1/10 ^ N de probabilidad, 10 ^ N veces. En realidad, es bastante mejor que eso, porque la cadena de destino puede ocurrir en cualquier posición. Pero debería ver que las probabilidades son al menos tan buenas como tratar de producir un problema de 1/10 ^ N. evento, intentándolo 10 ^ N veces.

También debería ver que si un evento tiene probabilidad 1 / M, el problema. de obtener éxito después de M intentos es mejor que el 50%. (De hecho, es un poco más del 60%). Entonces se vuelve más probable que lanzar una moneda y obtener caras.

Entonces, después de N * (10 ^ N) dígitos, la probabilidad de un “golpe” es mejor que lanzar una moneda y obtener caras. Y esta cantidad … N * (10 ^ N) … se ajusta infinitamente muchas veces al infinito.

Entonces es como lanzar una moneda infinitamente muchas veces.

Y también puede ver que si lanza una moneda infinitamente muchas veces, la probabilidad de obtener al menos una cara se aproxima a la certeza virtual.

El teorema del mono infinito, que es un caso especial del lema de Borel-Cantelli, indica que la probabilidad de que una secuencia finita de dígitos no ocurra en una secuencia de dígitos aleatorios es cero. De alguna manera, este es un argumento circular, ya que se supone que la “secuencia aleatoria de dígitos” tiene ciertas propiedades: cada carácter se elige “uniformemente, al azar”. La secuencia de Guildenstern y Rosencrantz de Peter Webb no es aleatoria.

No. Cualquier secuencia infinita de números podría generarse aleatoriamente, y en particular la secuencia 0.11111…. (1/9) podría ser producido; es tan probable como cualquier otra secuencia. Esto no contiene “22”.

Aquí hay una pregunta similar. Lanzas una moneda justa un número infinito de veces. ¿Cuál es la probabilidad de que cada lanzamiento sea una cabeza? Claramente no es imposible, pero la probabilidad de que esto ocurra es cero.

La probabilidad de una secuencia verdaderamente aleatoria que contenga cualquier secuencia finita dada es “1”. Esto no es lo mismo “es seguro que ocurrirá”. Simplemente significa que la posibilidad de que no ocurra es muy pequeña, pero no imposible.