Deje $A$ denota el conjunto de todos los $2^{100}$ cadenas binarias. Deje $S$ ser el azar inicial de la cadena de tamaño 100. Entonces
$$E[N] = \sum_{s \in A} E[N|S=s]P[S=s] $$
Ahora observe que el $P[S=s]>0$ todos los $s \in A$. Por lo tanto, fijar $s =(s_1, ..., s_{100})\in A$. Calculamos el $E[N|S=s]$. Considere la posibilidad de este experimento de azar flipping: Determinista revisión de los primeros 100 lanzamientos como el de la cadena de $s$. Luego aleatoriamente flip para siempre después (es decir, después de tiempo de 100). Deje $\{X_1, X_2, X_3, …\}$ representan el yo.yo.d. secuencia de entre los tiempos de llegada de la cadena de $s$ (incluyendo las superposiciones). Entonces
$$E[N|S=s] = E[X_1]$$
Deje $M_t$ el número total de ocurrencias de la cadena hasta el momento de $t \in \{1, 2, 3, ...\}$ (incluyendo las superposiciones). Por la renovación de la teoría sabemos
$$ \lim_{t\rightarrow\infty} \frac{E[M_t]}{t} = \frac{1}{E[X_1]} $$
Por otro lado, nos puede escribir $M_t$ a través de funciones de los indicadores:
$$ M_t = \sum_{i=1}^t 1_i$$
donde $1_i$ es un indicador de la función que es 1 si una ocurrencia de la cadena de $s$ termina en la ubicación de $i$, y 0 de otra cosa. Entonces
$$ E[M_t] = \sum_{i=1}^t P[1_i=1] $$
y nos cuenta que para todas las $i \geq 200$ hemos
$$P[1_i=1]=P[\mbox{Flip $i$ is $s_{100}$, Flip $1$ is $s_{99}$, ..., Flip $i-99$ is $s_1$}] = P[S=s]$$
Así
$$\lim_{t\rightarrow\infty} \frac{E[M_t]}{t} = P[S=s] $$
Por lo tanto, $E[X_1] =\frac{1}{P[S=s]}$. Por lo tanto:
$$ E[N] = \sum_{s \in A} \frac{1}{P[S=s]} P[S=s] = |A| = 2^{100}$$
