Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Comments on Multivariate urn/coupon collector problem without replacement

Post

Multivariate urn/coupon collector problem without replacement

+3
−0

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): $$\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.

History

1 comment thread

Given that $\frac{(ci)n}{(m)n}$ is the probability of getting $n$ balls of the $i$th color from an ur... (2 comments)
Given that $\frac{(ci)n}{(m)n}$ is the probability of getting $n$ balls of the $i$th color from an ur...
clemens‭ wrote 7 months ago · edited 7 months ago

Given that $\frac{(c_i)_n}{(m)_n}$ is the probability of getting $n$ consecutive balls of the $i$th color from an urn with $m$ balls total, I wonder how one derives such a simple solution as $\frac{m+1}{c_i+1}$ in your first partial solution above? And, relatedly, I am frankly a bit unsure about the fourth partial solution, because it seems it's using the Inclusion-Exclusion principle for expected values, and I'm not quite sure that makes sense given the interactions of expected values of different events.

Anyway, a very enjoyable question so far!

Dylan Callaghan‭ wrote 7 months ago · edited 7 months ago

For the first partial solution, there are two ways of deriving this. Intuitively, there is only one color of interest ($c_1$), accompanied by $c_b$ black balls. You could thus think of lining up all the balls in the order they were drawn, for which on average would see the colored balls equally dividing the black balls, leading to $\frac{m-c_1}{c_1+1}$ black balls before the first colored ball, and $\frac{m+1}{c_1+1}$ balls in total. Alternatively, you could derive this mathematically from the formula: $$\sum\limits^{c_b}_{i=1}\left(i \cdot \frac{\binom{c_b}{i} \cdot i! \cdot \binom{c_1}{1} \cdot (m - i - 1)!)}{m!}\right)$$ which is the sum of each possible number of balls $i$ occurring before the first colored ball, multiplied by the probability of that event occurring (i.e., the exp value formula). A simplification of this yields $\frac{c_b}{c_1+1}$, to which we add 1 to get the total number of balls seen.