An expected number of different items

Question

We know that for every purchase a costumer receives one plastic figure in a wrap (and it is random which figure is inside). The entire collection comprises $12$ figures. What is the expected number of different figures the children have after they have convinced their parents to go shopping $15$ times? How often does one have to go shopping so that you can expect to have $11$ figures in your collection?

I have the feeling so I could use the following rule to compute the expected value: Sum of $x \cdot p(x)$. The $p(x)$ would be, knowing that there're $12$ different figures, $1/12$. But it would be useless to find an $x$ because we don't compare $x$ of different values but just different figures.

Answer 1

For the first question, for $i = 1, \dots, 12$, let $X_i$ denote the random variable which is $1$ if figure $i$ has been collected at some point during the $15$ visits. Then $Y = \sum_{i=1}^{12} X_i$ is the number of different figures that has been collected.

Now, for each $i$, $P(X_i = 0) = (1 - \tfrac{1}{12})^{15}$, and so

$$E[Y] = \sum_{i=1}^{12} E[X_i] = 12 \cdot (1-(1 - \tfrac{1}{12})^{15}) \approx 8.75.$$

For the second one, let $T_i$ be the time it takes to get $i$ figures in total, given that we have already obtained $i-1$ figures, so that the time to get $11$ figures is $T = \sum_{i=1}^{11} T_i$. Given that we have $i-1$ figures, the probability of getting a new one is $p_i = (12-(i-1))/12$, and $T_i$ is geometrically distributed with parameter $p_i$ and so the expected time to get $11$ figures is

$$E[T] = \sum_{i=1}^{11} E[T_i] = \sum_{i=1}^{11} 1/p_i = 12 \sum_{i=1}^{11} \frac{1}{(12-(i-1))} = 12 \sum_{i=2}^{12} \frac{1}{i} \approx 25.24.$$

Answer 2

This experiment is like rolling a $12$-sided die.

For the first problem, let $X$ be the random variable that counts different figures (or different die roll results). Our sample space is hence $S =\{1,2,\dots,12\}^{15}$, with $|S|=12^{15}$, and our expected value is:

$$\sum_{x \in S}\frac{X(x)}{|S|}$$

Well, that's all very nice and dandy, but not very practical. We will rearranged this sum in a way that makes it more tractible. Notice $X$ takes on integer between and including $1$ and $12$. What we'll do is, for each of these values $1\leq n\leq 12$, count the number $a_n$ of $x \in X$ with $X(x)=n$. Then:

$$\mathbb{E}(X)=\sum_{1\leq n\leq 12}n\cdot \frac{a_n}{|S|}$$

Now that looks a bit better. All we have to do now is calculate the $a_n$. We do this as follows:

If $X(x)=n$, then exactly $n$ of the numbers $1,2,\dots,12$ appears in our experiment. There are $\binom{12}{n}$ ways to choose $n$ of those $12$ numbers to be the ones that show up.

Now, we use Stirling numbers of the second kind: $S(m,k)$ counts the number of ways to partition $m$ labelled objects into $k$ non-empty subsets, unlabelled. Our $m$ labelled objects will be the die rolls, the label being the order of the rolls. Each subset will be a different one of the $n$ distinct types of figure -- but remember, they are as yet unlabeled, we don't know what those types are! Hence, $m=15$ and $k=n$.

Finally, we label these subsets: we assign to each of them one of the $n$ types. We can do this in $n!$ ways. In short:

$$a_n=\binom{12}{n}\cdot S(15,n)\cdot n!=\frac{12!}{(12-n)!}\cdot S(15,n)$$

And so our expectation becomes

$$\mathbb{E}(X)=\frac{12!}{12^{15}}\sum_{1\leq n\leq 12}\frac{n}{(12-n)!}\cdot S(15,n)$$

You can check that this is the same result as fuglede's answer, an exact:

$$\frac{11229773405170717}{1283918464548864}\simeq 8.7465$$

This should perhaps be an indication that the probabilistic approach (fuglede's) is better suited to this problem than the combinatorial approach (mine).