5
$\begingroup$

This question is of interest:

If there is a $1 / x$ chance of something happening, in $x$ attempts, for large numbers over $50$ or so, the likelihood of it happening is about $63\%$. If there's a $1$ in $10\,000$ chance of getting hit by a meteor if you go outside, if you go outside $10\,000$ times, you have a $63\%$ chance of getting hit with a meteor at some point. If there's a $1$ in a million chance of winning the lottery and you buy a million (random) lottery tickets, you have a $63\%$ chance of winning.

What is the main idea underlying this property?

$\endgroup$
1
  • 5
    $\begingroup$ $(1-\frac{1}{x})^x\approx\frac{1}{e}\approx37\%$. In other words the chance of it not happening in $x$ attempts is about 37%. $\endgroup$
    – almagest
    May 25, 2016 at 17:40

2 Answers 2

5
$\begingroup$

Since the probability of each individual event is small, and the events are independent, these scenarios are well-approximated by a Poisson distribution. If the expected number of times an event occurs in some sample is $\lambda$, then the probability that the number of events that occurs is $k$ is $$P(k) \approx \frac{\lambda^k}{k!} e^{-\lambda} .$$

If the probability of an individual event occurring is $1 / N$ and our sample consists of $N$ trials, the expected number of events is $\lambda = N \cdot \frac{1}{N} = 1$, so the probability of $k$ events occurring among $N \gg k$ trials is $$P(k) \approx \frac{1}{e \cdot k!} .$$ In particular, the probability of at least one event occurring is $$P(\{1, 2, \ldots\}) = 1 - P(0) \approx 1 - \frac{1}{e} = 0.63212 \ldots .$$ As you've noticed, this approximation is good even for modest $N$: For $N = 10$, the actual value is $0.65132\ldots$, and for $N = 100$, it is $0.63396\ldots$.

We can write a higher-order approximation for $P(\{1, 2, \ldots\})$ by computing a power series for the exact probability, $P(\{1, 2, \ldots\}) = 1 - \left(1 - \tfrac{1}{N}\right)^N$, in $\frac{1}{N}$: $$P(\{1, 2, \ldots\}) = \left(1 - \frac{1}{e}\right) + \frac{1}{2 e N} + \frac{5}{24 e N^2} + O\left(\frac{1}{N^3}\right) .$$

This also suggests a way of formulating and proving a precise estimate: We can readily check that $x \mapsto 1 - (1 - x)^{1 / x}$ is increasing, so for $N$ at least, e.g., the suggested value of $50$, we have that $$0.63212\ldots < P(\{1, 2, \ldots\}) \leq 1 - \left(1 - \frac{1}{50}\right)^{50} = 0.63583\ldots,$$ giving a maximum relative error for $N \geq 50$ of $\approx 0.37\%$.

$\endgroup$
2
  • $\begingroup$ Good answer! Is there an illuminating explanation of why $e$ is appearing all over the place here, in relation to the exponential function and its slope? $\endgroup$
    – Hatshepsut
    May 25, 2016 at 18:03
  • 1
    $\begingroup$ Thank you, I'm glad you found it useful. A partial answer is that one almagest hints at in his comment: One of the usual definitions of $e$ is the limit $\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n$, and it's not too much work to conclude from this that the limit as $N \to \infty$ of the exact probability $\left(1 - \frac{1}{N}\right)^N$ is $\frac{1}{e}$. One needs to muddy their hands a little with numerical values to get a quantitative measure of how quickly this limit converges, i.e., how quickly the approximation becomes good. $\endgroup$ May 25, 2016 at 18:08
2
$\begingroup$

It's a limit problem.. the limit of 1-(x-1)/x)x as x approaches infinity is 1-(1/e) which is ~ 63%.

So yes, if you have a one in a million chance of winning the lotto, and you buy 1 million random tickets, you have a 63% chance of winning.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .