Le Problème du Collectionneur de Coupons

1. Décomposition de $T_N$ : Notons $T_N=X_1+X_2+\cdots +X_N$, où $X_k$ désigne le nombre de boîtes achetées pour découvrir la $k$-ième nouvelle figurine sachant qu'on en possède déjà $k-1$.

• $X_1=1$ presque sûrement (la première boîte apporte toujours une nouvelle figurine).
• Lorsqu'on possède $k-1$ figurines distinctes, chaque nouvel achat a une probabilité $p_k=\frac{N-(k-1)}{N}=\frac{N-k+1}{N}$ d'apporter une figurine inédite, et ce indépendamment des achats passés.
• Par conséquent, $X_k$ suit une loi géométrique $\mathcal{G}(p_k)$ et les variables $(X_1,\dots ,X_N)$ sont mutuellement indépendantes.

2. Espérance de $T_N$ : Par linéarité de l'espérance et sachant que pour $X_k\sim \mathcal{G}(p_k)$, $E(X_k)=\frac{1}{p_k}=\frac{N}{N-k+1}$ : $$E(T_N)=\sum _{k=1}^{N}E(X_k)=\sum _{k=1}^N\frac{N}{N-k+1}=N\sum _{j=1}^N\frac{1}{j}=N{H}_N,$$ où $H_N={\sum }_{j=1}^N\frac{1}{j}$ est le $N$-ième nombre harmonique. Comme $H_N=\ln N+\gamma +O(1/N)$ (avec la constante d'Euler-Mascheroni $\gamma \approx 0.577$), on a l'équivalent : $$E(T_N)\sim N\ln N(N\to +\infty ).$$

3. Variance de $T_N$ : Par indépendance des $(X_k)$ : $$V(T_N)=\sum _{k=1}^{N}V(X_k)=\sum _{k=1}^N\frac{1-p_k}{p_k^2}=\sum _{k=1}^N\left(\frac{1}{p_k^2}-\frac{1}{p_k}\right)=\sum _{j=1}^N\frac{N^2}{j^2}-N{H}_N=N^2\sum _{j=1}^N\frac{1}{j^2}-N{H}_N.$$ Sachant que ${\sum }_{j=1}^{+\infty }\frac{1}{j^2}=\frac{{\pi }^2}{6}$, on a ${\sum }_{j=1}^N\frac{1}{j^2}=\frac{{\pi }^2}{6}+o(1)$. Ainsi, le terme dominant est quadratique : $$V(T_N)=\frac{{\pi }^2}{6}{N}^2-N\ln N+O(N)\sim \frac{{\pi }^2}{6}{N}^2(N\to +\infty ).$$ L'écart-type est de l'ordre de $\sigma (T_N)\sim \frac{\pi }{\sqrt{6}}N$, ce qui est négligeable devant l'espérance $N\ln N$.