Encontrar una secuencia específica de dígitos en pi

Question

Mirando el proyecto pifs en GitHub y esta pregunta sobre el SO me ha despertado la curiosidad por saber si es factible encontrar una secuencia específica de dígitos dentro de Pi.

Esencialmente, en promedio, ¿cuántos dígitos de pi habría que recorrer para encontrar una secuencia específica de una longitud determinada?

Suponiendo que los dígitos de pi sean normales y por lo demás aleatorios, yo supondría que la dificultad de encontrar una secuencia específica aumenta exponencialmente (?) a medida que aumenta la longitud de la secuencia. Por ejemplo, tratar de encontrar una secuencia corta como "12345" es bastante fácil, ya que se encuentra en la posición 49702. Sin embargo, un solo dígito más, digamos "123456", te lleva a la posición 2458885. Por supuesto, difiere según la secuencia específica; '314159' es mucho más fácil de encontrar en términos del trabajo que tienes que hacer (especialmente en términos computacionales, donde los tiempos de ejecución y el uso de la memoria hacen una diferencia). Probablemente todavía hay una manera de encontrar un dígito medio de pi en el que cualquier secuencia dada comenzaría, pero está más allá del alcance de mi capacidad matemática.

Otra cuestión interesante es si existe una fórmula específica para la posición media en pi para una secuencia de una longitud determinada. Por ejemplo, si se toma una secuencia específica de 256 kb, se necesitaría un número absurdo de dígitos de pi para encontrarla, pero ¿cómo se compararía ese número absurdo con el número mucho más absurdo de dígitos que se necesitaría para encontrar una secuencia específica de 512 kb en pi?

Supongo que también se podría tener en cuenta la teoría de la información, porque como pi es efectivamente aleatorio, a primera vista parece que podría costar más identificar una secuencia que tenga un patrón repetitivo. Pensando más en ello, no creo que sea más difícil de encontrar que cualquier otra secuencia específica, pero no estoy seguro.

Como probablemente puedas deducir por el lenguaje horriblemente impreciso de arriba y mi completa falta de reputación en este sitio, no estoy muy familiarizado con este tipo de matemáticas, así que si las etiquetas de abajo son inapropiadas, por favor ayúdame editándolas.

Answer 1

Esencialmente, en promedio, ¿cuántos dígitos de pi habría que recorrer para encontrar una secuencia específica de una longitud determinada?

Si el comportamiento estadístico de los dígitos de $\pi$ está modelado por un i.i.d. secuencia de variables aleatorias uniformes en $\{0,1,2,3,4,5,6,7,8,9\}$ el siguiente teorema es relevante:

Si $(X_1, X_2, X_3, \dots)$ es una secuencia de variables aleatorias que son i.i.d. uniformes en un conjunto $S$ de $m$ elementos, entonces el tiempo esperado de primera aparición de una subsecuencia contigua $\tau\in S^n$ viene dada recursivamente por
$$ET_\tau = m^n + ET_\sigma $$ donde $\sigma$ es el suffix propio más largo de $\tau$ que también es un prefijo de $\tau$ . Aquí $T_\tau$ se define como el menor $k$ tal que $\tau$ es una subsecuencia contigua de $(X_1, \dots , X_k)$ y por convención $T_{\text{empty sequence}}=0$ .

(Una prueba de esto se encuentra en el libro de texto de Sheldon M. Ross, "Introducción a los modelos de probabilidad", 10ª edición, ejemplo 4.26, pp. 225-228. Ross demuestra un resultado mucho más general para las cadenas de Markov).

Por ejemplo, con $m = 10$ , $$\begin{align} ET_{01201201} & = 10^8 + ET_{01201}\\ & = 10^8 + 10^5 + ET_{01}\\ & = 10^8 + 10^5 + 10^2 + ET_{\text{empty sequence}}\\ & = 10^8 + 10^5 + 10^2 \end{align} $$ mientras que el tiempo de primera aparición de esta secuencia en los dígitos de $\pi$ es $91,997,854 \approx 0.9 ET_{01201201}$ .

Algunas observaciones:

• Un caso límite es cuando $\tau$ se compone de $n$ copias de un mismo símbolo, por ejemplo $0^n = 000...0$ Así que $$\begin{align} ET_{0^n} & = m^n + ET_{0^{n-1}}\\ & = m^n + m^{n-1} + ET_{0^{n-2}}\\ & ...\\ & = m^n + m^{n-1} + ... + 1\\ & = \frac{m^{n+1} - m}{m-1} \end{align} $$
  Por lo tanto, para todos los $\tau$ , $$m^n \le ET_\tau \le \frac{m^{n+1} - m}{m-1} \lt m^{n+1} $$ por lo que el crecimiento es exponencial en la longitud de la subsecuencia $n$ .

• Es interesante, $ET_\tau$ es siempre un entero .