Rupture de monotonie, seuil de Gnedenko et dérangements de Montmort
Dans cette partie géométrique, nous avons vu que le simplexe canonique $\Delta_k$ (l’ensemble des points de l’hypercube unité $[0, 1]^k$ dont les coordonnées sont rangées par ordre croissant $0 \le t_1 \le t_2 \le \dots \le t_k \le 1$) possède un volume exactement égal à $\mathbf{\frac{1}{k!}}$, car les $k!$ permutations de ses axes découpent l’hypercube $[0, 1]^k$ en $k!$ simplexes isométriques.
En probabilités, cette propriété produit un effet spectaculaire. Tirons $k$ nombres $U_1, \dots, U_k$ indépendants et uniformes sur $[0, 1]$ : le point $(U_1, \dots, U_k)$ tombe uniformément dans l’hypercube $[0, 1]^k$, si bien que la probabilité qu’il tombe dans une région est tout simplement le volume de cette région. Toute condition qui revient à imposer un ordre aux tirages a donc pour probabilité le volume d’un simplexe, $\frac{1}{k!}$, et le nombre $\mathrm{e} = \sum \frac{1}{k!}$ (ou son inverse $\mathrm{e}^{-1}$) surgit là où rien ne semblait l’annoncer. Le même $\frac{1}{k!}$ apparaît aussi, dans un cadre discret, quand on permute des objets au hasard.
Étudions trois problèmes célèbres qui s’illuminent grâce à cette vision géométrique.
Énoncé du problème. On tire successivement des nombres aléatoires $U_1, U_2, U_3, \dots$ de manière indépendante et uniforme sur l’intervalle $[0, 1]$. On continue les tirages tant que les nombres tirés forment une suite croissante ($U_1 \le U_2 \le U_3 \le \dots$), et l’on s’arrête dès qu’un tirage est strictement inférieur au précédent.
Notons $N$ le nombre total de tirages effectués au moment de l’arrêt : $\displaystyle N = \min\left\{ k \ge 2 \;\middle|\; U_k < U_{k-1} \right\}$.
Question : En moyenne, combien de nombres doit-on tirer avant que la croissance ne se brise ? Autrement dit, que vaut l’espérance $\mathbb{E}[N]$ ?
Une partie typique : trois tirages croissants, puis une baisse au quatrième. Ici $N = 4$.
Avant même de calculer les probabilités liées aux $U_i$, rappelons une identité très générale et extrêmement commode pour toute variable aléatoire $N$ à valeurs dans les entiers naturels ($\mathbb{N}$) : au lieu de calculer $\mathbb{E}[N] = \sum_{k=1}^{+\infty} k\,\mathbb{P}(N = k)$, on peut exprimer l’espérance comme la somme des probabilités de survie $\mathbb{P}(N > k)$.
Pourquoi a-t-on $\mathbb{E}[N] = \sum_{k=0}^{+\infty} \mathbb{P}(N > k)$ ? Parce que tout entier $m \ge 1$ est la somme de $m$ fois le nombre $1$ ($m = \sum_{k=0}^{m-1} 1$). Écrivons les termes de la somme $\sum_{m=1}^{+\infty} m\,\mathbb{P}(N = m)$ sous forme d’un tableau triangulaire et sommons colonne par colonne plutôt que ligne par ligne :
$$ \begin{aligned} \mathbb{E}[N] &= 1\,\mathbb{P}(N=1) + 2\,\mathbb{P}(N=2) + 3\,\mathbb{P}(N=3) + 4\,\mathbb{P}(N=4) + \cdots \\ &= \begin{array}{ccccccccc} \mathbb{P}(N=1) & + & \mathbb{P}(N=2) & + & \mathbb{P}(N=3) & + & \mathbb{P}(N=4) & + \cdots & = \mathbb{P}(N > 0) \\ & & \mathbb{P}(N=2) & + & \mathbb{P}(N=3) & + & \mathbb{P}(N=4) & + \cdots & = \mathbb{P}(N > 1) \\ & & & & \mathbb{P}(N=3) & + & \mathbb{P}(N=4) & + \cdots & = \mathbb{P}(N > 2) \\ & & & & & & \vdots & & \vdots \end{array} \\ &= \sum_{k=0}^{+\infty} \mathbb{P}(N > k) \end{aligned} $$
Que signifie l’événement de survie $\{N > k\}$ pour un entier $k \ge 1$ ? Dire que l’on ne s’est pas encore arrêté à l’issue du $k$-ième tirage signifie exactement que les $k$ premiers nombres tirés n’ont subi aucune baisse, autrement dit qu’ils sont rangés par ordre croissant :
$\displaystyle \{N > k\} = \left\{ 0 \le U_1 \le U_2 \le \dots \le U_k \le 1 \right\}$ $\displaystyle \quad \Longleftrightarrow \quad (U_1, U_2, \dots, U_k) \in \Delta_k$
Or, comme les variables $U_1, \dots, U_k$ sont indépendantes et uniformément distribuées sur $[0, 1]$, le point aléatoire $M = (U_1, \dots, U_k)$ tombe de manière uniforme dans l’hypercube unité $[0, 1]^k$ (la probabilité qu’il tombe dans un sous-domaine de $[0, 1]^k$ est égale au volume $k$-dimensionnel de ce sous-domaine).
La probabilité que l’expérience survive au-delà du tirage $k$ est donc tout simplement le volume du simplexe canonique $\Delta_k$ !
Pour tout entier $k \ge 0$, la probabilité que les $k$ premiers tirages uniformes soient croissants vaut $\displaystyle \mathbb{P}(N > k) = \operatorname{Vol}_k(\Delta_k) = \frac{1}{k!}$.
Le nombre moyen de tirages avant la première baisse vaut donc exactement $\mathrm{e}$ :
$$ \mathbb{E}[N] = \sum_{k=0}^{+\infty} \mathbb{P}(N > k) = \sum_{k=0}^{+\infty} \frac{1}{k!} = 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \cdots = \mathrm{e} \approx 2,71828 $$
Et la probabilité de s’arrêter exactement au $k$-ième tirage ($k \ge 2$) vaut $\displaystyle \mathbb{P}(N = k) = \mathbb{P}(N > k-1) - \mathbb{P}(N > k) = \frac{1}{(k-1)!} - \frac{1}{k!} = \frac{k - 1}{k!}$.
Changeons maintenant complètement la règle d’arrêt, tout en conservant la même suite de tirages uniformes $U_1, U_2, \dots \in [0, 1]$.
Énoncé du problème (Gnedenko / Forsythe). On tire des variables aléatoires $U_1, U_2, U_3, \dots$ indépendantes et uniformes sur $[0, 1]$ et on les additionne au fur et à mesure. On s’arrête dès que la somme cumulée dépasse strictement $1$.
Notons $M$ le nombre de tirages nécessaires pour franchir le seuil $1$ : $\displaystyle M = \min\left\{ k \ge 1 \;\middle|\; U_1 + U_2 + \dots + U_k > 1 \right\}$.
Question : Que vaut le nombre moyen de tirages $\mathbb{E}[M]$ ?
Une partie typique : la somme dépasse $1$ au troisième tirage. Ici $M = 3$.
À première vue, additionner des nombres jusqu’à dépasser $1$ semble très différent de les comparer l’un à l’autre ($U_1 \le U_2 \le \dots \le U_k$). Et pourtant, un simple cisaillement géométrique montre que les deux problèmes sont isomorphes !
Examinons l’événement de survie $\{M > k\}$ (pour $k \ge 1$). Dire qu’il faut strictement plus de $k$ tirages pour que la somme dépasse $1$ équivaut à dire que la somme des $k$ premiers tirages est restée inférieure ou égale à $1$, soit $\displaystyle \{M > k\} = \left\{ U_1 + U_2 + \dots + U_k \le 1 \right\}$.
Dans l’hypercube $[0, 1]^k$, cet événement correspond au domaine appelé simplexe orthogonal (ou coin de l’hypercube) :
$\displaystyle \Omega_k = \left\{ (u_1, u_2, \dots, u_k) \in \mathbb{R}^k \;\middle|\; u_1 \ge 0,\; \dots,\; u_k \ge 0 \text{ et } u_1 + \dots + u_k \le 1 \right\}$
Pourquoi ce coin $\Omega_k$ a-t-il exactement le même volume $\frac{1}{k!}$ que notre simplexe ordonné $\Delta_k = \{0 \le t_1 \le t_2 \le \dots \le t_k \le 1\}$ ? Associons à tout $k$-uplet d’incréments $(u_1, u_2, \dots, u_k)$ la suite de ses sommes cumulées $(t_1, t_2, \dots, t_k)$ :
$$ \begin{cases} t_1 = u_1 \\ t_2 = u_1 + u_2 \\ \;\vdots \\ t_k = u_1 + u_2 + \dots + u_k \end{cases} \qquad \Longleftrightarrow \qquad \begin{pmatrix} t_1 \\ t_2 \\ \vdots \\ t_k \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & 1 \end{pmatrix}}_{=\,J} \begin{pmatrix} u_1 \\ u_2 \\ \vdots \\ u_k \end{pmatrix} $$
Le cisaillement $t_1 = u_1$, $t_2 = u_1 + u_2$ fait glisser chaque tranche verticale du coin $\Omega_2$ vers le haut, d'autant plus qu'elle est à droite : les tranches gardent leur longueur, et le coin devient le triangle $\Delta_2$.
Analysons cette transformation linéaire $\Psi : (u_1, \dots, u_k) \mapsto (t_1, \dots, t_k)$ :
On en déduit sans aucun calcul d’intégrale que pour tout $k \ge 0$, $\displaystyle \mathbb{P}(M > k) = \operatorname{Vol}_k(\Omega_k) = \operatorname{Vol}_k(\Delta_k) = \frac{1}{k!}$.
D’où à nouveau, par sommation des probabilités de survie : $\displaystyle \mathbb{E}[M] = \sum_{k=0}^{+\infty} \mathbb{P}(M > k) = \sum_{k=0}^{+\infty} \frac{1}{k!} = \mathrm{e} \approx 2,71828$. $\blacksquare$
Peut-on retrouver $\mathbb{E}[M] = \mathrm{e}$ directement à partir de l’équation différentielle de l’exponentielle ($f’ = f$), sans même passer par la série $\sum \frac{1}{k!}$ ?
Oui, grâce à l’absence de mémoire des incréments indépendants ! Généralisons le problème en notant $m(x)$ le nombre moyen de tirages uniformes sur $[0, 1]$ nécessaires pour que leur somme dépasse un seuil réel quelconque $x \in [0, 1]$ :
$\displaystyle m(x) = \mathbb{E}[M_x], \qquad \text{où}$ $\displaystyle \quad M_x = \min\left\{ k \ge 1 \;\middle|\; U_1 + \dots + U_k > x \right\}$
Suivons ce qui se passe lors du tout premier tirage $U_1 = u \in [0, 1]$ :
En intégrant sur toutes les valeurs possibles $u \in [0, 1]$ du premier tirage uniforme, l’espérance conditionnelle donne :
$$ m(x) = \int_0^x \big(1 + m(x - u)\big)\,\mathrm{d}u + \int_x^1 1\,\mathrm{d}u = \underbrace{\int_0^1 1\,\mathrm{d}u}_{=\,1} + \int_0^x m(x - u)\,\mathrm{d}u $$
En posant $t = x - u$ dans l’intégrale, on obtient l’équation intégrale de renouvellement (identique à l’équation de Picard-Dyson vue ici) :
$$ \forall x \in [0, 1], \qquad m(x) = 1 + \int_0^x m(t)\,\mathrm{d}t $$
D’où $m(0) = 1$ et, par dérivation, $m’(x) = m(x)$, ce qui implique $m(x) = \mathrm{e}^x$. En particulier, pour le seuil $x = 1$, on a $\mathbb{E}[M] = m(1) = \mathrm{e}^1 = \mathrm{e}$. $\blacksquare$
Et au-delà de $1$ ? L’argument repose sur le fait que, tant que $x \le 1$, le premier tirage peut tomber n’importe où dans $[0, x]$ avec la même densité : le jeu est alors « sans mémoire », et l’on retrouve l’équation de l’exponentielle. Pour un seuil $x > 1$, ce n’est plus vrai (un tirage ne dépasse jamais $1$), et l’équation devient $m’(x) = m(x) - m(x - 1)$ : la valeur en $x$ dépend de ce qui s’est passé une unité plus tôt. La mémoire réapparaît, et l’exponentielle disparaît : on trouve par exemple $m(2) = \mathrm{e}^2 - \mathrm{e} \approx 4,67$, puis $m(x) \approx 2x + \frac{2}{3}$ pour les grands seuils. Ce lien entre $\frac{1}{k!}$ et absence de mémoire est détaillé dans la partie géométrique.
Simulons $100,000$ parties de chacun des deux jeux, et comptons dans quelle proportion de parties on a survécu au-delà du $k$-ième tirage :
Fréquences de survie observées sur $100\,000$ parties de chaque jeu. Elles collent aux volumes $\frac{1}{k!}$ des simplexes (traits magenta), et sont presque identiques d'un jeu à l'autre : le cisaillement l'avait prédit.
Les nombres moyens de tirages observés valent $2,716$ pour la rupture de monotonie et $2,722$ pour le seuil de Gnedenko, pour une valeur exacte $\mathrm{e} \approx 2,718$. Les écarts, de l’ordre de $0,003$, sont conformes aux fluctuations attendues : l’écart-type de $N$ (ou de $M$) vaut $\sqrt{3\mathrm{e} - \mathrm{e}^2} \approx 0,88$, donc celui d’une moyenne sur $100,000$ parties est d’environ $\frac{0,88}{\sqrt{100,000}} \approx 0,003$.
Énoncé du problème. À l’entrée d’une soirée, $n$ convives numérotés de $1$ à $n$ déposent chacun leur chapeau au vestiaire. En repartant, ils récupèrent chacun un chapeau totalement au hasard (ce qui revient à tirer uniformément une permutation $\sigma$ dans le groupe symétrique $\mathfrak{S}_n$, de cardinal $n!$).
On appelle dérangement une permutation qui ne laisse aucun élément à sa place initiale (aucun convive ne récupère son propre chapeau) :
$\displaystyle D_n = \left\{ \sigma \in \mathfrak{S}_n \;\middle|\; \forall i \in \{1, \dots, n\},\; \sigma(i) \neq i \right\}$
Question : Quelle est la probabilité $p_n = \frac{|D_n|}{n!}$ qu’aucun convive ne récupère son chapeau, et comment évolue cette probabilité lorsque le nombre de convives $n$ tend vers $+\infty$ ?
Quand le nombre de convives $n$ grandit, deux effets opposés s’affrontent : il y a de plus en plus d’individus susceptibles de tomber sur leur propre chapeau, mais chacun n’a plus qu’une chance $\frac{1}{n}$ de tomber sur le sien. Ces deux effets se compensent avec une précision stupéfiante : dès $n = 7$ convives, la probabilité $p_n$ vaut déjà $\frac{1}{\mathrm{e}} \approx 36,788\,\%$ à moins de trois cent-millièmes près !
Passons par l’événement complémentaire : « au moins un convive récupère son propre chapeau », c’est-à-dire la réunion $\bigcup_{i=1}^n A_i$, où $A_i = \{\sigma \in \mathfrak{S}_n \mid \sigma(i) = i\}$.
Par la formule du crible de Poincaré (principe d’inclusion-exclusion), on alterne la somme des probabilités des intersections de $k$ événements indexées par les $k$-uplets strictement croissants $1 \le i_1 < i_2 < \dots < i_k \le n$ (le simplexe discret) :
$$ \mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} \mathbb{P}\left(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}\right) $$
Or, imposer que $k$ convives précis $i_1 < \dots < i_k$ récupèrent chacun leur propre chapeau fige ces $k$ chapeaux et laisse $(n - k)!$ permutations possibles pour les $n - k$ autres convives, soit une probabilité $\frac{(n - k)!}{n!}$.
Comme le simplexe discret $1 \le i_1 < \dots < i_k \le n$ contient exactement $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$ termes tous égaux à $\frac{(n-k)!}{n!}$, la dépendance en $n$ s’élimine algébriquement et laisse exactement le volume du simplexe $\frac{1}{k!}$ :
$$ \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} \mathbb{P}\left(A_{i_1} \cap \dots \cap A_{i_k}\right) = \binom{n}{k} \times \frac{(n - k)!}{n!} = \frac{\cancel{n!}}{k!\,\cancel{(n - k)!}} \times \frac{\cancel{(n - k)!}}{\cancel{n!}} = \mathbf{\frac{1}{k!}} $$
Par exemple, avec $n = 4$ convives et $k = 2$ : il y a $\binom{4}{2} = 6$ paires de convives, et chaque paire a une probabilité $\frac{2!}{4!} = \frac{1}{12}$ de récupérer ses deux chapeaux (les deux autres chapeaux se répartissent de $2!$ façons parmi les $4!$ possibles). Au total : $6 \times \frac{1}{12} = \frac{1}{2} = \frac{1}{2!}$. Avec $n = 10$ convives, on aurait $45$ paires de probabilité $\frac{1}{90}$ chacune : toujours $\frac{1}{2}$ !
Théorème (Formule de Montmort et convergence vers $\mathrm{e}^{-1}$). Pour tout entier $n \ge 1$, la probabilité $p_n = \frac{|D_n|}{n!}$ qu’une permutation aléatoire uniforme de $\mathfrak{S}_n$ soit un dérangement est exactement égale à la $n$-ième somme partielle de la série alternée des inverses de factorielles :
$$ p_n = \frac{|D_n|}{n!} = 1 - \mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=0}^n \frac{(-1)^k}{k!} = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!} \xrightarrow[n \to +\infty]{} \mathrm{e}^{-1} \approx 0,367879 $$
De plus, dès $n = 1$, le nombre entier de dérangements $|D_n|$ est l’entier le plus proche de $\frac{n!}{\mathrm{e}}$, soit $\displaystyle |D_n| = \left\lfloor \frac{n!}{\mathrm{e}} + \frac{1}{2} \right\rfloor$.
D’après le critère des séries alternées, le reste de $\mathrm{e}^{-1} = \sum_{k=0}^{+\infty} \frac{(-1)^k}{k!}$ au-delà du rang $n$ est strictement majoré en valeur absolue par le premier terme négligé $\frac{1}{(n+1)!}$ :
$\displaystyle \left| \mathrm{e}^{-1} - \frac{|D_n|}{n!} \right| < \frac{1}{(n+1)!}$ $\displaystyle \quad \Longrightarrow \quad \left| |D_n| - \frac{n!}{\mathrm{e}} \right| < \frac{n!}{(n+1)!} = \frac{1}{n + 1} \le \frac{1}{2}$
La distance entre l’entier $|D_n|$ et le réel $\frac{n!}{\mathrm{e}}$ étant strictement inférieure à $\frac{1}{2}$, $|D_n|$ est toujours l’unique entier le plus proche de $\frac{n!}{\mathrm{e}}$ ! $\blacksquare$
La probabilité $p_n$ qu'aucun convive ne récupère son chapeau oscille autour de $\frac{1}{\mathrm{e}}$ et s'en rapproche très vite : l'écart est inférieur à $\frac{1}{(n+1)!}$.
On peut également retrouver $\lim p_n = \frac{1}{\mathrm{e}}$ sans aucun signe alterné, en classant les $n!$ permutations de $\mathfrak{S}_n$ selon leur nombre exact $k$ de points fixes ($k \in \{0, \dots, n\}$) :
En sommant sur $k$ et en divisant par $n!$, on obtient la décomposition exacte de la loi du nombre $X_n$ de points fixes :
Pour tout entier $n \ge 0$, les probabilités de dérangement $(p_m)_{m \ge 0}$ vérifient $\displaystyle 1 = \sum_{k=0}^n \frac{1}{k!} \, p_{n-k}$, et le nombre $X_n$ de points fixes d’une permutation uniforme de $\mathfrak{S}_n$ suit la loi :
$$ \forall k \in \{0, \dots, n\}, \qquad \mathbb{P}(X_n = k) = \frac{1}{k!}\,p_{n-k} = \frac{1}{k!} \sum_{j=0}^{n-k} \frac{(-1)^j}{j!} \xrightarrow[n \to +\infty]{} \frac{\mathrm{e}^{-1}}{k!} $$
En passant à la limite $n \to +\infty$ dans $1 = \sum_{k=0}^n \frac{1}{k!} p_{n-k}$ (l’échange de la limite et de la somme se justifie par le théorème de Tannery, car $0 \le p_{n-k} \le 1$), on obtient $1 = \mathrm{e} \times p_\infty$, soit $p_\infty = \mathrm{e}^{-1}$, et le nombre de points fixes $X_n$ converge en loi vers la loi de Poisson $\mathcal{P}(1)$.
Pour $n = 6$ chapeaux, la loi exacte du nombre $X_6$ de convives qui récupèrent leur chapeau (barres) est déjà presque indiscernable de la loi de Poisson $\mathcal{P}(1)$ (cercles).
La loi de Poisson n’est pas une coïncidence : c’est la loi du nombre d’événements dans un processus sans mémoire, et son $\frac{1}{k!}$ a la même origine géométrique que tous ceux de cette page (voir la partie géométrique).
Pour retrouver une autre apparition célèbre du seuil $\frac{1}{\mathrm{e}} \approx 36,8\,\%$ en probabilités, voir aussi le problème du secrétaire dans la page Curiosités !