I'm randomly sampling $N$ items and I want to find $n$ such that I have a probability $P$ that I'll miss one. Practically, I'd select $P$ to be something like $10^{-12}$ so I'm almost assured to sample everything from among a relatively small sample set of $n$ things (this is for some program tester).

Anyways, using the Bernoulli trials equation of

$$P = \binom{n}{k}p^kq^{n-k}$$

where $k$ = 1, and $p = N^{-1}$, I think I've simplified it correctly as shown:

$$ \begin{align}P &= \frac{n!}{(n-1)!}\left(\frac1N\right)\left(1-\frac1N\right)^{n-1} \\ P &= \frac{n}{N}\left(\frac{N-1}{N}\right)^{n-1} \\ PN^n &= n(N-1)^{n-1} \\ n \ln (PN) &= \ln(n) + (n-1)\ln(N-1) \end{align}$$

Now I don't know where to go; I can't seem to solve for $n$. The second line seems closer, but I can't seem to figure out how to solve for $x$ given something like $xk^x$ (I could also get this I think:)

$$\left(N-1\right)P = n\left(\frac{N-1}{N}\right)^n$$

  • $\begingroup$ Do you want to 'miss $exactly$ a $particular$ one' , miss exactly one, or miss at least one (that is, not get them all)? How do you get from your first to your second equation? $\endgroup$ – BruceET Aug 31 '15 at 21:12
  • $\begingroup$ I want the probability that I will miss exactly one (then as $n$ continues to rise, $P$ will continue to fall). If $k=1, p=N^{-1}$ and $q = 1-N^{-1}$, doesn't that go from 1 to 2? $\endgroup$ – Nick T Aug 31 '15 at 21:56
  • $\begingroup$ Maybe express $n = aN$. For large $n,$ one has $(1 - a/n)^n \approx e^{-a}.$ $\endgroup$ – BruceET Aug 31 '15 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.