Suppose I have an urn filled with infinitely many balls, each of which is colored one of $m$ (uniformly distributed) colors. Suppose I draw $n$ balls, so that I have $n_1$ balls of color $1$, $n_2$ balls of color $2$, ... , and $n_m$ balls of color $m$. What is the expected number of (disjoint) "complete sets" of colors balls (a complete set being a collection of balls, one of each color), that is, what is the expected value $\Bbb E[\min\{n_1, \ldots, n_m\}]$ of the quantity $\min\{n_1, \ldots, n_m\}$?

For example, for $m = 2$, there are $2^n$ ways to choose $n$ colored balls. There are $n\choose i$ ways to choose $i = n_1$ balls of color $1$ and $n_2 = n - i$ balls of color $2$, so the expected value of $\min\{n_1, n_2\}$ is just $$\Bbb E[\min\{n_1, n_2\}] = \frac{1}{2^n} \sum_{i = 0}^n {n \choose i} \min \{i, n - i\}.$$ For $n$ odd, we can use the symmetry of $\cdot\choose\cdot$ to rewrite this as $$2 \sum_{i = 0}^{(n - 1) / 2} i {n \choose i},$$ and using some familiar identities leads to $$\min\{n_1, n_2\} = n \left[\frac{1}{2} - \frac{1}{2^n} {{n - 1} \choose {\frac{n - 1}{2}}}\right] .$$ A similar formula holds for even $n$, and in both cases Stirling's approximation gives $$\Bbb E[\min\{n_1, n_2\}] = \frac{n}{2} - \sqrt{\frac{n}{2 \pi}} + O\left(\frac{1}{\sqrt{n}}\right) $$

By the same reasoning, for general $m$ we similarly have $$\Bbb E[\min\{n_1, \ldots, n_m\}] = \frac{1}{m^n} \sum_{n_1 + \cdots n_m = n} {n \choose {n_1 \,\cdots\, n_m}} \min\{n_1, \ldots, n_m\} .$$ Analogously to the $m = 2$ case, we should expect that this quantity is $\frac{n}{m} - O\left(\sqrt{n}\right)$ and that the exact formula depends on the residue class of $n$ modulo $m$.

Using the above strategy to produce an exact formula for the $m = 2$ case, which amounted to case splitting and using symmetry, is already unpleasantly tedious for $m = 3$, however.

My questions are:

  • Is there are a better way to produce an explicit formula for general $m$?
  • Is there an efficient heuristic for computing the coefficient $\color{red}{a_m}$ of the $\sqrt{n}$ term in the expansion $$\Bbb E[\min\{n_1, \ldots, n_m\}] = \frac{n}{m} - \color{red}{a_m} \sqrt{n} + O\left(\frac{1}{\sqrt{n}}\right) ?$$

While it would be nice to have an answer for general $m$, I am particularly interested in the case $m = 3$; numerical evidence suggests $\color{red}{a_3}$ is close to $\sqrt{\frac{3}{4 \pi}}$.

  • 1
    $\begingroup$ It should be possible to approximate $n_1, \ldots, n_m$ by a multivariate normal; then computing $a_m$ becomes "just" the computation of a high-dimensional integral... $\endgroup$ – Michael Lugo Mar 16 '17 at 18:06

Your Answer

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

Browse other questions tagged or ask your own question.