Coupon collector's problem

By definition of Stirling numbers of the second kind, the probability that exactly T draws are needed is$$\backslash frac\{S(T-1,\; n-1)n!\}\{n^T\}$$By manipulating the generating function of the Stirling numbers, we can explicitly calculate all moments of T:$$f\_k(x)\; :=\; \backslash sum\_T\; S(T,\; k)\; x^T\; =\; \backslash prod\_\{r=1\}^k\; \backslash frac\{x\}\{1-rx\}$$In general, the k-th moment is $(n-1)!\; ((D\_x\; x)^kf\_\{n-1\}(x))\; \backslash Big|\_\{x=1/n\}$, where $D\_x$ is the derivative operator $d/dx$.

For example, the 0th moment is$$\backslash sum\_T\; \backslash frac\{S(T-1,\; n-1)n!\}\{n^T\}\; =\; (n-1)!\; f\_\{n-1\}(1/n)\; =\; (n-1)!\; \backslash times\; \backslash prod\_\{r=1\}^\{n-1\}\; \backslash frac\{1/n\}\{1-r/n\}\; =\; 1$$and the 1st moment is $(n-1)!\; (D\_x\; xf\_\{n-1\}(x))\; \backslash Big|\_\{x=1/n\}$, which can be explicitly evaluated to $nH\_n$, etc.

Let time T be the number of draws needed to collect all n coupons, and let t_i be the time to collect the i-th coupon after i − 1 coupons have been collected. Then $T=t\_1\; +\; \backslash cdots\; +\; t\_n$. Think of T and t_i as random variables. Observe that the probability of collecting a {{em|new}} coupon is $p\_i\; =\; \backslash frac\{n\; -\; (i\; -\; 1)\}\{n\}\; =\; \backslash frac\{n\; -\; i\; +\; 1\}\{n\}$. Therefore, $t\_i$ has geometric distribution with expectation $\backslash frac\{1\}\{p\_i\}\; =\; \backslash frac\{n\}\{n\; -\; i\; +\; 1\}$. By the linearity of expectations we have:

:$$

\begin{align}

\operatorname{E}(T) & {}= \operatorname{E}(t_1 + t_2 + \cdots + t_n) \\

& {}= \operatorname{E}(t_1) + \operatorname{E}(t_2) + \cdots + \operatorname{E}(t_n) \\

& {}= \frac{1}{p_1} + \frac{1}{p_2} + \cdots + \frac{1}{p_n} \\

& {}= \frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} \\

& {}= n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}\right) \\

& {}= n \cdot H_n.

\end{align}

Here H_n is the n-th harmonic number. Using the asymptotics of the harmonic numbers, we obtain:

:$$

\operatorname{E}(T) = n \cdot H_n = n \log n + \gamma n + \frac{1}{2} + O(1/n),

where $\backslash gamma\; \backslash approx\; 0.5772156649$ is the Euler–Mascheroni constant.

Using the Markov inequality to bound the desired probability:

:$\backslash operatorname\{P\}(T\; \backslash geq\; cn\; H\_n)\; \backslash le\; \backslash frac\{1\}\{c\}.$

The above can be modified slightly to handle the case when we've already collected some of the coupons. Let k be the number of coupons already collected, then:

:$$

\begin{align}

\operatorname{E}(T_k) & {}= \operatorname{E}(t_{k+1} + t_{k+2} + \cdots + t_n) \\

& {}= n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n-k}\right) \\

& {}= n \cdot H_{n-k}

\end{align}

And when $k=0$ then we get the original result.

Using the independence of random variables t_i, we obtain:

:$$

\begin{align}

\operatorname{Var}(T)& {}= \operatorname{Var}(t_1 + \cdots + t_n) \\

& {} = \operatorname{Var}(t_1) + \operatorname{Var}(t_2) + \cdots + \operatorname{Var}(t_n) \\

& {} = \frac{1-p_1}{p_1^2} + \frac{1-p_2}{p_2^2} + \cdots + \frac{1-p_n}{p_n^2} \\

