Grinstead-Snell-Probability · Problem 11.2.30

Markov Chains

Mathematics · 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)f(n) be the number of sequences of length nn which do not have the pattern HTH. Let fp(n)f_p(n) be the number of sequences that have the pattern for the first time after nn tosses. By dividing the sequences, we have f(n)=fp(n+1)+fp(n+3).f(n) = f_p(n+1) + f_p(n+3). Thus, f(n)2n=2fp(n+1)2n+1+23fp(n+3)2n+3.\frac{f(n)}{2^n} = \frac{2 f_p(n+1)}{2^{n+1}} + \frac{2^3 f_p(n+3)}{2^{n+3}}. If TT is the time that the pattern occurs for the first time, this equality states that P(T>n)=2P(T=n+1)+8P(T=n+3).P(T > n) = 2P(T = n+1) + 8P(T = n+3). Show that if you sum this equality over all nn you obtain ∑n=0∞P(T>n)=2+8=10.\sum_{n=0}^{\infty} P(T > n) = 2 + 8 = 10. Show that for any integer-valued random variable E(T)=∑n=0∞P(T>n),E(T) = \sum_{n=0}^{\infty} P(T > n), and conclude that E(T)=10E(T) = 10.

Related theory

Browse the problem library