Le collectionneur de coupons, et sa concentration

Exercice de TD · niveau 3 (difficile) · mathématiques (PC), chapitre 11 — Espaces Probabilisés et Variables Aléatoires Discrètes · D. Inégalités et grands nombres

Énoncé

Chaque paquet d'une marque de céréales contient une image choisie uniformément parmi $n$ , indépendamment des autres paquets ( $n \geq 2$ ). Soit $T_{n}$ le nombre de paquets à ouvrir pour obtenir les $n$ images. Pour $1 \leq k \leq n$ , on note $D_{k}$ le nombre de paquets ouverts pour passer de $k - 1$ à $k$ images distinctes (en particulier $D_{1} = 1$ ), de sorte que $T_{n} = D_{1} + \dots + D_{n}$ , et l'on pose $p_{k} = \frac{n - k + 1}{n}$ et $H_{n} = \sum_{j = 1}^{n} \frac{1}{j}$ .

a) En admettant provisoirement que, pour $k \geq 2$ , $D_{k}$ suit la loi géométrique de paramètre $p_{k}$ (le b) le démontrera), montrer que $E (T_{n}) = n H_{n} \sim n ln n$ .

b) Montrer que pour tous $d_{1}, \dots, d_{n} \in N^{*}$ , $P (D_{1} = d_{1}, \dots, D_{n} = d_{n}) = k = 1 \prod n p_{k} (1 - p_{k})^{d_{k} - 1}$ (dénombrer les suites de paquets qui réalisent l'événement ; pour $k = 1$ , où $p_{1} = 1$ , on convient que $0^{0} = 1$ ), et en déduire que les $D_{k}$ sont indépendantes, $D_{k}$ suivant la loi $G (p_{k})$ pour $k \geq 2$ .

c) Montrer que $V (T_{n}) \leq n^{2} \sum_{j = 1}^{n} \frac{1}{j ^{2}} \leq \frac{π ^{2}}{6} n^{2}$ .

d) En déduire que pour tout $ε > 0$ , $P (∣ T_{n} - n H_{n} ∣ \geq ε n H_{n}) n \to + \infty 0.$ Pour $n = 50$ , comparer $E (T_{50}) \approx 225$ et l'écart-type $σ (T_{50}) \approx 62$ ; commenter la lenteur de cette concentration, qui se fait à l'échelle $\frac{1}{l n n}$ .

Corrigé

La modélisation. Notons $Y_{i}$ le numéro de l'image du $i$ -ième paquet : les $Y_{i}$ sont indépendantes et uniformes sur $[[1, n]]$ . Pour toute suite $(y_{1}, \dots, y_{m})$ d'images, $P (Y_{1} = y_{1}, \dots, Y_{m} = y_{m}) = n^{- m}$ : les $n^{m}$ suites de $m$ images sont équiprobables.

a) L'espérance, par linéarité. Si $D_{k} \sim G (p_{k})$ , alors $E (D_{k}) = \frac{1}{p _{k}} = \frac{n}{n - k + 1}$ , ce qui vaut encore pour $D_{1} = 1$ . La linéarité de l'espérance — qui ne demande aucune indépendance — donne, avec $j = n - k + 1$ , $E (T_{n}) = k = 1 \sum n \frac{n}{n - k + 1} = n j = 1 \sum n \frac{1}{j} = n H_{n} .$ Et $H_{n} \sim ln n$ (comparaison série-intégrale, chapitre des séries numériques), donc $E (T_{n}) \sim n ln n$ . Lecture : ce sont les dernières images qui coûtent cher — quand il n'en manque plus qu'une, il faut en moyenne $n$ paquets pour la trouver.

b) La loi conjointe, par dénombrement. Ce qui était admis au a) est le point délicat de l'exercice : « quand on possède $k - 1$ images, chaque nouveau paquet en apporte une nouvelle avec la probabilité $p_{k}$ , indépendamment du passé » est intuitif, mais l'instant où l'on possède $k - 1$ images est aléatoire. On remplace l'intuition par un dénombrement.

Posons $t_{k} = d_{1} + \dots + d_{k}$ et $m = t_{n}$ . L'événement $(D_{1} = d_{1}, \dots, D_{n} = d_{n})$ dit que les images nouvelles apparaissent exactement aux instants $t_{1} < \dots < t_{n}$ ; il ne dépend que des $m$ premiers paquets. Comptons les suites $(y_{1}, \dots, y_{m})$ qui le réalisent :

à l'instant $t_{k}$ apparaît la $k$ -ième image nouvelle, choisie parmi les $n - (k - 1)$ images pas encore vues : $n - k + 1$ choix ;
à chacun des $d_{k} - 1$ instants strictement compris entre $t_{k - 1}$ et $t_{k}$ , l'image doit être l'une des $k - 1$ déjà vues : $k - 1$ choix.

