= Solution
In discrete time, the bounded-time <optional stopping theorem> says that an integrable <supermartingale> $X$ and bounded <stopping times> $S\le T$ satisfy $\mathbb E[X_T\mid\mathcal F_S]\le X_S$. For a <martingale> there is equality. The assertion at a possibly unbounded, almost-surely finite <stopping time> $T$ also holds with $S=0$ if $\{X_{T\wedge n}:n\ge0\}$ is <uniformly integrable>: then $X_T$ is integrable and $\mathbb EX_T\le\mathbb EX_0$, with equality for a <martingale>. Boundedness of $T$ or the stated integrability condition cannot in general be omitted.
For the increment hypothesis here, $\mathbb ET<\infty$ implies $T<\infty$ almost surely, and telescoping gives
$$
|X_{T\wedge n}|\le|X_0|+KT,\qquad |X_T|\le|X_0|+KT.
$$
The right-hand side is an <integrable random variable>. Applying bounded-time <optional stopping> to $T\wedge n$ and then the <dominated convergence theorem> proves
$$
\boxed{X_T\in L^1,\qquad \mathbb EX_T\le\mathbb EX_0.}
$$
This is <bounded-increment optional stopping with integrable time>; the same reasoning gives equality for a <martingale>.
Put $q=1-p$ and first assume $0<p<1$. Let $\tau$ be the first occurrence time of the specified seven-letter word. Its probability in a prescribed block is $r=p^4q^3>0$. Disjoint seven-flip blocks are <independent>, and a match in one forces $\tau$ to have occurred by its end. Consequently $\mathbb P(\tau>7m)\le(1-r)^m$ and $\mathbb E\tau\le7/r<\infty$; this establishes the integrability needed for stopping before computing its value.
Start a new gambler with unit capital immediately before each flip. A gambler bets all current capital on the next required letter of the word, receives capital divided by $p$ for a correct head or by $q$ for a correct tail, and receives zero on failure. After completing all seven bets, the gambler retains the winnings without further betting. Each individual bet preserves its conditional expected capital. If $C_n$ is the total capital of all gamblers who have entered through flip $n$, then $C_n-n$ is a <martingale>.
At any time at most seven gamblers are still betting, and each one's capital is at most $L=1/(p^4q^3)$, since probabilities of shorter prefixes are at least the full-word probability. Completed winnings do not change. Thus the increments of $C_n-n$ have a deterministic bound, for example $14L+1$. The preceding optional-stopping argument therefore gives $\mathbb E(C_\tau-\tau)=0$.
At the first full match, no earlier gambler has completed the word. A surviving gambler who has placed $k$ successful bets corresponds to a suffix of the completed word which is also its length-$k$ prefix, namely a <border of a word>. The only such lengths are $3$ and $7$: the shorter common string is HHT. Their capitals are $1/(p^2q)$ and $1/(p^4q^3)$, respectively. Hence $C_\tau$ is this deterministic sum and
$$
\boxed{\mathbb E\tau=\frac1{p^4(1-p)^3}+\frac1{p^2(1-p)}.}
$$
For a fair coin this is \b[136 flips]. This is a <waiting time for a word in independent nonuniform symbols>; the overlap contribution is essential. If $p=0$ or $p=1$, the word cannot occur because it contains both types of flip, so the expected waiting time is infinite.
Back to article page
