markov chains and coin flips

Question

A coin that comes up heads with probability p is continually flipped until the pattern T T T H appears. Let X denote the number of flips, find EX.

If I use Markov chains is there a simpler way to set up the states than using each state as a different combo? Or should I proceed in that way so that I have 16 states?

Answer 1

Probably the most straightforward approach is to set up a Markov chain with only 4 states (plus a stopping state that occurs when you finally get TTTH). The states are

• $S_0$: No T's on the last move (which includes the starting state).
• $S_1$: Only 1 T on the last move.
• $S_2$: Exactly two T's on the last two moves.
• $S_3$: 3 T's on the last 3 moves.

Let $(E_i)$ be the expected number of moves to stopping after reaching state $S_i$. The number you are after is $E_0$.

The transition equations are:

$$ \begin{array} {c} E_3 = p +(1-p)(1+E_3) \\ E_2 = (1-p)(1+E_3) + p(1+E_0) \\ E_1 = (1-p)(1+E_2) + p(1+E_0) \\ E_0 = (1-p)(1+E_1) + p(1+E_0) \end{array} $$ You can handle these from the bottom up, always working with just 2 of the $E_i$: $$ E_1 = E_0 - \frac{1}{1-p} $$ $$ E_2 = E_0 - \frac{2-p}{(1-p)^2} $$ and so forth.

Answer 2

Define the state of the Markov chain to be the sequence of the previous 4 coin tosses. The invariant distribution $\pi$ puts mass $p(1-p)^3$ on the state $TTTH$. Therefore the expected number of tosses needed to reach $TTTH$ again, starting at $TTTH$ is ${1\over\pi(TTTH)}={1\over p(1-p)^3}.$ For this pattern, that is the same as starting from scratch, so this answers the question.

Answer 3

Building up step by step:

$E(T)=\frac 1 {1-p},E(H)=\frac 1 p$

$E(TT)=E(T)+(E(T)-1)(1+E(T))+1=E(T)+E^2(T)$

$E(TTT)=E(TT)+(E(T)-1)(1+E(TT))+1=E(T)+E(T)E(TT)=E(T)+E^2(T)+E^3(T)$

$E(TTTH)=E(TTT)+E(H)=\frac 1 {pq^3}$

Answer 4

There is a trick to solve this type of problems without any algebra.

In general you have two cases. The one where the pattern overlaps and the one without overlaps:

Overlap means that a part of the series at the beginning is repeated exactly at the end of the pattern. Example: A pattern HTHHTHTH. In this case the pattern 'HTH' is repeated at the beginning and EXACTLY at the end of the pattern. Also, the single 'H' is an overlap.

The above pattern has expected time $\frac{1}{p^5q^3} + \frac{1}{p^2q} + \frac{1}{p}$. Which means that you find the expected value of a series of tosses not taking into account the overlaps. And add the overlaps.

In your case there is no overlap. So the answer is simply: $\frac{1}{pq^3}$ as was pointed out.

Look at section 3.6.4 of Introduction to Probability models by Seldon Ross to see a thorough explanation of this formula.