# Probability of not drawing $1$ or more of $n$ items in $y$ draws?

I'm trying to solve a problem that is somewhat similar to the following (which I've just written now; I swear I'm much too old for this to be homework):

You are putting together a bag of 30 marbles. The bag is to be composed of a random assortment of seven different colored marbles. What is the probability that at least one color of marble is missing from the bag (assuming each marble color is equally likely)?

My current expectation is that the answer lies in the binomial distribution, i.e., $$7 \operatorname{dbinom}(0, 30, 1/7) = .068,$$ as this should provide the probability of at least one of seven marbles not being in the bag. Is my math correct here?

• Are you assuming that each color marble is equally likely? If so, you ought to state that explicitly. Jul 10, 2021 at 3:25
• Yes! Sorry. I've added that assumption. Jul 10, 2021 at 3:33
• This dbinom(k, n, p) is the value at $k$ successes of the pmf of the binomial distribution with $n$ trials and success probability $p$ in R, right? This should be included in the question as not everyone here may be familiar with R. Jul 10, 2021 at 5:13
• If I understand the question correctly, this seems to be a case of the Coupon Collector's Problem Jul 10, 2021 at 13:31

Unfortunately, your math is not correct. I will use your notation of $$\operatorname{dbinom}(k, n, p) = \binom{n}{k} p^k (1 - p)^{n - k}$$ to show why. I’m also assuming that there are at least $$30$$ marbles of each color to choose from, so that every sequence of color choices is possible, and that each color is equally likely to be chosen at each step.

It’s true that the probability that a specific (equally likely) color is missing among a sequence of $$30$$ marble choices is $$\operatorname{dbinom}(0, 30, 1/7)$$. Since we want to know the probability that at least one of the colors is missing, this is the probability of the union of the events $$A_i = \{\text{i-th color is missing}\}$$ for each color $$i$$.

If the events were mutually exclusive, we could add each individual events’ probabilities, and that would be the probability of the union. However, these events are not mutually exclusive; it is possible for two colors to be missing.

If there were $$13$$ colors, instead of $$7$$, your method would give a probability of $$13 \operatorname{dbinom}(0, 30, 1/13) \approx 1.17782.$$ This can’t be right, because probabilities must be between $$0$$ and $$1$$.

The correct counting method to employ is the inclusion-exclusion principle for probability. The probability of the intersection of the $$k$$ events $$A_{i_1}, \ldots, A_{i_k}$$ is the probability that the colors $$i_1, \ldots, i_k$$ are missing from a sequence. This is given by $$(1 - k/7)^{30}$$ because each of the $$30$$ choices is independent, and there are $$k$$ out of $$7$$ colors that we are not allowed to use. Note that this number only depends on $$k$$, not on the specific colors $$i_1, \ldots, i_k$$ that were chosen.

Thus, the special case of the inclusion-exclusion principle where each probability only depends on $$k$$ yields

$$P\bigl(\bigcup_{i = 1}^7 A_i\bigr) = \sum_{k = 1}^7 (-1)^{k - 1} \binom{7}{k} \Bigl(1 - \frac{k}{7}\Bigr)^{30}.$$

The term for $$k = 7$$ is $$0$$ so this is the same as

$$\sum_{k = 1}^6 (-1)^{k - 1} \binom{7}{k} \Bigl(1 - \frac{k}{7}\Bigr)^{30} \approx \fbox{0.0677926};$$

this is slightly smaller than your answer of $$7 \operatorname{dbinom}(0, 30, 1/7) \approx 0.0686585$$.

Edit: The formula has a nice generalization for $$n$$ marbles and $$r$$ colors as

$$\sum_{k = 1}^{r - 1} (-1)^{k - 1} \binom{r}{k} \Bigl(1 - \frac{k}{r}\Bigr)^n = 1 - \frac{r!}{r^n} S(n, r)$$

where $$S(n, r)$$ are the Stirling numbers of the second kind.

• Amazing. Thank you for such a detailed and fascinating response, and for explaining the error in my original logic. Jul 12, 2021 at 15:47