Probabilidad de encontrar un numero en Pi

Si vemos a Pi como una gran cadena aleatoria de números, entonces podemos calcular las probabilidades de encontrar cualquier cadena en los primeros 100 millones de dígitos de Pi:

Numero de dígitos	Posibilidad de encontrarlo
1-5	100%
6	Casi 100%
7	99.995%
8	63%
9	9.5%
10	0.995%%
11	0.09995%

¿De dónde vienen estos números y cómo se calculan?

Digamos que estás buscando un solo dígito en Pi, y pretendamos de nuevo que Pi es aleatorio. Si escoge un número entre 0 y 9 al azar, la probabilidad de que sea igual a su dígito de búsqueda es de 1 en 10, (10%, o 0.1).

Eso es bastante simple, pero ¿qué pasa si quieres buscar una cadena de dos dígitos? Bueno, puedes aproximarte a esto escogiendo dos números. Si el primero no coincide, se acabó. Pero si el primero coincide, tienes que tratar de coincidir con el segundo también. Cada uno de ellos tiene una probabilidad de 0.1, y asumiremos que los números son completamente independientes. Así que el 10% de las veces el primer número coincide, y el 10% del 10% de las veces, ambos números coinciden, que es el 1%, o una probabilidad de 0,01. Tendríamos una probabilidad de 1 en 1000 (0.001) de encontrar una cadena de búsqueda de tres dígitos, y así sucesivamente.

Si asumimos que Pi es aleatorio, la fórmula anterior nos da la oportunidad de que cualquier posición en particular coincida. Así que para una cadena de búsqueda de dos dígitos, hay un 1% de probabilidad de que coincida en la posición 1, un 1% de probabilidad de que coincida en la posición 2, y así sucesivamente. Así que la posibilidad de encontrar la cadena de búsqueda es igual a la posibilidad de encontrarla en cualquiera de esas posiciones. ¿Cómo lo averiguamos?

Vamos a darle la vuelta al problema. La posibilidad de encontrarla es simplemente lo contrario de la posibilidad de no encontrar la cadena de búsqueda. "Obvio, no?" puedes decir... pero espera. Ya nos dimos cuenta de este tipo de posibilidad antes. ¿Cómo es que no encontramos algo? Bueno, primero no tenemos que encontrarlo en la posición 1, y luego no encontrarlo en la posición 2, .... y seguir adelante hasta el final de nuestros dígitos. Esto es como lo que hicimos antes para averiguar la posibilidad de que una posición coincida!

Si tenemos un 10% de posibilidades de coincidencia en cualquier posición, entonces tenemos un 90% de posibilidades de no coincidencia. Así que las probabilidades de no coincidir con toda la cadena de pi es igual al 90% del 90% del 90% del 90% de .... y así sucesivamente, por cada dígito de Pi que tenemos. Matemáticamente, esto sería 0,9 a la potencia de "N" (0,9N) si tenemos N dígitos. Y entonces las probabilidades de encontrar la cadena serían de 1 - (0.9)N.

En conjunto, sabemos que las posibilidades de encontrar una cadena de búsqueda en cualquier posición son de 0,1d, donde "d" es la longitud de nuestra cadena de búsqueda. Así que toda la probabilidad es 1 - (1 - 0.1d)N.

Continuando con el camino matemático, resulta que accidentalmente nos hemos topado con algo llamado probabilidades binomiales. Los binomios surgen cuando uno se pregunta "¿cuáles son las probabilidades de sacar un número k de caras de n tiras de una moneda? Para hacer las cosas más complicadas, dejemos que la moneda esté inclinada de alguna manera - obtiene "cabezas" con probabilidad p (es decir, si p = 0.6, entonces el 60% de las veces, la moneda aterriza cabezas).

Afortunadamente para nosotros, preguntar sobre cero ocurrencias de caras es fácil, como lo demostró la fórmula anterior. Pero podríamos hacer otras preguntas, como "¿cuáles son las probabilidades de encontrar mi cumpleaños dos veces en los primeros 100.000.000 dígitos de Pi?" Estas preguntas son más difíciles de responder (computacionalmente) que el caso cero, porque tenemos muchas maneras diferentes de encontrar tu cumpleaños dos veces. Podríamos encontrarlo una vez en la posición 1 y otra vez en la posición 2, o una vez en la posición 1 y otra vez en la posición 3, y así sucesivamente. Incluso las computadoras muy rápidas comienzan a ahogarse cuando los números se hacen grandes. Y luego podríamos empeorarlo aún más, ¿qué pasa si queremos saber qué tan probable es encontrar tu cumpleaños por lo menos 100 veces en Pi?

La solución a este problema es usar lo que se conoce como la aproximación de Poisson al binomio, cuando los números son grandes. En realidad podemos aproximar la fórmula anterior como:

Probabilidades (encontrar una cadena de longitud k en N dígitos de pi) = 1 - 1/e(N*0.1d).

Eso parece un poco complicado, hasta que nos damos cuenta de que 0.1d es sólo 1 dividido por el número de cadenas de búsqueda que tienen dígitos d. Así que si d es tres, hay 1000 cadenas (0, 1, 2, ...., 999). Así que 0,13 = 1/1000 = 0,001. Y N es sólo el número de dígitos de pi. Así que lo que esto realmente significa es que podemos calcular las probabilidades simplemente como 1 - 1/e (dígitos de pi / posibles búsquedas). Así que si tenemos 100.000.000.000 dígitos de pi, y podemos buscar 100.000.000.000 de cadenas posibles (cadenas de búsqueda de 8 dígitos), entonces nuestra probabilidad es simplemente 1 - 1/e. Con el doble de dígitos que los strings de búsqueda, la probabilidad se convierte en 1 - 1/e2. Y así sucesivamente.

Si quieres buscar un numero en Pi entra aqui.