Suppose that on average, out of $N$ trials, $q$ succeed. $q$ is much smaller than $N$. For a concrete example, suppose $N = 100$ and $q = 2$.
Let $n$ be the number of trials run in a particular experiment. How large should $n$ be to ensure with probability $x$ that there is at least 1 success? For a concrete example, suppose that $x = 0.95$.
The probability that there are $k$ successes in $n$ trials might be approximated using the binomial distribution with probability parameter $p = q/N$.
The probability that there are is at least $1$ success is given by:
$$ x = 1 – P(\text{$0$ successes}) = 1 – {n \choose 0} p^0 (1 – p)^{n – 0} = 1 – (1 – p)^n $$
Solving for $n$:
$$ (1 – p)^n = 1 – x $$
Using our concrete values, we get:
$$ n \approx 150 $$
Let us now try the Poisson approximation approach. Let $\lambda = np$. Then:
$$ 1 – \frac{\lambda e^{-\lambda 0}}{0!} = x \Leftrightarrow 1 – \lambda = x \Leftrightarrow \frac{1 – x}{p} = n$$
Recalling that $p = q/N$:
$$ \frac{N(1 – x)}{q} = n $$
Using our concrete values for $N$, $x$ and $q$:
$$ n \approx 3 $$
There is already an issue with what I have done so far, since the Poisson approximation gives a result that is totally non-sensical. What am I doing wrong?
Going further, I want to try and bound the error in the estimate for $n$ that I get from the Poisson approximation. Tccuracy bounds on the Poisson approximation for the binomial distribution state that if $X \sim \text{Bin}(M, r)$, and $Y \sim \text{Poisson}(Mr)$:
$$ |P(X \in \mathbb{N}) – P(Y \in \mathbb{N})| \leq Mr^2 $$
since $\mathbb{N}$ is the set over which both Poisson and binomial distributions are defined (naturals include $0$).
I am a bit confused by the $P(X \in \mathbb{N})$ bit, and not quite sure how to use the bound to estimate how good $n$ is. Can you help?
Best Answer
You have miscalculated the probability in the Poisson case. Indeed, since the Poisson probability is given by $$ \mathbb P\bigl(\textrm{Poisson}(\lambda)=k\bigr)=\frac{\lambda^ke^{-\lambda}}{k!}, $$ we have that the probability of no successes is $$\frac{\lambda^0e^{-\lambda}}{0!}=e^{-\lambda},$$ not $\lambda$ as you have written. Thus, the Poisson approximation yields $$ 1-e^{-\lambda}=x\iff \lambda=-\ln(1-x) $$ Since $\lambda=np=\frac{nq}{N}$, we obtain that $$ n=\frac{\lambda N}{q}=\frac{-N\ln(1-x)}{q}=-50\ln(.05)\approx 149.787 $$
As a point of comparison, the true value of $n$ (without making any approximation) is $$ n=\frac{\ln(1-x)}{\ln(1-q/N)}=\frac{\ln(.05)}{\ln(.98)}\approx 148.284 $$ The difference between these two expressions is that in the exact expression the denominator is $\ln(1-q/N)$, which in the approximation is replaced by its first Taylor approximation, $-q/N$. (In general, the first Taylor approximation of $\ln(1+y)$ is simply $y$, and this is the case when $y=-q/N$.)