mathématiques (PC) · Chapitre 11 · Exercice de TD

Le collectionneur de coupons, et sa concentration

Espaces Probabilisés et Variables Aléatoires Discrètes · D. Inégalités et grands nombres · niveau 3 (difficile)

É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é de la question 1

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.

Question 2 : comment l'IA t'aide

Élève

Intuitivement, quand on possède $k - 1$ images, chaque nouveau paquet en apporte une nouvelle avec probabilité $p_{k}$ . Mais l'énoncé demande un dénombrement, et je ne vois pas pourquoi l'argument intuitif ne suffit pas.

L'intuition est juste, mais l'instant où l'on possède $k - 1$ images est aléatoire, ce qui rend le conditionnement délicat. L'événement $(D_{1} = d_{1}, \dots, D_{n} = d_{n})$ ne dépend que d'un nombre fini de paquets : lesquels, et que doit-il se passer à chaque instant ?

Élève

Avec $t_{k} = d_{1} + \dots + d_{k}$ , il ne porte que sur les $t_{n}$ premiers paquets. Aux instants $t_{k}$ , une image jamais vue doit apparaître ; aux autres instants, il ne doit rien apparaître de nouveau.

C'est cela. Combien de choix d'images as-tu à l'instant $t_{k}$ , puis à chacun des instants strictement compris entre $t_{k - 1}$ et $t_{k}$ , et comment passeras-tu ensuite de la loi conjointe aux lois de chaque $D_{k}$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →