Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
probability distribution of coverage of a set after X independently, randomly selected members of the set

If I sample with replacement $k$ times from a jar of with a finite population of $N$ unique marbles. What is the probability distribution for the fraction of the unique marbles that I sample?

share|improve this question

marked as duplicate by Byron Schmuland, tomasz, Chris Eagle, no identity, Noah Snyder Oct 7 '12 at 19:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 1 down vote accepted

We answer only the expectation question in the title, and not the more complicated distribution question asked in the body of the post. Questions like this one have been asked several times on MSE. There is also a large technical literature on related questions.

For $i=1$ to $N$, let random variable $X_i$ be $1$ if $i$ is chosen at least once, and let $X_i=0$ otherwise.

The probability that $X_i=1$ is $1$ minus the probability that the number is chosen no times. On any one trial, the probability of not choosing $i$ is $\frac{N-1}{N}$. Hence $$\Pr(X_i=1)=1-\left(\frac{N-1}{N}\right)^k.$$ The number $Y$ of $i$ chosen is given by $$Y=\sum_{i=1}^N X_i,$$ so by the linearity of expectation, $$E(Y)=\sum_{i=1}^N X_i=N\left( 1-\left(\frac{N-1}{N}\right)^k \right).$$ For the expected proportion, divide by $N$.

share|improve this answer

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