Suppose that there are \(N\) different types of coupons. Each box contains one coupon. The type of the coupon is chosen uniformly among \(\{1,2,\cdots,N\}\).

1. If we open \(k\) boxes what is the expected number of different  coupons thus we will find ? What is the limit  of this quantity as \(k \rightarrow \infty\) ?
2. Let \(T_k\), for \(k=1,\cdots,N\), be the number of boxes needed to obtain the \(k\)th unique type of coupon. Clearly \(T_1=1\) . For future reference define \(\tau_1=1\) and \(\tau_k=T_k- T_{k-1}\) for \(k=2,3,\cdots\).
   1. What is the distribution of \(\tau_k\) ?
   2. What is the expected value of \(T_N\) ? What is it approximately for \(N\) large ?
   3. What is the variance of \(\mathbf{Var}(T_N) \)?
   4. Show that \(\mathbf{SD}(T_N)  < cn \) from some constant \(c>0\).
   5. Use Chebychev’s inequality to show that the probability that for large \(N\), \(T_N\) differs from \(N\log(N)\)  by at most only a small multiple of \(N\) with high probabilty.
3. (***) What is the distribution of \( (T_N- N\log(N) \,)/N\) as \(N\rightarrow \infty\) ? Hint: It is not normal !