The Patient Coin Flipper

Let $X_n$ be the random variable for the number of coin tosses needed to obtain $n$ consecutive heads. Let $E_n$ be the expected value of $X_n$ . In order to obtain $n$ consecutive heads, we need to first obtain $n-1$ consecutive heads, and get heads on the next coin flip. If we get tails on the next coin flip, we are back at the start.

Hence, by Law of Iterated Expectation , $E[X_n] = \frac {1}{2} (E[X_{n-1}] + 1) + \frac {1}{2} ( E[X_{n-1}] + 1 + E[X_n])$ , or that $E_n = \frac {1}{2} ( E_{n-1} +1) + \frac {1}{2} ( E_{n-1} + 1 + E_n) \Rightarrow E_n = 2 E_{n-1} +2$ .

Clearly, $E_0 = 0$ , since we are guaranteed to get 0 consecutive heads after 0 coin flips. This allows us to calculate $E_1 = 2, E_2 = 6, E_3 = 14, \ldots E_{5} = 62$ .

Note: The closed form for $E_n$ is $2^{n+1}-2$ . This can be shown by solving the recurrence relation.

Let $E$ be the Expectation we want to calculate. Let $H$ stand for heads and $T$ stand for tails in the following. Note that if we ever get a $T$ , then since the coin tosses are independent, we would have to start over again.

If the first toss result in a $T$ , the probability is $\frac {1}{2}$ and the game restarts.

If the first and second tosses result in a $H$ , then a $T$ , the probability is $\frac {1}{4}$ ) and the game restarts.

If the first, second and third tosses result in a $H, H$ , then a $T$ , the probability is $\frac {1}{8}$ and the game restarts.

If the first, second, third and fourth tosses result in a $H, H, H$ then a $T$ , the probability is $\frac {1}{16}$ and the game restarts.

If the first, second, third, fourth and fifth tosses result in a $H, H, H, H$ then a $T$ , the probability is $\frac {1}{32}$ and the game restarts.

If the first, second, third, fourth and fifth tosses result in a $H, H, H, H$ and $H$ , the probability is $\frac {1}{32}$ , and the game ends.

Hence, by the linearity of expectation, we get $E= \frac {1}{2} \times (E+1) + \frac {1}{4}\times (E+2) + \frac {1}{8} \times (E+3) + \frac {1}{16} (E+4) + \frac {1}{4} \times (E+5) + \frac {1}{32} \times 5$ . Solving the equation, we get $E=62$ .

First of all, the expected number of coin tosses for getting a single head is 2 since on a coin toss, there are two possibilities but on the case of having consecutive number of heads, it is different . For example, as in the question, 5 consecutive heads. Before this would occur, we should first have to have a case where 4 consecutive heads to occur. And after that, depending on the next toss, we would either stop since a head is achieved otherwise continue if its a tail. Putting all this into equation: T = 1/2 (P+1) + 1/2(P+1+T) or T = 2P +2 where T is the expected number of coin tosses and P is the last expected coin tosses for the last consecutive number of heads.

So to get T for 2 consecutive heads: T = 2P + 2 T = 2(2) + 2 T = 6

For 3 consecutive heads: T = 2P + 2 T = 2(6) +2 T = 14

For 4 consecutive heads: T = 2P + 2 T = 2(14) + 2 T = 30

And lastly, for 5 consecutive heads: T = 2P + 2 T = 2(30) + 2 T = 62

At any stage, the situation can be described by a state variable $n =$ number of consecutive heads in the previous tosses. Whenever we toss another head, $n$ is increased by one; whenever we toss tail, we are back at state 0.

Let $E_n$ be the expected number of tosses from state $n$ . The answer to the problem will be $E_0$ .

