Exercice 33

1. Une répartition est une application de l'ensemble des $k$ objets dans l'ensemble des $n$ tiroirs ; l'univers est l'ensemble de ces $n^{k}$ applications (proposition 3), muni de la probabilité uniforme. Les répartitions favorables sont les injections, au nombre de $A_{n}^{k}$ si $k \leqslant n$, et de $0$ sinon (théorème 1) : $$\boxed{q_{k,n} = \frac{A_{n}^{k}}{n^{k}} = \prod_{i=0}^{k-1} \Big(1 - \frac{i}{n}\Big)}$$ la formule restant vraie pour $k > n$, puisque le produit contient alors le facteur nul $1 - \frac{n}{n}$.

2. La probabilité d'au moins une coïncidence vaut $1 - q_{k,365}$, comme dans l'exemple du cours (section 21.3.2). On la calcule en flottants, et l'on augmente $k$ jusqu'à dépasser le seuil :

def q(k, n):
    p = 1.0
    for i in range(k):
        p *= (n - i) / n
    return p

def seuil(s, n=365):
    k = 1
    while 1 - q(k, n) <= s:
        k += 1
    return k

print(seuil(0.5), seuil(0.9))   # affiche 23 41

On obtient $1 - q_{22,365} \approx 0{,}476$, $1 - q_{23,365} \approx 0{,}507$, puis $1 - q_{40,365} \approx 0{,}891$ et $1 - q_{41,365} \approx 0{,}903$ : $$\boxed{k = 23 \text{ pour le seuil } 0{,}5, \qquad k = 41 \text{ pour le seuil } 0{,}9}$$

3. (a) On pose $f(x) = \ln(1 - x) + x$ et $g(x) = \ln(1 - x) + x + x^{2}$, dérivables sur $\big[0\,,\frac{1}{2}\big]$, avec $$f'(x) = 1 - \frac{1}{1 - x} = -\frac{x}{1 - x} \leqslant 0, \qquad g'(x) = 1 + 2x - \frac{1}{1 - x} = \frac{x(1 - 2x)}{1 - x} \geqslant 0.$$ La fonction $f$ décroît et $g$ croît sur $\big[0\,,\frac{1}{2}\big]$, et $f(0) = g(0) = 0$, d'où $f \leqslant 0 \leqslant g$ : $$\boxed{-x - x^{2} \leqslant \ln(1 - x) \leqslant -x \qquad\text{pour tout } x \in \Big[0\,,\frac{1}{2}\Big]}$$ L'inégalité de droite est l'inégalité de concavité du logarithme (chapitre 9) ; celle de gauche cesse d'être vraie près de $1$, où $\ln(1 - x)$ tend vers $-\infty$, d'où la restriction à $\big[0\,,\frac{1}{2}\big]$.

(b) On note $k = k_{n}$. Comme $t\sqrt{n} - 1 < k \leqslant t\sqrt{n}$, on a $\frac{k}{\sqrt{n}} \to t$ par encadrement. Pour $n \geqslant 4t^{2}$ et $0 \leqslant i \leqslant k - 1$, on a $\frac{i}{n} \leqslant \frac{t\sqrt{n}}{n} = \frac{t}{\sqrt{n}} \leqslant \frac{1}{2}$ : la question (a) s'applique à chaque facteur, en particulier $k \leqslant n$ et $q_{k,n} > 0$. En sommant, $$-\sum_{i=0}^{k-1} \frac{i}{n} - \sum_{i=0}^{k-1} \frac{i^{2}}{n^{2}} \leqslant \ln q_{k,n} \leqslant -\sum_{i=0}^{k-1} \frac{i}{n}, \qquad\text{avec}\qquad \sum_{i=0}^{k-1} \frac{i}{n} = \frac{k(k - 1)}{2n} = \frac{1}{2} \cdot \frac{k}{\sqrt{n}} \cdot \frac{k - 1}{\sqrt{n}}.$$ Cette dernière quantité tend vers $\frac{t^{2}}{2}$, et la somme des $\frac{i^{2}}{n^{2}}$, qui a $k$ termes majorés par $\frac{k^{2}}{n^{2}}$, est majorée par $\frac{k^{3}}{n^{2}} \leqslant \frac{t^{3}}{\sqrt{n}}$, qui tend vers $0$. Par encadrement, $\ln q_{k_{n},n}$ tend vers $-\frac{t^{2}}{2}$, et, par continuité de l'exponentielle, $$\boxed{\lim_{n \to +\infty} q_{k_{n},n} = \mathrm{e}^{-t^{2}/2}}$$ Pour $n = 10^{6}$ et $t = 1$, on calcule $q_{1000,\,10^{6}} \approx 0{,}6067$, pour $\mathrm{e}^{-1/2} \approx 0{,}6065$ ✓.

Interprétation pour $n = 365$. Avec $k = t\sqrt{365}$, la probabilité que les $k$ anniversaires soient distincts vaut environ $\mathrm{e}^{-k^{2}/730}$. Elle vaut $\frac{1}{2}$ pour $k = \sqrt{730\ln 2} \approx 22{,}5$, et $\frac{1}{10}$ pour $k = \sqrt{730\ln 10} \approx 41{,}0$ : l'approximation retrouve les deux seuils de la question 2. Le nombre de personnes nécessaire pour une coïncidence probable est de l'ordre de $\sqrt{n}$, et non de $n$, parce que $\frac{k^{2}}{2n}$ est à peu près le nombre $\binom{k}{2}$ de paires de personnes, multiplié par la probabilité $\frac{1}{n}$ de coïncidence pour chaque paire.

Piège. L'erreur la plus répandue est d'écrire $\ln q_{k,n} \approx -\sum \frac{i}{n}$ sans contrôler l'erreur : chacun des $k$ termes commet une erreur de l'ordre de $\frac{i^{2}}{n^{2}}$, et c'est leur somme, de l'ordre de $\frac{k^{3}}{n^{2}}$, qu'il faut rendre négligeable. Elle tend vers $0$ parce que $k$ est de l'ordre de $\sqrt{n}$ ; pour $k$ de l'ordre de $n^{2/3}$, elle ne tendrait plus vers $0$.