Drawing at least that many "distinct" balls of each color

Question

We have an urn with $n_1$ red balls and $n_2$ black balls (total number of balls is $n = n_1+n_2$). We will draw a total of $k$ balls with replacement.

1) What's the probability that in the $k$ draws, we end up getting at least $m_1$ distinct red and $m_2$ "distinct" black balls? Note that unlike most arguments I have seen, the event of interest here concerns sequences of draws in which we see at least $m_1$ different balls from the red group and $m_2$ different balls from the black group (one can think of these balls being numbered in addition to having different colors).

I have tried to count the number of "good" sequences of draws (that satisfy the above requirement) as

$$\binom{n_1}{m_1}\binom{n_2}{m_2}\sum_{i = m_1 + m_2}^n S(k,i) ~ i! $$

where $S(k,i)$ is the Stirling number of the second kind counting the number of partitions of $k$ objects into $i$ subsets, and then divide by $n^k$ to obtain the probability. My reasoning is that we can partition the draws into $i$ subsets, where $i$ is at least $m_1 + m_2$ and at most $n$, then multiply by the possible number of labels for these partitions, but I seem to be overcounting or doing something wrong.

I am also not sure if this question can be tied to some variation of the coupon collector problem. I am aware of many variations of the original problem in the literature with quotas, non-uniform distributions etc. but I am still not able to see a direct mapping since I am not trying to obtain the entire collection of balls (I need $m_1$ distinct ones from the red and $m_2$ distinct ones from the black).

Another question is what is the expected number of draws needed to guarantee we satisfy the above requirement (or bounds)? Finally, how would the arguments change if we solve the problem without replacement?

Answer 1

You can choose $j_1$ distinct red balls in $\binom{n_1}{j_1}$ ways and $j_2$ distinct black balls in $\binom{n_2}{j_2}$ ways. The probability that $k$ balls drawn contain exactly these $j_1+j_2$ balls is $n^{-k}S(k,j_1+j_2)(j_1+j_2)!$. Thus the probability that the condition is fulfilled after $k$ draws is

$$ n^{-k}\sum_{j_1=m_1}^{n_1}\sum_{j_2=m_2}^{n_2}\binom{n_1}{j_1}\binom{n_2}{j_2}S(k,j_1+j_2)(j_1+j_2)!\;. $$

Your approach doesn't work because it separates out $m_1$ and $m_2$ of the balls, but all distinct red balls seen and all distinct black balls seen are on an equal footing.

To find the expected number of draws required to fulfil the condition, recall from the coupon collector's problem that it takes an expected $\frac n{n-j}$ draws to get a new distinct ball when $j$ distinct balls have already been seen. We can sum these expectations with the probabilities that another distinct ball will be required after $j$ distinct balls have been seen:

$$ n\sum_{j=0}^{n-1}\frac1{n-j}\left(1-\sum_{j_1=m_1}^{j-m_2}\frac{\binom{n_1}{j_1}\binom{n_2}{j-j_1}}{\binom nj}\right)\;, $$

where the inner sum over $j_1$ is the probability that the condition has already been fulfilled after $j$ distinct balls were seen (and is empty if $j\lt m_1+m_2$).

If the problem is solved without replacement, the factor $\frac n{n-j}$ in the expectation drops out, and the probability of fulfilling the condition after $j$ draws is simply the inner sum over $j_1$ in the expectation.

Answer 2

Here is an answer to your question on MO.

I use the same notation as the cited article (so that the results can be directly compared), so consider an urn which for $i\in\{1,\ldots n\}$ contains $x_i\geq 1$ distinguishable coupons of type $i$, altogether $X_n:=x_1+\ldots+x_n$ coupons.

Coupons are drawn with replacement from this urn until (for each $i$) $m_i$ (where $1\leq m_i\leq x_i$) mutually different coupons of type $i$ have been drawn.

Let $m:=(m_1,\ldots,m_n)$ and $T(m)$ the random time at which this happens, and let $p_{x_i}(m_i,t):=\sum_{k=0}^{m_i-1}{x_i \choose k}\,t^k$.

Let $Y_1(k),\ldots,Y_n(k)$ be the random variables $Y_i(k):=$ number of different coupons of type $i$'' that have been drawn at "time" $k$.

I use generating functions and start from the following basic

Proposition The generating function of (the joint distribution of) $Y_1(k),\ldots,Y_n(k)$ is given by: \begin{equation*} \mathbb{E}\, t_1^{Y_1(k)}\ldots t_n^{Y_n(k)}=\frac{k!} {X_n^k}[t^k] (1+(e^t-1)\,t_1)^{x_1}\cdot\ldots\cdot(1+(e^t-1)\,t_n)^{x_n} \end{equation*}

Proof Let $j_1+\ldots +j_m\leq k$. Clearly $$\mathbb{P}(Y_1(k)=j_1,\ldots,Y_n(k)=j_n)=\frac{1}{X_n^k}\cdot {x_1 \choose j_1}\cdots {x_m \choose j_m}\cdot Sur(k,j_1+\ldots+j_m)$$ where $Sur(k,r)$ denotes the number of surjective mappings from $\{1,\ldots,k\}$ onto $\{1,\ldots,r\}$. It is known that $Sur(k,r)=k!\,[t^k]\,(e^t-1)^r$ (since a such a surjective mapping corresponds uniquely to an ordered partition of $\{1,\ldots,k\}$ into $r$ non-empty subsets, and $e^t-1$ is the exponential generating function for non-empty sets). The assertion about the g.f. follows. End of proof.

(I) The distribution of $T(m)$

Since $\{\,T(m)\leq k\}=\{\,Y_1(k)\geq m_1,\ldots,Y_n(k)\geq m_n\,\}$ the above gives \begin{equation*} \mathbb{P}(T(m)\leq k) =\frac{k!} {X_n^k}[t^k] (e^{tx_1} -p_{x_i}(m_i,e^t-1))\cdot\ldots\cdot(e^{tx_n} -p_{x_n}(m_n,(e^t-1)\,) \end{equation*}

(II) The expectation of $T(m)$

Finally, using $\mathbb{E} T(m)=\sum_{k\geq 0} \mathbb{P}(T(m)>k)$ and writing ${k! \over X_n^k} =X_n\,\int_0^\infty s^k e^{-X_ns}\,ds$ leads to

$$\mathbb{E}(T(m))=X_n\int_0^\infty \big(1-\prod_{i=1}^n \left(1-p_{x_i}(m_i,e^s-1)\,e^{-x_i s}\right)\big)\,ds$$