Via generating functions edit

By definition of Stirling numbers of the second kind, the probability that exactly T draws are needed is

Calculating the expectation edit

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 ${\displaystyle T=t_{1}+\cdots +t_{n}}$ . Think of T and t_i as random variables. Observe that the probability of collecting a new coupon is ${\displaystyle p_{i}={\frac {n-(i-1)}{n}}={\frac {n-i+1}{n}}}$ . Therefore, ${\displaystyle t_{i}}$  has geometric distribution with expectation ${\displaystyle {\frac {1}{p_{i}}}={\frac {n}{n-i+1}}}$ . By the linearity of expectations we have:

${\displaystyle {\begin{aligned}\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{aligned}}}$ 

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

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

where ${\displaystyle \gamma \approx 0.5772156649}$  is the Euler–Mascheroni constant.

Using the Markov inequality to bound the desired probability:

${\displaystyle \operatorname {P} (T\geq cnH_{n})\leq {\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:

${\displaystyle {\begin{aligned}\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{aligned}}}$ 

And when ${\displaystyle k=0}$  then we get the original result.

Calculating the variance edit

Using the independence of random variables t_i, we obtain:

${\displaystyle {\begin{aligned}\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)\\&{}=n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}\right)\\&{}<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}}$ 

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

Bound the desired probability using the Chebyshev inequality:

${\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\frac {\pi ^{2}}{6c^{2}}}.}$ 

Tail estimates edit

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

${\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}.\end{aligned}}}$ 

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

${\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]=P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}.\end{aligned}}}$ 

• 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.^[1]

${\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}},{\text{ as }}n\to \infty .}$  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:

${\displaystyle \operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n),{\text{ as }}n\to \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:

${\displaystyle \operatorname {P} \left(T_{m}<n\log n+(m-1)n\log \log n+cn\right)\to e^{-e^{-c}/(m-1)!},{\text{ as }}n\to \infty .}$ 

• In the general case of a nonuniform probability distribution, according to Philippe Flajolet et al.^[2]

${\displaystyle \operatorname {E} (T)=\int _{0}^{\infty }\left(1-\prod _{i=1}^{m}\left(1-e^{-p_{i}t}\right)\right)dt.}$ 

This is equal to

${\displaystyle \operatorname {E} (T)=\sum _{q=0}^{m-1}(-1)^{m-1-q}\sum _{|J|=q}{\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.

This section is based on.^[3]

Define a discrete random process ${\displaystyle N(0),N(1),\dots }$  by letting ${\displaystyle N(t)}$  be the number of coupons not yet seen after ${\displaystyle t}$  draws. The random process is just a sequence generated by a Markov chain with states ${\displaystyle n,n-1,\dots ,1,0}$ , and transition probabilities

More generally, each ${\displaystyle \left({\frac {n}{n-k}}\right)^{t}N(t)\cdots (N(t)-k+1)}$  is a martingale process, which allows us to calculate all moments of ${\displaystyle N(t)}$ . For example,

Let ${\displaystyle N}$  be the random variable with the limit distribution. We have

At the ${\displaystyle t\to 0}$  limit, we have ${\displaystyle Pr(N=0)=e^{-e^{-c}}}$ , which is precisely what the limit law states.

By taking the derivative ${\displaystyle d/dt}$  multiple times, we find that ${\displaystyle Pr(N=k)={\frac {e^{-kc}}{k!}}e^{-e^{-c}}}$ , which is a Poisson distribution.

• 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

• "Coupon Collector Problem" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
• How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?, a short note by Doron Zeilberger.