exercise:C04b09a77f

[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Here is an elegant method due to Guibas and Odlyzko to obtain the expected time to reach a pattern, say HTH, for the first time. Let [math]f(n)[/math] be the number of sequences of length [math]n[/math] which do not have the pattern HTH. Let [math]f_p(n)[/math] be the number of sequences that have the pattern for the first time after [math]n[/math] tosses. To each element of [math]f(n)[/math], add the pattern HTH. Then divide the resulting sequences into three subsets: the set where HTH occurs for the first time at time [math]n + 1[/math] (for this, the original sequence must have ended with HT); the set where HTH occurs for the first time at time [math]n + 2[/math] (cannot happen for this pattern); and the set where the sequence HTH occurs for the first time at time [math]n + 3[/math] (the original sequence ended with anything except HT). Doing this, we have

[[math]] f(n) = f_p(n + 1) + f_p(n + 3)\ . [[/math]]

Thus,

[[math]] \frac{f(n)}{2^n} = \frac{2f_p(n + 1)}{2^{n + 1}} + \frac{2^3f_p(n + 3)}{2^{n + 3}}\ . [[/math]]

If [math]T[/math] is the time that the pattern occurs for the first time, this equality states that

[[math]] P(T \gt n) = 2P(T = n + 1) + 8P(T = n + 3)\ . [[/math]]

Show that if you sum this equality over all [math]n[/math] you obtain

[[math]] \sum_{n = 0}^\infty P(T \gt n) = 2 + 8 = 10\ . [[/math]]

Show that for any integer-valued random variable

[[math]] E(T) = \sum_{n = 0}^\infty P(T \gt n)\ , [[/math]]

and conclude that [math]E(T) = 10[/math]. Note that this method of proof makes very clear that [math]E(T)[/math] is, in general, equal to the expected amount the casino pays out and avoids the martingale system theorem used by Li.

Notes