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

I have a set of numbers where I am randomly and independently selecting elements within a set . After a number of these random element selections I want to know the coverage of the elements in the set. Coverage being how many elements from the set have been selected at least once divided by the total number of elements in the set.

To restate this: what is the probability distribution of the different coverage values on a set after X randomly, independently selected elements of the set?

share|cite|improve this question
up vote 6 down vote accepted

If there are $n$ elements of the set then the probability that $M=m$ have been selected after a sample of $x$ (with replacement) is

$$\frac{S_2(x,m) \; n!}{n^x \; (n-m)!} $$

where $S_2(x,m)$ is a Stirling number of the second kind.

The expected value of $M$ is: $n \left(1- \left(1-\dfrac{1}{n}\right)^x \right)$.

The variance is: $n\left(1-\dfrac{1}{n}\right)^x + n^2 \left(1-\dfrac{1}{n}\right)\left(1-\dfrac{2}{n}\right)^x - n^2\left(1-\dfrac{1}{n}\right)^{2x}. $

share|cite|improve this answer
I think you need to swap $m$ and $x$ in your expression for the probability. Does that affect the expected value and variance calculations, too? – Mike Spivey Apr 13 '11 at 18:31
@Mike Spivey: you are right about the probability. $m$ should not appear in the expressions for mean and variance – Henry Apr 13 '11 at 19:32
+1 from me for the updated version – Mike Spivey Apr 13 '11 at 19:34
@Henry This is a nice solution! – Byron Schmuland Apr 13 '11 at 19:47
@Ross: The argument Henry is using (I think) is as follows: The number of ways to choose which $m$ elements are to be covered is $\binom{n}{m}$. Then the number of ways to have the $x$ elements in the sample chosen only from those $m$ elements is the same as the number of ways to distribute $x$ elements into $m$ distinguishable nonempty subsets; i.e., $m! S(x,m)$, which is a Stirling number of the second kind. Then the probability is obtained by dividing by the number of ways to choose $x$ elements with replacement from $n$ elements, which is $n^x$. The factor of $m!$ cancels. – Mike Spivey Apr 13 '11 at 22:36

The expected proportion of elements covered, $E\left(\frac{m}{n}\right)$, has a simple limiting form as $n \rightarrow \infty$ with $ r / n $ fixed. Note that $\lim_{n \rightarrow \infty} \left(1-\frac{1}{n}\right)^n = e^{-1}$, and rewrite:

$$\lim_{n \rightarrow \infty} E\left(\frac{m}{n}\right) = 1 - e^{-\frac{r}{n}}$$

so that for example sampling $r=n$ times is expected to cover about 63% of the set. This is a reasonable approximation even for $n > 100$.

share|cite|improve this answer

Your Answer


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

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