1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think that in this problem it might be much easier to exploit the "at least" nature of the question and consider instead the "less than" complement version of the question. $\endgroup$ – Aaron Montgomery Jun 19 '18 at 16:44
  • $\begingroup$ Thank you Aaron. I am not sure how this would simplify things. One may be able to use a union bound to separate the events that the balls drawn from one of the groups is less than the needed number, but that also requires computing the probability that the number of distinct balls drawn from one color is exactly (say) i. Any clue how one would proceed? $\endgroup$ – Abas Jun 19 '18 at 19:00
  • $\begingroup$ Please forgive me -- I think I hadn't fully thought through my comment, and it doesn't appear to have been as helpful as I hoped. $\endgroup$ – Aaron Montgomery Jun 20 '18 at 16:32
  • $\begingroup$ Thanks Aaron. Joriki provided a fix below and an elegant way to compute the expectation. $\endgroup$ – Abas Jun 20 '18 at 17:23
  • $\begingroup$ You had a related question on MO (which disappeared). Shall I answer that question here? $\endgroup$ – esg Aug 10 '18 at 16:38
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much @joriki for the fix and for the expectation analysis! $\endgroup$ – Abas Jun 20 '18 at 13:30
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Thanks @esg! I need to read this carefully to understand your analysis. $\endgroup$ – Abas Aug 12 '18 at 2:33
  • $\begingroup$ I created a post @esg instead of the MO one. Would you mind adding your answer to this post math.stackexchange.com/questions/2879927/… $\endgroup$ – Abas Aug 12 '18 at 2:44
  • $\begingroup$ I think where it says "an ordered partition of $\{1,\ldots,k\}$ in $r$ into non-empty subsets" it's supposed to say "an ordered partition of $\{1,\ldots,k\}$ into $r$ non-empty subsets"? $\endgroup$ – joriki Aug 12 '18 at 4:13
  • $\begingroup$ Also, I think ${k! \over X_n^k} =X_n\,\int_0^\infty e^{-X_ns}$ should be something like $\sum_k{k! \over X_n^k}[t^k]\ldots=X_n\,\int_0^\infty e^{-X_ns}\ldots\mathrm ds$? $\endgroup$ – joriki Aug 12 '18 at 4:27
  • 1
    $\begingroup$ @joriki: you're right, the $s^k$ was missing on the rhs $\endgroup$ – esg Aug 12 '18 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.