I asked this question on the Bitcoin Forum, but I think it's more appropriate for a mathematics forum.
I'm making an informative video and I need a binomial distribution calculation. I want to find out how many trials are needed to get 1%, 50% and 90% likelihood 1 or more successes. The problem is that the likelihood of success is 1 out of 2^160 (number of distinct bitcoin/ethereum addresses).
Normally for something like this, I would use a binomial distribution calculation in Excel using this formula:
=1-BINOM.DIST(0,????,2^-160,TRUE)
I would then tinker with the ???? until the entire cell result returned 1%, 50% and 90%. However, Excel can't handle numbers anywhere near this large. Does anyone know of a way I can calculate the number of trials required for these 3 percentages given the infinitesimally small chance of success? It would be great if there was an online tool I could use to support my results.
Just to illustrate what I'm looking for. If this analysis was for something much simpler, such as a probability of success being 1%, then I could calculate the results to be:
- 229 trials needed for 90%, | 89.99%
=1-BINOM.DIST(0,229,0.01,TRUE) - 69 trials needed for 50%, | 50.01%
=1-BINOM.DIST(0,69,0.01,TRUE) - 1 trial needed for 1%, | 1.00%
=1-BINOM.DIST(0,1,0.01,TRUE)
Best Answer
Letting $p$ be the probability of success on one trial, and letting $T$ be the desired probability that you want to exceed (for at least one success in $n$ trials), we need $$1-(1-p)^n>T$$ This can be rewritten as $(1-p)^n<1-T$.
So we want $n\ln(1-p)<\ln(1-T)$
Which is equivalent to $n>\frac{\ln(1-T)}{\ln(1-p)}$
If $p$ is very small you get a very good approximation to $\ln(1-p)$ with a degree one Taylor approximation: $\ln(1-p)\approx -p$. (The next term of the Taylor approximation will be $\frac{-p^2}{2}$ which can probably be considered negligible; and the overall error will also be around this value.)
So you would want $n$ to be around $\frac{\ln(1-T)}{-p}$
In the case of $p=2^{-160}$, this gives $n > -2^{160}\cdot \ln(1-T)$