1
$\begingroup$

TLDR:

Let's say I have an urn with $n$ balls, with $K$ different colors of balls, where each color has the same number of balls: $\frac{n}{K}$. Given I reach into the urn and grab a ball (without replacement) $m$ times, what is the probability of getting $k$ different colors of balls?

Further explanation:

Example: I have an urn with $GGRRBBYY = n = 8$ number of balls, with $K = 4$ different colors of balls (Green, Red, Blue Yellow). What is the probability of me getting exactly $k = 3$ different colors of balls given I grab $m = 5$ balls from the urn.

Success: $$YGGBB$$

Failure: $$YRGBB$$

I want to find a way to solve this for any value of $m$,$k$,$K$,$n$.

This is essentially a more complicated version of figuring out the probability of $m$ balls falling into $k \leq n$ bins, for the 'balls into bins' question ($m$ balls in total, $n$ bins in total). See here (in equation 1) and here (at the end of the answer) solutions to solve the easier 'balls into bins' variant. The answer is:

$${n \choose k}\frac{\left\{\begin{array}{l} m \\ k \end{array}\right\} k !}{n^{m}}$$

I am looking for a similar solution to the urn problem I have stated. I believe using a multivariate hypergeometric distribution could give me the answer, although I think this will be complicated and extremely costly to compute. Basically, my idea is to count all possible combinations that exactly $k$ different colors of balls can be selected by applying the multivariate hypergeometric distribution formula many times. That is:

$$\frac{\sum {\frac{n}{K} \choose w_1}{\frac{n}{K} \choose w_2} \cdots {\frac{n}{K} \choose w_K}}{{n \choose m}}$$

The summation above denotes summing over all possible combinations of $w_i$ for all $i$, where $w_1 + w_2 \cdots + w_K = m$ and there are only $k$ number of $w_i$ that are greater than $0$. (excuse me on my potentially poor use of notation).

There must be a better way of formulating this... but if not, it would be nice of someone to suggest a fairly efficient way of computing this (by compute, I mean: some computer code that will calculate it for me). Or if someone could provide an approximation or a lower bound via a much more compact/simple formulation, that would also be wonderful! Perhaps modelling the problem as a 'balls into bin' scenario is a 'good enough' approximation...?

This similar question might also be inspiration for a better way to solve the problem.

$\endgroup$
5
  • 1
    $\begingroup$ Pick $K-k$ colors and compute the likelihood of avoiding those colors. Then multiply by $\binom Kk$ to get the likelihood of no more than $k$ colors. Do it again for the likelihood of excluding $k+1$ colors. Subtract one answer from the other to get the likelihood of excluding exactly $k$ colors. $\endgroup$
    – Robert Shore
    Jun 27, 2022 at 21:58
  • $\begingroup$ Thanks for the suggestion; it is clever yet simple! I noticed a couple grammar/logic errors. I think this is what you meant to say: "Pick $K−k$ colors and compute the probability of avoiding those colors. Then multiply by ${K \choose k}$ to get the probability of picking no more than k colors. Repeat the previous step to get the probability of avoiding $K - (k-1)$ colors (picking no more than $k-1$ colors). Subtract the second probability from the first probability to get the probability of picking exactly k colors." $\endgroup$
    – Quantum Guy 123
    Jun 28, 2022 at 16:56
  • $\begingroup$ hmmm... I'm a bit confused now. I tried calculating it the way you suggested and I think there is an issue with your method. Multiplying by ${K \choose k}$ results in over-counting (resulting in a probability greater than 1 in some instances). $\endgroup$
    – Quantum Guy 123
    Jun 28, 2022 at 18:13
  • $\begingroup$ You need to multiply the likelihood of avoiding $K-k$ specific colors by $\binom Kk$ in order to determine the likelihood of avoiding all possible sets of colors of that size. I suggest you edit the question to show this new work so we can see where the problem lies. $\endgroup$
    – Robert Shore
    Jun 28, 2022 at 20:02
  • $\begingroup$ Cross-posted at CrossValidated here, with currently one answer masquerading as a comment. Sometimes CV is more useful for probability and combinatorics questions... $\endgroup$
    – Stephan Kolassa
    Jul 23, 2022 at 7:16

0

Reset to default

You must log in to answer this question.