Easy mean-variance problem

Question

Find the mean and variance of X, where X is the number of distinct results of a 12-sided die rolled 5 times (e.g. {3,11,12,3,11} returns X=3).

Answer 1

We show how to solve the problem if a $d$-sided die is rolled $m$ times. The technique we use, called the method of Indicator Random Variables, is quite powerful.

Let $Y$ be the number of sides that we don't see. Then $X=d-Y$, so $E(X)=d-E(Y)$.

For each of the numbers $1$ to $d$, let $Y_i=1$ if we never see $i$, and $Y_i=0$ otherwise. Note that $$Y=Y_1+Y_2+\cdots +Y_d,$$ so by the linearity of expectation we have $$E(Y)=E(Y_1)+E(Y_2)+\cdots +E(Y_d).$$ For any $i$, we have $\Pr(Y_i=1)=\left(\frac{d-1}{d}\right)^m$. It follows that $E(Y)=d\left(\frac{d-1}{d}\right)^m$, and therefore $$E(X)=d-d\left(\frac{d-1}{d}\right)^m.$$

We will leave a small part of the variance calculation to you, but give a very detailed outline.

Note that $\text{Var}(X)=\text{Var}(Y)$, and $\text{Var}(Y)=E(Y^2)-(E(Y))^2$.

So it remains to calculate $E(Y_1+Y_2+\cdots+Y_d)^2$. Expand. We want $$\sum_1^dE(Y_i^2) +\sum_{i\ne j}E(Y_iY_j).$$ The first sum has already been computed, since $Y_i^2=Y_i$. For the second, we need to find $\Pr(X_iX_j)=1$. The probability that we see neither $i$ nor $j$ in $m$ trials is $\left(\frac{d-2}{d}\right)^m$. There are $d(d-1)$ ordered pairs $(i,j)$ with $i\ne j$. Now you can put the pieces together.

Remark: For a mere $5$ tosses, we can find explicitly the probability distribution of your random variable $X$, and then find the mean and variance. That is likely what you are expected to do. What is the probability that $X=1$? All results must be the same. There are $12$ possible results. Each has probability $1/12$, so the probability that $X=1$ is $(12)(1/12)^{5}$.

The probability that $X=5$ is also easy. We must get all different tosses. The probability of that is $(12)(11)(10)(9)(8)/12^5$.

Now find the probability that $X=4$. So we get $1$ repeat. The repeated result can be chosen n $12$ ways. Where in the tossing it occurs can be chosen in $\binom{5}{2}$ ways. The rest can be filled in with distinct numbers in $(11)(10)(9)$ ways. So $\Pr(X=3)=(12)\binom{5}{2}(11)(10)(9)/12^5$.

Now it remains to find one of $\Pr(X=2)$ or $\Pr(X=3)$. They are both a little unpleasant, but once you have one of them, the other is no problem, since $\Pr(X=1)+\cdots+\Pr(X=5)=1$.