Consider an urn containing $N$ balls of $P$ different colors, with $p_i$ being the proportion of balls of color $i$ among the $N$ balls ($\sum_i p_i = 1$). I draw $n \leq N$ balls from the urn without replacement and look at the number $\gamma$ of different colors among the balls that were drawn. What is the expectation of $\gamma$ as a function of $n/N$, depending on suitable properties of the distribution $\mathbf{p}$?

To give more insight: if $N = P$ and $p_i = 1/P$ for all $i$, then I will always see exactly $n$ colors, that is, $\gamma = P (n/N)$. Otherwise, it can be shown that the expectation of $\gamma$ is $>P(n/N)$. For fixed $P$ and $N$, it would seem that the factor by which to multiply $n/N$ would be maximal when $\mathbf{p}$ is uniform; maybe the expected number of different colors seen be bounded as a function of $n/N$ and, e.g., the entropy of $\mathbf{p}$?

This seems related to the coupon collector's problem, except that sampling is performed without replacement, and the distribution of the coupons is not uniform.

  • 1
    $\begingroup$ I think this problem can be stated as: what is the expected number of nonzero entries in a sample from a multivariate hypergeometric distribution? $\endgroup$ Commented Jun 25, 2016 at 19:07
  • $\begingroup$ This is a specific case of the skewed general distribution. See solution here adellera.it/static_html/investigations/distinct_balls/… $\endgroup$
    – RM-
    Commented Aug 23, 2021 at 11:57
  • $\begingroup$ There is nothing generally known as a "skewed general distribution:" that phrase is used in your reference to classify certain kinds of multinomial distributions. $\endgroup$
    – whuber
    Commented Aug 23, 2021 at 13:26

1 Answer 1


Suppose you have $k$ colors where $k \leq N$. Let $b_i$ denote the number of balls color $i$ so $\sum b_i = N$. Let $B = \{b_1, \ldots, b_k\}$ and let $E_i(B)$ notate the set which consists of the $i$ element subsets of $B$. Let $Q_{n, c}$ denote the number of ways we can choose $n$ elements from the above set such that the number of different colors in the chosen set is $c$. For $c = 1$ the formula is simple:

$$ Q_{n, 1} = \sum_{E \in E_{1}(B)}\binom{\sum_{e \in E}e}{n} $$

For $c = 2$ we can count sets of balls of size $n$ which has at most 2 colors minus the number of sets which have exactly $1$ color:

$$ Q_{n,2} = \sum_{E \in E_{2}(B)}\binom{\sum_{e \in E}e}{n} - \binom{k - 1}{1}Q_{n, 1} $$

$\binom{k - 1}{1}$ is the number of ways you can add a color to a fixed color such that you will have 2 colors if you have $k$ colors in total. The generic formula is if you have $c_1$ fixed colors and you want to make $c_2$ colors out of it while having $k$ colors in total($c_1 \leq c_2 \leq k$) is $\binom{k - c_1}{c_2 - c_1}$. Now we have everything to derive the generic formula for $Q_{n, c}$:

$$ Q_{n, c} = \sum_{E \in E_{c}(B)}\binom{\sum_{e \in E}e}{n} - \sum_{i = 1}^{c - 1}\binom{k - i}{c - i}Q_{n, i} $$

The probability that you will have exactly $c$ colors if you draw $n$ balls is:

$$ P_{n, c} = Q_{n, c} / \binom{N}{n} $$

Also note that $\binom{x}{y} = 0$ if $y > x$.

Probably there are special cases where the formula can be simplified. I didn't bother to find those simplifications this time.

The expected value you're looking for the number of colors dependent on $n$ is the following:

$$ \gamma_{n} = \sum_{i = 1}^{k} P_{n, i} * i $$

  • 4
    $\begingroup$ You call $P_{n,c}$ a probability, but you seem to have defined it as a sum of integers. Did you forget to divide by something? $\endgroup$ Commented Jun 27, 2016 at 14:57
  • $\begingroup$ Yes, I guess you're right. You need to divide by $\binom{N}{n}$, but unfortunately it's still not right that way. If $E, F \in E_{c}(B)$ and $E \cap F \neq \emptyset$ I do doublecounting in the above formula. $\endgroup$
    – jakab922
    Commented Jun 29, 2016 at 8:21
  • $\begingroup$ Seems like the formula can be fixed by using the sieve method. I will post a fix later today. $\endgroup$
    – jakab922
    Commented Jun 29, 2016 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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