mathématiques (PTSI) · Chapitre 16 · 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, je passe au logarithme : il suffirait que $\sum ln (1 - a_{i}) \leq - \sum a_{i}$ . Mais si l'un des $a_{i}$ vaut $1$ , le logarithme n'est pas défini.

Bonne remarque : le logarithme imposerait de traiter ce cas à part. Tu peux l'éviter en comparant directement chaque facteur $1 - a_{i}$ à une exponentielle : quelle inégalité du cours sur $e^{x}$ utiliser, et avec quel $x$ ?

Élève

$e^{x} \geq 1 + x$ avec $x = - a_{i}$ donne $1 - a_{i} \leq e^{- a_{i}}$ . Je multiplie ensuite ces $m$ inégalités, et le produit des exponentielles est l'exponentielle de la somme.

Qu'est-ce qui t'autorise à multiplier ces inégalités membre à membre, compte tenu du signe de $1 - a_{i}$ ? Et pour la minoration, quelle récurrence sur $m$ envisages-tu, en multipliant par quel facteur ?

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 →