Comments on Multivariate urn/coupon collector problem without replacement
Post
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:
- 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.
- 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:
- 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$.
- 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}$.
- The expected number of balls before seeing the first color is always: $$\frac{m+1}{\left(\sum^{n}_{i=1} c_i\right) + 1}$$
- The expected number of balls before seeing the last color (i.e., coupon collector) is always (taken from this SE answer): $$\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 and this other post 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 comment thread