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)
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.