Number of original toys found after buying $k+1$ packs of milk.

Question

I was trying to play around with the Coupon Collector's Problem and got to solve this related problem:

There is a promotion in the store: you get a free random toy per 1 pack of milk. The collector wants these toys however he can buy only $k+1$ packs of milk. There are $n$ amount of toys in total. How many original toys does he get on average after buying $k+1$ pack of milk?

So let's try to get that expected value.

Obviously, on the very first pack - he gets an original toy. That means that we can set it as a starting point in our imaginary graph: $k$ packs of milk left to consider. And here is my helping chain where each vertex represents current amount of original toys and each edge represents buying next pack of milk:

From this point, after all other packs of milk he will get these amounts of original toys with corresponding probabilities:

• $p = 1$ original toy with $\left(\frac{1}{n}\right)^{k}$ probability - he got $k$ same toys and never went upper in this pictured chain.
• $p = 2$ original toys with $\sum_{i,j=0}^{i+j=k-1}\left(\frac{1}{n}\right)^{i}\left(\frac{n-1}{n}\right)\left(\frac{2}{n}\right)^{j}=\left(\frac{n-1}{n}\right)\sum_{i,j=0}^{i+j=k-1}\left(\frac{1}{n}\right)^{i}\left(\frac{2}{n}\right)^{j}$ probability because he needs to find another original toy with $\frac{n-1}{n}$ chance and to have $k-1$ horizontal edges in order to stay on the same level.
• $p = 3$ original toys with $\sum_{i,j,m=0}^{i+j+m=k-2}\left(\frac{1}{n}\right)^{i}\left(\frac{n-1}{n}\right)\left(\frac{2}{n}\right)^{j}\left(\frac{n-2}{n}\right)\left(\frac{3}{n}\right)^{m}$ for same reasoning. ...
• $p = p$ original toys with $$ f(p)=\sum_{i_1,i_2,\dots,i_p=0}^{i_1+i_2+\dots+i_p=k-p+1} \left(\frac{1}{n}\right)^{i_1}\left(\frac{n-1}{n}\right) \left(\frac{2}{n}\right)^{i_2}\left(\frac{n-2}{n}\right)\cdot\cdots \left(\frac{p-1}{n}\right)^{i_{p-1}}\left(\frac{n-(p-1)}{n}\right) \left(\frac{p}{n}\right)^{i_{p}} $$

Now for the expected value we should do:

$$ E = \sum_{p=1}^{n} p f(p) = \sum_{p=1}^{n} p \sum_{i_1,i_2,\dots,i_p=0}^{i_1+i_2+\dots+i_p=k-p+1} \left(\frac{1}{n}\right)^{i_1}\left(\frac{n-1}{n}\right) \left(\frac{2}{n}\right)^{i_2}\left(\frac{n-2}{n}\right)\cdot\cdots \left(\frac{p-1}{n}\right)^{i_{p-1}}\left(\frac{n-(p-1)}{n}\right) \left(\frac{p}{n}\right)^{i_{p}} $$ after some transformations I get this: $$ E = \sum_{p=1}^{n} pf(p) = \sum_{p=1}^{n} \left(\frac{n!}{(n-(p-1))!}\right)\frac{p}{n^k} \sum_{i_1,i_2,\dots,i_p=0}^{i_1+i_2+\dots+i_p=k-p+1} 1^{i_1} 2^{i_2}\cdot\cdots (p-1)^{i_{p-1}}p^{i_{p}} $$

And for now, I really can't understand what I should do with this statement next... Help!

Answer 1

Let $X_i$, be a random variable whose value is $1$ if prize number $i$ is found, and $0$ if it is not, for $i=1,2,\dots n$. You want to compute $$E\left(\sum_{i=1}^n X_i\right)=\sum_{i=1}^nE(X_i)$$ by linearity of expectation.

Can you take it from here?

P.S. I felt sure that this question must have been asked before, but I couldn't find it.

Answer 2

This can also be done using Stirling numbers. Suppose $m$ coupons are drawn, then we have from first principles

$$\frac{1}{n^m} \sum_{q=0}^n q {n\choose q} q! {m\brace q} = \frac{1}{n^m} \sum_{q=1}^n q {n\choose q} m! [z^m] (\exp(z)-1)^q \\ = n \frac{m!}{n^m} [z^m] \sum_{q=1}^n {n-1\choose q-1} (\exp(z)-1)^q = n \frac{m!}{n^m} [z^m] (\exp(z)-1) \exp((n-1)z) \\ = n\frac{1}{n^m} (n^m - (n-1)^m).$$

This is

$$\bbox[5px,border:2px solid #00A000]{ n \left(1 - \left(1-\frac{1}{n}\right)^m\right)}$$

confirming linarity of expectation from the answer that was first to be posted. This formula has appeared on various occasions..