1
$\begingroup$

The Sticker Collector

You need to collect $n>1$ different Stickers.

Each day you get one pack with $1$ random sticker until you don't collect at least one of each kind.
* Each sticker has an equal chance of being in that pack.

$(1)$ What is the chance of completing the collection with $k$ duplicates?

$(2)$ What is the average number of duplicates you are expected to have after the completion?

$(3)$ Placing $x$ stickers in each pack, what is the average number of packs needed to complete the collection and what is the average number of duplicates you are expected to have then?


Any answers bringing any progress or insight to any part of this problem are helpful.



My progress on $(1)$

I've found the following things trying to solve $(1)$:
* $C_n(k)$ is chance of completion with $k$ duplicates and $n$ cards to collect *

$$C_n(0)=\frac{n!}{n^n}$$

$$C_n(1)=\frac{n-1}{2}\times C_n(0)$$

$$C_n(2)=\frac{3n^2+n-2}{12n}\times C_n(1)$$

At this point I'm not sure where this leads, neither how to efficiently calculate the next expression since I'm having doubts in whether the last expression is correct.


Simplest Case $(n=2)$

I've also approached the simplest case.

Since after opening the $1$st pack, we have $\frac{1}{2}$ chance of either completing the collection or gaining a duplicate, we can conclude:

$(1)$ A Expression for calculating the first question in this case: $$ C_2(k)=\frac{1}{2^{k+1}}$$

$(2)$ Which on average gives $1$ duplicate: $$ \frac{0}{2}+\frac{1}{4}+\frac{2}{8}+\frac{3}{16}\dots = \sum_{k=1}^{\infty}\frac{k}{2^{k+1}} = 1$$

$\endgroup$
1
$\begingroup$

Parts $(1)$ and $(2)$ are corollaries of the well-known results about the coupon collector's problem, since you complete with $k$ duplicates exactly if you complete after $k+n$ steps.

For $(1)$, the probability distribution for the number $M$ of stickers drawn to complete a set given at Probability distribution in the coupon collector's problem,

$$\def\stir#1#2{\left\{#1\atop#2\right\}} P(M=m)=\frac{n!}{n^m}\stir{m-1}{n-1}\;,$$

(where $\stir mn$ is a Stirling number of the second kind) yields

$$ P(K=k)=\frac{n!}{n^{k+n}}\stir{k+n-1}{n-1}\;, $$

in agreement with your results for $k\le2$.

For $(2)$, the well-known expected value of $M$,

$$ E[M]=nH_n\;, $$

yields

\begin{align} E[K]&=nH_n-n\\ &=n\sum_{k=2}^n\frac1k\;, \end{align}

in agreement with your result for $n=2$.

Questions like $(3)$ have been addressed with various variations in various posts on this site:

Coupon Collectors Problem with Packets: Clarifying Wikipedia

Coupon Collector Problem with Batched Selections

Coupon Collector Problem with packs

coupon collector problem with groups

$\endgroup$

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.