Canyi Chen's Homepage

Selected Exercises for Markov Chain

  1. A fair coin is tossed repeatedly and independently. Find the expected number of tosses till the pattern HTH appears.

Solution. Call HTH our target. Consider a chain that starts from a state called nothing \emptyset and is eventually absorbed at HTH. If we first toss H then we move to state H because this is the first letter of our target. If we toss a T then we move back to \emptyset having expended 1 unit of time. Being in state H we either move to a new state HT if we bring T and we are 1 step closer to the target or, if we bring H, we move back to H: we have expended 1 unit of time, but the new H can be the beginning of a target. When in state HT we either move to HTH and we are done or, if T occurs then we move to \emptyset. The transition diagram is

Rename the states ,H,HT,HTH\emptyset, \mathrm{H}, \mathrm{HT}, \mathrm{HTH} as 0,1,2,30,1,2,3, respectively. Let ψ(i)\psi(i) be the expected number of steps to reach HTH starting from ii. We have

ψ(2)=1+12ψ(0)ψ(1)=1+12ψ(1)+12ψ(2)ψ(0)=1+12ψ(0)+12ψ(1) \begin{aligned} &\psi(2)=1+\frac{1}{2} \psi(0) \\ &\psi(1)=1+\frac{1}{2} \psi(1)+\frac{1}{2} \psi(2) \\ &\psi(0)=1+\frac{1}{2} \psi(0)+\frac{1}{2} \psi(1) \end{aligned}

We solve and find ψ(0)=10\psi(0)=10.