Assume you have a bag containing $m$ marbles, of $c$ different colors, where the number of marbles of each color is equal to $\frac mc$.

If $n$ marbles are drawn from the bag, without replacement, what is the probability $P$ that at least one complete set of all the marbles of one color is drawn?

Obviously, if $n<\frac mc$, then $P=0$.

Also, by the pigeonhole principle, if $n>m-c$ then $P=1$, because $m-c$ is the number of marbles you would have to draw in order to draw all but one of each color.

So far, all I've been able to find information on is how to find the probability that all marbles drawn are the same color, in which case, if $n>\frac mc$, then $P=0$.

In the case where $n=\frac mc$, the formulas are the same: $$\frac{c\left(\frac{\left(\frac mc\right)!}{\left(\left(\left(\frac mc\right)-n\right)!\right)n!}\right)}{\frac{m!}{\left(\left(m-n\right)!\right)n!}}$$

That's assuming I correctly translated that formula from my notes on the subject. In case I didn't, here's the original, which is unformatted and uses a different set of variables:

"Where: t = total # of marbles, s = # of marbles of each color, and p = # of marbles picked

(t / s) * (s!/((s-p)!p!)) / (t!/((t-p)!p!))"

I'm sure the formula to solve this is out there somewhere, assuming that finding a general formula isn't np-hard, as a programmer friend of mine suggested it might be, but, for the life of me, I haven't been able to find it. If needed, I have a 14-page Google Doc full of my notes on my attempts to solve this problem, including several brute-force attempts (which contribute most of its length), but it's a slog, and I don't want to subject you to it if someone can just give me a general formula.

  • $\begingroup$ Is there something up with your formatting/variable usage? You talk about P being 0 if n<m, but that would basically be if you didnt draww all the marbles. I suspect you meant m/c $\endgroup$ – Kitter Catter Jun 15 at 13:37
  • $\begingroup$ I would think this can be solved by a somewhat tedious application of the Inclusion-Exclusion principle. $\endgroup$ – antkam Jun 15 at 13:50
  • $\begingroup$ @KitterCatter Whoops. I made that mistake a couple of times in there. Fixed it. $\endgroup$ – AgentA1cr Jun 15 at 18:57
  • $\begingroup$ @antkam I may be misunderstanding you, but a tedious way to solve an individual case isn't what I'm looking for. I've already done enough of that in the brute force attempts mentioned in my original question. What I'm looking for is a general formula for P given m, n, and c. $\endgroup$ – AgentA1cr Jun 15 at 19:03

It's a straightforward application of inclusion and exclusion. Writing $k=m/c$ for the number of marbles of a given color, the probability is $${1\over{m\choose n}}\sum_{j=0}^{c-1}(-1)^j{(c-j)k\choose n}{c\choose j}$$

Each summand includes of excludes the number of ways of choosing $n$ marbles of $c-j$ of the colors, times the number of ways of choosing the colors.


NOTE: When I started writing this there was no Answer yet, but it took me so long to write this and get all the formatting correct, that @saulspatz scooped me. :) I will leave this up anyway...

You can solve this using Inclusion-Exclusion Principle, but (as usual for I-E) the result is a big summation, not a closed form.

  • For shorthand, define $r = m/c =$ no. of marbles of each color.

  • For $j \in \{1, 2, \dots, c\}$ let $N_j =$ the event that color $j$ is Not drawn (among the $n$ marbles), and $D_j =$ the complementary event that the color $j$ is Drawn.

  • You want every color to be drawn, i.e. you want $P(\bigcap_{j=1}^c D_j) = 1 - P(\bigcup_{j=1}^c N_j)$

The union can be calculated by I-E:

$$ \begin{align} P(\bigcup_{j=1}^c N_j) &= \sum_{1\le j \le c} P(N_j) - \sum_{1 \le j_1 < j_2 \le c} P(N_{j_1} \cap N_{j_2}) + \sum_{1 \le j_1 < j_2 < j_3 \le c} P(N_{j_1} \cap N_{j_2} \cap N_{j_3}) - \cdots\\ &= \sum_{k=1}^c (-1)^{k+1} \Big(\sum_{1 \le j_1 < \cdots < j_k \le c} P(N_{j_1} \cap \cdots \cap N_{j_k}) \Big) \end{align} $$

Now consider a particular $k$. Each term in the summation represents a subset of $k$ colors that are not drawn, i.e. the event that all $n$ must come from the other $c-k$ colors, i.e. the other $r(c-k) = m-rk$ marbles. The probability is:

$$P(N_{j_1} \cap \cdots \cap N_{j_k}) = \begin{cases} {m-rk \choose n} / {m \choose n} & \text{if } m-rk \ge n, \text{ i.e. } k \le {m-n \over r}\\ 0 & \text{if } m-rk < n \end{cases}$$

The number of terms in the summation $\sum_{1 \le j_1 < \cdots < j_k \le c}$ is ${c \choose k}$, representing all possible $k$-sized subsets. Combining these observations:

$$ \begin{align} P(\bigcup_{j=1}^c N_j) &= \sum_{k=1}^d (-1)^{k+1} \Big( {c \choose k} {{m - rk \choose n} \over {m \choose n}} \Big) \end{align} $$

where $d = \lfloor {m-n \over r} \rfloor$ is the new limit of the summation because for $k > d$ the terms are zero.


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.