There are $2N$ balls in an urn, 2 from each of N colors. We draw $2M$ (M < N) balls from the urn (independently and without replacement) and randomly place $M$ balls in each of two smaller urns. Let $X$ be the number of colors that are represented in both of the smaller urns.

What is the pmf of $X$?

Ideally, I'd like to know the pmf of X. If this is not tractable, then some way to estimate the tail of the distribution would be okay. In particular I am interested in this problem with values of N $\approx$ 1000 and $M \approx$ 50.

Example of the sampling procedure

Suppose $N = 5$ and $M = 3$. The big urn contains: RED, RED, BLUE, BLUE, GREEN, GREEN, PINK, PINK, YELLOW, YELLOW.


and place them into:

small urn 1: RED, BLUE, GREEN

small urn 2: GREEN, PINK, YELLOW

Then $X$ = 1 since GREEN is represented in both of the smaller urns.

However, given the same original draw, if the balls had been placed as

small urn 1: RED, GREEN, GREEN

small urn 2: BLUE, PINK, YELLOW

Then $X$ = 0 because there is no color represented in both of the smaller urns.


Note that the sampling procedure here is the same as picking two consecutive samples of $M$ balls from the big urn without replacement. Treating the balls as distinguishable (even those of the same color) and the small urns as distinguishable, we see our sample space has ${{2N}\choose{M}}{{2N-M}\choose{M}}$ members.

Let $S$ be the set of all samplings which have exactly $k$ colors represented in both small urns. For each fixed $\lambda \in \{0\ldots\lfloor \frac{M-k}{2}\rfloor\}$, define $S_\lambda$ to be the set of samplings in $S$ where the first urn contains exactly $\lambda$ pairs of balls with matching colors.

To count $S_\lambda$, we note that there are $${{N}\choose{\lambda}}{{N-\lambda}\choose{M-2\lambda}}2^{M-2\lambda}$$ ways to pick the contents of the first urn. The first binomial picks the colors of the $\lambda$ pairs, the second binomial picks the colors of the remaining $M-2\lambda$ balls in the urn from the other colors, and the last factor picks one ball of each color.

Once the first urn is picked, we pick the contents of the second urn. Exactly $k$ colors must match, so from the $M-2\lambda$ singletons in the first urn, we must pick exactly $k$ balls to match in the second urn, which can be done in ${{M-2\lambda}\choose{k}}$ ways; once the colors are picked, there only remains one ball of each color. To pick the remaining $M-k$ balls in the second urn, we must avoid any previously chosen colors, so these balls can be picked in ${{2N-2(M-\lambda)}\choose{M-k}}$ ways.

Combining all this, and summing over all the possible values of $\lambda$, we have $$Pr[X=k] = \frac{\displaystyle\sum_{\lambda=0}^{\lfloor \frac{M-k}{2}\rfloor}{{N}\choose{\lambda}}{{N-\lambda}\choose{M-2\lambda}}{{M-2\lambda}\choose{k}}{{2N-2(M-\lambda)}\choose{M-k}}2^{M-2\lambda}} {\displaystyle{{2N}\choose{M}}{{2N-M}\choose{M}}}$$

  • $\begingroup$ Very nice, thank you. $\endgroup$
    – user35546
    Aug 27 '16 at 23:31

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.