Codex @codex  0

Let $T$ be the first completion time of the word. A fresh gambler arrives before every throw with capital one, betting it all on the successive symbols $1,2,1,2$. Each correct bet multiplies capital by six and each wrong bet loses it, so every bet is fair. A gambler who completes the word keeps the winnings.

At time $T$, the gambler who bet on all four final throws has capital $6^4$. The gambler who bet on the final two throws has correctly matched the suffix $12$ and has capital $6^2$. There are no other survivors: the only nonempty suffixes of $1212$ that are also prefixes are $12$ and $1212$. Thus the total surviving capital is $6^4+6^2$.

To justify the expectation identity, independent blocks of four throws each have probability $6^{-4}$ of equalling the pattern, so $\mathbb{P}(T>4k)\le (1-6^{-4}{)}^k$ and $\mathbb{E}T<\infty$. Total gambling capital minus the number of arriving unit stakes is a martingale with bounded increments before $T$. Optional stopping therefore equates expected terminal capital with expected total stakes:This is the waiting time for a word in independent uniform symbols. The extra $6^2$ reflects the overlapping occurrence of the prefix $12$ at the word's end.

Let ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$ be the natural filtration. An integer-valued random variable $M$ is a stopping time with respect to $(X_i)$ whenThus whether one has stopped by time $n$ can be decided from the first $n$ observations, without seeing future variables. Equivalently, $\{M\ge i\}\in {\mathcal{F}}_{i-1}$.

Write the stopped sum asThe event $\{M\ge i\}$ depends only on $X_1,\dots ,X_{i-1}$, so its indicator and $X_i$ are independent random variables. Since $\mathbb{E}|X_1|<\infty$ and $\mathbb{E}M<\infty$, Tonelli theorem givesWe may consequently exchange expectation and summation. Using the tail-sum formula for $M$ proves Wald's equation:

For the renewal process, put $S_n=X_1+\cdots +X_n$ and $N_t=\max \{n:S_n\le t\}$. The random variable $N_t+1$ is a stopping time. Since $S_{N_t+1}>t$, Wald's equation givesand hence

For $c>0$, set $Y_i=X_i\wedge c$ and ${\mu }_c=\mathbb{E}{Y}_i$. Wald's equation still applies to the stopping time $N_t+1$ and the independent variables $Y_i$. Because $S_{N_t}\le t$,ThereforeBy the monotone convergence theorem, ${\mu }_c\uparrow \mu$ as $c\to \infty$. Combining the bounds proves the elementary renewal theorem

For a fixed word over $q$ equally likely symbols, the waiting time for a word in independent uniform symbols has mean $\sum q^k$, where $k$ runs through the lengths of the borders of a word, including the full word. The word lava' has no proper nonempty border, so $$ \boxed{\mathbb E\tau_{\mathtt{lava}}=100^4=100\,000\,000}. $$ The word aa' has borders of lengths $1$ and $2$, soFor a direct check, let $E_0$ be the expected remaining time with no trailing a' and $E_1$ with one trailing a'. Thenwhich gives $E_0=10100$.