Based on the process described above and the probabilities of $\tfrac12$ , we get the recurrence relations $E_n = 1 + \tfrac12 E_0 + \tfrac12 E_{n+1},$ and we set $E_5 = 0$ because it is the final state. In matrix form, $\left(\begin{array}{ccccc} \tfrac12 & -\tfrac12 & 0 & 0 & 0 \\ -\tfrac12 & 1 & -\tfrac12 & 0 & 0 \\ -\tfrac12 & 0 & 1 & -\tfrac12 & 0 \\ -\tfrac12 & 0 & 0 & 1 & -\tfrac12 \\ -\tfrac12 & 0 & 0 & 0 & 1 \end{array}\right) \left(\begin{array}{c} E_0 \\ E_1 \\ E_2 \\ E_3 \\ E_4\end{array}\right) = \left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array}\right).$ Solve this by (a) doubling the values of each row, (b) then adding each row to all rows underneath, $\left(\begin{array}{ccccc} 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right) \left(\begin{array}{c} E_0 \\ E_1 \\ E_2 \\ E_3 \\ E_4\end{array}\right) = \left(\begin{array}{c} 2 \\ 4 \\ 8 \\ 16 \\ 32 \end{array}\right),$ and finally (c) (starting at the bottom) adding each row to the one above it, $\left(\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array}\right) \left(\begin{array}{c} E_0 \\ E_1 \\ E_2 \\ E_3 \\ E_4\end{array}\right) = \left(\begin{array}{c} 62 \\ 60 \\ 56 \\ 48 \\ 32 \end{array}\right).$ These are the values of $E_n$ ; we read off immediately that $E_0 = \boxed{62}$ .

General case

The expected number of rolls to obtain $N$ consecutive heads is $2^{N+1} - 2$ .

Proof : with the definitions above, $E_n = 2^{N+1}-2^{n+1}.$ It is easy to check that $E_N = 2^{N+1}-2^{N+1} = 0$ to make state $N$ the proper endpoint; and $E_n = 2^{N+1} - 2^{n+1} = \tfrac12(2^{N+1}+2^{N+1} + 2 - 2 - 2^{n+2}) \\ = 1 + \tfrac12(2^{N+1} - 2) + \tfrac12(2^{N+1} - 2^{n+2}) = 1 + \tfrac12 E_0 + \tfrac12 E_{n+1}.$

Let $x$ be the expected number of tosses. It is clear that $x$ is finite.

Now, start tossing. If we get a tail immediately (probability $\frac{1}{2}$ ) then the expected number is $x$ +1.

If we get a head then a tail (probability $\frac{1}{4}$ ), then the expected number is $x$ +2.

Continue …. If we get 4 heads then a tail, the expected number is $x$ +5.

Finally, if our first 5 tosses are heads, then the expected number is 5.

Thus $x$ = $\frac{1}{2}$ ( $x$ +1)+ $\frac{1}{4}$ ( $x$ +2)+ $\frac{1}{8}$ ( $x$ +3)+ $\frac{1}{16}$ ( $x$ +4)+ $\frac{1}{32}$ ( $x$ +5)+ $\frac{1}{32}$ (5).

Solve this linear equation for $x$ . We get $x$ =62.

Let e be the expected number of tosses. It is clear that e is finite.

Start tossing. If we get a tail immediately (probability 1/2) then the expected number is e+1. If we get a head then a tail (probability 1/4), then the expected number is e+2. Continue ….

If we get 4 heads then a tail, the expected number is e+5. Finally, if our first 5 tosses are heads, then the expected number is 5. Thus,

e = 1/2 (e+1) + 1/4 (e+2) + 1/8 (e+3) + 1/16 (e+4) + 1/32 (e+5) + 1/32 (5).

Solve this linear equation for e. We get e = 62.

Imagine a gambler in a casino who bets against a fair coin. If he guesses correctly he doubles his stake, if he guesses incorrectly he loses his stake. Each time a coin is tossed he bets a new $1 that it lands heads. If he wins then he bets his winnings that the next coin will also be heads. He keeps going until the first time that five heads occur in a row.

When five heads occur in a row he leaves the casino with $32+16+8+4+2=62$ dollars i.e. 32 dollars from the stake that had accumulated 5 winning, 16 dollars from the stake with four winnings and so on.

As the casino is fair he would expect to leave the casino with the same amount of money that he had put in as bets. He gambles one dollar per round so the expected number of tosses is 62.

125-1=124/2=62