Le collectionneur de coupons

La stratégie. Chercher la loi de $T_n$ serait une faute de méthode : elle fait intervenir une formule d'inclusion-exclusion pénible, et elle est inutile. On découpe l'attente totale en attentes successives, chacune de loi connue, et l'espérance tombe par linéarité — qui ne demande aucune indépendance.

a) Le découpage. Notons $D_k$ le nombre de paquets ouverts pour passer de $k-1$ images distinctes à $k$ images distinctes, de sorte que $$T_n=D_1+D_2+\cdots +D_n.$$ Quand on possède déjà $k-1$ images, chaque nouveau paquet apporte une image nouvelle si et seulement si il tombe sur l'une des $n-(k-1)$ images manquantes, ce qui a lieu avec probabilité $$p_k=\frac{n-k+1}{n},$$ indépendamment des paquets précédents et quelles que soient les images déjà possédées — c'est ici que sert l'uniformité et l'indépendance des paquets. On attend donc un premier succès dans une suite d'épreuves indépendantes de même paramètre $p_k$ : $$D_k\sim \mathcal{G}(p_k),E(D_k)=\frac{1}{p_k}=\frac{n}{n-k+1}.$$ (En particulier $D_1=1$ : le premier paquet apporte toujours une image nouvelle, et $p_1=1$.)

b) L'espérance. Par linéarité de l'espérance — et sans aucune hypothèse d'indépendance des $D_k$, ce que la linéarité n'exige jamais : $$E(T_n)=\sum _{k=1}^n\frac{n}{n-k+1}=n\sum _{j=1}^n\frac{1}{j}=n{H}_n,$$ où l'on a posé $j=n-k+1$, qui parcourt $\{1,\dots ,n\}$ quand $k$ parcourt $\{1,\dots ,n\}$. Comme $H_n\sim \ln n$ (chapitre des séries), $$E(T_n)\sim n\ln n.$$

Application. Pour $n=50$ vignettes : $H_{50}=4,4992$, donc $E(T_{50})=50\times 4,4992=224,96$, soit environ $225$ paquets. Le détail est éloquent : la dernière image coûte à elle seule $E(D_{50})=\frac{50}{1}=50$ paquets en moyenne, l'avant-dernière $25$ — les deux dernières images coûtent un tiers du total, alors que les vingt-cinq premières n'en coûtent qu'une trentaine.

c) La variance. Les variables $D_1,\dots ,D_n$ sont indépendantes : chaque attente ne dépend que des paquets ouverts après l'obtention de la $(k-1)$-ième image nouvelle, et la probabilité de succès n'y dépend que du nombre d'images déjà obtenues, jamais de lesquelles ni du temps mis à les obtenir. (Ce point se démontre en écrivant la loi conjointe des $(D_k)$, qui se factorise ; nous l'admettons ici.) La variance est donc additive : $$V(T_n)=\sum _{k=1}^{n}V(D_k)=\sum _{k=1}^n\frac{1-p_k}{p_k^2}.$$ Avec $j=n-k+1$ et $p_k=\frac{j}{n}$ : $$\frac{1-p_k}{p_k^2}=\frac{1-\frac{j}{n}}{\frac{j^2}{n^2}}=\frac{n(n-j)}{j^2}\le \frac{n^2}{j^2},$$ d'où $$V(T_n)\le n^2\sum _{j=1}^n\frac{1}{j^2}\le n^2\sum _{j=1}^{+\infty }\frac{1}{j^2}=\frac{{\pi }^2}{6}{n}^2.$$ L'écart-type est donc au plus $\frac{\pi }{\sqrt{6}}n\approx 1,28n$ — de l'ordre de $n$, alors que la moyenne est de l'ordre de $n\ln n$ : la fluctuation est négligeable devant la moyenne dès que $n$ est grand.

d) La concentration. L'inégalité de Bienaymé-Tchebychev, appliquée à $T_n$ avec l'écart $\epsilon n\ln n$, donne $$P(|T_n-n{H}_n|\ge \epsilon n\ln n)\le \frac{V(T_n)}{{\epsilon }^2{n}^2{\ln }^{2}n}\le \frac{{\pi }^2}{6{\epsilon }^2{\ln }^{2}n}\underset{n\to +\infty }{\to }0.$$ Autrement dit : le nombre de paquets nécessaires est, avec une probabilité qui tend vers $1$, proche de $n\ln n$ à un facteur $(1+\epsilon )$ près. Ce n'est pas seulement une moyenne : c'est une garantie sur le comportement typique. (La décroissance en $\frac{1}{{\ln }^{2}n}$ est lente, parce que Bienaymé-Tchebychev est une inégalité grossière ; la vraie concentration est bien meilleure, mais elle demande des inégalités exponentielles hors programme.)

Ce que l'exercice installe. Le schéma « découper une durée d'attente en somme de temps d'attente géométriques, puis sommer par linéarité » est l'un des plus rentables du chapitre : il donne l'espérance sans jamais chercher la loi. Retenir la séparation des rôles : la linéarité de l'espérance n'exige rien, la variance, elle, exige l'indépendance (ou le calcul des covariances — c'est l'exercice suivant). Et retenir l'ordre de grandeur $n\ln n$, qui gouverne aussi le temps de couverture d'un graphe par une marche aléatoire et le remplissage d'une table de hachage.