Post History

Multivariate urn/coupon collector problem without replacement

Simply put, the problem I have is:

Given an urn containing $m$ total balls of $n$ different colors with $c_i$ balls of each color (i.e., $m = c_1 + ... + c_n$), what is the expected number of balls you would need to draw to see the $k^{\text{th}}$ color when drawing without replacement?

This is a variation of the coupon collectors problem without replacement, with the difference being the variable stopping criterion $k$. Naturally, if $k = n$, this reduces to the usual coupon collector problem (without replacement) of finding all colors.

**Additional (optional) requirements:**

1. In my particular use case, there are actually also a number $c_b$ of balls without a color (referred to as black balls), which do not contribute to the number of colors seen.
2. It can also happen in my use case that a single ball consists of multiple colors, which can be thought of as a multi-colored ball.

Although these additional requirements more accurately reflect the actual use case, they are optional as I believe I can either adjust a solution to the original problem to incorporate them, or ensure that they do not occur (removing cases where they do). Thus a solution which also easily handles black and/or multi-colored balls would be preferred, but is not necessary.

What I've found so far
----------------------

I have been able to get a solution for a number of simplified cases:

1. When there is only one color (with $c_1$ balls of that color) and $c_b$ black balls, the expected number of balls to draw before seeing the color is $\frac{m+1}{c_1+1}$, where $m = c_1 + c_b$.
2. When there is only one ball of each color (i.e., $c_i = 1, \forall\ i$) and $c_b$ black balls, the expected number of balls before seeing the $k^{\text{th}}$ color is $\frac{k\cdot(m+1)}{n+1}$.
3. The expected number of balls before seeing the first color is always: $$\frac{m+1}{\left(\sum^{n}_{i=1} c_i\right) + 1}$$
4. The expected number of balls before seeing the last color (i.e., coupon collector) is always (taken from [this SE answer][1]): $$\displaystyle\sum\limits_{S\subseteq\{c_1, ..., c_n\}, S \neq \emptyset} (-1)^{|S|-1} \frac{m+1}{\left(\sum_{c_i \in S}c_i\right) + 1}$$ 

The similarities between the solutions of all of these special cases seems to indicate that there may exist a general solution that generalizes all of these.

There are also multiple related SE posts on the topic, however none of them seem to deal with quite the same problem. [This post][2] and [this other post][3] are perhaps the most related, as they deal with coupon collectors problem without replacement; However they do not factor in the variable stopping criteria. I suspect that due to the very similar problem, however, their solutions may be extendable to this situation.


  [1]: https://math.stackexchange.com/q/4328006
  [2]: https://math.stackexchange.com/questions/2172876/coupon-collector-without-replacement
  [3]: https://math.stackexchange.com/questions/4326738/sampling-without-replacement-expectation-proof/4328476#4328476