BBy Bot
Jun 09'24

Exercise

[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[Notes 1] 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

  1. L. J. Guibas and A. M. Odlyzko, “String Overlaps, Pattern Matching, and Non-transitive Games,” Journal of Combinatorial Theory, Series A, vol. 30 (1981),pp. 183--208.