# How many random selections needed to be 90%, 95%, 99% confident that a specific selection occurred?

For example, let's say that I have a bag of 100 marbles labeled 1 to 100. A "selection" is randomly picking a marble from the bag and then placing it back into the bag. The marble selected is not known.

How many random selections do I need to make to be X% confidence that a specific marble was one of the marbles I selected, say marble #42?

Is there a formula or a distribution that helps me solve for X (90%, 95%, 99% confidence)?

Bernoulli or Binomial distributions seem close, but I can not quite make them solve for what I want.

Each time you grab a marble you have a 1 out of 100 chance of selecting the correct one. What you are asking is what are the odds that at least one of these will be correct which would be an inclusive "or" statement

$$P_{selected} = p \cup p \cup p \cup p \cup p... \cup p$$

However this is not trivial to calculate since you could select your marble multiple times. Thus it's better to use the negative of this and calculate when it was not selected.

$$P_{selected}^\sim = (1-p)\cap(1-p)\cap(1-p)(1-p)\cap(1-p)...(1-p)\cap(1-p)$$

which can be easily calculated to N times by

$$P_{selected}^\sim = (1-p)^N$$

Where you can then show

$$P_{selected} = 1- P_{selected}^\sim = 1-(1-p)^N$$

and after some algebra

$$N = \frac{\ln(1-P_{selected})}{\ln(1-p)}$$

so 90% confidence is N = 229.

95% confidence is N = 298

99% confidence is N = 458.

If $X$ has $k$ distinct values, each appearing with equal probability $1/k$, then it follows discrete uniform distribution. Probability of drawing a specific $x$ in a single draw is

$$\Pr(X=x) = \frac{1}{k}$$

probability of drawing value other than $x$ is

$$\Pr(X \ne x) = \frac{k-1}{k} = 1-\frac{1}{k}$$

so if you make $n$ draws, probability that in neither of the draws $x$ is drawn is

$$\left(1-\frac{1}{k} \right)^n$$

from here you can easily find that probability of drawing at least one $x$ in $n$ draws is

$$1-\left(1-\frac{1}{k} \right)^n$$

Now all you need to know is find such $n$ that leads to prespecified probability.

This can be easily checked by simulation.

set.seed(123)

f <- function(n, k = 100) 1-((1-1/k)^n)
g <- function() which(sample(100, 1e4, replace = TRUE) == 42)[1]
sim <- replicate(5e4, g())

that returns

> quantile(sim, c(0.9, 0.95, 0.99))
90%    95%    99%
230.00 301.00 460.01
> f(c(230, 301, 460))
[1] 0.9008952 0.9514495 0.9901782

(Notice that example above concerns not with confidence intervals but with exact probabilities.)

This shows us that we need to sample $n$ values until $x$ occurs, so we are talking about negative binomial distributed variable with parameters $p=1/k$ and $r=1$ (observe $n$ values until $X=x$ occurs once, where probability of observing $x$ is $1/k$). Results obtained using negative binomial distribution agree with the simulation.

> pnbinom(c(230, 301, 460)-1, 1, 1/k)
[1] 0.9008952 0.9514495 0.9901782

So you intuition about binomial distribution was close, as it follows negative binomial distribution. Negative binomial with $r=1$ simplifies to geometric distribution. This is how we ended up with distribution that is traditionally used for modeling discrete waiting times.

> pgeom(c(230, 301, 460)-1, 1/k)
[1] 0.9008952 0.9514495 0.9901782

In fact, if you recall, cumulative distribution function for geometric distribution is

$$F(n) = 1 - (1-p)^n$$

where $p$ is a probability of observing $x$ in a single draw. So geometric distribution can be used to obtain confidence intervals for the number of samples that need to be taken.

# 95% CI using quantile function of geometric distribution
> qgeom(c(0.025, 0.975), 1/k)
[1]   2 367

Let $M=100$. Let's say you make $N$ selections and you are looking for the occurrence of marble $m$.

Let $E_n$ be the event that marble $m$ is drawn at draw $n$. Let $F_n=E_n^c$ be the event that marble $m$ is NOT drawn.

Note that $P(E_n)=1/M$. This means, $P(F_n)=1-1/M$.

Let $F$ be the failure event that marble $m$ is not drawn for any $N$. Success is then $F^c$.

$P(F^c)=1-P(F)$

Assuming independent draws, we have:

$P(F)=P(F_1 \cap F_2 \cap F_3 \cap \ldots \cap F_N)=\prod_{n=1}^N P(F_n)=(1-1/M)^N$

Therefore, $P(F^c)=1-(1-1/M)^N$.

For the $c \in [0,1]$ (e.g. $c=0.9 \equiv 90\%$ confidence) confidence, set the LHS to $c$ and solve for $N$.

$\Rightarrow N=\dfrac{\ln(1-c)}{\ln(1-1/M)}$