3
$\begingroup$

If I'm selecting $N$ elements uniformly at random (with replacement) from $\{1, \dots, N\}$, what is the chance that a given value is selected at least once?

What is the name for the distribution for the more general case where I'm selecting $N$ elements from a domain with $M$ elements?

$\endgroup$
  • 1
    $\begingroup$ by random do you mean equally-probable ? $\endgroup$ – user451844 Sep 6 '17 at 23:31
  • 2
    $\begingroup$ @Roddy Uniformly at random means equally-probable. The key word is "uniformly". $\endgroup$ – Trevor Gunn Sep 6 '17 at 23:51
  • $\begingroup$ @TrevorGunn yeah I'm stupid sorry. $\endgroup$ – user451844 Sep 6 '17 at 23:55
3
$\begingroup$

Your answer is a particular case of the binomial distribution. Let getting a $1$ be a Success. You have $N$ independent trials. In the general version, the success probability is $p = 1/M.$

If $X \sim \mathsf{Binom}(N, 1/M),$ then you seek $$P(X > 0) = 1 - (1-p)^N = 1 - (1 - 1/M)^N = 1 - \left(\frac{M-1}{M}\right)^N,$$ as in the Answer of @ConMan (+1), which I hope you will Accept. [On each trial, you might say that you are using a discrete uniform distribution on the integers $1$ through $M$.]


Example: What is the probability you get at least one $6$ in ten rolls of a fair die? Then $X = \mathsf{Binom}(10, 1/6)$ is the number of $6$'s and you seek $P(X > 0) = P(X \ge 1) = 0.8385,$ computed in R statistical software as:

1 - dbinom(0, 10, 1/6)
## 0.8384944

In the figure below, you want the total heights of the bars to the right of the dotted red line.

enter image description here

$\endgroup$
  • $\begingroup$ All the answers here were excellent, but I accepted this one since I mentioned binomial distribution and included a graphic, and because you fixed up my notation in the question. $\endgroup$ – BeeOnRope Sep 7 '17 at 17:26
6
$\begingroup$

If you're drawing with equal probability and subsequent draws are independent of each other, then the probability that you do not draw, for example, "1" in a single draw from $M$ elements is $\frac{M-1}{M}$.

The probability that you do not draw any "1"s in $N$ draws is the product of the individual probabilities, i.e. $\frac{M-1}{M}\cdot\frac{M-1}{M}\cdot\ldots\cdot\frac{M-1}{M}=\left(\frac{M-1}{M}\right)^N = \left(1 - \frac{1}{M}\right)^N$.

The probability that you draw at least 1 "1" in the $N$ draws is the complement of the probability that you draw none, i.e. it is $1 - \left(1 - \frac{1}{M}\right)^N$.

$\endgroup$
3
$\begingroup$

The distribution for drawing $M$ elements with replacement from a set of $N$ elements is the uniform distribution on all $M$-tuples from $\{1,\dots,N\}$. For example, with $M = 3$ and $N = 2$ we get 8 ($=2^3$) $3$-tuples:

$$(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2) $$

and each is equally likely.

Viewed this way, the question of how likely it is to see a given value at least once comes down to counting those sequences that contain the value somewhere. We can count this by counting the tuples that do not contain that value. We know that there are $N^N$ total $N$-tuples and $(N - 1)^N$ tuples not containing a specified value. Thus there are

$$ N^N - (N - 1)^N $$

tuples that contain a specified value. Since the distribution is uniform, the probability of selecting such a tuple is

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


Now let's say that we have the elements $\{1,\dots,N\}$, we draw $M$ of them and we want at least $P$ of them to equal $1$ (or any other fixed element). Then to count the number of $M$-tuples with $P$ $1$'s, first we select the $P$ slots to put the $1$'s in, then from the $M - P$ remaining slots, we have $N - 1$ options each. This gives

$$ \binom{M}{P} (N - 1)^{M - P}. $$

Now we may divide by the total number of $M$-tuples ($N^M$) to get a probability of

$$ \binom{M}{P} \frac{(N - 1)^{M - P}}{N^{M - P}} \cdot \frac{1}{N^P} = \binom{M}{P} \left( 1 - \frac{1}{N} \right)^{M - P} \left( \frac1N \right)^{P}. $$

This is the probability mass function of the binomial distribution. Namely $\mathsf{Bin}(M, \frac{1}{N})$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.