Consider independent tosses of a rather biased coin that has $$\begin{align} \Pr({\tt Head})&=1/G\\ \Pr({\tt Tail})&=1-\Pr({\tt Head}),\end{align}$$ where $G$ is Graham's Number. Let the first $100$ tosses establish a "target" pattern, then let $N$ be the number of additional tosses needed to get a repetition of that target pattern (allowing overlap). E.g., a sequence that begins with $101$ consecutive ${\tt Tail}$s would have $N=1$.
Question: $\ \mathbb{E}(N)\ =\ ?\quad$
I'm posting in the spirit of this advice, and will eventually post the answer if no one else does so.
Let $A$ denote the set of all $2^{100}$ binary strings. Let $S$ be the random initial string of size 100. Then $$E[N] = \sum_{s \in A} E[N|S=s]P[S=s] $$ Now observe that $P[S=s]>0$ for all $s \in A$. So fix $s =(s_1, ..., s_{100})\in A$. We compute $E[N|S=s]$. Consider this thought experiment of random flipping: Deterministically fix the first 100 flips as the string $s$. Then randomly flip forever after (i.e., after time 100). Let $\{X_1, X_2, X_3, …\}$ represent the i.i.d. sequence of inter-arrival times of the string $s$ (including overlaps). Then $$E[N|S=s] = E[X_1]$$ Let $M_t$ be the total number of occurrences of the string up to time $t \in \{1, 2, 3, ...\}$ (including overlaps). By renewal theory we know $$ \lim_{t\rightarrow\infty} \frac{E[M_t]}{t} = \frac{1}{E[X_1]} $$ On the other hand we can write $M_t$ via indicator functions: $$ M_t = \sum_{i=1}^t 1_i$$ where $1_i$ is an indicator function that is 1 if an occurence of string $s$ ends in location $i$, and 0 else. Then $$ E[M_t] = \sum_{i=1}^t P[1_i=1] $$ and we note that for all $i \geq 200$ we have $$P[1_i=1]=P[\mbox{Flip $i$ is $s_{100}$, Flip $i-1$ is $s_{99}$, ..., Flip $i-99$ is $s_1$}] = P[S=s]$$ So $$\lim_{t\rightarrow\infty} \frac{E[M_t]}{t} = P[S=s] $$ Thus, $E[X_1] =\frac{1}{P[S=s]}$. Hence: $$ E[N] = \sum_{s \in A} \frac{1}{P[S=s]} P[S=s] = |A| = 2^{100}$$