Yesterday evening I read a very interesting article on prime numbers which contained the following paragraph on coin tosses:

If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses.

I immediately tried to look into this question. Using the formula provided by André Nicolas, it can be shown that the expected number of coin tosses we need before getting $n$ consecutive heads is given by:

\begin{equation} e_n = \sum_{k=1}^n\frac{1}{2^k}(e_n+k)+\frac{n}{2^n} \end{equation}

For $n=2$, the expected number of heads($e_2$) is 6. Analytically, this makes sense once you become familiar with the above equation. Now, what I find interesting is that, as mentioned in the article, the probability of obtaining two heads is the same as the probability of obtaining a head followed by a tail:

\begin{equation} P(HH)=P(HT)=\frac{1}{4} \end{equation}

However, the expected number of coin tosses required to get the $HT$ pattern is 4 not 6. I still find this quite counter-intuitive. In fact, I ran a simulation using the following python code:

import numpy as np

head_tail = np.zeros(10000)
two_heads = np.zeros(10000)

for i in range(10000):
    z = np.random.randint(2, size=100)

    for j in range(100):
        if z[j] == 1 and z[j+1] == 0:

            head_tail[i] = j+2


    for j in range(100):

        if z[j] == 1 and z[j+1] == 1:

            two_heads[i] = j+2


And I noticed that their distributions behaved very differently:

enter image description here

It's by no means intuitive to me that the behaviour of these two distributions should be very different and yet they are remarkably different. Is there an intuitive reason why this must be the case?

  • 3
    $\begingroup$ To get a head requires at average $2$ throws, then every tail following completes the $HT$-pattern. So, $4$ throws are needed in average. However, for Bob, it is not enough to get two heads, for example $HTH$ does not give the $HH$-pattern. This is the reason why Bob needs more throws in the average. $\endgroup$ – Peter Oct 6 '17 at 13:46

Alice and Bob toss their coins until they see their first head.   The expected tosses until this happens is the same for each.   Then things are different.

Alice just needs to continue until she finally sees a tail.

However, if Bob doesn't immediately see a head on the next throw, he needs to start over from the beginning.

Thus $\mathsf E(A) ~{= \mathsf E(H)+\mathsf E(T)\\ = 2+2\\= 4}\\ \mathsf E(B)~{=\mathsf E(H)+1+\tfrac12\mathsf E(B)\\ =3+\tfrac 12\mathsf E(B)\\=6}$


Your Answer

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