2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For the second problem, this recent question is similar, the same techniques apply here. $\endgroup$ – lulu May 27 '19 at 9:36
  • 1
    $\begingroup$ 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. $\endgroup$ – quasi May 27 '19 at 9:37
  • $\begingroup$ @quasi that's right, computing the 19-th power gives indeed 0.45840. Thanks! $\endgroup$ – J. D. May 27 '19 at 9:50
1
$\begingroup$

You are starting with HT or TH, which consists of two flips, the full outcome of which is (HT,TH) = state 1 and (TT,HH) = state 2.
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$$

$\endgroup$
  • $\begingroup$ +1: That is a nice and quick answer $\endgroup$ – Maximilian Janisch May 28 '19 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.