mathématiques (PCSI) · Chapitre 15 · Exercice de TD

Le paradoxe des anniversaires, encadré

Probabilités sur un univers fini · A. Modèles et probabilités uniformes · niveau 2

Énoncé

Dans un groupe de $k$ personnes ( $2 \leq k \leq N$ , avec $N = 365$ ), les jours d'anniversaire sont modélisés par $k$ variables aléatoires indépendantes, de loi uniforme sur ${1, \dots, N}$ . On note $p_{k}$ la probabilité qu'au moins deux personnes partagent leur anniversaire.

a) Montrer que $1 - p_{k} = i = 1 \prod k - 1 (1 - \frac{i}{N})$ .

b) Montrer que pour tous réels $a_{1}, \dots, a_{m}$ de $[0, 1]$ : $1 - i = 1 \sum m a_{i} \leq i = 1 \prod m (1 - a_{i}) \leq exp (- i = 1 \sum m a_{i}) .$

c) En déduire $1 - e^{- k (k - 1) / (2 N)} \leq p_{k} \leq \frac{k ( k - 1 )}{2 N}$ . Montrer que $p_{k} > \frac{1}{2}$ pour tout $k \geq 23$ , et que $p_{k} < \frac{1}{2}$ pour tout $k \leq 19$ .

d) Pour $N$ quelconque, de quel ordre en $N$ est la taille de groupe à partir de laquelle une coïncidence devient probable ?

Corrigé de la question 1

La stratégie. Passer au complémentaire — « les $k$ anniversaires sont deux à deux distincts », qui se compte comme un nombre de listes sans répétition —, puis encadrer le produit obtenu, pour décider sans machine à partir de quelle taille la coïncidence devient plus probable que son absence.

a) Le complémentaire. Notons $X_{1}, \dots, X_{k}$ les jours d'anniversaire. Par indépendance, pour toute liste $(x_{1}, \dots, x_{k})$ de jours, $P (X_{1} = x_{1}, \dots, X_{k} = x_{k}) = i = 1 \prod k P (X_{i} = x_{i}) = \frac{1}{N ^{k}} :$ le $k$ -uplet suit la loi uniforme sur ${1, \dots, N}^{k}$ . L'événement « les $X_{i}$ sont deux à deux distincts » est réalisé par les listes de $k$ éléments distincts, au nombre de $N (N - 1) \dots (N - k + 1)$ : $N$ choix pour le premier terme, $N - 1$ pour le deuxième, et ainsi de suite. Donc $1 - p_{k} = \frac{N ( N - 1 ) \dots ( N - k + 1 )}{N ^{k}} = i = 0 \prod k - 1 \frac{N - i}{N} = i = 1 \prod k - 1 (1 - \frac{i}{N}),$ le facteur d'indice $0$ valant $1$ . Le numérateur compte exactement $k$ facteurs, le dernier étant $N - k + 1$ : c'est là qu'on se trompe d'une unité.

Question 2 : comment l'IA t'aide

b) Montrer que pour tous réels $a_{1}, \dots, a_{m}$ de $[0, 1]$ : $1 - i = 1 \sum m a_{i} \leq i = 1 \prod m (1 - a_{i}) \leq exp (- i = 1 \sum m a_{i}) .$

Élève

Pour la majoration, j'utilise $1 - a_{i} \leq e^{- a_{i}}$ et je multiplie. Mais pour la minoration, développer le produit donne une somme énorme de termes de signes alternés : je ne vois pas comment la contrôler.

Ta majoration est la bonne idée, à condition que tous les facteurs soient positifs, ce que garantit $a_{i} \leq 1$ . Pour la minoration, ne développe pas tout : raisonne par récurrence sur $m$ . Par quoi multiplies-tu pour passer de $m$ à $m + 1$ facteurs, et pourquoi le sens est-il conservé ?

Élève

Je multiplie par $1 - a_{m + 1}$ , qui est positif puisque $a_{m + 1} \leq 1$ . J'obtiens à droite $(1 - \sum_{i = 1}^{m} a_{i}) (1 - a_{m + 1})$ , que je développe.

Dans ce développement, repère le terme en trop par rapport à $1 - \sum_{i = 1}^{m + 1} a_{i}$ : quel est son signe, et pourquoi peux-tu t'en débarrasser sans changer le sens de l'inégalité ?

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 →