Qu'est-ce que « Indépendance » ?

Exemple 21.21 (Indépendance lue sur une structure de produit)

Lançons deux dés équilibrés : $\Omega = \intint16^2$ avec des poids uniformes. Posons $A = {}$« premier dé pair » et $B = {}$« second dé au moins $5$ ». Dénombrement : $\abs A = 3\cdot6 = 18$, $\abs B = 6\cdot2 = 12$, $\abs{A\cap B} = 3\cdot2 = 6$, de sorte que

indépendants, et le mécanisme est visible — $A$ ne contraint que la première coordonnée, $B$ que la seconde, et la mesure uniforme sur un ensemble produit fait multiplier les dénombrements par coordonnée. Toute affirmation du type « des événements dépendant de groupes disjoints de lancers sont indépendants » (utilisée massivement dans le devoir du week-end) est ce calcul, avec davantage d’indices.

Exemple 21.8 (La borne de l’union : grossière mais indestructible)

La sous-additivité avec un nombre fini d’événements — la borne de l’union — échange la précision contre l’universalité. Pour le problème des anniversaires avec $23$ personnes, borner la probabilité de collision par la somme sur les paires donne

contre la vraie valeur $0.507$ : éloignée d’une large marge, car les collisions se recouvrent. Pourtant la borne ne requiert aucune indépendance, aucune loi jointe, rien d’autre que les probabilités des paires — c’est pourquoi, dans le devoir du week-end et tout au long du Chapitre 22, la borne de l’union est le premier outil dégainé : lorsqu’elle se trouve être petite, l’affaire est réglée sans autre modélisation.

Exemple 21.15 (La collision d’anniversaires, par la règle des probabilités composées)

Avec $n$ personnes dont les anniversaires sont indépendants et uniformes sur $365$ jours, posons $D_n = {}$« les $n$ anniversaires sont tous distincts ». En conditionnant personne par personne (règle des probabilités composées) :

chaque nouvelle personne devant éviter les $k$ jours déjà pris. Pour $n = 23$ : $\P(D_{23}) \approx 0.493$ — un anniversaire partagé est déjà plus probable qu’improbable. L’heuristique qui explique la petitesse de $23$ : en prenant les logarithmes, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$, et $\binom{23}2 = 253$ donne $253/365 \approx 0.693 \approx \ln 2$. Ce qui importe, c’est le nombre de paires, qui croît quadratiquement : les problèmes de collision vivent à l’échelle $n \sim \sqrt{365}$, non $n \sim 365$ — le paradoxe des anniversaires est une racine carrée déguisée.

Exemple 22.7 (Le problème des anniversaires, honnêtement)

Parmi $n$ personnes d’anniversaires indépendants, uniformes sur $N = 365$ jours, la probabilité que tous les anniversaires diffèrent est

par conditionnement itéré (ou directement : les $N(N-1)\cdots(N - n + 1)$ favorables sur le total $N^n$, un argument de comptage que la formule produit de l’indépendance rend rigoureux). En prenant les logarithmes et en utilisant $-\ln(1 - x) = x + O(x^2)$ :

Le point de bascule $p_n = \frac12$ se situe en $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$ : pour $N = 365$, $n = 23$ ($p_{23} = 0.4927$). Deux morales. Premièrement, les collisions parmi $n$ items dans $N$ boîtes apparaissent à l’échelle $n \sim \sqrt N$, non $n \sim N$ — l’échelle des anniversaires qui gouverne les collisions de hachage et le coût $\sqrt N$ des attaques d’anniversaire en cryptographie. Deuxièmement, le calcul est un modèle : les $\binom n2$ événements de collision par paires ne sont pas indépendants, et pourtant la réponse se comporte comme s’ils l’étaient ($\eu^{-\binom n2/N}$ est exactement l’heuristique des paires indépendantes) — une première instance de l’approximation de Poisson rendue rigoureuse dans le problème de week-end du Chapitre 23 (inégalité de Le Cam).

Exemple 22.14 (Ce que la loi forte achète)

(a) Fréquences : pour des piles ou faces i.i.d., la fréquence observée de faces converge p.s. vers $p$ — la justification empirique de la probabilité elle-même. (b) Monte-Carlo : pour $g \in L^1(\intcc01)$ et $(U_n)$ i.i.d. uniformes (Théorème 22.6), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ p.s. : intégrales par échantillonnage, en toute dimension, au taux indépendant de la dimension $\sim n^{-1/2}$ précisé au Chapitre 23. (c) Nombres normaux : presque tout nombre réel a, dans son développement binaire, une fréquence asymptotique $\frac12$ de uns (appliquer la loi forte aux variables chiffres du Théorème 22.6) — le théorème de Borel, un énoncé sur les nombres de tous les jours prouvé par la mesure : le Problème 22.1 le complète dans toutes les bases.