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:

enter image description here

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.

  • 1
    $\begingroup$ 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). $\endgroup$ – Lust_For_Love Dec 5 '19 at 21:06
  • 1
    $\begingroup$ @Lust_For_Love Shouldn't the exponent be $k+1$ if he buys $k+1$ cartons? $\endgroup$ – saulspatz Dec 5 '19 at 21:39
  • $\begingroup$ Oups,you are right. $\endgroup$ – 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..


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.