# Streaks of heads/tails with Markov chains

Consider the following problem, from Tijms's Understanding Probability:

Calculate the probability of a run of five heads or five tails occurring in 20 tosses of a fair coin. What is the probability of a run of five heads occurring in 20 tosses of a fair coin? Do you think the following game is fair? A fair coin is tossed until heads appears three times in a row. You pay \$1 for each toss of the coin, but you get \$12.50 as soon as heads has appeared three times in a row.

This problem should be solvable by an absorbing Markov chain.

Let 1 be the state where in the last two tosses we had HT or TH, 2 be the state where in the last three tosses we got HTT or THH, 3 be the state HTTT or THHH in the last four tosses, 4 be the state HTTTT or THHHH in the last five tosses, 5 be the state with 5 heads or 5 tails.

The problem is equivalent to asking what is the probability of reaching state 5 in 20 steps starting from state 1.

The transition probabilities are the following:

$$P= \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 1 \\ \end{bmatrix},$$ because, for example, if we currently have HT (state 1), we can get to HTH (state 1) with probability $$1/2$$, and to HTT (state 2) with probability $$1/2$$ (this explains the numbers in the first column of $$P$$).

The entry in row 5, column 1 of $$P^{20}$$ is 0.47802, but the book says this probability is wrong (it should be 0.4584).

As for the second problem (if the game is a fair game), I suppose that we should compute the expected number of tosses before having three heads in a row, but I am not sure on how to do this.

Edit: following the hint by lulu, for the second part of the problem I think we should proceed as follows.

Let the state 1 correspond to only one T, or to a string that ends in T, the state 2 correspond to a single H or something that ends in TH, state 3 correspond to HH or something that ends in THH, state 4 correspond to HHH or something that ends in THHH. State 4 is absorbing.

The transition matrix is: $$P = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$$ (note that I use the opposite convention with respect to the first part of the problem, namely $$P$$ now would be $$P^T$$ in the first part).

Now, let $$e_i$$ be the expected number of tosses for reaching state 4 starting from state $$i$$. Clearly $$e_4=0$$ because if we are at state 4 we don't need to toss to arrive at state 4.

We have the following system of equations for the expected number of tosses: \begin{aligned} e_1 &= (1+e_1)\frac12 + (1+e_2)\frac12 \\ e_2 &= (1+e_1)\frac12 + (1+e_3)\frac12 \\ e_3 &= (1+e_1)\frac12 + (1+e_4)\frac12. \end{aligned} Replacing $$e_4=0$$ and solving for $$e_1$$, we get $$e_1=14$$. So the game would be fair if the reward were of 14\$or more, otherwise it is a losing game. Does it sound right? • For the second problem, this recent question is similar, the same techniques apply here. – lulu May 27 '19 at 9:36 • For the first problem, your work is fine (+1), except for one minor error. Since your specified initial state already assumes one flip, you should raise the matrix to the$19$-th power, not the$20\$-th. – quasi May 27 '19 at 9:37
• @quasi that's right, computing the 19-th power gives indeed 0.45840. Thanks! – J. D. May 27 '19 at 9:50

So you start with $$(1/2,1/2,0,0,0)$$ and multiply by $$P^{18}$$ , which in fact gives $$p(5)= \frac{240335}{524288} \approx 0.45840 \ldots$$