& {} = \left(\frac{n^2}{n^2} + \frac{n^2}{(n-1)^2} + \cdots + \frac{n^2}{1^2}\right) - \left(\frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1}\right) \\

& {} = n^2 \cdot \left(\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} \right) - n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n} \right)\\

& {} < \frac{\pi^2}{6} n^2

\end{align}

since $\backslash frac\{\backslash pi^2\}6=\backslash frac\{1\}\{1^2\}+\backslash frac\{1\}\{2^2\}+\backslash cdots+\backslash frac\{1\}\{n^2\}+\backslash cdots$ (see Basel problem).

Bound the desired probability using the Chebyshev inequality:

:$\backslash operatorname\{P\}\backslash left(|T-\; n\; H\_n|\; \backslash geq\; cn\backslash right)\; \backslash le\; \backslash frac\{\backslash pi^2\}\{6c^2\}.$

A stronger tail estimate for the upper tail be obtained as follows. Let $\{Z\}\_i^r$ denote the event that the $i$-th coupon was not picked in the first $r$ trials. Then

:$$

\begin{align}

P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n}.

\end{align}

Thus, for $r\; =\; \backslash beta\; n\; \backslash log\; n$, we have $P\backslash left\; [\; \{Z\}\_i^r\; \backslash right\; ]\; \backslash le\; e^\{(-\backslash beta\; n\; \backslash log\; n\; )\; /\; n\}\; =\; n^\{-\backslash beta\}$. Via a union bound over the $n$ coupons, we obtain

:$$

\begin{align}

P\left [ T > \beta n \log n \right ] = P \left [ \bigcup_i {Z}_i^{\beta n \log n} \right ] \le n \cdot P [ {Z}_1^{\beta n \log n} ] \le n^{-\beta + 1}.

\end{align}

• Pierre-Simon Laplace, but also Paul Erdős and Alfréd Rényi, proved the limit theorem for the distribution of T. This result is a further extension of previous bounds. A proof is found in.{{Cite book |last=Mitzenmacher |first=Michael |title=Probability and computing : randomization and probabilistic techniques in algorithms and data analysis |date=2017 |others=Eli Upfal |isbn=978-1-107-15488-9 |edition=2nd |location=Cambridge, United Kingdom |at=Theorem 5.13 |oclc=960841613}}

:: which is a Gumbel distribution. A simple proof by martingales is in the next section.

• Donald J. Newman and Lawrence Shepp gave a generalization of the coupon collector's problem when m copies of each coupon need to be collected. Let T_m be the first time m copies of each coupon are collected. They showed that the expectation in this case satisfies:

::$\backslash operatorname\{E\}(T\_m)\; =\; n\; \backslash log\; n\; +\; (m-1)\; n\; \backslash log\backslash log\; n\; +\; O(n),\; \backslash text\{\; as\; \}\; n\; \backslash to\; \backslash infty.$

:Here m is fixed. When m = 1 we get the earlier formula for the expectation.

• Common generalization, also due to Erdős and Rényi:

::

• In the general case of a nonuniform probability distribution, according to Philippe Flajolet et al.{{citation |first=Philippe |last=Flajolet |first2=Danièle |last2=Gardy |first3=Loÿs |last3=Thimonier |title=Birthday paradox, coupon collectors, caching algorithms and self-organizing search |journal=Discrete Applied Mathematics |volume=39 |issue=3 |year=1992 |pages=207–229 |doi=10.1016/0166-218x(92)90177-c|citeseerx=10.1.1.217.5965 }}

::$\backslash operatorname\{E\}(T)=\backslash int\_0^\backslash infty\; \backslash left(1\; -\; \backslash prod\_\{i=1\}^m\; \backslash left(1-e^\{-p\_it\}\backslash right)\backslash right)dt.$

:This is equal to

::$\backslash operatorname\{E\}(T)=\backslash sum\_\{q=0\}^\{m-1\}\; (-1)^\{m-1-q\}\; \backslash sum\_\{|J|=q\}\; \backslash frac\{1\}\{1-P\_J\},$