Le nombre de suites favorables est donc $\prod_{k = 1}^{n} (n - k + 1) (k - 1)^{d_{k} - 1}$ ; comme $n^{m} = \prod_{k = 1}^{n} n \cdot n^{d_{k} - 1}$ et $1 - p_{k} = \frac{k - 1}{n}$ , $P (D_{1} = d_{1}, \dots, D_{n} = d_{n}) = k = 1 \prod n \frac{n - k + 1}{n} (\frac{k - 1}{n})^{d_{k} - 1} = k = 1 \prod n p_{k} (1 - p_{k})^{d_{k} - 1} .$

La collection se complète presque sûrement. Sommons cette probabilité sur tous les $n$ -uplets $(d_{1}, \dots, d_{n})$ : une somme de termes positifs indexée par un produit se calcule comme un produit de sommes, et chaque $\sum_{d \geq 1} p_{k} (1 - p_{k})^{d - 1}$ vaut $1$ (série géométrique ; pour $k = 1$ , seul $d = 1$ compte). Le total vaut $1$ : par $σ$ -additivité, « toutes les attentes sont finies » est presque sûr.

Les marginales et l'indépendance. Fixons $k$ et $d_{k}$ et sommons de même sur les autres $d_{j}$ (l'événement négligeable où une attente est infinie ne compte pas) : il reste $P (D_{k} = d_{k}) = p_{k} (1 - p_{k})^{d_{k} - 1}$ . Donc $D_{k} \sim G (p_{k})$ pour $k \geq 2$ , et la loi conjointe est le produit des lois marginales : les $D_{k}$ sont indépendantes. Le a) est désormais entièrement justifié.

c) La variance. Les $D_{k}$ sont indépendantes, donc la variance de leur somme est la somme de leurs variances ; avec $V (D_{k}) = \frac{1 - p _{k}}{p _{k}^{2}}$ , qui vaut aussi pour $D_{1}$ , constante, $V (T_{n}) = k = 1 \sum n \frac{1 - p _{k}}{p _{k}^{2}} \leq k = 1 \sum n \frac{1}{p _{k}^{2}} = n^{2} j = 1 \sum n \frac{1}{j ^{2}} .$ Enfin $\sum_{j = 1}^{n} \frac{1}{j ^{2}} \leq \sum_{j = 1}^{+ \infty} \frac{1}{j ^{2}} = \frac{π ^{2}}{6}$ , valeur d'Euler admise dans le livre ; seule la convergence de la série sert ici, et la majoration par $2$ , obtenue par télescopage à partir de $\frac{1}{j ^{2}} \leq \frac{1}{j - 1} - \frac{1}{j}$ pour $j \geq 2$ , suffirait. D'où $V (T_{n}) \leq \frac{π ^{2}}{6} n^{2}$ ; le calcul exact donne $V (T_{n}) = n^{2} \sum_{j = 1}^{n} \frac{1}{j ^{2}} - n H_{n}$ .

d) La concentration. L'inégalité de Bienaymé-Tchebychev, avec $E (T_{n}) = n H_{n}$ et l'écart $ε n H_{n} > 0$ , donne $P (∣ T_{n} - n H_{n} ∣ \geq ε n H_{n}) \leq \frac{V ( T _{n} )}{ε ^{2} n ^{2} H _{n}^{2}} \leq \frac{π ^{2}}{6 ε ^{2} H _{n}^{2}},$ qui tend vers $0$ car $H_{n} \sim ln n$ . Le temps de collection est déterminé, en valeur relative, par son espérance : $T_{n}$ est de l'ordre de $n ln n$ avec une probabilité qui tend vers $1$ .

Les chiffres, pour $n = 50$ . $H_{50} \approx 4, 499$ , donc $E (T_{50}) \approx 225$ ; la variance exacte vaut $V (T_{50}) \approx 3838$ , soit un écart-type $σ (T_{50}) \approx 62$ . L'écart-type relatif, $\frac{62}{225} \approx 0, 28$ , est loin d'être petit : il est de l'ordre de $\frac{π}{6 H _{n}}$ , et ne décroît que comme $\frac{1}{l n n}$ . Pour le ramener à $0, 05$ , il faudrait $H_{n} \approx 25, 7$ , soit $n$ de l'ordre de $1 0^{11}$ . La loi faible des grands nombres dit que la concentration a lieu, pas à quelle vitesse.

Ce que l'exercice installe. Découper une attente en attentes géométriques indépendantes : la linéarité donne l'espérance sans indépendance ; l'indépendance — démontrée par un dénombrement, pas postulée — donne la variance ; Bienaymé-Tchebychev donne la concentration. Le schéma revient chaque fois qu'on attend qu'un tirage au hasard ait tout couvert : toutes les cellules d'un détecteur touchées, tous les sites d'un réseau visités, toutes les molécules d'une bibliothèque combinatoire observées.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.