Expected Number Of Coin Tosses Until You Get Tail

Because of my interest in BitCoin I was confronted with the question of the expected number of attempts to achieve a specific result if the probability of achieving the result per attempt is fixed. In BitCoin mining, the miners test nonces for hashing a certain value, trying to find a nonce so that the sha256 hash of the nonce combined with the value is a number below a certain threshold. Every test of a nonce has a fixed probability of succeeding, so it is exactly this classic problem of the expected number of attempts.

A simpler variant of the problem is: what is the expected number of coin tosses until you receive head (or tail). Or how many dice rolls on average until you roll a six.

Anyway, my maths being a little rusty I did not know immediately how to calculate it. I remember how to calculate the expected “value” of some event: it is the sum of the values of the possible outcomes multiplied with the respective probabilities for the outcomes. But for the expected number of attempts until something happens, this yields an infinite sum: p*1+(1-p)*p*2+(1-p)^2*p*3+…+(1-p)^(n-1)*p*n+… if the probability for the desired result is p. That is because the probability to get the result after n attempts for the first time is the probability to not get it in the first n-1 attempts (1-p)^(n-1) multiplied by p. And we want to sum the probability for it taking one attempt+the prob. for it taking two attempts+… up to infinity.

On the internet I found some claims that the expected number of attempts is simply 1/p, but I could not find an explanation for it. Now in the meantime I found a really elegant and much more versatile solution to the problem, but I had already decided that I needed to tackle that “nasty” infinite sum. So while the solution mentioned above obliterates the need, I still want to show how to compute that infinite sum, as I could find no other explanation on the internet.

To compute the infinite sum, we’ll look at the partial sums p*1+(1-p)*p*2+(1-p)^2*p*3+…+(1-p)^(n-1)*p*n. Thinking about progressions, one famous progression immediately comes to mind: the Geometric Progression p+p^2+p^3+…+p^n. It is memorable for the neat trick for computing it’s value: multiply the whole thing by (1-p)/(1-p), then most terms in the numerator cancel each other out and we are left with (1-p^(n+1))/(1-p).

Our sum almost looks like the geometric progression, if only we could use the same trick to compute it. Luckily we can. First, let’s say q = (1-p) and observe that we can factor out the p from the sum. So we are left with the problem to compute p(1+2q+3q^2+…+nq^(n-1)). If we multiply this with (1-q)/(1-q) we get

p(1+(2q-q)+(3q^2-2q^2)+…+(nq^(n-1)-(n-1)q(n-1)-nq^n)/(1-q) = (since p = 1-q)

= 1+q+q^2+…+q^(n-1)-nq^n

The first part of that is a geometric progression, so we know it is equal to

(1-q^n)/(1-q) – nq^n

Still not that pretty, but we are making progress. Rather than trying to make that partial sum more pretty, let’s see what happens for n-> infinity: since q < 1 we have q^n -> 0 and I claim that nq^n -> 0 too (will show this later). Therefore lim_n_to_infinity((1-q^n)/(1-q) – nq^n) = 1/(1-q), or 1/p. So there we have it, the expected number of attempts until a result of probability p happens is 1/p.

For toin cosses p = 0.5, so the number of attempts is 2. For rolling a six with a die, it is 6.

As for the remaining step, nq^n -> 0 for q < 1, I admit I also had to Google for a hint. The (or one trick) is to write q as 1/(1+a) for some a > 0. Then the equation becomes n/(1+a)^n. Then we look at the Binomial Sum for (1+a)^n, which is

1+(1 out of n)a+(2 out of n)a^2+…+a^n <= n(n-1)*a^2/2 (since 2 out of n = n(n-1)/2).

Therefore n/(1+a)^n <= n/(n(n-1)*a^2/2) = 2/((n-1)a^2) which obviously goes to 0 for n -> infinity.

I am not sure who the audience for this blog post could be, but anyway, I am glad I found a small puzzle and managed to learn some simple new tricks while trying to solve it. I am excited about the solution I linked to above, which sets up equations for the expected value E = 1*p+(1-p)*(E+1). It is much simpler, and also more versatile, as you can use the same approach to answer questions like “how many coin tosses until you get three times head in a row”. Somehow I have never encountered that approach before, as far as I remember.

Also I must admit I was a bit disappointed by the internet, namely the apparent willingness to accept the formula E(number of attempts) = 1/p without questioning how to derive it. This has to be explained somewhere else already, but if not, maybe I did my small part to plug an information hole in the internet. :-)

This entry was posted in Uncategorized. Bookmark the permalink.

10 Responses to Expected Number Of Coin Tosses Until You Get Tail

  1. M. M. says:

    I googled for math homework help and this was exactly what I was looking for, thanks!

  2. Jake says:

    In the elegant solution you linked in the first half of this post, you can derive the E(x) = 1/p equation by solving the elegant formula for any probability p (instead of just using p=0.5 for a coin flip). The derivation would look something like this:

    X = (1-p)(1+X) + (p)(1)
    X = 1 + X – p – pX + p
    X – X + pX = 1 – p + p
    pX = 1
    X = 1/p

    Also thank you for posting this, I also found it extremely helpful for one of my homework assignments.

  3. Alfreda Dale says:

    is the (H, 2) sum of 1 − 2 3 − 4 … guarantees that it is the Abel sum as well; this will also be proved directly below.

  4. David says:

    Another way of thinking about it…
    1/(1 – x) = 1 + x + x^2 + x^3 + …

    Taking the derivative gives

    1/(1 – x)^2 = 1 + 2x + 3x^2 + 4x^3 + n*x^n-1

    sum(n*(1-p)^(n-1)) = 1/(1-(1-p))^2. = 1/p^2

  5. Nishad says:

    I just cant get it to display this line :o
    There’s an error , you posted:
    1 + nC1*a + nC2*a^2 …. (less than or equals) nC2a^2,=.

    Actually, its the opposite. It must be, LHS (greater than or equals) RHS, as the RHS is just one single term from the LHS(binomial expansion).

    I tried multiple times, but its not lettimg me post the less than or equals symbol correctly . Sorry for multiple posts!

    • admin says:

      You are right, thanks! I’ll correct the error asap, somehow WordPress doesn’t let me at the moment :-(

  6. rsquirrel says:

    The answer E=1/p may be valid but one important note is that
    questions like “how many coin tosses until you get three times head in a row”
    cannot be applied to this formula.
    The reason is that on any given flip, you can get tails with 1/p
    But on the first flip, your probability of getting tails is 0

    For the specific solution to that problem turns out to be
    x = 2^(N+1)-2
    i.e. 6 flips for 2 heads in a row and 14 for 3 heads in a row.

    • rsquirrel says:

      oops that should be
      “But on the first flip, your probability of getting 2 tails in a row is 0″

      So I guess one way to look at is is, you wait 2 tries to get the first tail to start your chain for 2 tails, then you have 1/4 chance for 2 tails = 2+4 = 6
      Then you wait 6 tries to get the first 2 tails to start and 1/8 chance it will happen
      = 6+8 = 14

  7. Kat says:

    What does the * mean in the notation? Does it mean multiply??
    Thanks.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>