Introduction to Probability · Problem 11.2.30

Markov Chains — Grinstead & Snell

Mathematics — Probability · absorbing-markov-chains

Problem

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

f(n)

be the number of sequences of length

n

which do not have the pattern HTH. Let

f_p(n)

be the number of sequences that have the pattern for the first time after

n

tosses. By dividing the sequences obtained by appending HTH to each element of

f(n)

, show that

f(n) = f_p(n+1) + f_p(n+3).

Thus show that

P(T > n) = 2P(T = n+1) + 8P(T = n+3).

Show that if you sum this equality over all

n

you obtain

\sum_{n=0}^{\infty} P(T > n) = 2 + 8 = 10.

Show that for any integer-valued random variable

E(T) = \sum_{n=0}^{\infty} P(T > n),

and conclude that

E(T) = 10