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

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!

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.

• so the answer is $n \left( 1 - \left(\frac{n-1}{n}\right)^k\right)$ ? Oh my god, I can't believe the solution was so simple... It will be even crazier if my final sum somehow can be reduced to this (if I didnt do any mistakes in my chain-approach). – Lust_For_Love Dec 5 '19 at 21:06
• @Lust_For_Love Shouldn't the exponent be $k+1$ if he buys $k+1$ cartons? – saulspatz Dec 5 '19 at 21:39
• Oups,you are right. – Lust_For_Love Dec 5 '19 at 21:46

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..