Introduction : Le miracle le plus contre-intuitif des probabilités
En 2003, l’informaticien danois Peter Bro Miltersen a présenté une énigme devenue célèbre, le problème des 100 prisonniers :
- \(100\) condamnés à mort sont numérotés de \(1\) à \(100\). Dans une pièce se trouvent \(100\) boîtes fermées contenant chacune un numéro de \(1\) à \(100\) mélangé aléatoirement (une permutation \(\sigma \in S_{100}\)).
- Règle : Chaque prisonnier entre seul à son tour et peut ouvrir au plus \(50\) boîtes pour trouver son propre numéro. Les boîtes sont refermées à l’identique après son passage et toute communication est strictement impossible après le début du jeu (mais une stratégie commune peut être fixée avant).
- Verdict : Si les \(100\) prisonniers trouvent tous leur numéro, tous sont graciés ; si un seul échoue, les \(100\) sont exécutés.
Si chacun ouvre \(50\) boîtes au hasard (stratégie indépendante), chacun réussit avec probabilité \(1/2\), mais la survie collective tombe à :
\[\mathbb{P}(\text{survie collective})_{\text{indép.}} = \left(\frac{1}{2}\right)^{100} \approx 7{,}89 \times 10^{-31}\]Pourtant, Sven Skyum a découvert la stratégie du suivi de pointeurs (Pointer-Following Strategy) qui hisse la probabilité de survie collective à \(31{,}18\,\%\) sans transmettre le moindre bit d’information !
Chapitre 1 : Suivi de pointeurs et décomposition en cycles disjoints
Pour le prisonnier numéro \(k \in \{1, \dots, 100\}\), la stratégie de Skyum consiste à :
- Étape 1 : Ouvrir d’abord la boîte n° \(k\).
- Étape 2 : Si le billet intérieur vaut \(x_1 = k\), c’est gagné ; si \(x_1 \neq k\), ouvrir ensuite la boîte n° \(x_1\).
- Étape 3 : Lire le billet \(x_2\) et ouvrir la boîte n° \(x_2\), en suivant la chaîne \(k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots\) jusqu’à trouver \(k\) ou épuiser ses \(50\) essais.
flowchart TD
Start["Le prisonnier k entre dans la salle (max. 50 essais)"]
Step1["Étape 1 : Ouvrir la boîte k, lire le billet x = σ(k)"]
Check{"Billet x == k ?"}
Win["Numéro k trouvé !"]
Limit{"Boîtes ouvertes < 50 ?"}
Next["Suivre le pointeur : Ouvrir la boîte x (x ← σ(x))"]
Lose["k non trouvé en 50 essais : Exécution générale"]
Start --> Step1 --> Check
Check -- "Oui" --> Win
Check -- "Non" --> Limit
Limit -- "Oui" --> Next --> Check
Limit -- "Non (longueur du cycle ℓ > 50)" --> Lose
Pourquoi cela fonctionne-t-il ? L’application boîte \(\mapsto\) billet est une bijection \(\sigma\) du groupe symétrique \(S_{2n}\) (\(2n=100\)). Toute permutation finie se décompose de manière unique en un produit de cycles disjoints :
\[\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100\]Comme \(\sigma\) est bijective, en partant de la boîte \(k\), le prisonnier parcourt l’unique cycle fermé contenant \(k\) et finit par atteindre \(\sigma^{-1}(k)\) (la boîte contenant le billet \(k\)). Ainsi :
- Le prisonnier \(k\) réussit en au plus \(50\) essais si et seulement si son cycle est de longueur \(\ell \le 50\).
- Les \(100\) prisonniers survivent tous si et seulement si la permutation \(\sigma \in S_{100}\) ne contient aucun cycle de longueur \(\ell > 50\) !
Chapitre 2 : Dénombrement des grands cycles et nombres harmoniques (\(1 - \ln 2\))
Pour \(2n\) prisonniers (\(n = 50\)), une permutation \(\sigma \in S_{2n}\) contient au plus un seul cycle de longueur \(\ell > n\), car deux cycles disjoints de longueur \(> n\) nécessiteraient au moins \(2n+2 > 2n\) éléments. Les événements \(E_\ell := \{\sigma \text{ possède un cycle de longueur } \ell\}\) pour \(\ell = n+1, \dots, 2n\) sont donc deux à deux disjoints ! Le nombre de permutations dans \(E_\ell\) vaut :
- Choix des \(\ell\) éléments du grand cycle : \(\binom{2n}{\ell}\) ;
- Nombre de cycles orientés sur ces \(\ell\) éléments : \((\ell - 1)!\) ;
- Permutations des \(2n - \ell\) éléments restants : \((2n - \ell)!\).
Le produit se simplifie remarquablement :
\[|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}\]En divisant par \(|S_{2n}| = (2n)!\), on obtient \(\mathbb{P}(E_\ell) = \frac{1}{\ell}\). Avec les nombres harmoniques \(H_N = \sum_{k=1}^N \frac{1}{k}\), la probabilité exacte de survie collective est :
\[\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30{,}685\,\%}\]Pour \(2n = 100\), on trouve \(P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31{,}1828\,\%}\) !
Chapitre 3 : Couplage des risques sans transmission d’information
flowchart TD
Pool["Risque total fixé : Espérance d'échecs E[échecs] = 50"]
Indep["Stratégie indépendante : Échecs dispersés dans presque tous les univers"]
Cycle["Suivi de cycles : Destins couplés par la structure cyclique de σ"]
ResI["Au moins 1 mort dans 99,99...92 % des univers → Survie ≈ 7,89×10⁻³¹"]
ResC["Échecs concentrés dans 68,82 % des univers (ℓ>50) → 31,18 % d'univers à 100 % de survie !"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| Caractéristique | 1. Stratégie indépendante | 2. Stratégie des cycles |
|---|---|---|
| Succès individuel \(\mathbb{P}(A_k)\) | \(50{,}00\,\%\) | \(50{,}00\,\%\) (identique) |
| Espérance de succès \(\mathbb{E}[X]\) | \(50\) prisonniers | \(50\) prisonniers (identique) |
| Corrélation | Nulle (indépendance) | Fortement couplée via \(\sigma\) |
| Survie des \(100\) prisonniers | \((1/2)^{100} \approx 7{,}89 \times 10^{-31}\) | \(1 - (H_{100} - H_{50}) \approx 31{,}18\,\%\) |
| Limite \(n \to \infty\) | \(0\) | \(1 - \ln 2 \approx 30{,}685\,\%\) |
- Couplage (Coupling) : Comme 1 échec ou 51 échecs entraînent la même peine capitale, la stratégie des cycles concentre tous les échecs dans les \(68{,}82\,\%\) de permutations ayant un cycle \(\ell > 50\), libérant ainsi \(31{,}18\,\%\) de l’espace probabiliste sans aucun échec !
- Parade contre un gardien malveillant : En convenant d’avance d’une bijection secrète aléatoire \(\tau \in S_{100}\), la conjugaison \(\tau \sigma \tau^{-1}\) restaure exactement la probabilité de survie de \(31{,}18\,\%\).