Introduction to Probability · Problem 11.2.28

Markov Chains — Grinstead & Snell

Mathematics — Probability · absorbing-markov-chains

Problem

A coin is tossed repeatedly. We are interested in finding the expected number of tosses until a particular pattern, say B=HTHB = \text{HTH}, occurs for the first time. If, for example, the outcomes of the tosses are HHTTHTH we say that the pattern B has occurred for the first time after 7 tosses. Let TBT^B be the time to obtain pattern B for the first time. Using the associated Markov chain (with states HTH, HT, H, and ∅\emptyset, where ∅\emptyset is the empty set, and transition matrix (HTHHTH∅HTH1000HT.500.5H0.5.50∅00.5.5),\begin{pmatrix} & \text{HTH} & \text{HT} & \text{H} & \emptyset \\ \text{HTH} & 1 & 0 & 0 & 0 \\ \text{HT} & .5 & 0 & 0 & .5 \\ \text{H} & 0 & .5 & .5 & 0 \\ \emptyset & 0 & 0 & .5 & .5 \end{pmatrix}, show that the values E(TB)=10E(T^B) = 10 and E(TB)=14E(T^B) = 14 are correct for the expected time to reach the patterns HTH and HHH, respectively.

Related theory

Browse the problem library