Show that $\text{Var}[N]\approx cn^2$ for large $n$.

56 Views Asked by At

Consider coupons numbered $1, 2, ..., n,$ which you collect until you have all numbers. Each time you get a coupon, its number is independent of previous numbers and all numbers are equally likely. Let $N$ be the number of coupons you need, and show that

(a) $\mathbb E[N] = n\sum^n_{k=1}\frac{1}{k} \sim n\log n$ for large $n$,

(b) there is a constant c such that $\operatorname{Var}[N] \sim cn^2$ for large $n$. What is $c$?

The problem (a) is already solved in another post, I just included it in case it's needed to be referred to in order to solve (b).

Attempt: We know that

$$\text{Var}[N]=\text{Var}[X_1+X_2+...+X_n]=\text{Var}[X_1]+\text{Var}[X_2]+...+\text{Var}[X_n].$$

From (a) we got that $X_k\sim \text{geom}(\frac{n-k+1}{n}).$ This means that

$$\text{Var}[X_k]=\frac{1-\frac{n-k+1}{n}}{\left(\frac{n-k+1}{n}\right)^2}=\frac{(1-k)n}{n-k+1}.$$

And finally

$$\text{Var}[N]=n\sum_{k=1}^n\frac{1-k}{n-k+1}.$$

Here I'm stuck. I'm not even sure that this is correct because the sum seems quite hard to evaluate.

1

There are 1 best solutions below

2
On

You haven't simplified the variance of $X_k$ properly: it should be $$ \frac{(k-1)n}{(n-k+1)^2} = \frac{n^2}{(n-k+1)^2} - \frac{n}{(n-k+1)}. $$ Then $$ \frac{\operatorname{Var}{[N]}}{n^2} = \sum_{k=1}^n \frac{1}{(n-k+1)^2} - \frac{1}{n(n-k+1)} = \sum_{r=1}^n \frac{1}{r^2} - \frac{1}{nr}, $$ putting $k=n-r+1$. The first term converges to $\pi^2/6$, while the second term is $\sim -(\log{n})/n$ by comparing with an integral.