Application of Lyapunov's Central Limit Theorem (2): Coupon Collector's Problem

About Posts which Tagged by 'Probability'

Coupon Collector's Problem.  Coupons are drawn at random with replacement from among $N$ distinct coupons until exactly $n$ distinct coupons are observed.  Let $S_n$ denote the total number of coupons drawn.  Then $S_n=Y_1+\cdots+Y_n$, where $Y_j$ is the number of coupons drawn after observing $j-1$ distinct coupons until the $j$th distinct coupon is drawn.  Then $Y_1$, ..., $Y_n$ are independent Geometric random variables with means and variances, $$\begin{array}{rl}\mathscr{E}(Y_j)&=\frac{N}{N-j+1};\\ \sigma^2(Y_j)&=\frac{N(j-1)}{(N-j+1)^2}.\end{array}$$Let $n=\lceil Nr\rceil$ for some fixed $r\in(0,1)$, then $$\alpha_n=\mathscr{E}(S_n)=\sum_{j=1}^n\mathscr{E}(Y_j)=\sum_{j=1}^n\frac{N}{N-j+1}=\sum_{j=1}^n\frac{1}{1-\frac{j-1}{N}},$$we have $$N\int_{-\frac{1}{N}}^{r-\frac{1}{N}}\frac{1}{1-x}\,dx\leq\mathscr{E}(S_n)\leq N\int_{0}^{r}\frac{1}{1-x}\,dx.$$Thus, as $N\rightarrow\infty$, $$\underset{N\rightarrow\infty}{\lim}\mathscr{E}(S_n)=\frac{n}{r}\log{\left(\frac{1}{1-r}\right)}.$$Similarly, we have $$\sigma^2_n=\sigma^2(S_n)=\sum_{j=1}^n\sigma^2(Y_j)=\sum_{j=1}^n\frac{N(j-1)}{(N-j+1)^2}=\sum_{j=1}^n\frac{\frac{j-1}{N}}{\left(1-\frac{j-1}{N}\right)^2},$$then $$\underset{N\rightarrow\infty}{\lim}\sigma^2(S_n)=N\int_0^r\frac{x}{(1-x)^2}\,dx=\frac{n}{r}\left(\frac{r}{1-r}+\log{(1-r)}\right).$$Consider the Lyapunov's condition with $\delta=2$.  Since $Y_j\overset{i.i.d.}{\sim}\mbox{Geo}\left(p_j=\frac{N-j+1}{N}\right)$, we have $$\mathscr{E}|Y_j|^4=\frac{1}{p_j^4}(2-p_j)(12-12p_j+p_j^2)<\infty.$$The Lyapunov's condition  $$\begin{array}{rl}\frac{1}{\sigma^4_n}\sum_{j=1}^n\mathscr{E}\left|Y_j-\mathscr{E}(Y_j)\right|^4
&\leq\frac{1}{\sigma^4_n}\sum_{j=1}^n\mathscr{E}|Y_j|^4 \\
&=\frac{1}{\sigma^4_n}\sum_{j=1}^n\left[\frac{1}{p_j^4}(2-p_j)(12-12p_j+p_j^2)\right] \\
&\leq\frac{1}{\sigma^4_n}\sum_{j=1}^n\frac{26}{p_j^4}\quad(\because\,0\leq p_j\leq1)\\
&\leq\frac{26}{\sigma^4_n}N\int_0^r\frac{1}{(1-x)^4}\,dx \\
&=\frac{N}{N^2}\frac{26\cdot c(r)}{\left[\frac{r}{1-r}+\log{(1-r)}\right]^2}\quad (c(r)\mbox{ is a constant})\\
&\rightarrow0\mbox{ as }N\rightarrow\infty\end{array}$$holds.  Thus, $$\sqrt{n}\left(\frac{S_n}{n}-m\right)\overset{d}{\rightarrow}N(0,\sigma^2),$$where $$\begin{array}{rl}nm=\mathscr{E}(S_n) &\implies m=-\frac{\log{(1-r)}}{r}\\
n\sigma^2=\sigma^2_n &\implies\sigma^2=\frac{1}{r}\left(\frac{r}{1-r}+\log{(1-r)}\right).\end{array}$$