2
$\begingroup$

This question is inspired by this question on collecting cereal toys.

Imagine a cereal manufacturer starts a promotion where their customers have to collect 5 different coupons which they can redeem for a free packet of cereal. They expect their customers to have to buy $137/12 \approx 11.4..$ packets of cereal on average to get the free packet and very roughly this is equivalent to giving a discount of 10% to their customers and they can budget for this and balance the cost against expected increase in sales. But what if large groups of friends get together and freely exchange coupons to get the 5 they require? What is the calculation?

For a single customer with no swapping the expectation is that they will have to buy on average $1 + \frac 5 4 + \frac 5 3 + \frac 5 2 + 5 \approx 11$ packets. Now if a group of 10 customers get together and swap coupons in an optimal manner, a naïve calculation might be $\left( 1 + \frac 5 4 + \frac 5 3 + \frac 5 2 + 5 \right) \frac 1{10} \approx 1 $, which is obviously not correct.

What is the correct way to do this, so that the manufacturer can correctly estimate the cost of the promotion? For the exercise assume the average size a typical group of friends is known, e.g. ten.

$\endgroup$
1
  • 1
    $\begingroup$ I don't know of an easy way to calculate it. Your intuition that it will take rather less than $11$ per person is correct because one person can fill in another's shortfall. If the group is huge it will take barely over $5$ coupons per person because the law of large numbers says they will be roughly evenly distributed. It depends on how they buy boxes. If they each buy $5$ and check whether they have the proper distribution it will be rare. If they each have to buy another one I would guess the chance will be high they do, so the expected value will be close to $6$. $\endgroup$ Commented Nov 20, 2023 at 14:41

1 Answer 1

1
$\begingroup$

You haven’t actually said exactly what you want to calculate. One way to interpret the question would be that $m$ friends freely swap coupons and you want to know how many cereal packets they need to buy to get $m$ complete sets of coupons. This is a well-known generalization of the coupon collector’s problem; see for instance Wikipedia, Finite sample bounds for generalized coupon collector problem and the article Some New Aspects of the Coupon Collector’s Problem, SIAM Journal on Discrete Mathematics $17$($1$), pp. $1$-$17$ by Amy Myers and Herbert Wilf.

Asymptotically for $n\to\infty$, the expected number of draws to collect $m$ copies of each of $n$ coupons is

$$ n\log n+(m-1)n\log\log n+O(n)\;. $$

(Note that this is for $n\to\infty$, not $m\to\infty$, so it doesn’t imply that the expected number of draws increases linearly with $m$ for fixed $n=5$.)

The above article also gives a probability generating function for the number $T$ of draws required (Theorem $4.1$ on p. $13$):

$$ P(x)=\frac n{(m-1)!}\int_0^\infty t^{m-1}\mathrm e^{-tn/x}\left(\mathrm e^t-\sum_{k=0}^{m-1}\frac{t^k}{k!}\right)^{n-1}\mathrm dt\;. $$

The expected number of draws required is

$$ \langle T\rangle = P'(1)=\frac{n^2}{(m-1)!}\int_0^\infty t^m\mathrm e^{-tn}\left(\mathrm e^t-\sum_{k=0}^{m-1}\frac{t^k}{k!}\right)^{n-1}\mathrm dt\;. $$

For $m=1$, this reduces to $$ \langle T\rangle = n^2\int_0^\infty t\mathrm e^{-tn}\left(\mathrm e^t-1\right)^{n-1}\mathrm dt\;. $$

Some integrations with Wolfram|Alpha yield the following approximate expectations for $n=5$:

\begin{array}{c|cc} m&1&2&3&4&5&10\\\hline \langle T\rangle&11.42&19.04&25.99&32.60&39.01&69.50 \end{array}

This is indeed roughly linear in $m$. The number of purchases it takes $10$ friends to collect $10$ complete sets of coupons is only about $\frac{69.50}{11.42}\approx6$ times the number it would take each friend individually; the discount is then about $\frac{10}{69.50}\approx14\%$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .