{"id":937,"date":"2010-10-20T00:38:05","date_gmt":"2010-10-19T22:38:05","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=937"},"modified":"2020-06-22T15:04:53","modified_gmt":"2020-06-22T13:04:53","slug":"back-to-basics-coupon-collector","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2010\/10\/20\/back-to-basics-coupon-collector\/","title":{"rendered":"Back to basics - Coupon collector"},"content":{"rendered":"

\"\"<\/a><\/p>\n

Let \\( {X_1,X_2,\\ldots} \\) be i.i.d. random variables uniformly distributed on \\( {\\{1,\\ldots,r\\}} \\). The classical coupon collector problem<\/em> consists in looking at the random time<\/p>\n

\\[ T=\\min\\{n\\geq1:\\{X_1,\\ldots,X_n\\}=\\{1,\\ldots,r\\}\\}. \\]<\/p>\n

Since we have \\( {T=G_1+\\cdots+G_r} \\) where \\( {G_1,\\ldots,G_r} \\) are independent geometric random variables on \\( {\\{1,2,\\ldots\\}} \\) with \\( {\\mathbb{E}(G_i)=r\/(r-i+1)} \\), we obtain<\/p>\n

\\[ \\mathbb{E}(T)=r\\sum_{i=1}^r\\frac{1}{i}=r(\\log(r)+\\gamma+o_{r\\rightarrow\\infty}(1)). \\]<\/p>\n

One may compute similarly the variance and obtain a deviation bound around the mean via Chebyshev's inequality (exercise!). A simple reasoning shows that for any \\( {n\\geq r} \\),<\/p>\n

\\[ \\mathbb{P}(T=n)=\\frac{r!}{r^n}S(n-1,r-1) \\]<\/p>\n

where \\( {S(n-1,r-1)} \\) is the Stirling number of the second kind (the number of ways to partition \\( {n-1} \\) objects into \\( {r-1} \\) non empty blocs). It is difficult to get the tail of \\( {T} \\) from this formula.<\/p>\n

Another possibility is to write, for every \\( {n\\geq r} \\),<\/p>\n

\\[ \\mathbb{P}(T>n) = \\mathbb{P}(E_{n,1}\\cup\\cdots\\cup E_{n,r}) \\quad\\text{where}\\quad E_{n,i} = \\{X_1\\neq i,\\ldots,X_n\\neq i\\}. \\]<\/p>\n

Note that if \\( {1\\leq i_1,\\ldots,i_k\\leq r} \\) are distincs, then with \\( {R:=\\{1,\\ldots,r\\}\\setminus\\{i_1,\\ldots,i_k\\}} \\),<\/p>\n

\\[ \\mathbb{P}(E_{n,i_1}\\cap\\cdots\\cap E_{n,i_k}) =\\mathbb{P}(X_1\\in R)\\cdots\\mathbb{P}(X_n\\in R) =\\left(\\frac{r-k}{r}\\right)^n=\\left(1-\\frac{k}{r}\\right)^n. \\]<\/p>\n

Now, by the inclusion-exclusion principle (also known as the Poincaré sieve), for every \\( {n\\geq r } \\),<\/p>\n

\\[ \\mathbb{P}(T>n) = \\sum_{k=1}^r(-1)^{k-1}\\binom{r}{k}\\left(1-\\frac{k}{r}\\right)^n. \\]<\/p>\n

Unfortunately, the signs are alternating. Actually, if we write<\/p>\n

\\[ \\mathbb{P}(T>n)\\leq \\sum_{i=1}^r \\mathbb{P}(E_{n,i}) \\]<\/p>\n

and if we note that<\/p>\n

\\[ \\mathbb{P}(E_{n,i})=\\left(1-\\frac{1}{r}\\right)^n\\leq e^{-n\/r} \\]<\/p>\n

then, taking \\( {n=\\lceil t r\\log(r)\\rceil} \\), we obtain that for all real \\( {t>0} \\),<\/p>\n

\\[ \\mathbb{P}(T> \\lceil tr\\log(r)\\rceil) \\leq r^{-t+1}. \\]<\/p>\n

It turns out that the asymptotic fluctuations of \\( {T} \\) are Gumbel.<\/p>\n

Theorem 1 (Gumbel fluctuations)<\/b> We have<\/em> <\/p>\n

\\[ \\frac{T-r\\log(r)}{r} \\underset{r\\rightarrow\\infty}{\\overset{\\mathrm{law}}{\\longrightarrow}} G \\]<\/em><\/p>\n

where \\( {G} \\) is the Gumbel law on \\( {\\mathbb{R}} \\) with density \\( {t\\mapsto e^{-e^{-t}-t}} \\).<\/em><\/p><\/blockquote>\n

Proof:<\/em> Let us fix \\( {t\\in\\mathbb{R}} \\) and let us show that<\/p>\n

\\[ \\lim_{r\\rightarrow\\infty}\\mathbb{P}(T> r\\log(r)+tr)=S(t)=1-e^{-e^{-t}}. \\]<\/p>\n

Fix \\( {t\\in\\mathbb{R}} \\) and take \\( {r} \\) large enough such that \\( {r\\log(r)+tr>r} \\). Set \\( {n_{t,r}=r\\log(r)+tr} \\) if \\( {r\\log(r)+tr\\in\\mathbb{N}} \\) and \\( {n_{t,r}=\\lceil r\\log(r)+tr\\rceil} \\) if not. We already know that<\/p>\n

\\[ \\mathbb{P}(T> r\\log(r)+tr) = \\sum_{k=1}^r(-1)^{k-1}\\binom{r}{k} \\left(1-\\frac{k}{r}\\right)^{n_{t,r}}. \\]<\/p>\n

Now, since \\( {\\binom{r}{k}\\leq r^kk!} \\) and \\( {(1-u)\\leq e^{-u}} \\) for all \\( {u\\geq0} \\), we have<\/p>\n

\\[ \\binom{r}{k}\\left(1-\\frac{k}{r}\\right)^{n_{t,r}} \\overset{\\leq}{\\underset{r\\rightarrow\\infty}{\\longrightarrow}} \\frac{e^{-kt}}{k!}. \\]<\/p>\n

By dominated convergence, we obtain finally<\/p>\n

\\[ \\lim_{r\\rightarrow\\infty} \\sum_{k=1}^r(-1)^{k-1}\\binom{r}{k} \\left(1-\\frac{k}{r}\\right)^{n_{t,r}} =\\sum_{k=1}^\\infty(-1)^{k-1}\\frac{e^{-kt}}{k!}=S(t). \\]<\/p>\n

$\\Box$<\/p>\n