Le collectionneur de coupons

Espaces Probabilisés et Variables Aléatoires Discrètes · Niveau ★★★ — approfondissement · niveau 3 (difficile)

Énoncé

Chaque paquet contient une image choisie uniformément parmi $n$ , indépendamment des autres paquets. Soit $T_{n}$ le nombre de paquets nécessaires pour obtenir les $n$ images. Montrer que $E (T_{n}) = n H_{n} = n (1 + \frac{1}{2} + \dots + \frac{1}{n}) \sim n ln n .$

Corrigé

Découpons l'attente : $T_{n} = D_{1} + D_{2} + \dots + D_{n}$ , où $D_{k}$ est le nombre de paquets ouverts pour passer de $k - 1$ images distinctes à $k$ . Quand on possède $k - 1$ images, chaque paquet apporte une image nouvelle avec probabilité $p_{k} = \frac{n - k + 1}{n}$ , indépendamment des paquets précédents : $D_{k} \sim G (p_{k})$ , donc $E (D_{k}) = \frac{n}{n - k + 1}$ . Par linéarité de l'espérance (aucune indépendance des $D_{k}$ n'est nécessaire pour elle) : $E (T_{n}) = k = 1 \sum n \frac{n}{n - k + 1} = n j = 1 \sum n \frac{1}{j} = n H_{n} \sim n ln n$ (équivalent de la série harmonique, chapitre 6). (Pour $n = 50$ vignettes : $E (T) = 50 H_{50} \approx 225$ paquets — la dernière image coûte à elle seule $50$ paquets en moyenne. Le découpage en attentes géométriques + linéarité est un schéma à retenir.)

Énoncé

Corrigé

Exercices semblables