Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I sample with replacement from a set of $N$ unique elements s.t. elements are selected with uniform probability. If I sample with replacement $M$ times from this set, what is the exact probability $P(x)$ that I have observed at least $x$ unique elements?

I believe different variants of this question have been asked on this site, however, I haven't seen a form that asks for an explicit probability $P(x)$?

For example, Ross Rogers asks a variant of this question here: probability distribution of coverage of a set after `X` independently, randomly selected members of the set, and Henry calculates the mean number of unique elements, $x$, and variance for the coverage of a set of $N$ elements after sampling with replacement $M$ times (we switch $M$ and $x$ here to fit with our variable specification).

Reproducing Henry's derivation here:

Mean[x] = $N * (1 - (1 - \frac{1}{N})^M)$

Var[x] = $N\left(1-\dfrac{1}{N}\right)^M + N^2 \left(1-\dfrac{1}{N}\right)\left(1-\dfrac{2}{N}\right)^M - N^2\left(1-\dfrac{1}{N}\right)^{2M}$

(I'll note that I don't quite understand the derivation for Var[x]...)

How can we translate this variance into our $P(x)$?

share|cite|improve this question
When you say "exact probability", are you after a numerical answer? That would vary, depending on the values of M and N surely? – Widor Nov 2 '12 at 15:33
@Widor I mean a formula for P(x) that would let me compute a numerical answer for arbitrary (positive integer) N, M, and x. – Wilk Nov 2 '12 at 20:00
I don't understand why you cite only the mean and variance from that post -- it explicitly gives the probability of sampling exactly $x$ elements in terms of the Stirling numbers of the second kind; all you need to do is sum it from $x$ to $N$ to get the probability of sampling at least $x$ elements. Is your question about whether that sum can be simplified? If not, I don't understand what it's about. – joriki Nov 5 '12 at 15:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.