:where m denotes the number of coupons to be collected and P_J denotes the probability of getting any coupon in the set of coupons J.

• McDonald's Monopoly – an example of the coupon collector's problem that further increases the challenge by making some coupons of the set rarer
• Watterson estimator
• Birthday problem

{{notelist}}

{{Reflist|30em}}

{{refbegin}}

• {{citation

| last1 = Blom | first1 = Gunnar

| last2 = Holst | first2 = Lars

| last3 = Sandell | first3 = Dennis

| contribution = 7.5 Coupon collecting I, 7.6 Coupon collecting II, and 15.4 Coupon collecting III

| isbn = 0-387-94161-4

| location = New York

| mr = 1265713

| pages = 85–87, 191

| publisher = Springer-Verlag

| title = Problems and Snapshots from the World of Probability

| url = https://books.google.com/books?id=KCsSWFMq2u0C&pg=PA85

| year = 1994}}.

• {{citation

| last = Dawkins | first = Brian

| issue = 1

| journal = The American Statistician

| jstor = 2685247

| pages = 76–82

| title = Siobhan's problem: the coupon collector revisited

| volume = 45

| year = 1991

| doi=10.2307/2685247}}.

• {{citation

| last1 = Erdős | first1 = Paul | author1-link = Paul Erdős

| last2 = Rényi | first2 = Alfréd | author2-link = Alfréd Rényi

| journal = Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei

| mr = 0150807

| pages = 215–220

| title = On a classical problem of probability theory

| url = http://www.renyi.hu/~p_erdos/1961-09.pdf

| volume = 6

| year = 1961}}.

• {{citation

| last1 = Laplace | first1 = Pierre-Simon | author1-link = Pierre-Simon Laplace

| title = Théorie analytique des probabilités

| pages = 194–195

| year = 1812}}.

• {{citation

| last1 = Newman | first1 = Donald J. | author1-link = Donald J. Newman

| last2 = Shepp | first2 = Lawrence | author2-link = Lawrence Shepp

| doi = 10.2307/2308930

| journal = American Mathematical Monthly

| mr = 0120672

| pages = 58–61

| title = The double dixie cup problem

| volume = 67

| issue = 1 | year = 1960| jstor = 2308930 }}

• {{citation

| last1 = Flajolet | first1 = Philippe | author1-link = Philippe Flajolet

| last2 = Gardy | first2 = Danièle

| last3 = Thimonier | first3 = Loÿs

| doi = 10.1016/0166-218X(92)90177-C

| issue = 3

| journal = Discrete Applied Mathematics

| mr = 1189469

| pages = 207–229

| title = Birthday paradox, coupon collectors, caching algorithms and self-organizing search

| url = http://algo.inria.fr/flajolet/Publications/alloc2.ps.gz

| volume = 39

| year = 1992| doi-access = free

}}.

• {{citation

| last = Isaac | first = Richard

| contribution = 8.4 The coupon collector's problem solved

| isbn = 0-387-94415-X

| location = New York

| mr = 1329545

| pages = 80–82

| publisher = Springer-Verlag

| series = Undergraduate Texts in Mathematics

| title = The Pleasures of Probability

| url = https://books.google.com/books?id=a_2vsIx4FQMC&pg=PA80

| year = 1995}}.

• {{citation

| last1 = Motwani | first1 = Rajeev | author1-link = Rajeev Motwani

| last2 = Raghavan | first2 = Prabhakar

| contribution = 3.6. The Coupon Collector's Problem

| location = Cambridge

| mr = 1344451

| pages = 57–63

| publisher = Cambridge University Press

| title = Randomized algorithms

| url = https://books.google.com/books?id=QKVY4mDivBEC&pg=PA57

| year = 1995| isbn = 9780521474658 }}.

{{refend}}

• "[http://demonstrations.wolfram.com/CouponCollectorProblem/ Coupon Collector Problem]" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
• [http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/coupon.html How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?], a short note by Doron Zeilberger.

Category:Articles containing proofs

Category:Gambling mathematics

Category:Theorems in probability theory

Category:Probability problems