Number of distinct balls selected from n balls.

Question

$n$ distinct balls are placed in a box. $m$ balls are selected with substitution. Let X be the number of the distinct balls that have been taken out. Find $E(X)$. I have tried to write $X$ as the sum of $n$ Bernoulli random variables $Y_i$ where $Y_i$ is 1 if at least $i$ distinct balls have been taken out and 0 otherwise. But I get into very deep computational trouble when dealing with summations. Is there an easier way to do this?

Answer 1

For any of the $n$ balls, let $X_i=1$ if Ball $i$ is chosen at some stage, and let $X_i=0$ if Ball $i$ is never chosen. Then the number $Y$ of distinct balls is given by $Y=\sum_1^n X_i$. By the linearity of expectation we have $E(Y)=\sum_1^n E(X_i)$.

The probability Ball $i$ is picked at some stage is $1$ minus the probability it is never picked. The probability it is never picked is $\left(\frac{n-1}{n}\right)^m$.

It follows that our expectation is $n\left(1-\left(\frac{n-1}{n}\right)^m\right)$.

Answer 2

It is certainly no accident that this result matches the one at this MSE link which is $$n^{-m} \sum_{q=1}^n q\times {m\brace q} \times q! \times {n\choose q}.$$

Here is the combinatorial explanation: partition your $m$ events into $q$ sets each of which receive the same type of ball, yielding $q$ distinct types being selected (Stirling number). Choose a set of types from the $n$ available types (binomial coefficient). These can be matched to the sets in $q!$ ways.

From this point on we may continue as in the cited link.