Recueil de modèles aléatoires

Djalil Chafai, Florent Malrieu

► To cite this version:

Djalil Chafai, Florent Malrieu. Recueil de modèles aléatoires. Springer, Mathématiques et applications n°78, 2016, 978-3662497678. hal-01897577v4

HAL Id: hal-01897577

https://hal.science/hal-01897577v4

Submitted on 4 Jan 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Recueil de modèles aléatoires

Version post-publication de l'hiver 2021

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>
Avant-propos

<figure><img src="image_4.png" /></figure>

«... I prefer concrete things and I don't like to learn more about abstract stuff than I absolutely have to....». Marc Kac (1914 – 1984), in *Enigmas of Chance: An Autobiography* (1985, chapitre 5 page 112).

Ce recueil est une collection accumulée au fil du temps que nous souhaitons partager avec plaisir et enthousiasme. Il a été conçu pour être consulté ponctuellement, au hasard, en feuilletant les pages, en consultant la table des matières ou l'index. Ce type de document nous semble utile dans un univers scientifique hyperspecialisé laissant peu de place à l'ouverture et à l'éclectisme.

Le premier public visé est celui des enseignants-chercheurs en probabilités, débutants ou confirmés. Ce recueil a pour but de les aider à enrichir leur culture probabiliste en excitant leur curiosité. Nous espérons qu'il les inspirera pour la conception de leur enseignement de master ou l'encadrement de stages d'ouverture à la recherche. De nombreux chapitres peuvent également bénéficier directement à des étudiants de master ou préparant l'agrégation.

Le parti pris de cet ouvrage est de polariser la rédaction par les modèles plutôt que par les outils, et de consacrer chaque chapitre à un modèle. Bien que parfois reliés, les chapitres sont essentiellement autonomes. Ils ne contiennent
VIII

pas ou peu de rappels de cours. Nous fournissons toutefois en fin d'ouvrage,
juste avant la bibliographie, une liste de références conseillées concernant les
théorèmes limites, les martingales à temps discret, les chaînes de Markov
à espace d'états au plus dénombrable, et les bases du calcul stochastique.
En tête de chaque chapitre sont proposées des listes de mots-clés et d'outils
utilisés, ainsi qu'une indication du degré de difficulté (de une à trois étoiles).
L'introduction et surtout la section «Pour aller plus loin» de chaque chapitre
ont pour but de mettre en perspective le thème abordé et de proposer des
références bibliographiques.

Ce recueil ne prétend pas constituer une référence sur des modèles proba-
bilistes en biologie, informatique, ingénierie, ou physique, et prétend encore
moins fournir des solutions pour les praticiens de ces domaines d'applica-
tion. Les modèles considérés dans ce recueil ne sont souvent qu'inspirés des
applications, et le traitement ne concerne en général que des versions consi-
dérablement simplifiées. Cela est déjà beaucoup !

Ce recueil puise sa source dans les cours de Master de mathématiques
appliquées et de préparation à l'épreuve de modélisation de l'agrégation de
mathématiques, que nous avons dispensés aux étudiants des universités de
Toulouse, Rennes, Marne-la-Vallée, Paris-Dauphine, et Tours. La qualité du
texte, aussi bien sur le fond que sur la forme, doit beaucoup à nos tous pre-
miers lecteurs, petits et grands. Grand merci, donc, à nos anciens étudiants!
Grand merci également à Arnaud Guyader, à Bernard Bercu et à Olivier
Zindy pour leur relecture substantielle. Grand merci aussi à Jürgen Angst,
Amine Asselah, Jean-Baptiste Bardet, Charles Bordenave, Raphaël Butez,
Marie-Line Chabanol, Bertrand Cloez, Yan Doumerc, Olivier Durieu, Lucas
Gerin, Hélène Guérin, Bénédicte Haas, Igor Kortchemski, Jamal Najim, Julien
Poisat, Justin Salez, Pierre Tarrès, Marie-Noémie Thai, Frédérique Watbled,
et Pierre-André Zitt pour leur aide. Ce recueil a également bénéficié des re-
lectures attentives et constructives de plusieurs rapporteurs anonymes. Nous
sommes enfin reconnaissants à Sylvie Méléard de nous avoir incités à trans-
former un polycopié en un livre, puis d'avoir mené un solide travail éditorial.
Malgré tout, et comme toute œuvre humaine, ce recueil reste limité et impar-
fait. Un erratum sera disponible sur Internet, ainsi que les programmes ayant
fourni les illustrations.

Bonne lecture !

Djalil Chafaï et Florent Malrieu
Vincennes et Saint-Avertin, automne 2015
Mis à jour à l'hiver 2021
$$ (\Omega, \mathcal{F}, \mathbb{P}) $$

Toutes les variables aléatoires de ce recueil sont définies sur cet espace.
Table des matières

<table><tbody><tr><td>1</td><td>Pile, face, coupons</td><td>1</td></tr><tr><td>1.1</td><td>Jeu de pile ou face</td><td>1</td></tr><tr><td>1.2</td><td>Approximation binomiale-gaussienne</td><td>4</td></tr><tr><td>1.3</td><td>Distance en variation totale</td><td>5</td></tr><tr><td>1.4</td><td>Approximation binomiale-Poisson</td><td>8</td></tr><tr><td>1.5</td><td>Problème du collectionneur de coupons</td><td>9</td></tr><tr><td>1.6</td><td>Pour aller plus loin</td><td>15</td></tr><tr><td>2</td><td>Marches aléatoires</td><td>19</td></tr><tr><td>2.1</td><td>Marche aléatoire simple sur la droite</td><td>19</td></tr><tr><td>2.2</td><td>Marche aléatoire simple symétrique dans l'espace</td><td>26</td></tr><tr><td>2.3</td><td>Problème de Dirichlet et champ libre gaussien</td><td>30</td></tr><tr><td>2.4</td><td>Marche aléatoire sur le groupe symétrique</td><td>34</td></tr><tr><td>2.5</td><td>Pour aller plus loin</td><td>37</td></tr><tr><td>3</td><td>Branchement et processus de Galton-Watson</td><td>39</td></tr><tr><td>3.1</td><td>Extinction et phénomène de seuil</td><td>40</td></tr><tr><td>3.2</td><td>Étude des trois cas possibles</td><td>45</td></tr><tr><td>3.3</td><td>Taille de l'arbre en régimes critique et sous-critique</td><td>49</td></tr><tr><td>3.4</td><td>Immigration</td><td>52</td></tr><tr><td>3.5</td><td>Pour aller plus loin</td><td>54</td></tr><tr><td>4</td><td>Permutations, partitions, et graphes</td><td>57</td></tr><tr><td>4.1</td><td>Algorithme basique pour les lois discrètes</td><td>57</td></tr><tr><td>4.2</td><td>Permutations aléatoires</td><td>58</td></tr><tr><td>4.3</td><td>Partitions aléatoires</td><td>60</td></tr><tr><td>4.4</td><td>Graphes aléatoires</td><td>62</td></tr><tr><td>4.5</td><td>Arbres aléatoires</td><td>64</td></tr><tr><td>4.6</td><td>Pour aller plus loin</td><td>66</td></tr></tbody></table>
<table><tbody><tr><td>5</td><td>Mesures de Gibbs</td><td>69</td></tr><tr><td>5.1</td><td>Mesures de Gibbs</td><td>69</td></tr><tr><td>5.2</td><td>Algorithme de Metropolis-Hastings</td><td>72</td></tr><tr><td>5.3</td><td>Algorithme du recuit simulé</td><td>74</td></tr><tr><td>5.4</td><td>Algorithme de Propp-Wilson</td><td>77</td></tr><tr><td>5.5</td><td>Modélisation d'un composé chimique</td><td>78</td></tr><tr><td>5.6</td><td>Pour aller plus loin</td><td>80</td></tr><tr><td>6</td><td>Agrégation limitée par diffusion interne</td><td>83</td></tr><tr><td>6.1</td><td>Modèle d'agrégation par diffusion</td><td>83</td></tr><tr><td>6.2</td><td>Modèle unidimensionnel</td><td>84</td></tr><tr><td>6.3</td><td>Convergence presque sûre</td><td>85</td></tr><tr><td>6.4</td><td>Convergence en loi</td><td>86</td></tr><tr><td>6.5</td><td>Une inégalité de concentration</td><td>89</td></tr><tr><td>6.6</td><td>Dimensions supérieures</td><td>89</td></tr><tr><td>6.7</td><td>Pour aller plus loin</td><td>91</td></tr><tr><td>7</td><td>Chaînes de Markov cachées</td><td>93</td></tr><tr><td>7.1</td><td>Algorithme progressif-rétrograde</td><td>93</td></tr><tr><td>7.2</td><td>Filtre de Kalman</td><td>99</td></tr><tr><td>7.3</td><td>Pour aller plus loin</td><td>102</td></tr><tr><td>8</td><td>Algorithme EM et mélanges</td><td>105</td></tr><tr><td>8.1</td><td>Modèle pour les nids de mouettes</td><td>105</td></tr><tr><td>8.2</td><td>Situation favorable mais irréaliste</td><td>107</td></tr><tr><td>8.3</td><td>Résolution du vrai problème</td><td>108</td></tr><tr><td>8.4</td><td>Pour aller plus loin</td><td>111</td></tr><tr><td>9</td><td>Urnes d'Ehrenfest</td><td>113</td></tr><tr><td>9.1</td><td>Modèle microscopique</td><td>113</td></tr><tr><td>9.2</td><td>Urne d'Ehrenfest</td><td>121</td></tr><tr><td>9.3</td><td>Pression au fil du temps</td><td>122</td></tr><tr><td>9.4</td><td>Fluctuations autour de la moyenne à l'équilibre</td><td>124</td></tr><tr><td>9.5</td><td>Quand reverra-t-on le vide?</td><td>125</td></tr><tr><td>9.6</td><td>Pour aller plus loin</td><td>127</td></tr><tr><td>10</td><td>Records, extrêmes, et recrutements</td><td>129</td></tr><tr><td>10.1</td><td>Élitisme</td><td>129</td></tr><tr><td>10.2</td><td>Au-dessus de la moyenne</td><td>132</td></tr><tr><td>10.3</td><td>Cas de la loi exponentielle</td><td>133</td></tr><tr><td>10.4</td><td>Cas de la loi de Pareto</td><td>136</td></tr><tr><td>10.5</td><td>Pour aller plus loin</td><td>137</td></tr></tbody></table>
<table><tbody><tr><td>11</td><td>File d'attente M/M/Infini</td><td>141</td></tr><tr><td>11.1</td><td>Lois exponentielles</td><td>143</td></tr><tr><td>11.2</td><td>Temps de demi-vie des clients initiaux</td><td>146</td></tr><tr><td>11.3</td><td>Loi du nombre de clients</td><td>147</td></tr><tr><td>11.4</td><td>Comportement en temps long</td><td>151</td></tr><tr><td>11.5</td><td>Pour aller plus loin</td><td>155</td></tr><tr><td>12</td><td>Modèle de Wright-Fisher</td><td>157</td></tr><tr><td>12.1</td><td>Loi de Hardy-Weinberg</td><td>157</td></tr><tr><td>12.2</td><td>Modèle de Moran</td><td>158</td></tr><tr><td>12.3</td><td>Modèle de Wright-Fisher et fixation</td><td>161</td></tr><tr><td>12.4</td><td>Modèle de Wright-Fisher avec mutations</td><td>166</td></tr><tr><td>12.5</td><td>Modèle de Wright-Fisher avec sélection</td><td>168</td></tr><tr><td>12.6</td><td>Modèle de Cannings</td><td>169</td></tr><tr><td>12.7</td><td>Pour aller plus loin</td><td>172</td></tr><tr><td>13</td><td>Généalogies et coalescence</td><td>173</td></tr><tr><td>13.1</td><td>Modèle généalogique à temps continu</td><td>176</td></tr><tr><td>13.2</td><td>Longueur de l'arbre généalogique</td><td>178</td></tr><tr><td>13.3</td><td>Mutations</td><td>180</td></tr><tr><td>13.4</td><td>Coalescent de Kingman</td><td>183</td></tr><tr><td>13.5</td><td>Pour aller plus loin</td><td>185</td></tr><tr><td>14</td><td>Restaurants chinois</td><td>187</td></tr><tr><td>14.1</td><td>Lois d'Ewens</td><td>189</td></tr><tr><td>14.2</td><td>Nombre de tables</td><td>191</td></tr><tr><td>14.3</td><td>Tables extrêmes</td><td>195</td></tr><tr><td>14.4</td><td>Compléments de combinatoire</td><td>197</td></tr><tr><td>14.5</td><td>Pour aller plus loin</td><td>198</td></tr><tr><td>15</td><td>Renforcement</td><td>201</td></tr><tr><td>15.1</td><td>Urne de Pólya</td><td>201</td></tr><tr><td>15.2</td><td>Graphe de Barabási-Albert</td><td>205</td></tr><tr><td>15.3</td><td>Marche aléatoire renforcée</td><td>208</td></tr><tr><td>15.4</td><td>Théorème de Rubin</td><td>212</td></tr><tr><td>15.5</td><td>Pour aller plus loin</td><td>214</td></tr><tr><td>16</td><td>Percolation</td><td>217</td></tr><tr><td>16.1</td><td>Percolation dans un graphe</td><td>217</td></tr><tr><td>16.2</td><td>Graphe de Bethe (arbre régulier)</td><td>220</td></tr><tr><td>16.3</td><td>Graphe euclidien (grille)</td><td>222</td></tr><tr><td>16.4</td><td>Graphe complet et modèle de Erdős-Rényi</td><td>226</td></tr><tr><td>16.5</td><td>Pour aller plus loin</td><td>228</td></tr></tbody></table>
<table><tr><td>17</td><td>Croissance et fragmentation</td><td>231</td></tr><tr><td>17.1</td><td>Processus TCP window-size en informatique</td><td>231</td></tr><tr><td>17.2</td><td>Intensité des sauts variable selon la position</td><td>238</td></tr><tr><td>17.3</td><td>Branchement et croissance-fragmentation</td><td>239</td></tr><tr><td>17.4</td><td>Pour aller plus loin</td><td>242</td></tr><tr><td>18</td><td>Ruine d'une compagnie d'assurance</td><td>245</td></tr><tr><td>18.1</td><td>Processus de Poisson composé</td><td>247</td></tr><tr><td>18.2</td><td>La ruine est-elle presque sûre?</td><td>248</td></tr><tr><td>18.3</td><td>Expression de la probabilité de ruine</td><td>249</td></tr><tr><td>18.4</td><td>Sinistres exponentiels</td><td>250</td></tr><tr><td>18.5</td><td>Pour aller plus loin</td><td>252</td></tr><tr><td>19</td><td>Polymères dirigés en environnement aléatoire</td><td>253</td></tr><tr><td>19.1</td><td>Modèle et résultats principaux</td><td>253</td></tr><tr><td>19.2</td><td>Fonction de partition normalisée</td><td>257</td></tr><tr><td>19.3</td><td>Borne inférieure en grandes dimensions</td><td>259</td></tr><tr><td>19.4</td><td>Énergie libre moyenne</td><td>261</td></tr><tr><td>19.5</td><td>Borne supérieure sur le paramètre critique</td><td>263</td></tr><tr><td>19.6</td><td>Pour aller plus loin</td><td>265</td></tr><tr><td>20</td><td>Problème du voyageur de commerce</td><td>267</td></tr><tr><td>20.1</td><td>Concentration pour le cas uniforme</td><td>269</td></tr><tr><td>20.2</td><td>Évaluation de la moyenne du cas uniforme</td><td>273</td></tr><tr><td>20.3</td><td>Démonstration du cas uniforme</td><td>277</td></tr><tr><td>20.4</td><td>Pour aller plus loin</td><td>277</td></tr><tr><td>21</td><td>Matrices aléatoires</td><td>279</td></tr><tr><td>21.1</td><td>Théorème de Wigner</td><td>280</td></tr><tr><td>21.2</td><td>Réduction à un cas plus simple</td><td>283</td></tr><tr><td>21.3</td><td>Convergence des moments et convergence étroite</td><td>287</td></tr><tr><td>21.4</td><td>Preuve du théorème de Wigner simplifié</td><td>290</td></tr><tr><td>21.5</td><td>Pour aller plus loin</td><td>294</td></tr><tr><td>22</td><td>Naissances et assassinats</td><td>297</td></tr><tr><td>22.1</td><td>Condition suffisante de stabilité</td><td>299</td></tr><tr><td>22.2</td><td>Condition suffisante d'instabilité</td><td>300</td></tr><tr><td>22.3</td><td>Pour aller plus loin</td><td>303</td></tr><tr><td>23</td><td>Modèle du télégraphe</td><td>305</td></tr><tr><td>23.1</td><td>Aspects markoviens du processus complet</td><td>306</td></tr><tr><td>23.2</td><td>Lien entre équation et processus</td><td>309</td></tr><tr><td>23.3</td><td>Modification ergodique</td><td>310</td></tr><tr><td>23.4</td><td>Pour aller plus loin</td><td>313</td></tr></table>
<table><tbody><tr><td>24</td><td>Problème de Dirichlet</td><td>315</td></tr><tr><td></td><td>24.1 Interprétation probabiliste</td><td>317</td></tr><tr><td></td><td>24.2 Cas de la boule unité</td><td>319</td></tr><tr><td></td><td>24.3 Approches numériques</td><td>320</td></tr><tr><td></td><td>24.4 Demi-plan supérieur : du discret au continu</td><td>321</td></tr><tr><td></td><td>24.5 Récurrence, transience, et fonctions harmoniques</td><td>323</td></tr><tr><td></td><td>24.6 Pour aller plus loin</td><td>324</td></tr><tr><td>25</td><td>Processus d'Ornstein-Uhlenbeck</td><td>327</td></tr><tr><td></td><td>25.1 Premières propriétés</td><td>328</td></tr><tr><td></td><td>25.2 Décomposition spectrale et inégalité de Poincaré</td><td>333</td></tr><tr><td></td><td>25.3 Entropie, couplage, et temps long</td><td>337</td></tr><tr><td></td><td>25.4 Inégalité de Sobolev logarithmique</td><td>340</td></tr><tr><td></td><td>25.5 Pour aller plus loin</td><td>343</td></tr><tr><td>26</td><td>Modèles de diffusion cinétique</td><td>345</td></tr><tr><td></td><td>26.1 Modèle de Langevin</td><td>345</td></tr><tr><td></td><td>26.2 Processus de Langevin confiné</td><td>347</td></tr><tr><td></td><td>26.3 Comportement en temps long du processus confiné</td><td>350</td></tr><tr><td></td><td>26.4 Pour aller plus loin</td><td>356</td></tr><tr><td>27</td><td>Des chaînes de Markov aux processus de diffusion</td><td>359</td></tr><tr><td></td><td>27.1 Paresse et échantillonnage</td><td>359</td></tr><tr><td></td><td>27.2 Convergence d'une chaîne vers une diffusion</td><td>361</td></tr><tr><td></td><td>27.3 Diffusion sur un intervalle</td><td>364</td></tr><tr><td></td><td>27.4 Application aux processus de Wright-Fisher</td><td>366</td></tr><tr><td></td><td>27.5 Fonction de répartition empirique</td><td>370</td></tr><tr><td></td><td>27.6 Schéma d'Euler</td><td>371</td></tr><tr><td></td><td>27.7 Pour aller plus loin</td><td>373</td></tr><tr><td></td><td>Suggestions bibliographiques</td><td>375</td></tr><tr><td></td><td>Littérature</td><td>377</td></tr><tr><td></td><td>Index</td><td>393</td></tr><tr><td></td><td>Principales notations et abréviations</td><td>401</td></tr></tbody></table>
# Pile, face, coupons

**Mots-clés.** Combinatoire; loi discrète; distance en variation totale; loi des petits nombres; convergence abrupte; loi de Gumbel.

**Outils.** Loi des grands nombres; théorème limite central; inégalité de Markov.

## Difficulté. *

Ce chapitre est consacré au jeu de pile ou face et au problème du collectionneur de coupons, deux objets probabilistes importants qu'il est bon de connaître et savoir reconnaître. Ce chapitre contient également une étude de la distance en variation totale pour les mesures de probabilité discrètes.

## 1.1 Jeu de pile ou face

Le jeu de pile ou face consiste en des lancers successifs d'une pièce de monnaie qui donnent à chaque fois soit pile (succès, codé 1) soit face (échec, codé 0). On modélise cela par une suite $(X_n)_{n \ge 1}$ de variables aléatoires indépendantes et identiquement distribuées de loi de Bernoulli $\text{Ber}(p)$ :

$$ \mathbb{P}(X_n = 1) = 1 - \mathbb{P}(X_n = 0) = p \in [0, 1]. $$

Le nombre de succès dans les $n$ premiers lancers

$$ S_n = X_1 + \cdots + X_n $$

est une variable aléatoire à valeurs dans $\{0, 1, \dots, n\}$ qui suit la loi binomiale $\text{Bin}(n, p)$ de taille $n$ et de paramètre $p$, donnée pour tout $k = 0, 1, \dots, n$ par

$$ \mathbb{P}(S_n = k) = \binom{n}{k} p^k (1-p)^{n-k} = \frac{n!}{k!(n-k)!} p^k (1-p)^{n-k}. $$
La moyenne et la variance de $S_n$ sont donnés par

$$E(S_n) = np \quad \text{et} \quad \text{Var}(S_n) = np(1-p).$$

Le temps $T$ du premier succès, qui est aussi le nombre de lancers pour obtenir un premier succès, est donné par

$$T := \inf\{n \ge 1 : X_n = 1\}$$

Si $p > 0$, $T$ suit la loi géométrique $\text{Geo}(p)$ sur $\mathbb{N}^*$ de paramètre $p$ donnée par

$$\mathbb{P}(T = k) = (1-p)^{k-1}p, \quad k \in \mathbb{N}^*.$$

On a $T \equiv \infty$ si $p = 0$ et $\mathbb{P}(T < \infty) = 1$ sinon. De plus

$$\mathbb{E}(T) = \frac{1}{p} \quad \text{et} \quad \text{Var}(T) = \frac{1-p}{p^2}.$$

Le nombre d'échecs avant le premier succès

$$T' := \inf\{n \ge 0 : X_{n+1} = 1\} = T - 1$$

suit la loi géométrique $\text{Geo}_N(p)$ sur $\mathbb{N}$ et de paramètre $p$ donnée par

$$\mathbb{P}(T' = k) = \mathbb{P}(T - 1 = k) = (1-p)^k p, \quad k \in \mathbb{N},$$

et on a

$$\mathbb{E}(T') = \mathbb{E}(T) - 1 = \frac{1-p}{p} \quad \text{et} \quad \text{Var}(T') = \text{Var}(T) = \frac{1-p}{p^2}.$$

Pour tout $r \in \mathbb{N}^*$, le nombre de lancers $T_r$ nécessaires pour obtenir $r$ succès est défini par récurrence par

$$T_1 := T \quad \text{et} \quad T_{r+1} := \inf\{n > T_r : X_n = 1\}.$$

Les variables aléatoires $T_1, T_2 - T_1, T_3 - T_2, \dots$ sont indépendantes et identiquement distribuées de loi géométrique $\text{Geo}(p)$. La variable aléatoire $T_r$ suit la loi de Pascal ou loi binomiale-négative $\text{Geo}(p)^{*r}$. On a pour tout $k \ge r$,

$$\mathbb{P}(T_r = k) = \sum_{\substack{k_1 \ge 1, \dots, k_r \ge 1 \\ k_1 + \dots + k_r = k}} (1-p)^{k_1-1} p \dots (1-p)^{k_r-1} p = (1-p)^{k-r} p^r \binom{k-1}{r-1}$$

et

$$\mathbb{E}(T_r) = r \mathbb{E}(T) = \frac{r}{p} \quad \text{et} \quad \text{Var}(T_r) = r \text{Var}(T) = r \frac{1-p}{p^2}.$$

Le processus de Bernoulli $(S_n)_{n \ge 0}$ a des trajectoires constantes par morceaux, avec des sauts d'amplitude +1, et les temps de saut sont donnés par $(T_r)_{r \ge 1}$ (temps inter-sauts i.i.d. géométriques). Il constitue le processus de
comptage de tops espacés par des durées indépendantes de même loi géométrique, analogue discret du *processus de Poisson*. Comme $S_n$ est une somme de variables indépendantes, $(S_n)_{n \ge 0}$ est une chaîne de Markov sur $\mathbb{N}$ de noyau $\mathbf{P}(x, y) = p \mathbf{1}_{y=x+1} + (1-p) \mathbf{1}_{y=x}$, et $(S_n - np)_{n \ge 0}$ est une martingale.

Par la loi des grands nombres (LGN) et le théorème limite central (TLC)

$$ \frac{S_n}{n} \xrightarrow{n \to \infty} p \quad \text{et} \quad \frac{\sqrt{n}}{\sqrt{p(1-p)}} \left( \frac{S_n}{n} - p \right) \xrightarrow{n \to \infty} \mathcal{N}(0, 1). $$

Cela permet notamment de construire un intervalle de confiance asymptotique pour $p$ appelé *intervalle de Wald*, qui est cependant peu précis.

**Remarque 1.1** (Intervalle de Clopper-Pearson). Il est également possible de confectionner des intervalles de confiance pour $p$ non asymptotiques, comme celui de Clopper-Pearson par exemple, basé sur la correspondance Beta-binomiale. Soit $U_1, \dots, U_n$ des v.a.r. i.i.d. de loi uniforme sur $[0, 1]$. Notons $U_{(1,n)} \le \dots \le U_{(n,n)}$ leur réordonnement croissant. Alors pour tout $k = 1, \dots, n$ la v.a.r. $U_{(k,n)}$ suit la loi Beta$(k, n-k+1)$ sur $[0, 1]$ de densité

$$ t \in [0, 1] \mapsto \frac{t^{k-1}(1-t)^{n-k}}{\text{Beta}(k, n-k+1)}, \quad \text{où } \text{Beta}(a, b) := \int_0^1 s^{a-1}(1-s)^{b-1} ds, $$

et

$$ \mathbf{P}(S_n \ge k) = \mathbf{P}(\mathbf{1}_{\{U_1 \le p\}} + \dots + \mathbf{1}_{\{U_n \le p\}} \ge k) = \mathbf{P}(U_{(k,n)} \le p). $$

On déduit de cette identité une expression exacte de la probabilité que $S_n$ appartienne à un intervalle donné. Notons que comme $S_n$ est discrète, ses quantiles sont aussi discrets, ce qui empêche de fabriquer un intervalle exact de niveau $\alpha \in [0, 1]$ arbitraire, et suggère de procéder à un lissage.

**Remarque 1.2** (Motifs répétés et lois du zéro-un). Lorsque $0 < p < 1$, le lemme de Borel-Cantelli (cas indépendant) entraîne que toute suite finie de 0 et de 1 apparaît presque sûrement une infinité de fois dans la suite $X_1, X_2, \dots$. L'indépendance est capitale. Un singe éternel tapant sur un clavier finira toujours par écrire les œuvres complètes de William Shakespeare ! Alternativement, on peut déduire ce résultat de la nature géométrique du temps d'apparition du premier succès dans un jeu de pile ou face obtenu en découplant le jeu de pile ou face en blocs successifs de même longueur que la chaîne recherchée.

**Remarque 1.3** (Jeu de pile ou face et loi uniforme sur $[0, 1]$). Si $U$ est une variable aléatoire sur $[0, 1]$ et si $U = \sum_{n=1}^{\infty} b_n 2^{-n}$ est son écriture en base 2, alors $U$ suit la loi uniforme sur $[0, 1]$ si et seulement si les bits $(b_n)_{n \ge 1}$ de son écriture en base 2 sont des v.a.r. i.i.d. de Bernoulli de paramètre $1/2$.

**Remarque 1.4** (Algorithme de débiaisage de von Neumann). Soit $(X_n)_{n \ge 1}$ une suite de variables aléatoires de Bernoulli indépendantes et de paramètre $0 < p < 1$ inconnu. On fabrique la suite $(Y_n)_{n \ge 1}$ de variables aléatoires indépendantes et de même loi sur $\{0, 1, 2\}$ comme suit
$$
\underbrace{X_1 X_2}_{Y_1} \underbrace{X_3 X_4}_{Y_2} \cdots
$$

en posant $Y_n = 0$ si $(X_{2n-1}, X_{2n}) = (0,1)$, $Y_n = 1$ si $(X_{2n-1}, X_{2n}) = (1,0)$, et $Y_n = 2$ sinon. La suite $(Z_n)_{n \ge 1}$ obtenue à partir de $(Y_n)_{n \ge 1}$ en effaçant les 2 est constituée de variables aléatoires de Bernoulli indépendantes de paramètre 1/2. La production de chaque terme de la suite $(Z_n)_{n \ge 1}$ nécessite un nombre aléatoire géométrique de termes de la suite $(X_n)_{n \ge 1}$.

1.2 Approximation binomiale-gaussienne

Soit $(X_n)_{n \ge 1}$ des v.a.r. i.i.d. de moyenne $m$ et variance $0 < \sigma^2 < \infty$, et
$S_n = X_1 + \dots + X_n$. Le théorème limite central indique que pour tout $t \in \mathbb{R}$,

$$
\lim_{n \to \infty} \mathbb{P} \left( \frac{S_n - nm}{\sqrt{n\sigma}} \le t \right) = \int_{-\infty}^{t} \frac{1}{\sqrt{2\pi}} e^{-\frac{x^2}{2}} dx.
$$

Le théorème limite central de Berry-Esseen raffine ce résultat asymptotique en
fournissant une borne quantitative uniforme : si $X_1, X_2, \dots$ sont de Bernoulli
de paramètre $p \in ]0, 1[$, on a $m := \mathbb{E}(X_1) = p$, $\sigma^2 := \mathbb{E}((X-m)^2) = p(1-p)$,
$\tau^3 := \mathbb{E}(|X_1 - m|^3) = p(1-p)(1-2p(1-p))$, et

$$
\sup_{t \in \mathbb{R}} \left| \mathbb{P} \left( S_n \le \sqrt{np(1-p)}t + np \right) - \int_{-\infty}^{t} \frac{e^{-\frac{x^2}{2}}}{\sqrt{2\pi}} dx \right|
$$
$$
\le \frac{\tau^3}{\sqrt{n}\sigma^3} = \frac{1 - 2p(1-p)}{\sqrt{p(1-p)}\sqrt{n}}.
$$

Cette approximation de la loi binomiale par la loi gaussienne est d'autant
meilleure que $(1 - 2p(1 - p)) / \sqrt{np(1 - p)}$ est petit. À n fixé, cette borne est
minimale pour p = 1/2 mais explose quand p se rapproche de 0 ou de 1. Pour
ces régimes extrêmes, il est plus approprié d'utiliser une approximation par
la loi de Poisson, abordée dans la section 1.4.

Lorsque $X_1, X_2, \dots$ sont des variables de Bernoulli de paramètre $p \in ]0, 1[$, le TLC suggère d'approcher la loi binomiale Bin($n, p$) de $S_n$ par la loi gaussienne $N(nm, n\sigma^2)$ lorsque $n$ est grand. Le théorème limite central de de Moivre et Laplace précise que pour tous $-\infty < a < b < +\infty$,

$$
\lim_{n \to \infty} \sqrt{n} \sup_{k \in I_n(a,b)} \left| \mathbb{P}(S_n = k) - \frac{\exp\left(-\frac{(k-np)^2}{2np(1-p)}\right)}{\sqrt{2\pi np(1-p)}} \right| = 0
$$

où

$$
I_n(a, b) = \left\{ 0 \le k \le n : \frac{k - np}{\sqrt{np(1-p)}} \in [a, b] \right\},
$$
<figure><img src="image_5.png" /><figcaption>Fig. 1.1. Lois binomiales de même taille, pour trois valeurs du second paramètre, illustrant la pertinence de l'approximation de la loi binomiale par une loi gaussienne et par une loi de Poisson selon les cas.</figcaption></figure>

qui redonne le TLC par intégration :

$$ \lim_{n \to \infty} \mathbb{P} \left( \frac{S_n - np}{\sqrt{np(1-p)}} \in [a, b] \right) = \frac{1}{\sqrt{2\pi}} \int_a^b e^{-\frac{x^2}{2}} dx. $$

## 1.3 Distance en variation totale

Dans toute cette section, $E$ est un ensemble au plus dénombrable muni de la topologie et de la tribu discrètes $\mathcal{P}(E)$. L'ensemble des lois sur $E$ est un espace métrique complet pour la distance en variation totale

$$ d_{VT}(\mu, \nu) := \sup_{A \subset E} |\mu(A) - \nu(A)|. $$
Notons que $d_{VT}(\mu, \nu) = \|\mu - \nu\|_{VT}$ où $\|\eta\|_{VT} := \sup_{A \subset E} |\eta(A)|$ pour toute mesure signée $\eta$ de masse finie sur $E$. On a $0 \le d_{VT}(\mu, \nu) \le 1$ car le diamètre de $[0, 1]$ est 1. De plus $d_{VT}(\mu, \nu) = 1$ si $\mu$ et $\nu$ ont des supports disjoints.

**Théorème 1.5** (Autres expressions). Si $\mu$ et $\nu$ sont des lois sur $E$ alors<fnref n="1" />

$$d_{VT}(\mu, \nu) = \frac{1}{2} \sup_{f:E \to [-1,1]} \left| \int f d\mu - \int f d\nu \right| = \frac{1}{2} \sum_{x \in E} |\mu(x) - \nu(x)|.$$

De plus, le supremum dans la définition de $d_{VT}(\cdot, \cdot)$ est atteint pour l'ensemble

$$A_* = \{x \in E : \mu(x) \ge \nu(x)\},$$

et il est atteint dans l'expression variationnelle fonctionnelle de $d_{VT}(\cdot, \cdot)$ pour

$$f = \mathbb{1}_{A_*} - \mathbb{1}_{A_*^c}.$$

**Démonstration.** La seconde égalité provient de l'inégalité

$$\left| \int f d\mu - \int f d\nu \right| \le \sum_{x \in E} |f(x)| |\mu(x) - \nu(x)| \le \sup_{x \in E} |f(x)| \sum_{x \in E} |\mu(x) - \nu(x)|$$

qui est saturée pour $f = \mathbb{1}_{A_*} - \mathbb{1}_{A_*^c}$. Pour la première égalité, on écrit

$$|\mu(A) - \nu(A)| = \frac{1}{2} \left| \int f_A d\mu - \int f_A d\nu \right|$$

où $f = \mathbb{1}_A - \mathbb{1}_{A^c}$, ce qui donne

$$|\mu(A) - \nu(A)| \le \frac{1}{2} \sup_{f:E \to [-1,1]} \left| \int f d\mu - \int f d\nu \right| = \frac{1}{2} \sum_{x \in E} |\mu(x) - \nu(x)|$$

qui est saturée pour $A = A_*$ car, par définition de $A_*$,

$$\begin{aligned} 2|\mu(A_*) - \nu(A_*)| &= \mu(A_*) - \nu(A_*) + \nu(A_*^c) - \mu(A_*^c) \\ &= \sum_{x \in A_*} |\mu(x) - \nu(x)| + \sum_{x \in A_*^c} |\mu(x) - \nu(x)|. \end{aligned}$$

□

**Théorème 1.6** (Convergence en loi). Si $(X_n)_{n \ge 1}$ sont des variables aléatoires sur $E$ et si $\mu_n$ désigne la loi de $X_n$, alors pour toute loi $\mu$ sur $E$, les propriétés suivantes sont équivalentes :

1. $\lim_{n \to \infty} \int f d\mu_n = \int f d\mu$ pour toute fonction bornée $f : E \to \mathbb{R}$;

2. $\lim_{n \to \infty} \mu_n(x) = \mu(x)$ pour tout $x \in E$;

<footnote n="1">1. En particulier on a $2\|\cdot\|_{VT} = \|\cdot\|_{\ell^1(E, \mathbb{R})}$.</footnote>
3. $\lim_{n \to \infty} d_{VT}(\mu_n, \mu) = 0$.

Lorsqu'elles ont lieu on dit que $(X_n)$ converge en loi vers $\mu$ quand $n \to \infty$.

Toute fonction $E \to \mathbb{R}$ est continue pour la topologie discrète sur $E$.

*Démonstration.* Pour déduire 1. de 3. il suffit d'utiliser l'expression variationnelle fonctionnelle de $d_{VT}(\cdot, \cdot)$. Pour déduire 2. de 1. on peut prendre $f = 1_{\{x\}}$. Pour déduire 3. de 2. on observe que pour tout $A \subset E$,

$$ \sum_{x \in E} |\mu_n(x) - \mu(x)| = \sum_{x \in A} |\mu_n(x) - \mu(x)| + \sum_{x \in A^c} |\mu_n(x) - \mu(x)|. $$

Grâce à 2., si $A$ est fini, alors pour tout $\varepsilon > 0$, il existe un entier $N = N(A, \varepsilon)$ tel que le premier terme du membre de droite est majoré par $\varepsilon$ pour tout $n \ge N$. Le second terme du membre de droite peut se contrôler comme suit :

$$ \sum_{x \in A^c} |\mu_n(x) - \mu(x)| \le \sum_{x \in A^c} \mu_n(x) + \sum_{x \in A^c} \mu(x). $$

Puisqu'on a

$$ \sum_{x \in A^c} \mu_n(x) = \sum_{x \in A} \mu(x) - \sum_{x \in A} \mu_n(x) + \sum_{x \in A^c} \mu(x), $$

on obtient

$$ \sum_{x \in A^c} |\mu_n(x) - \mu(x)| \le \sum_{x \in A} |\mu_n(x) - \mu(x)| + 2 \sum_{x \in A^c} \mu(x). $$

Puisque $\mu \in \mathcal{P}$, pour tout $\varepsilon' > 0$, on peut choisir $A$ fini tel que $\mu(A^c) \le \varepsilon'$. Ainsi, on obtient

$$ \lim_{n \to \infty} \sum_{x \in E} |\mu_n(x) - \mu(x)| = 0, $$

qui n'est rien d'autre que 3. d'après le théorème 1.5. $\square$

**Remarque 1.7** (Dispersion à l'infini). Si $(\mu_n)_{n \ge 1}$ sont des lois sur $E$ et $\mu(x) := \lim_{n \to \infty} \mu_n(x)$ alors $\mu$ n'est pas forcément une loi, sauf si $E$ est fini. En effet, lorsque $E$ est infini, il peut se produire un phénomène de dispersion de masse à l'infini. Un contre-exemple est fourni par $E = \mathbb{N}$ et $\mu_n$ qui affecte la masse $1/n$ aux singletons $\{1\}, \dots, \{n\}$, ce qui donne $\mu$ identiquement nulle.

**Théorème 1.8** (Minimum). Si $\mu$ et $\nu$ sont des lois sur $E$ alors

$$ d_{VT}(\mu, \nu) = 1 - \sum_{x \in E} (\mu(x) \wedge \nu(x)). $$

En particulier, $d_{VT}(\mu, \nu) = 1$ ssi $\mu$ et $\nu$ ont des supports disjoints.
*Démonstration.* Rappelons que $a \wedge b = \min(a, b)$. Il suffit d'écrire

$$ \sum_{x \in E} (\mu(x) \wedge \nu(x)) = \frac{1}{2} \sum_{x \in E} (\mu(x) + \nu(x) - |\mu(x) - \nu(x)|) = 1 - d_{\text{VT}}(\mu, \nu). $$

□

**Théorème 1.9 (Couplage).** Si $\mu$ et $\nu$ sont des lois sur $E$ alors

$$ d_{\text{VT}}(\mu, \nu) = \inf_{(X,Y)} \mathbb{P}(X \neq Y) $$

où l'infimum porte sur les couples de variables aléatoires sur $E \times E$ de lois marginales $\mu$ et $\nu$. De plus, il existe un couple de ce type pour lequel l'égalité est atteinte c'est-à-dire que l'infimum est un minimum.

Le théorème 1.9 est souvent utilisé de la manière suivante : on construit explicitement grâce au contexte un couple $(X, Y)$ de variables aléatoires tel que $X \sim \mu$ et $Y \sim \nu$, et on en déduit que $d_{\text{VT}}(\mu, \nu) \le \mathbb{P}(X \neq Y)$.

*Démonstration.* Soit $(X, Y)$ un couple de v.a. sur $E \times E$ de lois marginales $\mu$ et $\nu$. Comme $\mathbb{P}(X = x, Y = x) \le \mu(x) \wedge \nu(x)$ pour tout $x \in E$,

$$ 1 - d_{\text{VT}}(\mu, \nu) = \sum_{x \in E} (\mu(x) \wedge \nu(x)) \ge \sum_{x \in E} \mathbb{P}(X = x, Y = x) = \mathbb{P}(X = Y). $$

Il suffit donc de construire un couple $(X, Y)$ pour lequel l'égalité est atteinte. Posons $p = 1 - d_{\text{VT}}(\mu, \nu) \in [0, 1]$ et distinguons trois cas.

— Cas où $p = 0$. On prend $(X, Y)$ avec $X$ et $Y$ indépendantes de lois respectives $\mu$ et $\nu$. Puisque $d_{\text{VT}}(\mu, \nu) = 1$, $\mu$ et $\nu$ ont des supports disjoints, d'où $\mathbb{P}(X = Y) = \sum_{x \in E} \mu(x)\nu(x) = 0$;

— Cas où $p = 1$. Alors $d_{\text{VT}}(\mu, \nu) = 0$, d'où $\mu = \nu$. On prend $(X, Y)$ où $X \sim \mu$ et $Y = X$;

— Cas où $0 < p < 1$. Soit $U, V, W$ des variables aléatoires de lois

$$ p^{-1}(\mu \wedge \nu), \quad (1-p)^{-1}(\mu - (\mu \wedge \nu)), \quad (1-p)^{-1}(\nu - (\mu \wedge \nu)). $$

Notons que $p = \sum_{x \in E} (\mu(x) \wedge \nu(x))$ (théorème 1.8). Soit $B$ une v.a. de loi de Bernoulli $\text{Ber}(p)$ indépendante du triplet $(U, V, W)$. Posons $(X, Y) = (U, U)$ si $B = 1$ et $(X, Y) = (V, W)$ si $B = 0$. On a alors $X \sim \mu$ et $Y \sim \nu$, et puisque les lois de $V$ et $W$ ont des supports disjoints, on a $\mathbb{P}(V = W) = 0$, et donc $\mathbb{P}(X = Y) = \mathbb{P}(B = 1) = p$. □

## 1.4 Approximation binomiale-Poisson

Si $S_n$ suit la loi binomiale $\text{Bin}(n, p)$ alors pour tout $k \in \mathbb{N}$, on a,
$$
P(S_n = k) - e^{-np} \frac{(np)^k}{k!} = \left( \frac{n}{n(1-p)} \cdots \frac{n-k+1}{n(1-p)} (1-p)^n - e^{-np} \right) \frac{(np)^k}{k!}.
$$

Ceci montre que si $p$ dépend de $n$ avec $\lim_{n \to \infty} np = \lambda$ alors la loi de $S_n$ tend vers Poi($\lambda$). La distance en variation totale permet de quantifier cette convergence en loi : l'inégalité de Le Cam du théorème 1.10 ci-dessous donne

$$
\sum_{k=0}^{\infty} \left| \mathbb{P}(S_n = k) - e^{-np} \frac{(np)^k}{k!} \right| \le 2np^2,
$$

utile si np² est petit. Si par exemple p = λ/n alors np = λ et np² = λ²/n.

**Théorème 1.10** (Inégalité de Le Cam). Soient $X_1, \dots, X_n$ des variables aléatoires indépendantes de lois de Bernoulli $\text{Ber}(p_1), \dots, \text{Ber}(p_n)$. Soit $\mu_n$ la loi de $S_n = X_1 + \dots + X_n$ et soit $\nu_n = \text{Poi}(p_1 + \dots + p_n)$ la loi de Poisson de même moyenne que $S_n$. Alors on a

$$
d_{VT}(\mu_n, \nu_n) \le p_1^2 + \dots + p_n^2.
$$

Démonstration. On établit par récurrence sur $n$ que si $\alpha_1, \dots, \alpha_n$ et $\beta_1, \dots, \beta_n$ sont des lois de probabilité sur $\mathbb{N}$ alors on a l'inégalité sous-additive

$$
d_{\mathrm{VT}}(\alpha_1 * \dots * \alpha_n, \beta_1 * \dots * \beta_n) \le d_{\mathrm{VT}}(\alpha_1, \beta_1) + \dots + d_{\mathrm{VT}}(\alpha_n, \beta_n).
$$

On établit ensuite que $d_{\text{VT}}(\text{Ber}(p), \text{Poi}(p)) \le p^2$, et on exploite le semi-groupe de convolution des lois de Poisson : $\text{Poi}(a) * \text{Poi}(b) = \text{Poi}(a + b)$. $\square$

$$
\text{L'inégalité } \ell^2 - \ell^1 - \ell^\infty \text{ suivante}
$$

$$
p_1^2 + \cdots + p_n^2 \le (p_1 + \cdots + p_n) \max_{1 \le k \le n} p_k
$$

permet de retrouver la loi des petits nombres : si $(X_{n,k})_{1\le k\le n}$ est un tableau
triangulaire de variables aléatoires indépendantes de lois de Bernoulli avec
$X_{n,k} \sim \text{Ber}(p_{n,k})$ pour tous $n \ge k \ge 1$, et si

$$
\lim_{n \to \infty} p_{n,1} + \dots + p_{n,n} = \lambda \quad \text{et} \quad \lim_{n \to \infty} \max_{1 \le k \le n} p_{n,k} = 0,
$$

alors $X_{n,1} + \cdots + X_{n,n}$ converge en loi vers $Poi(\lambda)$ quand $n \to \infty$.

1.5 Problème du collectionneur de coupons

Le problème du *collectionneur de coupons* est dans la même boîte à outils que le jeu de pile ou face ou le jeu de dé, auquel il est intimement relié. Un grand nombre de situations concrètes cachent un collectionneur de coupons ou une de ses variantes. Nous nous limitons ici à sa version la plus simple.
Il faut jouer un nombre de fois (aléatoire) géométrique à pile ou face pour voir apparaître les deux côtés de la pièce. Si on remplace la pièce de monnaie par un dé à $r \ge 2$ faces, combien de fois faut-il lancer le dé pour voir apparaître les $r$ faces différentes ? On modélise cela, pour un entier fixé $r \ge 2$, en considérant la variable aléatoire

$$ 
\begin{aligned}
T &:= \min\{n \ge 1 : \{X_1, \dots, X_n\} = \{1, \dots, r\}\} \\
&= \min\{n \ge 1 : \text{card}\{X_1, \dots, X_n\} = r\}
\end{aligned}
$$

où $(X_n)_{n \ge 1}$ est une suite de variables aléatoires i.i.d. de loi uniforme sur $\{1, \dots, r\}$. La variable aléatoire $T$ est le premier instant où les $r$ faces du dé sont apparues. Ce temps dépend bien entendu de $r$ mais, par souci de simplicité, nous omettrons cette dépendance dans la notation. Le nom collectionneur de coupons provient des coupons à collectionner présents dans certains paquets de céréales.

**Théorème 1.11 (Combinatoire).** On a $T \ge r$, et pour tout $n \ge r$,

$$ \mathbb{P}(T = n) = \frac{r!}{r^n} \binom{n-1}{r-1} $$

où la notation en accolades désigne le nombre de Stirling de seconde espèce, qui est le nom donné en combinatoire au nombre de manières de partitionner un ensemble à $n-1$ éléments en $r-1$ sous-ensembles non vides.

**Démonstration.** On a $X_T \notin \{X_1, \dots, X_{T-1}\}$ car le coupon qui termine la collection n'a forcément jamais été vu auparavant. Si on fixe $n \ge r$, l'événement $\{T = n\}$ correspond à choisir le type du dernier coupon puis à répartir les $n-1$ coupons restants sur les $r-1$ types restants. Le résultat désiré en découle car la loi des types est uniforme. $\square$

Bien qu'explicite, le théorème 1.11 n'est malgré tout pas très parlant. Le résultat intuitif suivant va beaucoup nous aider à étudier la variable $T$.

**Lemme 1.12 (Décomposition).** On a $T = G_1 + \dots + G_r$ où $G_1, \dots, G_r$ sont des variables aléatoires indépendantes avec

$$ G_i \sim \text{Geo}(\pi_i), \quad \pi_i := \frac{r-i+1}{r}, \quad 1 \le i \le r. $$

En particulier, on a $\mathbb{P}(T < \infty) = 1$, et de plus

$$ \mathbb{E}(T) = r(\log(r) + \gamma) + o_{r \to \infty}(r) \quad \text{et} \quad \text{Var}(T) = \frac{\pi^2}{6}r^2 + o_{r \to \infty}(r^2), $$

où $\gamma = \lim_{n \to \infty} \left( \sum_{i=1}^{n} \frac{1}{i} - \log(n) \right) \approx 0.577$ est la constante d'Euler.
Démonstration. On pose $G_1 \equiv 1$ et pour tout $1 < i \le r$,

$$
G_i = \min\{n \ge 1 : X_{G_{i-1}+n} \notin \{X_1, \dots, X_{G_{i-1}}\}\}.
$$

On a $\text{card}(\{X_1, \dots, X_{G_i}\}) = i$ pour tout $1 \le i \le n$. Les variables aléatoires $G_1, G_1+G_2, \dots, G_i + \dots + G_r$ sont les temps d'apparition des $r$ premiers succès dans un jeu de pile ou face spécial dans lequel la probabilité de gagner change après chaque succès : cette probabilité vaut successivement

$$
\pi_1 = 1, \pi_2 = \frac{r-1}{r}, \pi_3 = \frac{r-2}{r}, \dots, \pi_r = \frac{1}{r}.
$$

La décroissance de cette suite traduit le fait qu'il est de plus en plus difficile
d'obtenir un coupon d'un nouveau type au fil de la collection.

Calculons à présent les moments de T. La linéarité de l'espérance donne

$$
\begin{align*}
\mathbb{E}(T) &= \sum_{i=1}^{r} \mathbb{E}(G_i) = \sum_{i=1}^{r} \frac{1}{\pi_i} \\
&= \sum_{i=1}^{r} \frac{r}{r-i+1} = r \sum_{i=1}^{r} \frac{1}{i} = r(\log(r) + \gamma + o(1)).
\end{align*}
$$

D'autre part, l'indépendance des v.a. $G_1, \dots, G_r$ (exercice !) donne

$$
\begin{align*}
\mathrm{Var}(T) &= \sum_{i=1}^{r} \mathrm{Var}(G_i) = \sum_{i=1}^{r} \frac{1 - \pi_i}{\pi_i^2} \\
&= r \sum_{i=1}^{r-1} \frac{r-i}{i^2} = \frac{\pi^2}{6} r^2 - r(\log(r) + \gamma) + o(r^2).
\end{align*}
$$

I

**Théorème 1.13** (Queue de distribution). *Pour tout $n \ge 1$,*

$$
\mathbb{P}(T > n) = \sum_{k=1}^{r} (-1)^{k-1} \binom{r}{k} \left(1 - \frac{k}{r}\right)^n .
$$

Démonstration. On a

$$
\{T > n\} = E_{n,1} \cup \dots \cup E_{n,r} \quad \text{où} \quad E_{n,i} := \{X_1 \neq i, \dots, X_n \neq i\}.
$$

Si $i_1, \dots, i_k \in \{1, \dots, r\}$ sont deux à deux distincts, alors, en notant

$$
R = \{1, \dots, r\} \setminus \{i_1, \dots, i_k\},
$$

on a

$$
\mathbb{P}(E_{n,i_1} \cap \dots \cap E_{n,i_k}) = \mathbb{P}(X_1 \in R) \dots \mathbb{P}(X_n \in R)
$$
$$= \left( \frac{r-k}{r} \right)^n = \left( 1 - \frac{k}{r} \right)^n.$$

On utilise enfin le principe d'inclusion-exclusion ou crible de Poincaré<fnref n="2" />. □

Il est délicat de déduire le comportement de la queue de T en fonction de n et r à partir du théorème 1.13 en raison de l'alternance des signes.

**Théorème 1.14 (Déviation).** Pour tout réel $t > 0$,

$$\mathbb{P}(T > rt + r \log(r)) = \mathbb{P}\left(\frac{T - r \log(r)}{r} > t\right) \le e^{-t+\varepsilon_r}$$

$$où \varepsilon_r = (rt + r \log(r) - \lfloor rt + r \log(r) \rfloor)/r \in [0, 1/r[$$

*Démonstration.* Pour tout entier $n \ge 1$, on peut écrire

$$\mathbb{P}(T > n) = \mathbb{P}(\cup_{i=1}^{r} E_{n,i}) \le \sum_{i=1}^{r} \mathbb{P}(E_{n,i}) \quad \text{où } E_{n,i} := \{X_1 \ne i, \dots, X_n \ne i\}.$$

$$\text{Comme } \mathbb{P}(E_{n,i}) = (1 - 1/r)^n \le e^{-n/r}, \text{ on choisit } n = \lfloor rt + r \log(r) \rfloor. \quad \square$$

Pour $\alpha > 0$ et $r$ fixés, on peut choisir $t$ assez grand pour que $e^{-t+\varepsilon_r} \le \alpha$, par exemple $t = -\log(\alpha) + 1/r$, ce qui donne l'intervalle de prédiction non asymptotique $[r, r \log(r) - r \log(\alpha) + 1]$ de niveau $1 - \alpha$ pour $T$.

**Théorème 1.15 (Comportement asymptotique).**

$$\frac{T}{r \log(r)} \xrightarrow{P} 1.$$

*Démonstration.* Fixons $\varepsilon > 0$. Par l'inégalité de Markov et le lemme 1.12,

$$\begin{align*}
\mathbb{P}\left(\left|\frac{T}{r \log(r)} - 1\right| > \varepsilon\right) &\le \frac{\mathrm{E}((T - r \log(r))^2)}{\varepsilon^2 r^2 \log(r)^2} \\
&= \frac{\mathrm{Var}(T) + (\mathrm{E}(T) - r \log(r))^2}{\varepsilon^2 r^2 \log(r)^2} \\
&= \mathcal{O}\left(\frac{1}{\log(r)^2}\right).
\end{align*}$$

□

Il s'agit d'une preuve par *méthode du second moment*. Dans le même esprit, une méthode du quatrième moment est utilisée pour le théorème 11.6.

La borne établie dans la preuve du théorème précédent n'est pas sommable en $r$ et ne permet donc pas de démontrer une convergence presque sûre en utilisant le lemme de Borel-Cantelli, qui n'aurait de sens qu'avec un espace de

<footnote n="2">2. $\mathbb{P}(\cup_{k=1}^n A_k) = \sum_{j=1}^n (-1)^{j+1} \sum_{k_1 < \dots < k_j} \mathbb{P}(A_{k_1} \cap \dots \cap A_{k_j})$.</footnote>
probabilité unique valable pour tout r. D'autre part, la borne établie permet
d'obtenir un intervalle de prédiction non asymptotique : pour α = 0.05, r fixé,
et t bien choisi, on a $P(|T - r \log(r)|/r > t) = O(1/t^2) = \alpha$. L'intervalle de
prédiction est de largeur $2rt$, et se dégrade quand t croît ($\alpha$ diminue).

Le théorème suivant affirme que les fluctuations asymptotiques dans la
convergence précédente suivent une loi de Gumbel.

**Théorème 1.16** (Fluctuations asymptotiques). On a

$$
\frac{T - r \log(r)}{r} = \log(r) \left( \frac{T}{r \log(r)} - 1 \right) \xrightarrow{r \to \infty} \text{Gumbel}
$$

où la loi de Gumbel a pour fonction de répartition $t \in \mathbb{R} \mapsto e^{-e^{-t}}$.

La figure 1.2 illustre ce résultat.

<figure><img src="image_6.png" /><figcaption>**Fig. 1.2.** Approximations de la queue de distribution de la variable aléatoire *T* par
celle de *r* log(*r*) + *r*G où *G* suit la loi de Gumbel en vertu du théorème 1.16, ainsi
que par une méthode de Monte-Carlo avec *N* tirages en utilisant la représentation
de *T* en somme de variables aléatoires géométriques indépendantes.</figcaption></figure>

Démonstration. Il suffit d'établir que pour tout $t \in \mathbb{R}$ on a
$$
\lim_{r \to \infty} \mathbb{P}(T > r \log(r) + tr) = S(t) := 1 - e^{-e^{-t}}.
$$

Fixons $t \in \mathbb{R}$ et supposons que $r$ est assez grand pour que $r \log(r) + tr > r$.
Introduisons l'entier $n_{t,r} = \lfloor r \log(r) + tr \rfloor$. Le théorème 1.13 donne

$$
\mathbb{P}(T > r \log(r) + tr) = \mathbb{P}(T > n_{t,r}) = \sum_{k=1}^{r} (-1)^{k-1} \binom{r}{k} \left(1 - \frac{k}{r}\right)^{n_{t,r}}.
$$

Comme $\binom{r}{k} \le r^k/k!$ et $1-u \le e^{-u}$ pour tout $u \ge 0$, on a

$$
\binom{r}{k} \left(1 - \frac{k}{r}\right)^{n_{t,r}} \underset{r \to \infty}{\le} \frac{e^{-tk}}{k!}.
$$

Enfin, par convergence dominée, on obtient

$$
\lim_{r \to \infty} \sum_{k=1}^{r} (-1)^{k-1} \binom{r}{k} \left(1 - \frac{k}{r}\right)^{n_{t,r}} = \sum_{k=1}^{\infty} (-1)^{k-1} \frac{e^{-tk}}{k!} = S(t).
$$

Ceci achève la preuve du théorème. Alternativement, il est possible d'établir
le théorème en utilisant l'approximation exponentielle des lois géométriques.
Posons $H_k := \frac{1}{r} G_{r-k+1}$. Pour tout $k \ge 1$ fixé, la suite $(H_k)_{r \ge k}$ converge en
loi vers la loi exponentielle de paramètre $k$. On dispose de plus de la version
quantitative suivante sur les fonctions caractéristiques : pour tout $t \in \mathbb{R}$ et
tout $k \ge 1$, il existe une constante $C > 0$ telle que pour $r$ assez grand,

$$
|\mathbb{E}(e^{itH_k}) - \mathbb{E}(e^{itE_k})| \le \frac{C}{rk}
$$

où $E_k$ est une v.a.r. de loi exponentielle de paramètre $k$. En utilisant l'inégalité

$$
|a_1 \cdots a_r - b_1 \cdots b_r| \le |a_1 - b_1| + \cdots + |a_r - b_r|, \quad a, b \in \{z \in \mathbb{C} : |z| \le 1\}^r,
$$

il vient, en considérant des variables aléatoires réelles $E_1, \dots, E_r$ indépen-
dantes de lois exponentielles de paramètres respectifs $1, \dots, r$,

$$
|\mathbb{E}(e^{it\frac{T}{r}}) - \mathbb{E}(e^{it(E_1+\dots+E_r)})| \le C \frac{\log(r)}{r}.
$$

Le lemme de Rényi 11.3 indique que $E_1 + \dots + E_r$ a même loi que la variable
aléatoire $\max(F_1, \dots, F_r)$ où $F_1, \dots, F_r$ sont des v.a.r. i.i.d. de loi exponen-
tielle de paramètre 1, puis on utilise la convergence en loi vers la loi de Gumbel
de la suite de v.a.r. $(\max(F_1, \dots, F_r) - \log(r))_{r \ge 1}$.
$\square$

Le théorème 1.16 fournit un intervalle de prédiction asymptotique pour la variable aléatoire $T$ : pour tous réels $b \ge a$,

$$
\lim_{r \to \infty} \mathbb{P}(T \in [r \log(r) + ra, r \log(r) + rb]) = e^{-e^{-b}} - e^{-e^{-a}}.
$$
La loi de Gumbel est très concentrée, et sa fonction de répartition fait apparaître une montée abrupte de 0 à 1. Cela donne un phénomène de seuil<fnref n="3" /> pour la variable aléatoire $T$. La quantité $P(T > n)$ passe abruptement de $\approx 1$ à $\approx 0$ autour de $n = r \log(r)$ si $r \gg 1$ :

**Théorème 1.17** (Convergence abrupte en $n = r \log(r)$). Pour tout réel $c > 0$,

$$P(T > r \log(r) + rc) \le e^{-c+\epsilon_r} \quad \text{où} \quad 0 \le \epsilon_r < 1/r.$$

Si $(c_r)_{r \in \mathbb{N}^*}$ est une suite qui tend vers l'infini, alors

$$\lim_{r \to \infty} P(T > r \log(r) - rc_r) = 1.$$

*Démonstration.* La première majoration provient du théorème 1.14. D'autre part, le théorème 1.16 affirme que $(T - r \log(r))/r$ converge en loi vers la loi de Gumbel quand $r \to \infty$, ce qui donne, grâce au fait que $c_r \to \infty$,

$$P(T > r \log(r) - rc_r) = P\left(\frac{T - r \log(r)}{r} > -c_r\right) \underset{r \to \infty}{\longrightarrow} 1.$$

□

## 1.6 Pour aller plus loin

Notre étude du jeu de pile ou face fait l'impasse sur un certain nombre de propriétés remarquables, comme la loi de l'arc-sinus et les principes d'invariance, abordées dans le livre de William Feller [Fel68, Fel71]. Ce livre contient également une preuve du théorème de Berry-Esseen, à base d'analyse de Fourier. Un joli problème de la plus longue sous-suite commune à deux jeux de pile ou face est étudié dans le livre d'optimisation combinatoire randomisée de Michael Steele [Ste97]. L'article [Ste94] de Michael Steele sur l'approximation par la loi de Poisson est bien éclairant. On trouvera également dans le livre [BHJ92] de Andrew Barbour, Lars Holst, et Svante Janson une version renforcée de l'inégalité de Le Cam, obtenue par Barbour et Eagleson en utilisant la méthode d'intégration par parties de Louis Chen et Charles Stein :

$$d_{VT} (\text{Ber}(p_1) * \dots * \text{Ber}(p_n), \text{Poi}(p_1 + \dots + p_n)) \\ \le (1 - e^{-(p_1+\dots+p_n)}) \frac{p_1^2 + \dots + p_n^2}{p_1 + \dots + p_n}.$$

À titre de comparaison, une version inhomogène du théorème limite central de Berry-Esseen, tirée du livre de William Feller, affirme que si $(X_n)_{n \ge 1}$ sont des variables aléatoires indépendantes alors en notant $S_n = X_1 + \dots + X_n$, $\sigma_k^2 = E(|X_k - E(X_k)|^2)$, $\tau_k^3 = E(|X_k - E(X_k)|^3)$, on a

<footnote n="3">3. « Threshold phenomenon » en anglais.</footnote>
$$
\sup_{x \in \mathbb{R}} \left| \mathbb{P} \left( \frac{S_n - \mathbb{E}(S_n)}{\sqrt{\mathrm{Var}(S_n)}} \le x \right) - \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{x} e^{-\frac{t^2}{2}} dt \right|^2 \le \frac{(\tau_1^3 + \cdots + \tau_n^3)^2}{(\sigma_1^2 + \cdots + \sigma_n^2)^3}.
$$

D'autre part, on peut voir la distance en variation totale $d_{VT}(\cdot, \cdot)$ comme
une *distance de Wasserstein* (couplage). Pour le voir, on observe tout d'abord
que $P(X \neq Y) = E(d(X, Y))$ pour la distance atomique $d(x, y) = \delta_{x \neq y}$, d'où,
en notant $\Pi(\mu, \nu)$ l'ensemble des lois sur $E \times E$ de lois marginales $\mu$ et $\nu$,

$$
d_{VT}(\mu, \nu) = \min_{\pi \in \Pi(\mu, \nu)} \int_{E \times E} d(x, y) d\pi(x, y).
$$

Le problème du collectionneur de coupons est notamment abordé dans le
livre de William Feller [Fel68, Fel71], le livre de Rejeev Motwani et Prabhakar
Raghavan [MR95], et dans les articles de Lars Holst [Hol01] et de Aristides
Doumas et Vassilis Papanicolaou [DP13]. Donald Newman et Lawrence Shepp
on montré dans [NS60] que si on impose que chaque type soit observé m fois,
alors le temps de complétion de la collection vaut en moyenne

$$
r \log(r) + (m-1)r \log(\log(r)) + \mathcal{O}(r).
$$

D'autres variantes se trouvent dans le livre de Claude Bouzitat, Gilles Pagès, Frédérique Petit, et Fabrice Carrance [BPPC99]. Le théorème 1.16 révélant une fluctuation asymptotique de loi de Gumbel a été obtenu par Paul Erdős et Alfréd Rényi [ER61a]. Une analyse du cas non uniforme associé à une probabilité discrète ($p_1, \dots, p_r$) est menée dans un article de Lars Holst [Hol01]. Lorsque $r$ n'est pas connu, on dispose de l'estimateur

$$
\hat{r}_n := \mathrm{card}\{X_1, \dots, X_n\}.
$$

Si $e_1, \dots, e_r$ est la base canonique de $\mathbb{R}^r$ alors le vecteur aléatoire

$$
C_n := (C_{n,1}, \dots, C_{n,r}) := e_{X_1} + \dots + e_{X_n}
$$

de $\mathbb{N}^r$ suit la loi multinomiale de taille $n$ et de paramètre $(p_1, \dots, p_r)$, et on a

$$
\hat{r}_n = \sum_{i=1}^{r} \mathbb{1}_{\{C_{n,i} > 0\}} = r - \sum_{i=1}^{r} \mathbb{1}_{\{C_{n,i} = 0\}}.
$$

En particulier,

$$
E(\hat{r}_n) = r - \sum_{i=1}^{r} \mathbb{P}(C_{n,i} = 0) = r - \sum_{i=1}^{r} (1 - p_i)^n.
$$

Notons enfin que comme les *r* types sont ordonnés, la variable aléatoire
max(*X*₁, ..., *X*ₙ) est un estimateur du bord droit *r* du support {*1*, ..., *r*}.

Le collectionneur de coupons est un cas particulier du problème du recou-
vrement abordé dans l'article [Ald91] de David Aldous, dans le livre de David
Aldous et James Fill [AF01], dans le cours de Amir Dembo [Dem05], et le
livre de David Levin, Yuval Peres, et Elizabeth Wilmer [LPW09] : si $(X_n)_{n\ge 1}$
est une suite de variables aléatoires, pas nécessairement indépendantes ou de
même loi, et prenant leurs valeurs dans un même ensemble fini $E$, alors le
*$temps de recouvrement*^4$ de $E$ est $T := \inf\{n \ge 1 : \{X_1, \dots, X_n\} = E\}$.

<footnote n="4">4. En anglais : *covering time*.</footnote>
<figure><img src="image_7.png" /></figure>
# Marches aléatoires

**Mots-clés.** Marche aléatoire; temps de sortie; ruine du joueur; problème de Dirichlet; fonction harmonique; champ libre gaussien.

**Outils.** Combinatoire; chaîne de Markov; martingale; loi multinomiale; transformée de Fourier; groupe symétrique; collectionneur de coupons.

## Difficulté. *

Les marches aléatoires constituent des objets probabilistes incontour- nables, d'une richesse et d'une diversité surprenante. Ce chapitre en présente quelques aspects simples, en liaison notamment avec le caractère markovien.

## 2.1 Marche aléatoire simple sur la droite

La marche aléatoire simple sur la droite $\mathbb{Z}$ est la suite $(X_n)_{n\ge 0}$ de variables aléatoires définie par la relation récursive (ou autorégressive)

$$X_{n+1} = X_n + \varepsilon_{n+1} = X_0 + \varepsilon_1 + \cdots + \varepsilon_{n+1}$$

pour tout $n \ge 0$, où $(\varepsilon_n)_{n\ge 1}$ est une suite de v.a.r. i.i.d. de loi de Rademacher, indépendante de $X_0$. On pose

$$p := \mathbb{P}(\varepsilon_n = 1) = 1 - \mathbb{P}(\varepsilon_n = -1) \in ]0, 1[.$$

La suite $(X_n)_{n\ge 0}$ est une chaîne de Markov d'espace d'états $\mathbb{Z}$ et de noyau de transition donné pour tous $x, y \in \mathbb{Z}$ par

$$\mathbf{P}(x, y) = p1_{\{y=x+1\}} + (1-p)1_{\{y=x-1\}}$$

et la matrice $\mathbf{P}$ est tridiagonale. Une variable aléatoire $B$ suit la loi de Bernoulli $(1-p)\delta_0 + p\delta_1$ si et seulement si la variable aléatoire $2B-1$ suit la loi de Rademacher $(1-p)\delta_{-1} + p\delta_1$. Ainsi, pour tout $n \ge 0$,

$$\frac{X_n - X_0 + n}{2} \sim \text{Bin}(n, p).$$
<figure><img src="image_8.png" /><figcaption>Fig. 2.1. Trajectoires issues de 0 de la marche aléatoire simple sur $\mathbb{Z}$.</figcaption></figure>

**Théorème 2.1 (Récurrence).** La marche aléatoire simple sur $\mathbb{Z}$ est récurrente nulle si $p = 1/2$ (marche aléatoire simple symétrique) et transitoire si $p \neq 1/2$ (marche aléatoire simple asymétrique).

*Démonstration.* Rappelons qu’un état $x$ est récurrent lorsque la marche issue de $x$ y revient p.s. ou de manière équivalente lorsque cette chaîne visite une infinité de fois $x$. Un critère utile est le suivant : l’état $x$ est récurrent si et seulement si $\sum_n \mathbf{P}^n(x, x) = \infty$. La chaîne est de période 2 et donc $\mathbf{P}^{2n+1}(x, x) = 0$ pour tout $n \ge 0$. Comme la chaîne est irréductible, tous les états ont même nature, et on peut donc se ramener à l’état 0. La formule binomiale donne

$$ \mathbf{P}^{2n}(0,0) = \mathbb{P}(X_{2n} = 0 | X_0 = 0) = \binom{2n}{n} p^n (1-p)^n. $$

La formule de Stirling $n! \sim \sqrt{2\pi n}(n/e)^n$ donne, en notant $\rho = 4p(1-p)$,

$$ \mathbf{P}^{2n}(0,0) \sim \frac{\rho^n}{\sqrt{\pi n}}. $$

À présent, si $p = 1/2$ alors $\rho = 1$ et la chaîne est récurrente tandis que si $p \neq 1/2$ alors $\rho < 1$ et la chaîne est transitoire. Lorsque $p = 1/2$ la mesure de comptage est symétrique (car la matrice $\mathbf{P}$ est symétrique) donc invariante, et comme il ne s'agit pas d'une mesure finie, la chaîne est récurrente nulle.

On peut alternativement traiter le cas $p \neq 1/2$ avec un peu plus d'intuition probabiliste. En effet, la loi forte des grands nombres affirme qu'on a presque
sûrement $X_n = X_0 + n(2p - 1 + o_{n \to \infty}(1))$, donc $X_n \to +\infty$ p.s. si $p > 1/2$ et $X_n \to -\infty$ p.s. si $p < 1/2$, ce qui interdit toute récurrence. $\square$

Le théorème suivant permet d'étudier le problème de la ruine d'un joueur qui gagne 1 Euro avec probabilité $p$ et perd 1 Euro avec probabilité $1-p$. La fortune initiale est $x$ et le joueur quitte le jeu lorsqu'il possède $a < x$ Euros (ruine) ou $b > x$ Euros (gain). On adopte la notation conditionnelle traditionnelle $\mathbb{P}_x(\cdot) := \mathbb{P}(\cdot | X_0 = x)$ et $\mathbb{E}_x(\cdot) = \mathbb{E}(\cdot | X_0 = x)$.

**Théorème 2.2** (Sortie de boîte<fnref n="1" /> ou ruine du joueur). Soient $a < b$ dans $\mathbb{Z}$, et les temps d'arrêt $\tau_a$, $\tau_b$, et $\tau$ définis par

$$ \tau_a = \inf\{n \ge 0 : X_n = a\}, \quad \tau_b = \inf\{n \ge 0 : X_n = b\}, \quad \text{et} \quad \tau = \min(\tau_a, \tau_b). $$

Alors pour tout $x \in [a, b] \cap \mathbb{Z}$, il existe $c > 0$ tel que $\mathbb{E}_x(e^{c\tau}) < \infty$. En particulier $\mathbb{E}_x(\tau) < \infty$ et donc $\mathbb{P}_x(\tau < \infty) = 1$. De plus, en posant $\rho = \frac{1-p}{p}$,

$$ \mathbb{P}_x(X_\tau = a) = \begin{cases} \frac{\rho^b - \rho^x}{\rho^b - \rho^a} & \text{si } p \neq \frac{1}{2}, \\ \frac{b-x}{b-a} & \text{si } p = \frac{1}{2}, \end{cases} $$

et

$$ \mathbb{E}_x(\tau) = \begin{cases} \frac{x-a}{1-2p} - \frac{(b-a) \rho^x - \rho^a}{1-2p \rho^b - \rho^a} & \text{si } p \neq \frac{1}{2}, \\ (b-x)(x-a) & \text{si } p = \frac{1}{2}. \end{cases} $$

Si $p = 1/2$ alors la chaîne est récurrente et visite presque sûrement chaque état une infinité de fois et donc $\mathbb{P}_x(\tau_a < \infty) = 1$ et $\mathbb{P}_x(\tau_b < \infty) = 1$ pour tout $a \le x \le b$. En revanche, si $p \ne 1/2$ alors la chaîne est transitoire et les temps d'atteinte de $a$ ou de $b$ ne sont plus finis presque sûrement (selon la probabilité $p$ et le point de départ $x$). On le voit bien dans les formules du théorème 2.2 en faisant tendre $a$ ou $b$ vers l'infini. Le temps de sortie $\tau$ de $[a, b]$ est identique en loi au temps d'absorption $T$ par $\{a, b\}$ de la chaîne $Y = (Y_n)_{n \ge 0}$ d'espace d'états fini $\{a, \dots, b\}$ de mêmes transitions que $(X_n)_{n \ge 0}$ mais avec absorption en $a$ et $b$. Comme pour $Y$, les états $a$ et $b$ sont récurrents et tous les autres (en nombre fini) transitoires, et comme presque sûrement la chaîne $Y$ ne visite qu'un nombre fini de fois chaque état transitoire, on en déduit que $\mathbb{P}_x(\tau < \infty) = \mathbb{P}_x(T < \infty) = 1$ pour tout $a \le x \le b$.

**Démonstration.** Montrons que $\mathbb{E}_x(\tau) < \infty$ pour tout $a \le x \le b$. Il suffit d'obtenir une majoration géométrique pour la queue de la loi de $\tau$. Il serait possible de procéder par couplage, comme pour le modèle de Wright-Fisher, voir remarque 12.7. Pour tout $a \le x \le b$, il existe un chemin $\ell_x$ de longueur $|\ell_x| \le (b-a)$ qui mène de $x$ à $a$ ou $b$. On a

<footnote n="1">1. Quoi de plus naturel pour un ivrogne modélisé par la marche aléatoire.</footnote>
$$
\begin{align*}
\mathbb{P}_x(\tau > (b-a)) &\le \mathbb{P}(X_{1:|\ell_x|} \ne \ell_x) \\
&= 1 - \mathbb{P}(X_{1:|\ell_x|} = \ell_x) \\
&\le 1 - \min(p, 1-p)^{|\ell_x|}.
\end{align*}
$$

Si $\eta = \max_{a<x<b}(1 - \min(p, 1-p)^{|\ell_x|}) < 1$ alors on obtient, par récurrence,
pour tout $k \ge 1$, en utilisant l'indépendance conditionnelle du passé et du
futur sachant le présent,

$$
\begin{align*}
\mathbb{P}_x(\tau > k(b-a))
&= \sum_{a<y<b} \mathbb{P}_x(\tau > k(b-a), X_{(k-1)(b-a)} = y, \tau > (k-1)(b-a)) \\
&= \sum_{a<y<b} \mathbb{P}_y(\tau > (b-a)) \mathbb{P}_x(X_{(k-1)(b-a)} = y, \tau > (k-1)(b-a)) \\
&\le \eta \mathbb{P}_x(\tau > (k-1)(b-a)) \le \eta \eta^{k-1} = \eta^k.
\end{align*}
$$

Comme $\eta < 1$ on obtient que $\mathbb{E}_x(e^{c\tau}) < \infty$ pour un réel $c > 0$, et en particulier tous les moments de $\tau$ sont finis sous $\mathbb{P}_x$ et $\mathbb{P}_x(\tau < \infty) = 1$. Calculons

$$
r(x) := \mathbb{P}_x(X_\tau = a).
$$

On a pour tout $a < x < b$

$$
\begin{align*}
r(x) &= \mathbb{P}_x(X_\tau = a | X_1 = x+1)p + \mathbb{P}_x(X_\tau = a | X_1 = x-1)(1-p) \\
&= pr(x+1) + (1-p)r(x-1).
\end{align*}
$$

L'ensemble des solutions de cette récurrence linéaire d'ordre deux est un es-
pace vectoriel qui contient la solution constante 1. Si $p \neq 1/2$ alors $\rho^x$ est
aussi solution, linéairement indépendante de 1, et donc les solutions sont de
la forme $A + B\rho^x$ avec A et B constantes. Les conditions aux bords $r(a) = 1$,
$r(b) = 0$ fixent A et B, ce qui donne l'unique solution

$$
r(x) = \frac{\rho^b - \rho^x}{\rho^b - \rho^a}.
$$

Si $p = 1/2$ alors $\rho = 1$ et les deux solutions fondamentales précédentes sont
confondues. Cependant, on observe que dans ce cas, $x$ est également solution,
linéairement indépendante de $1$, et donc les solutions sont de la forme $A+Bx$
où $A$ et $B$ sont des constantes. Les conditions aux bords $r(a)=1$ et $r(b)=0$
fixent $A$ et $B$, ce qui donne l'unique solution

$$
r(x) = \frac{b-x}{b-a}.
$$

Calculons à présent

$$
R(x) := \mathbb{E}_x(\tau).
$$
En conditionnant selon $X_1$ on obtient pour tout $a < x < b$ la récurrence linéaire (la méthode est valable pour toute chaîne de Markov, idem pour $r(x)$)

$$R(x) = pR(x+1) + (1-p)R(x-1) + 1.$$

La présence du second membre 1 fait rechercher des solutions particulières. Si $p \neq 1/2$ alors $x/(1-2p)$ est solution particulière, et les solutions de l'équation sont de la forme $R(x) = x/(1-2p) + A + B\rho^x$. Les conditions aux bords $R(a) = 0$ et $R(b) = 0$ donnent enfin

$$R(x) = \frac{x-a}{1-2p} - \frac{(b-a) \rho^b - \rho^x}{1-2p \rho^b - \rho^a}.$$

Si $p = 1/2$ alors $-x^2$ est solution particulière, et les solutions sont de la forme $-x^2 + A + Bx$. Les conditions aux bords $R(a) = R(b) = 0$ donnent enfin

$$R(x) = (b-x)(x-a).$$

On peut de même calculer les fonctions suivantes :

$$F(x, s) = E_x(s^\tau), \quad G(x, s) = E_x(s^\tau 1_{X_\tau=a}), \quad \text{et} \quad G(x, s) = E_x(s^\tau 1_{X_\tau=b})$$

qui, pour $a \le x \le b$ et $s \in [-1, 1]$, vérifient la relation de récurrence

$$r(x) = psr(x+1) + (1-p)sr(x-1)$$

avec les conditions aux bords respectives suivantes :

$$F(a, s) = F(b, s) = 1, \quad G(a, s) = 1 = 1-G(b, s), \quad H(a, s) = 0 = 1-H(b, s).$$

On peut alors retrouver l'expression de $E_x(\tau)$ en dérivant la fonction généra-trice. Les expressions explicites de $F$, $G$ et $H$ sont toutefois assez lourdes. $\square$

**Remarque 2.3** (Les théorèmes limites à la rescousse). Voici un autre argu-ment pour établir que $P_x(\tau < \infty) = 1$. Posons $m = 2p-1$ et $\sigma^2 = 4p(1-p)$. Si $m \neq 0$ alors par la loi des grands nombres, presque sûrement $(X_n)_{n \ge 1}$ tend vers $+\infty$ si $m > 0$ et vers $-\infty$ si $m < 0$, et donc $P_x(\tau < \infty) = 1$. Si $m = 0$ alors pour tout $n \ge 1$, en posant $I_n = \frac{1}{\sqrt{n}}$]a, b[, on a

$$P_x(\tau = \infty) \le P(a < X_n < b) = P\left(\frac{X_n}{\sqrt{n}} \in I_n\right).$$

Or $(n^{-1/2}X_n)_{n \ge 1}$ converge en loi vers $\mathcal{N}(0, \sigma^2)$ par le théorème limite central. Mais $I_n$ dépend de $n$. Cependant, comme $(I_n)_{n \ge 1}$ est décroissante,

$$\limsup_{n \to \infty} P\left(\frac{X_n}{\sqrt{n}} \in I_n\right) \le \inf_{n \ge 1} \frac{1}{\sqrt{2\pi\sigma^2}} \int_{I_n} e^{-\frac{t^2}{2\sigma^2}} dt = 0.$$
**Remarque 2.4 (Martingales).** Si $(Z_n)_{n \ge 0}$ est une chaîne de Markov sur $E$ fini de noyau $\mathbf{P} = \mathbf{L}+\mathbf{I}$ alors pour toute fonction $f : E \to \mathbb{R}$, la suite $(M_n)_{n \ge 0}$ donnée par $M_0 = 0$ et pour tout $n \ge 1$

$$M_n = f(Z_n) - f(Z_0) - \sum_{k=0}^{n-1} (\mathbf{L}f)(Z_k)$$

est une martingale pour la filtration naturelle de la suite $(Z_n)_{n \ge 0}$. La formule ci-dessus peut être vue comme une formule d'Itô discrète. Lorsque $f$ est harmonique pour $\mathbf{L}$, c'est-à-dire que $\mathbf{L}f = 0$, alors $(f(Z_n) - f(Z_0))_{n \ge 0}$ est une martingale. Il se trouve que le vecteur des probabilités d'atteinte d'un ensemble clos est harmonique. Il est possible de retrouver les formules du théorème 2.2 en utilisant des martingales bien choisies et le théorème d'arrêt. Par exemple, la martingale $(X_n - n(p-q))_{n \ge 0}$ donne $\mathbb{E}_0(X_\tau) = (p-q)\mathbb{E}_0(\tau)$ tandis que la martingale $(\rho^{X_n})_{n \ge 0}$ donne $\mathbb{E}_0(\rho^{X_\tau}) = 1$. Cette méthode à base de martingales s'adapte au cadre des processus à temps et espace d'états continus, et permet notamment d'obtenir des formules pour le temps de sortie pour un processus de diffusion sur $\mathbb{R}^d$, voir chapitre 27. D'autre part, les équations satisfaites par les fonctions $r$ et $R$ dans la preuve du théorème 2.2 sont des cas particuliers du problème de Dirichlet du théorème 2.8.

**Théorème 2.5 (Nombres de Catalan).** Si $\tau := \inf\{n \ge 1 : X_n = 0\}$ alors

$$P_0(\tau = 2n + 2) = \frac{2}{n+1} \binom{2n}{n} p^{n+1} (1-p)^{n+1}, \quad n \ge 0.$$

<figure><img src="image_9.png" /><figcaption>**Fig. 2.2.** Un chemin de 0 à 0 ne restant pas positif et le chemin de 0 à $-2$ qui lui est associé dans la preuve du théorème 2.5.</figcaption></figure>

On reconnaît le $n^e$ nombre de Catalan $\frac{1}{n+1}\binom{2n}{n}$. Les nombres de Catalan sont également les moments pairs de la loi du demi-cercle, voir chapitre 21.
Démonstration. Sachant {$X_0 = 0$}, l'événement {$\tau = 2n + 2$} correspond à
une trajectoire de longueur $2n + 2$ partant de 0 et revenant à zéro en restant
strictement positive ou strictement négative. Ces deux cas sont équiprobables,
d'où le facteur 2 dans le résultat. Dans les deux cas, il y a eu forcément $n + 1$
incrément +1 et $n + 1$ incréments $-1$, d'où

$$
\mathbb{P}_0(\tau = 2n + 2) = 2C_n p^{n+1} (1-p)^{n+1}.
$$

où $C_n$ est le nombre de chemins de longueur $2n+2$ partant de zéro et revenant
à zéro, et restant strictement positifs. Le premier incrément est forcément +1
et le dernier forcément −1 et $C_n$ est égal au nombre de chemins de longueur
$2n$ partant de zéro et revenant à zéro et restant positifs. Il y a $n$ incréments
+1 et $n$ incréments $-1$. Considérons les chemins partant de zéro et revenant
à zéro et contenant $n$ incréments +1 et $n$ incréments $-1$. Il y en a $\binom{2n}{n}$. Si
un chemin de ce type n'est pas positif alors juste après la première position
négative, modifions tous les incréments en permutant le signe des +1 et des
$-1$. Un exemple d'illustration est donné dans la figure 2.2. On obtient de
la sorte un chemin avec $n-1$ incréments +1 et $n+1$ incréments $-1$, et il
s'avère que tous les chemins partant de zéro avec $n-1$ incréments +1 et $n+1$
incrément $-1$ s'obtiennent de la sorte, et il y en a $\binom{2n}{n-1}$. Cette bijection
donne donc $C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}$ (formule de Désiré André). $\square$

**Théorème 2.6** (du scrutin <fnref n="2" />). *Si* $n = a + b$ *et* $k = a - b$ *avec* $0 \le b \le a$ *alors*

$$
\mathbb{P}(S_1 > 0, \dots, S_n > 0 | S_0 = 0, S_n = k) = \frac{k}{n} = \frac{a-b}{a+b}.
$$

Le théorème 2.6 indique que lors d'une élection avec deux candidats A et B et n votants, dans laquelle A obtient a votes et B obtient b ≤ a votes, la probabilité que A soit devant B tout le long du dépouillement des n bulletins de vote est (a - b)/(a + b).

Démonstration. Notons tout d'abord que $0 \le k \le n$ et $(n+k, n-k) = 2(a, b)$.
Soit $P_{n,k}$ l'ensemble des chemins de la marche aléatoire simple, de longueur $n$,
partant de $(0,0)$ et finissant en $(n,k)$. Tous ces chemins possèdent exactement
$a$ incréments +1 et $b$ incréments $-1$. Ils sont donc au nombre de $\binom{a+b}{a}$. Soit
$P_{n,k}^{+}$ l'ensemble de ces chemins strictement positifs aux temps $1, \dots, n$. On a

$$
\mathbb{P}(S_1 > 0, \dots, S_n > 0 | S_0 = 0, S_n = k) = \mathrm{card}(P_{n,k}^{+}) \frac{p^a (1-p)^b}{\mathbb{P}(S_n = k | S_0 = 0)}.
$$

D'un autre côté $\mathbb{P}(S_n = k | S_0 = 0) = \mathrm{card}(P_{n,k}) p^a (1-p)^b$ et donc

$$
\mathbb{P}(S_1 > 0, \dots, S_n > 0 | S_0 = 0, S_n = k) = \frac{\mathrm{card}(P_{n,k}^{+})}{\mathrm{card}(P_{n,k})}.
$$

<footnote n="2">2. « *Ballot theorem* » en anglais.</footnote>
Il est tout à fait remarquable que cette formule ne dépende pas de $p$. L'ensemble $P_{n,k} \setminus P_{n,k}^{+}$ est invariant par la réflexion sur la portion du chemin située avant le retour à 0. On reconnaît là l'astuce de la preuve du théorème 2.5. Il en découle que l'ensemble des éléments de $P_{n,k} \setminus P_{n,k}^{+}$ qui commencent par un incrément +1 est en bijection avec l'ensemble des éléments de $P_{n,k} \setminus P_{n,k}^{+}$ qui commencent par un incrément $-1$. Or ce dernier est en bijection avec l'ensemble des éléments de $P_{n,k}$ qui commencent par un incrément $-1$, lui même en bijection avec $P_{n-1,k+1}$. Cela donne $\text{card}(P_{n,k}) - \text{card}(P_{n,k}^{+}) = 2\text{card}(P_{n-1,k+1})$. Comme $\text{card}(P_{n,k}) = \binom{n}{(n+k)/2}$, on obtient enfin

$$ \text{card}(P_{n,k}^{+}) = \binom{n}{(n+k)/2} - 2\binom{n-1}{(n+k)/2} = \frac{k}{n}\binom{n}{(n+k)/2}. $$

En d'autres termes, $\text{card}(P_{n,k}^{+}) = (k/n)\text{card}(P_{n,k})$. $\square$

La formule à base de nombres de Catalan du théorème 2.5 s'écrit

$$ \begin{aligned} & 2^{2n+2}\mathbb{P}(S_1 > 0, \dots, S_{2n+1} > 0 | S_0 = 0, S_{2n+2} = 0) \\ & = \text{card}(P_{2n+1,1}^{+}) = \frac{1}{n+1}\binom{2n}{n}. \end{aligned} $$

## 2.2 Marche aléatoire simple symétrique dans l'espace

La marche aléatoire simple symétrique sur $\mathbb{Z}^d$, $d \ge 1$, est définie par

$$ X_{n+1} = X_n + \varepsilon_{n+1} = X_0 + \varepsilon_1 + \dots + \varepsilon_{n+1} $$

où $(\varepsilon_n)_{n \ge 1}$ est une suite de variables aléatoires i.i.d., indépendantes de la position initiale $X_0$, et de loi uniforme sur $\{\pm e_1, \dots, \pm e_d\}$, où $e_1, \dots, e_d$ est la base canonique de $\mathbb{R}^d$. La suite $(X_n)_{n \ge 0}$ est une chaîne de Markov d'espace d'états $\mathbb{Z}^d$ et de noyau de transition

$$ \mathbf{P}(x, y) = \frac{1}{2d} \mathbb{1}_{|x-y|=1} $$

où $|x|_1 := |x_1| + \dots + |x_d|$. On parle également de marche aléatoire symétrique aux plus proches voisins pour la norme $|\cdot|_1$. Les incrément (ε_n)_{n≥1} sont de loi uniforme sur la sphère unité pour la norme $|\cdot|_1$. En concevant les incrément ε_1, ..., ε_n comme issus de n jets d'un dé équilibré à 2d faces, on voit que $\text{Loi}(X_n - X_0)$ est l'image de la loi multinomiale

$$ \left( \frac{1}{2d} \delta_{e_1} + \frac{1}{2d} \delta_{-e_1} + \dots + \frac{1}{2d} \delta_{-e_d} + \frac{1}{2d} \delta_{e_d} \right)^{*n} = \text{Mul} \left( n, \left( \frac{1}{2d}, \dots, \frac{1}{2d} \right) \right) $$

par l'application
<figure><img src="image_10.png" /><figcaption>Fig. 2.3. Début de trajectoire de la marche aléatoire simple sur $\mathbb{Z}^2$.</figcaption></figure>

$$ (k_1, \dots, k_{2d}) \in \mathbb{N}^{2d} \mapsto (k_1 - k_2, \dots, k_{2d-1} - k_{2d}) \in \mathbb{Z}^d. $$

Notons que le temps (aléatoire) au bout duquel la marche aléatoire a emprunté les $2d$ directions qui s'offrent à elle suit la loi du collectionneur de coupons étudiée dans le chapitre 1 avec $r = 2d$.

**Théorème 2.7** (Marche aléatoire simple symétrique). La marche aléatoire simple symétrique sur $\mathbb{Z}^d$ est récurrente nulle si $d \le 2$ et transitoire si $d \ge 3$.

*Démonstration.* La preuve est basée sur l'analyse de Fourier. Rappelons tout d'abord que pour toute variable aléatoire $Z$ à valeurs dans $\mathbb{Z}^d$ on a

$$ P(Z = z) = \int_{[0,1]^d} e^{2\pi i \langle z, x \rangle} \varphi_Z(x) \, dx \quad \text{où} \quad \varphi_Z(x) = \sum_{z \in \mathbb{Z}^d} e^{-2\pi i \langle z, x \rangle} P(Z = z). $$

Ensuite, en introduisant un paramètre $\rho \in [0, 1[$ pour permuter série et intégrale, on a, en utilisant ce qui précède, la série d'égalités suivante :

$$ \begin{align*} \sum_{n=0}^{\infty} \mathbf{P}^n(0,0) &= \lim_{\rho \uparrow 1} \sum_{n=0}^{\infty} \rho^n \mathbf{P}^n(\varepsilon_1 + \dots + \varepsilon_n = 0) \\ &= \lim_{\rho \uparrow 1} \sum_{n=0}^{\infty} \int_{[0,1]^d} \rho^n e^{2\pi i \langle 0,x \rangle} \varphi_{\varepsilon_1 + \dots + \varepsilon_n}(x) \, dx \\ &= \lim_{\rho \uparrow 1} \sum_{n=0}^{\infty} \int_{[0,1]^d} \rho^n (\varphi_{\varepsilon_1}(x))^n \, dx \end{align*} $$
$$
\begin{align*}
&= \lim_{\rho \uparrow 1} \int_{[0,1]^d} \sum_{n=0}^{\infty} \rho^n (\varphi_{\varepsilon_1}(x))^n dx \\
&= \lim_{\rho \uparrow 1} \int_{[0,1]^d} \frac{1}{1 - \rho \varphi_{\varepsilon_1}(x)} dx \\
&= \lim_{\rho \uparrow 1} \int_{[0,1]^d} \frac{d}{\sum_{k=1}^{d} (1 - \rho \cos(2\pi x_k))} dx \\
&= \int_{[0,1]^d} \frac{d}{\sum_{k=1}^{d} (1 - \cos(2\pi x_k))} dx,
\end{align*}
$$

où la commutation de la limite quand $\rho \uparrow 1$ et de l'intégrale s'obtient par
convergence monotone. Le comportement de l'intégrale obtenue dépend uni-
quement du comportement de la fonction sous le signe somme au voisinage
de 0. Un passage en coordonnées sphériques ainsi qu'un développement limité
en 0 montrent que l'intégrale est finie ssi $r \ge 0 \mapsto r^{d-3}$ est intégrable au
voisinage de 0, c'est-à-dire $d > 2$, c'est-à-dire $d \ge 3$ car $d$ est entier !
□

On peut étudier la récurrence de la marche aléatoire simple symétrique
sur $\mathbb{Z}^d$ $(X_n)_{n\ge 0}$ en utilisant la combinatoire, plutôt que l'analyse de Fourier.
En effet, la chaîne est irréductible et de période 2 pour tout $d \ge 1$ et il suffit
donc d'étudier $\sum_n \mathbf{P}^{2n}(0,0)$. La formule multinomiale donne

$$
\begin{align*}
\mathbf{P}^{2n}(0,0) &= \frac{1}{(2d)^{2n}} \sum_{\substack{r_1+\dots+r_{2d}=n \\ r_1=r_2,\dots,r_{d-1}=r_d}} \binom{2n}{r_1,\dots,r_{2d}} \\
&= \frac{1}{(2d)^{2n}} \sum_{r_1+\dots+r_d=n} \frac{(2n)!}{r_1!^2 \dots r_d!^2}.
\end{align*}
$$

Le cas $d=1$ est déjà traité. Restent les cas $d=2$ et $d \ge 3$.

Cas $d=2$ (méthode directe). L'identité de Vandermonde <fnref n="3" /> donne

$$
\begin{align*}
\mathbf{P}^{2n}(0,0) &= \frac{1}{4^{2n}} \sum_{n_1+n_2=n} \frac{(2n)!}{n_1!^2 n_2!^2} \\
&= \frac{(2n)!}{4^{2n} n!^2} \sum_{k=0}^{n} \binom{n}{k}^2 \\
&= \frac{(2n)!}{4^{2n} n!^2} \frac{(2n)!}{n!^2} \stackrel{\sim}{\rightarrow} \frac{1}{\pi n}
\end{align*}
$$

qui n'est donc pas sommable, et la chaîne est donc récurrente. La récurrence
nulle vient du fait que la mesure de comptage, qui n'est pas finie car $\mathbb{Z}^2$ est
infini, est une mesure symétrique et donc invariante.

Cas $d=2$ (méthode astucieuse). Soient $U_n$ et $V_n$ les projections de $X_n$
sur les première et seconde bissectrices (pentes $\pm 1$). On vérifie que $(U_n)_{n\ge 0}$

<footnote n="3">3. Il s'agit de la formule de «convolution» $\binom{n+m}{r} = \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k}$.</footnote>
et $(V_n)_{n\ge 0}$ sont des marches aléatoires simples symétriques sur $\frac{1}{\sqrt{2}}\mathbb{Z}$, indépendantes ! De plus, $X_n = 0$ si et seulement si $U_n = V_n = 0$, ce qui donne $\mathbf{P}^{2n}(0,0) \sim \frac{1}{\pi n}$, et la chaîne est donc récurrente. Attention : les composantes de $(X_n)_{n\ge 0}$ (abscisse et ordonnée) ne sont pas des marches aléatoires simples sur $\mathbb{Z}$, mais constituent des chaînes de Markov de noyau $\mathbf{Q}(x,y) = \frac{1}{4}1_{|x-y|=1} + \frac{1}{2}1_{x=y}$ (il est possible d'établir qu'elles sont récurrentes, mais cela ne conduit à rien de bien utile).

Cas $d=3$ (méthode directe). La formule du multinôme donne ici

$$ 
\begin{aligned}
\mathbf{P}^{2n}(0,0) &= \frac{1}{6^{2n}} \sum_{r_1+r_2+r_3=n} \frac{(2n)!}{r_1!^2 r_2!^2 r_3!^2} \\
&= \frac{(2n)!}{2^{2n} 3^n n!^2} \sum_{r_1+r_2+r_3=n} \left( \binom{n}{r_1 r_2 r_3} \right)^2 \left(\frac{1}{3}\right)^n.
\end{aligned}
$$

Si $n=3m$ alors une petite étude montre que

$$ \binom{n}{r_1 r_2 r_3} \le \binom{n}{m m m} $$

et donc, grâce à la formule du trinôme de taille $n$ et de second paramètre $(1/3, 1/3, 1/3)$, on obtient, pour $n=3m$,

$$ \mathbf{P}^{2n}(0,0) \le \frac{(2n)!}{2^{2n} 3^n n!^2} \binom{n}{m m m} \sim \frac{1}{2} \left(\frac{3}{\pi n}\right)^{3/2} = \frac{c}{n^{3/2}}. $$

Ainsi, $\sum_m \mathbf{P}^{6m}(0,0) < \infty$. Comme pour $k=1,2$,

$$ \frac{1}{6^{2k}} \mathbf{P}^{6m}(0,0) \le \mathbf{P}^{6m+2k}(0,0), $$

il vient,

$$ \sum_n \mathbf{P}^{2n}(0,0) = \sum_{k=0,1,2} \sum_m \mathbf{P}^{6m+2k}(0,0) < \infty, $$

et donc la chaîne est transitoire.

Cas $d>3$ (méthode astucieuse à partir du cas $d=3$). Soit $X' = (X'_n)_{n\ge 0}$ la chaîne projetée sur $\mathbb{Z}^3$ c'est-à-dire constituée par les trois premières coordonnées de $X = (X_n)_{n\ge 0}$. Il s'agit d'une chaîne de Markov sur $\mathbb{Z}^3$ de noyau

$$ \mathbf{Q} := \left(1 - \frac{d-3}{d}\right) \mathbf{P} + \frac{d-3}{d} \mathbf{I} $$

où $\mathbf{P}$ est le noyau de la marche aléatoire simple symétrique $X''$ sur $\mathbb{Z}^3$. Un retour à zéro de $X$ s'accompagne toujours d'un retour à zéro de $X'$, et donc si $X'$ est transitoire alors forcément $X$ l'est aussi. Or les trajectoires de $X'$ sont les trajectoires de $X''$ avec des temporisations géométriques à chaque site, et en particulier, les fréquences asymptotiques de passage sont les mêmes, ce qui fait que la transience de $X''$ implique celle de $X'$, et donc $X$ est transitoire.
## 2.3 Problème de Dirichlet et champ libre gaussien

Soit $(X_n)_{n \ge 0}$ la marche aléatoire simple sur $Z^d$, et $\mathbf{P}$ son noyau de transition. Pour toute fonction bornée $f: Z^d \to \mathbb{R}$ et tout $x \in Z^d$ on a,

$$ \mathbb{E}(f(X_{n+1}) | X_n = x) - f(x) = (\mathbf{P}f)(x) - f(x) = (\Delta f)(x), $$

où $\Delta := \mathbf{P} - \mathbf{I}$. L'opérateur $\Delta$ est le générateur de la marche aléatoire simple symétrique sur $Z^d$. Il s'agit d'un opérateur laplacien discret, qui calcule l'écart à la moyenne sur les voisins :

$$ (\Delta f)(x) = \left( \frac{1}{2d} \sum_{y:|y-x|_1=1} f(y) \right) - f(x) = \frac{1}{2d} \sum_{y:|y-x|_1=1} (f(y) - f(x)). $$

On dit que $f$ est harmonique sur $A \subset Z^d$ lorsque $\Delta f = 0$ sur $A$, ce qui signifie qu'en tout point de $A$ la valeur de $f$ est égale à la moyenne de ses valeurs sur les $2d$ voisins. L'opérateur $\Delta$ est local en ce sens que $(\Delta f)(x)$ ne dépend que des valeurs de $f$ en $x$ et ses plus proches voisins. Ainsi la valeur de $\Delta f$ sur $A$ ne dépend que des valeurs de $f$ sur $\bar{A} := A \cup \partial A$ où

$$ \partial A := \{ y \notin A : \exists x \in A, |x - y|_1 = 1 \} $$

est le bord extérieur de $A$. Le problème de Dirichlet consiste à trouver une fonction harmonique sur $A$ dont la valeur sur $\partial A$ est prescrite. Il s'agit en fait d'un problème d'algèbre linéaire, pour lequel le théorème 2.8 ci-dessous fournit une expression probabiliste de la solution utilisant le temps d'atteinte

$$ \tau_{\partial A} := \inf\{n \ge 0 : X_n \in \partial A\}. $$

On s'intéresse à la même question sur un ouvert de $\mathbb{R}^d$ pour l'opérateur laplacien classique dans le chapitre 24.

**Théorème 2.8 (Problème de Dirichlet).** Soit $A \subset Z^d$ un ensemble non vide fini. Alors pour tout $x \in A$ on a $P_x(\tau_{\partial A} < \infty) = 1$. De plus, pour toute fonction $g: \partial A \to \mathbb{R}$, la fonction $f: \bar{A} \to \mathbb{R}$ définie pour tout $x \in \bar{A}$ par

$$ f(x) = \mathbb{E}_x(g(X_{\tau_{\partial A}})) $$

est l'unique solution du système

$$ \begin{cases} f = g & \text{sur } \partial A, \\ \Delta f = 0 & \text{sur } A. \end{cases} $$

Lorsque $d=1$ on retrouve la fonction $r$ étudiée dans la preuve du théorème 2.2 sur la ruine du joueur. D'autre part, d'après la remarque 2.4, l'image d'une chaîne de Markov par une fonction harmonique pour son générateur est une
martingale, ce qui explique après coup la formule probabiliste pour la solution
du problème de Dirichlet grâce au théorème d'arrêt.

La quantité $f(x) = \mathbb{E}_x(g(X_{\tau_{\partial A}})) = \sum_{y \in \partial A} g(y) \mathbb{P}_x(X_{\tau_{\partial A}} = y)$ est la moyenne de $g$ pour la loi $\mu_x$ sur $\partial A$, appelée mesure harmonique, définie par

$$
\mu_x(y) = \mathbb{P}_x(X_{\tau_{\partial A}} = y), \quad y \in \partial A.
$$

On peut également parler de noyau de Poisson discret par analogie avec le
problème de Dirichlet sur un ouvert de $\mathbb{R}^d$ (voir chapitre 24).

Démonstration. La propriété $\mathbb{P}_x(\tau_{\partial A} < \infty) = 1$ pour tout $x \in A$ peut être établie en procédant comme dans la remarque 2.3, ou encore comme dans la preuve du théorème 2.2, qui fournit de plus une borne sous-géométrique pour la queue de la loi de $\tau$.

Vérifions que la fonction $f$ proposée est bien solution. Pour tout $x \in \partial A$
on a $\tau_{\partial A} = 0$ sur $\{X_0 = x\}$ et donc $f = g$ sur $\partial A$. Montrons à présent que
$\Delta f = 0$ sur $A$. On se ramène tout d'abord par linéarité au cas où $g = 1_{\{z\}}$
avec $z \in \partial A$. Ensuite on écrit, pour tout $y \in \bar{A}$,

$$
\begin{align*}
f(y) &= \mathbb{P}_y(X_{\tau_{\partial A}} = z) = \sum_{n=0}^{\infty} \mathbb{P}_y(X_n = z, \tau_{\partial A} = n) \\
&= \mathbb{1}_{y=z} + \mathbb{1}_{y \in A} \sum_{n=1}^{\infty} \sum_{x_1, \dots, x_{n-1} \in A} \mathbf{P}(y, x_1) \mathbf{P}(x_1, x_2) \cdots \mathbf{P}(x_{n-1}, z).
\end{align*}
$$

D'autre part, comme $f = 0$ sur $\partial A \setminus \{z\}$ et $\Delta$ est local, on a, pour tout $x \in A$,

$$
(\mathbf{P}f)(x) = \sum_{y \in \mathbb{Z}^d} \mathbf{P}(x, y) f(y) = \mathbf{P}(x, z) f(z) + \sum_{y \in A} \mathbf{P}(x, y) f(y).
$$

Par conséquent, pour tout $x \in A$,

$$
\begin{align*}
(\mathbf{P}f)(x) &= \mathbf{P}(x, z)f(z) + \sum_{n=1}^{\infty} \sum_{y,x_1,\dots,x_{n-1} \in A} \mathbf{P}(x,y)\mathbf{P}(y,x_1)\cdots\mathbf{P}(x_{n-1},z) \\
&= \mathbf{P}(x,z)f(z) + (f(x) - (\mathbb{1}_{x=z} + \mathbf{P}(x,z))) \\
&= f(x)
\end{align*}
$$

où la dernière égalité vient de $\mathbb{1}_{x=z} = 0$ et $f(z) = 1$. Ainsi on a $\mathbf{P}f = f$ sur $A$, c'est-à-dire que $\Delta f = 0$ sur $A$.

Pour établir l'unicité de la solution, on se ramène par linéarité à établir que
$f = 0$ est l'unique solution lorsque $g = 0$. Or, si $f : \bar{A} \to \mathbb{R}$ est harmonique
sur $A$, l'interprétation de $(\Delta f)(x)$ comme écart à la moyenne sur les plus
proches voisins permet d'établir qu'à la fois le minimum et le maximum de $f$
sur $\bar{A}$ sont (au moins) nécessairement atteints sur le bord $\partial A$. Or, comme par
ailleurs $f$ est nulle sur $\partial A$, il en découle que $f$ est nulle sur $\bar{A}$. $\square$
Le théorème 2.8 se généralise de la manière suivante :

**Théorème 2.9** (Problème de Dirichlet et fonction de Green). Si $A \subset \mathbb{Z}^d$ est un ensemble non vide fini alors pour toutes fonctions $g : \partial A \to \mathbb{R}$ et $h : A \to \mathbb{R}$, la fonction $f : \bar{A} \to \mathbb{R}$ définie pour tout $x \in \bar{A}$ par

$$f(x) = E_x(g(X_{\tau_{\partial A}}) + \sum_{n=0}^{\tau_{\partial A}-1} h(X_n))$$

est l'unique solution de

$$\begin{cases} f = g & \text{sur } \partial A, \\ \Delta f = -h & \text{sur } A. \end{cases}$$

Lorsque $d=1$ et $h=1$ on retrouve la fonction $R$ de la preuve du théorème 2.2. Le théorème 2.8 correspond au cas où $h=0$. Pour tout $x \in A$ on a

$$f(x) = \sum_{y \in \partial A} g(y) \mathbb{P}_x(\tau_{\partial A} = y) + \sum_{y \in A} h(y) G_A(x, y)$$

où $G_A(x, y)$ est le nombre moyen de passages en $y$ en partant de $x$ et avant de sortir de $A$, c'est-à-dire

$$G_A(x, y) := E_x \left( \sum_{n=0}^{\tau_{\partial A}-1} \mathbb{1}_{X_n=y} \right) = \sum_{n=0}^{\infty} \mathbb{P}_x(X_n = y, n < \tau_{\partial A}).$$

On dit que $G_A$ est la fonction de Green de la marche aléatoire simple symétrique sur $A$ tuée au bord $\partial A$. C'est l'inverse de la restriction $-\Delta_A$ de $-\Delta$ aux fonctions sur $\bar{A}$ nulles sur $\partial A$ :

$$G_A = -\Delta_A^{-1}.$$

En effet, si $g=0$ et $h=1_{\{y\}}$ alors $f(x) = G_A(x, y)$ d'où $\Delta_A G_A = -I_A$.

**Démonstration du théorème 2.9.** Grâce au théorème 2.8 il suffit par linéarité de vérifier que $f(x) = 1_{x \in A} G_A(x, z)$ est solution lorsque $g=0$ et $h = 1_{\{z\}}$ avec $z \in A$. Or pour tout $x \in A$, grâce à la propriété de Markov,

$$\begin{align*} f(x) &= 1_{\{x=z\}} + \sum_{n=1}^{\infty} \mathbb{P}_x(X_n = z, n < \tau_{\partial A}) \\ &= 1_{\{x=z\}} + \sum_{y:x-y|_1=1} \sum_{n=1}^{\infty} \mathbb{P}(X_n = z, n < \tau_{\partial A} | X_1 = y) \mathbf{P}(x, y) \\ &= 1_{\{x=z\}} + \sum_{u:x-y|_1=1} f(y) \mathbf{P}(x, y). \end{align*}$$

On a bien $f = h + \mathbf{P}f$ sur $A$, c'est-à-dire $\Delta f = -h$ sur $A$. $\square$
Les preuves des théorèmes 2.8 et 2.9 restent valables pour des marches aléatoires asymétriques sur $Z^d$, à condition de remplacer le générateur $\Delta$ de la marche symétrique par le générateur $L := P - I$, qui est un opérateur local : $|x - y| > 1 \Rightarrow L(x, y) = P(x, y) = 0$. Le dépassement de ce cadre nécessite l'adaptation de la notion de bord : $\{y \notin A : \exists x \in A, L(x, y) > 0\}$.

Le champ libre gaussien<fnref n="4" /> est un modèle d'interface aléatoire lié à la marche aléatoire simple symétrique et au problème de Dirichlet. Soit $A \subset Z^d$ un sous-ensemble non-vide fini. Une interface est une fonction de hauteur $f : \bar{A} \to \mathbb{R}$ qui associe à chaque site $x \in \bar{A}$ une hauteur $f(x)$, aussi appelée spin. Pour simplifier, on impose la condition au bord $f = 0$ sur le bord extérieur $\partial A$ de $A$. On note $\mathcal{F}_A$ l'ensemble des interfaces $f$ sur $\bar{A}$ nulles sur le bord $\partial A$, qu'on peut identifier à $\mathbb{R}^A$. L'énergie $H_A(f)$ de l'interface $f \in \mathcal{F}_A$ est définie par

$$H_A(f) = \frac{1}{4d} \sum_{\substack{\{x,y\} \subset \bar{A} \\ |x-y|_1 = 1}} (f(x) - f(y))^2,$$

où on a posé $f = 0$ sur $\partial A$. L'énergie $H_A(f)$ est d'autant plus petite que l'interface $f$ est «plate». En notant

$$\langle u, v \rangle_A := \sum_{x \in A} u(x)v(x)$$

il vient, pour tout $f \in \mathcal{F}_A$,

$$H_A(f) = \frac{1}{4d} \sum_{x \in A} \sum_{\substack{y \in \bar{A} \\ |x-y|_1 = 1}} (f(x) - f(y))f(x) = \frac{1}{2} \langle -\Delta f, f \rangle_A.$$

Comme $H_A(0) = 0$ et $H_A(f) = 0$ entraîne $f = 0$, la forme quadratique $H_A$ n'est pas dégénérée, et on peut définir une loi gaussienne $Q_A$ sur $\mathcal{F}_A$ favorisant les faibles énergies :

$$Q_A(df) = \frac{1}{Z_A} e^{-H_A(f)} df \quad \text{où} \quad Z_A := \int_{\mathcal{F}_A} e^{-H_A(f)} df.$$

Cette loi gaussienne, appelée champ libre gaussien, est caractérisée par sa moyenne $m_A : A \to \mathbb{R}$ et sa matrice de covariance $C_A : A \times A \to \mathbb{R}$, données pour tous $x, y \in A$ par

$$m_A(x) := \int f_x Q_A(df) = 0$$

et

$$C_A(x, y) := \int f_x f_y Q_A(df) - m_A(x) m_A(y) = -(\Delta_A^{-1})(x, y) = G_A(x, y),$$

où $f_x$ désigne l'application coordonnée $f_x : f \in \mathcal{F}_A \mapsto f(x) \in \mathbb{R}$.

<footnote n="4">4. « Gaussian free field » (GFF) en anglais.</footnote>
## 2.4 Marche aléatoire sur le groupe symétrique

On considère $r \ge 2$ cartes à jouer empilées en un paquet vertical, et numérotées de 1 à $r$. On dit que la carte du dessus est en position 1, etc et que celle du dessous est en position $r$. On étudie un battage de cartes très simple pour mélanger le paquet de cartes, appelé « top to random shuffle » en anglais. Plus précisément, on considère la $k$-insertion qui consiste à prendre la carte du sommet du paquet et à l'insérer entre la $k$-e et $k+1$-e positions. La $1$-insertion n'a aucun effet. On convient que la $r$-insertion place la carte du sommet sous le paquet. On choisit d'effectuer des $k$-insertions successives en utilisant une suite i.i.d. uniforme sur $\{1, \dots, r\}$ pour choisir $k$.

Une configuration du paquet est codée par un élément $\sigma$ du groupe symétrique $\Sigma_r$, de sorte que $\sigma(k)$ désigne la position de la carte numéro $k$. Une $k$-insertion fait passer de la configuration $\sigma$ à la configuration $(k, k-1, \dots, 1)\sigma$ où $(k, k-1, \dots, 1) \in \Sigma_r$ désigne le $k$-cycle $k \to k-1 \to \dots \to 1 \to k$.

En notant $X_n$ la configuration du paquet à l'instant $n$, on obtient une suite aléatoire $(X_n)_{n \ge 0}$ de $\Sigma_r$ vérifiant pour tout $n \ge 0$,

$$X_{n+1} = \varepsilon_{n+1} X_n = \varepsilon_{n+1} \cdots \varepsilon_1 X_0$$

où $(\varepsilon_n)_{n \ge 1}$ sont i.i.d. de loi uniforme sur $C := \{(k, k-1, \dots, 1) : 1 \le k \le r\} \subset \Sigma_r$. La suite $(X_n)_{n \ge 0}$ est une marche aléatoire à gauche sur le groupe (non abélien) $\Sigma_r$, d'incréments $C$. C'est aussi une chaîne de Markov d'espace d'états fini $\Sigma_r$ (de cardinal $r!$) et de noyau

$$\mathbf{P}(\sigma, \sigma') = \frac{\mathbb{1}_C(\sigma'\sigma^{-1})}{|C|} = \frac{\mathbb{1}_C(\sigma'\sigma^{-1})}{r}.$$

<table><caption>**Fig. 2.4.** La carte en position $k$ se déplace en position $\sigma(k)$.</caption><tr><td>1</td><td>σ<sup>-1</sup>(1)</td></tr><tr><td>...</td><td>...</td></tr><tr><td>r</td><td>σ<sup>-1</sup>(r)</td></tr><tr><td>Configuration initiale</td><td>Configuration après mélange</td></tr></table>

**Théorème 2.10** (Convergence en loi). La chaîne $(X_n)_{n \ge 0}$ est récurrente irréductible apériodique. Son unique loi invariante est la loi uniforme sur $\Sigma_r$ :

$$\mu = \sum_{\sigma \in \Sigma_r} \frac{1}{|\Sigma_r|} \delta_{\sigma} = \frac{1}{r!} \sum_{\sigma \in \Sigma_r} \delta_{\sigma}.$$

La chaîne $(X_n)_{n \ge 0}$ converge en loi vers $\mu$ quelle que soit la loi initiale $\text{Loi}(X_0)$.
Démonstration. L'ensemble de transpositions spécial

$$
\mathcal{T} := \{(r, r-1), \dots, (2, 1), (1, r)\}
$$

engendre Σ<sub>r</sub>. Comme les *k*-insertions (r, r − 1, . . . , 1) et (2, 1) correspondant à k = r et à k = 2 engendrent T, on en déduit qu’elles engendrent Σ<sub>r</sub>. Donc C engendre Σ<sub>r</sub> et la chaîne est irréductible. Comme l’identité (1) est également une *k*-insertion (*k* = 1), la diagonale de la matrice de transition de la chaîne est > 0 et donc la chaîne est apériodique. Comme Σ<sub>r</sub> est un groupe, il y a exactement *r* états qui conduisent à chaque état, donc les colonnes de la matrice de transition ont exactement *r* entrées non nulles, toutes égales à 1/*r*. Ainsi, la transposée de la matrice de transition est également une matrice de transition<sup>5</sup> et donc la loi uniforme est invariante. Or toute chaîne finie récurrente apériodique possède une unique loi invariante vers laquelle elle converge en loi quelle que soit sa loi initiale.
□

On souhaite à présent étudier la vitesse de convergence de la chaîne vers sa
loi invariante, partant d'une configuration initiale X₀ fixée. Par invariance par
translation, on peut supposer que X₀ = (1), c'est-à-dire que toutes les cartes
sont dans l'ordre au départ. Au temps 0 la carte r est en position r (tout
en bas du paquet), et subit une remontée pas à pas au fil du temps jusqu'au
sommet. Cette remontée est de plus en plus rapide. Pour tout 1 ≤ k ≤ r − 1,
on note T_k le temps que cette carte passe en position r − k (et T_0 = 0). Pour
tout k ≥ 1, on a, avec la convention T_1 + ... + T_{k−1} = 0 si k = 1,

$$
\begin{align*}
T_k &= \min\{n \ge 1 : X_{T_1 + \cdots + T_{k-1} + n} = r - k\} \\
    &= \min\{n \ge 1 : X_n(r) = r - k\} - (T_1 + \cdots + T_{k-1}).
\end{align*}
$$

Au temps $T_1 + \dots + T_{r-1}$ la carte $r$ est en position 1 (sommet du paquet). La variable aléatoire

$$
T := 1 + T_1 + \dots + T_{r-1}
$$

suit la loi du collectionneur de coupons de *r* coupons de probabilité d'appari-
tion uniforme (chapitre 1). Les variables aléatoires *T*<sub>1</sub>, ..., *T*<sub>*r*−1</sub> sont indépen-
dantes avec *T*<sub>*k*</sub> ~ Geo(*k*/*r*) pour tout 1 ≤ *k* ≤ *r* − 1. Notons que *T* ≥ *r*.

**Théorème 2.11** (Bon mélange après remontée). Le temps *T* est un temps fort de stationnarité : pour tout *n* ≥ 0, les variables aléatoires *X*<sub>*T*+*n*</sub> et *T* sont indépendantes et de plus *X*<sub>*T*+*n*</sub> suit la loi uniforme *μ* sur *Σ*<sub>*r*</sub>.

Démonstration. La loi uniforme sur Σ_r peut s'obtenir en tirant uniformément sans remise les images de 1, ..., r. D'autre part, la loi uniforme sur Σ_r est invariante par translation.

<footnote n="5">5. Elle est *doublement stochastique* (ou *bistochastique*). L'ensemble des matrices doublement stochastiques $n \times n$ est un polytope (intersection de demi-espaces) convexe et compact à $(n-1)^2$ degrés de liberté. Ses points extrémaux sont les matrices de permutations (Birkhoff et von Neumann). Encore le groupe symétrique!</footnote>
Au temps $T_1$, la carte $r$ se trouve pour la première fois en position $r-1$, car la carte numéro 1 a été glissée sous le paquet. Au temps $T_1 + T_2$, la carte $r$ se trouve pour la première fois en position $r-2$ car la carte numéro 2 a été glissée sous ou sur la carte 1. Les numéros des deux cartes sous le paquet sont 1, 2 ou 2, 1 avec probabilité $1/2$. Par récurrence, au temps $T_1 + \cdots + T_{r-1} = T-1$, la carte $r$ se trouve au sommet du paquet pour la première fois et les $r-1$ cartes qui sont sous elle ont des numéros répartis uniformément sans remise dans $\{1, \dots, r-1\}$. Au temps $T$, la carte $r$ est placée aléatoirement et uniformément dans le paquet à une position entre 1 et $r$ et donc $X_T$ suit la loi uniforme. Comme la probabilité $\mathbb{P}(X_T = \sigma, T = k)$ ne dépend pas de $\sigma$, on en déduit que $T$ et $X_T$ sont indépendantes. Or comme la loi $\mu$ est invariante, on obtient $X_{T+n} \sim \mu$ pour tout $n \ge 0$. $\square$

Pour bien mélanger le paquet de cartes, on pourrait s’arrêter au temps $T$. Malheureusement, on ne connaît pas $T$ en pratique ! Alternativement, on pourrait chercher à déterminer une valeur de $n$, aussi petite que possible, telle que $d_{VT}(\text{Loi}(X_n), \mu)$ est proche de zéro, où $d_{VT}(\cdot, \cdot)$ est la distance en variation totale (section 1.3). Il s’avère que pour $r$ assez grand, la quantité $d_{VT}(\text{Loi}(X_n), \mu)$ passe de 1 à 0 de manière abrupte$^6$ autour de $n = r \log(r)$. Ce phénomène de convergence abrupte est quantifié par le théorème suivant.

**Théorème 2.12** (Convergence abrupte en $n = r \log(r)$). *Pour tout réel $c > 0$,*

$$d_{VT}(\text{Loi}(X_{\lfloor r \log(r) + cr \rfloor}), \mu) \le e^{-c+\epsilon_r} \quad \text{avec} \quad 0 \le \epsilon_r < 1/r.$$

Si $c_r \ge 0$ vérifie $\lim_{r \to \infty} c_r = \infty$ et $r \log(r) - rc_r > 0$ pour tout $r \ge 1$, alors

$$\lim_{r \to \infty} d_{VT}(\text{Loi}(X_{r \log(r) - rc_r}), \mu) = 1.$$

*Démonstration.* Grâce au théorème 2.11, on a, pour tout $A \subset \Sigma_r$,

$$
\begin{align*}
\mathbb{P}(X_n \in A) &= \sum_{k=0}^{n} \mathbb{P}(X_n \in A, T = k) + \mathbb{P}(X_n = \sigma, T > n) \\
&\le \sum_{k=0}^{n} \mathbb{P}(X_n \in A, T = k) + \mathbb{P}(T > n) \\
&= \sum_{k=0}^{n} \mathbb{P}(X_{T+n-k} \in A, T = k) + \mathbb{P}(T > n) \\
&= \sum_{k=0}^{n} \mu(A)\mathbb{P}(T = k) + \mathbb{P}(T > n) \\
&= \mu(A)\mathbb{P}(T \le n) + \mathbb{P}(T > n) \\
&\le \mu(A) + \mathbb{P}(T > n).
\end{align*}
$$

<footnote n="6">6. On parle de « cutoff phenomenon » en anglais.</footnote>
d'où $P(X_n \in A) - \mu(A) \le P(T > n)$. Appliqué à A et $A^c$, cela donne

$$d_{VT}(\text{Loi}(X_n), \mu) \le P(T > n), \quad n \ge 0.$$

Le résultat découle du théorème 1.17 sur le collectionneur de coupons. □

La figure 1.2 illustre le phénomène de convergence abrupte.

## 2.5 Pour aller plus loin

La marche aléatoire simple sur $Z^d$, étudiée notamment par George Pólya puis par Frank Spitzer, fait partie des modèles de base des probabilités. Elle fait l'objet d'une attention particulière dans les livres de William Feller [Fel68], Frank Spitzer [Spi70], Peter G. Doyle et Laurie Snell [DS84], et de James Norris [Nor98a]. La démonstration du théorème 2.7 est tirée d'un article [CF51] de Kai Lai Chung et Wolfgang Heinrich Johannes Fuchs. Cette analyse de Fourier peut être poussée plus loin, comme expliqué par exemple dans les livres de Gregory Lawler et Vlada Limic [Law13, LL10]. L'astuce combinatoire de Désiré André se trouve dans [And87].

Les nombres de Catalan interviennent très fréquemment en combinatoire. Ils comptent, outre les chemins de la marche aléatoire simple, les mots de Dyck, les parenthèsages, les triangulations d'un polygone, les partitions non croisées, les chemins sous-diagonaux dans le carré, les arbres planaires, etc.

La physique statistique a inspiré nombre de modèles de marches aléatoires : marches aléatoires en milieu aléatoire, en paysage aléatoire, en auto interaction (évitement, renforcement, excitation, ...), etc. Ce sujet historique est d'une grande richesse et fait toujours l'objet de recherches à l'heure actuelle. Les chapitres 3, 6, et 15 font intervenir des marches aléatoires. Par ailleurs le théorème limite central permet de concevoir le mouvement brownien comme un analogue en temps et en espace continus de la marche aléatoire simple, obtenu comme limite d'échelle de modèles discrets ($\varepsilon Z^d$ approche $\mathbb{R}^d$). Le problème de Dirichlet discret est étudié en détail dans le livre de Gregory Lawler [Law13]. Le problème de Dirichlet possède une version à temps et espace continus, étudiée dans le chapitre 24, qui est une limite d'échelle du problème de Dirichlet discret. Au niveau du processus, la marche aléatoire simple symétrique devient le mouvement brownien grâce au théorème limite central, tandis qu'au niveau du générateur, le laplacien discret devient l'opérateur différentiel laplacien grâce à une formule de Taylor. Le champ libre gaussien constitue un objet fondamental en physique mathématique, abordé par exemple dans le livre de James Glimm et Arthur Jaffe [GJ87], tandis que sa limite d'échelle est présentée dans l'article [She07] de Scott Sheffield.

Le modèle de battage de cartes étudié dans ce chapitre, bien que peu réaliste, a le mérite de mener très simplement au phénomène important de convergence abrupte à l'équilibre, commun à la plupart des manières de mélanger les cartes qui ont été étudiées, comme par exemple le « riffle shuffle» :
on coupe le paquet en deux et on fusionne les deux sous-paquets en intercalant leurs cartes. La convergence abrupte dans les battages de cartes fait partie plus généralement du thème de la convergence à l'équilibre des chaînes de Markov, très étudié par Persi Diaconis et ses collaborateurs, et brillamment présenté dans les livres de David Aldous et James Fill [AF01] et de David Levin, Yuval Peres, et Elizabeth Wilmer [LPW09].

Le collectionneur de coupons intervient également dans l'analyse de la
marche aléatoire sur l'hypercube (section 9.1) qui constitue un exemple re-
marquable de marche aléatoire sur un graphe régulier. Il est également possible
de définir des marches aléatoires sur des graphes orientés ou non plus géné-
raux, en considérant, pour chaque sommet, une loi sur ses voisins. Ces marches
constituent des chaînes de Markov. Réciproquement, toute chaîne de Markov
d'espace d'états au plus dénombrable peut être vue comme une marche aléa-
toire sur son graphe squelette. L'algorithme PageRank de Google est basé sur
une marche aléatoire sur le graphe orienté des pages web. Un autre exemple
classique est celui de la marche aléatoire sur le graphe de Cayley d'un groupe
finiment engendré. On peut enfin définir une marche aléatoire sur un groupe
en utilisant des «incréments» i.i.d.
# Branchement et processus de Galton-Watson

**Mots-clés.** Arbre aléatoire; branchement; généalogie; dynamique de population; phénomène de seuil.

**Outils.** Fonction génératrice; transformée de Laplace; martingale; chaîne de Markov; marche aléatoire.

## Difficulté. *

Les processus de branchement constituent une classe importante présente dans un grand nombre de situations probabilistes. Ce chapitre est une introduction au processus de branchement de Galton-Watson, qui joue un rôle presque aussi important que les marches aléatoires au sein des probabilités.

Le processus de Galton-Watson décrit l'évolution d'une population asexuée au fil de générations qui ne se recoupent pas. Soit $P := p_0\delta_0 + p_1\delta_1 + \dots$ une loi sur $\mathbb{N}$ appelée *loi de reproduction*. On passe de la génération $n$ à la génération $n+1$ comme suit : tous les individus de la génération $n$ donnent indépendamment un nombre aléatoire d'enfants de loi $P$ puis meurent. Si $Z_n$ désigne le nombre d'individus de la génération $n \in \mathbb{N}$, alors $Z_0$ représente la taille de la population initiale et $Z_{n+1}$ vérifie l'équation de récurrence

$$Z_{n+1} = \sum_{k=1}^{Z_n} X_{n+1,k}$$

où $(X_{n,k})_{n \ge 1, k \ge 1}$ sont des variables aléatoires i.i.d. de loi $P$, indépendantes de $Z_0$. On adopte la convention $\sum_{\emptyset} = 0$ de sorte que si $Z_n = 0$ alors $Z_{n+1} = 0$. Pour tous $n \in \mathbb{N}$ et $z_0, \dots, z_n \in \mathbb{N}$, on a

$$\mathrm{Loi}(Z_{n+1} | Z_0 = z_0, \dots, Z_n = z_n) = \mathrm{Loi}(Z_{n+1} | Z_n = z_n) = P^{*z_n}.$$

La suite $(Z_n)_{n \ge 0}$ est donc une chaîne de Markov d'espace d'états $\mathbb{N}$ et de noyau de transition $\mathbf{P}$ donné pour tout $z \in \mathbb{N}$ par
$$P(z, \cdot) = P^{*z}.$$

L'état 0 est absorbant (extinction de population). Le temps d'extinction est

$$T := \inf\{n \ge 0 : Z_n = 0\} \in \mathbb{N} \cup \{\infty\}.$$

**Remarque 3.1** (Motivations initiales). *L'une des motivations initiales de ce modèle était d'estimer la probabilité de survie de la lignée masculine d'une famille, et ceci explique sans doute le fait que le modèle soit asexué.*

**Remarque 3.2** (Arbre de Galton-Watson). *La suite $(Z_n)_{n \ge 0}$ issue de $Z_0 = 1$ se représente comme un arbre aléatoire dont la loi de branchement est $P$. La variable $Z_n$ est le nombre de noeuds de profondeur $n$. Un arbre r-naire correspond à $P = \delta_r$ mais on prendra garde au fait qu'il ne s'agit pas d'un graphe r-régulier car la racine (ancêtre général) possède r voisins tandis que tous les autres sommets (descendants de l'ancêtre général) possèdent $r+1$ voisins. L'arbre a pour profondeur ou hauteur $T = \inf\{n \in \mathbb{N} : Z_n = 0\}$, pour largeur $\max_{n \in \mathbb{N}} Z_n$, et pour taille totale $N = Z_0 + \dots + Z_{T-1}$. L'arbre de la figure 3.2 est de profondeur 3, largeur 5, et taille totale 12. Lorsque $Z_0 > 1$, on parle parfois de forêt aléatoire.*

On effectue à présent les observations suivantes :

- Le comportement de $(Z_n)_{n \ge 0}$ se ramène au cas $Z_0 = 1$ car conditionnellement à $\{Z_0 = z\}$, la suite $(Z_n)_{n \ge 0}$ a la loi de la somme de $z$ copies i.i.d. partant de 1. C'est la propriété de branchement :

$$Z^{(x+y)} \stackrel{\text{loi}}{=} Z^{(x)} + Z^{(y)}$$

où $Z^{(x)}$ et $Z^{(y)}$ sont indépendants;

- Si $p_z = 1$ pour un $z \in \mathbb{N}$ alors $P = \delta_z$ d'où, pour tout $n \ge 0$,

$$Z_{n+1} = zZ_n = \dots = z^{n+1}Z_0;$$

- Si $p_0 = 0$ et $p_1 < 1$ alors $P(Z_n \uparrow \infty | Z_0 = 1) = 1$ en comparant à un jeu de pile ou face;

- Si $p_0 + p_1 = 1$ et $p_0 \ne 0$, alors $P(Z_n \searrow 0 | Z_0 = 1) = 1$ en comparant à un jeu de pile ou face, et le temps d'extinction $T$ est géométrique.

Ces observations nous conduisent à supposer que dans toute la suite :

$$Z_0 = 1 \text{ et } 0 < p_0 \le p_0 + p_1 < 1.$$

Ceci implique que $p_z < 1$ pour tout $z \in \mathbb{N}$. Ceci implique aussi que $Z_1 \sim P$ car $Z_0 = 1$. Dans toute la suite, on note $m := p_1 + 2p_2 + \dots$ la moyenne de $P$ lorsqu'elle existe, et $\sigma^2 \in \bar{\mathbb{R}}_+$ la variance de $P$ lorsque $m$ existe.

## 3.1 Extinction et phénomène de seuil

Nous commençons par les deux premiers moments de $Z_n$.
**Théorème 3.3** (Moyenne et variance).

— si m existe alors $E(Z_n) = m^n$ pour tout $n \ge 0$;

— si m existe et si $\sigma^2 < \infty$ alors pour tout $n \ge 0$,

$$ \mathrm{Var}(Z_n) = \begin{cases} \sigma^2 m^{n-1} \frac{(m^n - 1)}{m-1} & \text{si } m \neq 1; \\ n\sigma^2 & \text{si } m = 1. \end{cases} $$

*Démonstration.* La formule de l'espérance découle de $E(Z_{n+1} | Z_n) = mZ_n$ et $Z_0 = 1$. Pour la variance, $E(Z_{n+1}^2 | Z_n) = Z_n(\sigma^2 + m^2) + Z_n(Z_n - 1)m^2$ donne

$$ E(Z_{n+1}^2) = E(Z_n)(\sigma^2 + m^2) + (E(Z_n^2) - E(Z_n))m^2, $$

et un calcul conduit alors à la récurrence $\mathrm{Var}(Z_{n+1}) = \mathrm{Var}(Z_n)m^2+m^n\sigma^2$. $\square$

Le comportement asymptotique de la taille moyenne $E(Z_n) = m^n$ ne dépend que du paramètre $m$ et révèle un phénomène de seuil autour de la valeur critique $m = 1$. On adopte tout naturellement la terminologie suivante polarisée par le paramètre $m$ :

— cas sous-critique : $m < 1$,

$$ E(Z_n) \searrow 0 \quad \text{avec} \quad \mathrm{Var}(Z_n) \to 0 \quad \text{si } \sigma^2 < \infty; $$

— cas critique : $m = 1$,

$$ E(Z_n) = 1 \quad \text{avec} \quad \mathrm{Var}(Z_n) \to \infty \quad \text{si } \sigma^2 < \infty; $$

— cas sur-critique : $m > 1$,

$$ E(Z_n) \nearrow \infty \quad \text{avec} \quad \mathrm{Var}(Z_n) \to \infty \quad \text{si } \sigma^2 < \infty. $$

Les formules pour l'espérance $E(Z_n)$ et la variance $\mathrm{Var}(Z_n)$ de $Z_n$ peuvent être obtenues en utilisant une fonction générateur. Rappelons que la fonction générateur $g : [0, 1] \mapsto [0, 1]$ de la loi $P$ est la série entière réelle

$$ g(s) = E(s^{X_{1,1}}) = \sum_{z=0}^{\infty} p_z s^z. $$

Si $P$ a un moment d'ordre $r$ alors

$$ \lim_{s \to 1} g^{(r)}(s) = E(X_{1,1}(X_{1,1} - 1) \cdots (X_{1,1} - r + 1)) $$

(moment factoriel d'ordre $r$ de $P$), en particulier

$$ g'(1^{-}) = m \quad \text{et} \quad g''(1^{-}) = \sigma^2 + m^2 - m. $$

**Théorème 3.4** (Fonction générateur de $Z_n$). Pour tout $n \ge 1$ la fonction générateur $g_n$ de $Z_n$ vérifie $g_n = g^{\circ n} := \underbrace{g \circ \cdots \circ g}_{n \text{ fois}}$.
Démonstration. On a $g_1 = g$ car $Z_0 = 1$. Pour tout $n \ge 1$ et tout $s \in [0, 1]$,

$$ 
\begin{aligned}
g_{n+1}(s) &= \mathrm{E}(s^{Z_{n+1}}) = \mathrm{E}(\mathrm{E}(s^{Z_{n+1}}|Z_n)) \\
&= \mathrm{E}((\mathrm{E}(s^{X_{1,1}}))^{Z_n}) = \mathrm{E}(g(s)^{Z_n}) = g_n(g(s)).
\end{aligned}
$$

□

**Remarque 3.5** (Liens entre Galton-Watson et Wright-Fisher). *Considérons le cas où la loi de reproduction P est une loi de Poisson Poi(λ). Pour tout entier N ≥ 1 fixé, la loi de (X̄<sub>1,1</sub>, ..., X̄<sub>1,N</sub>) sachant que X̄<sub>1,1</sub> + ... + X̄<sub>1,N</sub> = N est la loi multinomiale Mul(N, (1/N, ..., 1/N)). En effet, pour (k<sub>1</sub>, ..., k<sub>N</sub>) dans N<sup>N</sup> tels que k<sub>1</sub> + ... + k<sub>N</sub> = N, la probabilité*

$$ P(X_{1,1} = k_1, \dots, X_{1,N} = k_N | X_{1,1} + \dots + X_{1,N} = N) $$

est égale à (puisque $X_{1,1} + \dots + X_{1,N}$ suit la loi de Poisson de paramètre $\lambda N$)

$$ \frac{\mathrm{P}(X_{1,1} = k_1, \dots, X_{1,N} = k_N)}{\mathrm{P}(X_{1,1} + \dots + X_{1,N} = N)} = \frac{N!}{k_1! \dots k_N!} $$

Ainsi, le modèle de Wright-Fisher du chapitre 12 est lié au modèle de Galton-Watson de loi de reproduction Poisson conditionné à être de taille constante (remarque 13.1). Le processus de Galton-Watson décrit l'évolution de la taille de la population, et ne dit rien à l'échelle individuelle. Réciproquement, si $(Y_1, \dots, Y_N)$ suit la loi multinomiale Mul$(N, (1/N, \dots, 1/N))$ alors pour tout $k \ge 1$ fixé, $(Y_1, \dots, Y_k)$ converge en loi quand $N \to \infty$ vers la loi produit Poi$(1)^{\otimes k}$, ce qui indique que les individus dans un processus de Wright-Fisher de grande taille ont tendance à faire des enfants de manière poissonnienne et indépendante les uns des autres.

**Théorème 3.6** (Dichotomie). *Presque sûrement, soit le processus s'éteint :*

$$ \lim_{n \to \infty} Z_n = 0 $$

soit il tend vers l'infini (explosion) :

$$ \lim_{n \to \infty} Z_n = \infty. $$

Autrement dit, presque sûrement

$$ \lim_{n \to \infty} Z_n = \begin{cases} \infty & \text{si } T = \infty; \\ 0 & \text{si } T < \infty. \end{cases} $$

Démonstration. Comme $p_0 > 0$, on a $\mathbf{P}(z, 0) = p_0^z > 0$ pour tout $z \in \mathbb{N}^*$, et comme 0 est absorbant, on en déduit que tout $z \in \mathbb{N}^*$ est transitoire. Or presque sûrement, la chaîne ne visite qu'un nombre fini de fois chaque état transitoire, et donc presque sûrement, soit la chaîne est capturée par l'état absorbant 0 soit elle diverge vers l'infini. Autrement dit, p.s. le processus finit par sortir, en temps suffisamment grand, de tout intervalle fini de $\mathbb{N}^*$. □
Le théorème 3.6 suggère d'étudier la probabilité d'extinction $\mathbb{P}(T < \infty)$.

**Théorème 3.7 (Probabilité d'extinction du processus).** La probabilité d'extinction $\mathbb{P}(T < \infty)$ est point fixe de g. Si $m \le 1$ alors g possède un unique point fixe, égal à 1, et $\mathbb{P}(T < \infty) = 1$. Si $m > 1$ alors g possède deux points fixes, $s \in ]0, 1[$ (attractif) et $1$ (répulsif) et $\mathbb{P}(T < \infty) = s$.

*Démonstration.* Comme $Z_n$ est entière, on a

$$ \{T < \infty\} = \{\lim_{n \to \infty} Z_n = 0\} = \cup_{n \ge 0} \{Z_n = 0\}. $$

La suite $(\{Z_n = 0\})_{n \ge 0}$ est croissante et la probabilité d'extinction vérifie

$$ \mathbb{P}(T < \infty) = \mathbb{P}(\lim_{n \to \infty} Z_n = 0) = \mathbb{P}(\cup_{n \ge 0} \{Z_n = 0\}) = \lim_{n \to \infty} \mathbb{P}(Z_n = 0). $$

Or du théorème 3.4 on tire $\mathbb{P}(Z_n = 0) = g_n(0) = g^{\circ n}(0)$ et donc

$$ \mathbb{P}(T < \infty) = \lim_{n \to \infty} g_n(0) = \lim_{n \to \infty} g^{\circ n}(0). $$

La probabilité d'extinction $\rho := \mathbb{P}(T < \infty) = \lim_{n \to \infty} g^{\circ n}(0)$ vérifie $g(\rho) = \rho$ car $g: [0, 1] \to [0, 1]$ est continue. La fonction $g$ est convexe car

$$ g''(s) = \sum_{z=0}^{\infty} (z+2)(z+1)s^z p_{z+2}. $$

Comme $p_0 + p_1 < 1$, la fonction $g$ est en fait strictement convexe (elle est affine lorsque $p_0 + p_1 = 1$). D'autre part, $g(0) = p_0 \in ]0, 1[$ et $g(1) = 1$. Par conséquent, si $g'(1^-) = m \le 1$ alors le graphe de $g$ est au-dessus de la première bissectrice et $1$ est le seul point fixe. Si $g'(1^-) = m > 1$ alors le graphe de $g$ traverse une et une seule fois la première bissectrice sur l'intervalle $]0, 1[$ et $g$ admet un second point fixe $s \in ]0, 1[$. Reste à observer que si $m > 1$ alors $g'(1^-) = m > 1$ et donc $1$ n'est pas un point fixe attractif. La figure 3.1 illustre des cas particuliers tirés des exemples 3.8 et 3.9. $\square$

**Exemple 3.8 (Reproduction poissonnienne).** Si $P = \text{Poi}(\lambda)$ alors $m = \lambda$ et $g(s) = e^{\lambda(s-1)}$ et donc si $\lambda \le 1$ alors la population s'éteint presque sûrement tandis que si $\lambda > 1$ alors la probabilité d'extinction $s$ est l'unique solution sur $]0, 1[$ de l'équation $\lambda = \log(s)/(s-1)$.

**Exemple 3.9 (Reproduction géométrique).** Si $P = \text{Geo}_N(p) = \sum_{n \ge 0} q^n p \delta_n$ alors $m = q/p$ et $g(s) = p/(1-sq)$ et donc si $p \ge 1/2$ alors la population s'éteint presque sûrement tandis que si $p < 1/2$ alors la probabilité d'extinction $s$ est l'unique solution sur $]0, 1[$ de l'équation $qs^2 - s + p = 0$. Un petit calcul fort agréable donne $s = p/q$.

On a donc la classification suivante d'après le théorème 3.7 :

— sous-critique ($m < 1$) : la population s'éteint presque sûrement;
<figure><img src="image_11.png" /><figcaption>**Fig. 3.1.** En pointillés, la fonction génératrice de la loi géométrique de paramètre 1/4 (deux points fixes : 1/3, attractif, et 1, répulsif) ainsi que celle de la loi de Poisson de paramètre 1 (unique point fixe en 1). La ligne continue est la première bissectrice.</figcaption></figure>

— critique ($m = 1$) : la population s'éteint presque sûrement ;

— sur-critique ($m > 1$) : la population s'éteint avec probabilité $p \in ]0, 1[$.

Pour étudier plus finement ($Z_n$)$_{n \ge 0}$, on introduit ($Y_n$)$_{n \ge 0}$ définie par

$$Y_n = \frac{Z_n}{\mathbb{E}(Z_n)} = \frac{Z_n}{m^n}.$$

Son utilité vient du fait que c'est une martingale pour la filtration naturelle :

$$\mathbb{E}(Y_{n+1} | \sigma(Y_0, \dots, Y_n)) = \frac{\mathbb{E}(X_{n+1,1} + \dots + X_{n+1,Z_n} | Z_n)}{m^{n+1}} = \frac{mZ_n}{m^{n+1}} = Y_n.$$

On a $\mathbb{E}(Y_n) = 1$. Comme $(Y_n)_{n \ge 0}$ est une martingale positive, elle converge presque sûrement vers une v.a.r. positive et intégrable $Y_\infty$, et donc en particulier $Y_\infty < \infty$ p.s. Sur l'événement $\{Y_\infty > 0\}$ on a $Z_n \sim_{n \to \infty} m^n Y_\infty$ p.s.

Comme $Y_n = 0$ si $n \ge T$, on obtient $\{T < \infty\} \subset \{Y_\infty = 0\}$ presque sûrement. D'après le théorème 3.7, dans le cas sous-critique ($m < 1$) et critique ($m = 1$), on a $\mathbb{P}(T < \infty) = 1$, d'où $\mathbb{P}(Y_\infty > 0) = 0$. Néanmoins, toujours si $m \le 1$ alors $\sup_{n \ge 0} \frac{Z_n}{m^n}$ n'est pas intégrable, car sinon, par convergence dominée, on aurait $0 = \mathbb{E}(Y_T) = \mathbb{E}(\lim_{n \to \infty} Y_n) = \lim_{n \to \infty} \mathbb{E}(Y_n) = 1$.

**Remarque 3.10** (Martingales). Il est possible de retrouver une partie du théorème 3.7 en utilisant les martingales. En effet, si $m < 1$, alors

$$Y_n \ge Y_n 1_{\{T=\infty\}} \ge m^{-n} 1_{\{T=\infty\}}$$
car $Z_n \ge 1$ si $n < T$, et par conséquent

$$1 = \mathbb{E}(Y_0) = \mathbb{E}(Y_n) \ge m^{-n} \mathbb{P}(T = \infty),$$

d'où $\mathbb{P}(T < \infty) = 1$. Lorsque $m = 1$, on a $Z_n = Y_n \to Y_\infty < \infty$ p.s. d'où $Z_n \not\to \infty$ p.s. d'où $\mathbb{P}(T < \infty) = 1$ (théorème 3.6). Supposons à présent que $m > 1$, et notons $s$ le plus petit point fixe de $g$. La suite

$$(s^{Z_n})_{n \ge 0}$$

est une martingale à valeurs dans $[0, 1]$. Comme $Z_n \to \infty$ p.s. sur $\{T = \infty\}$ (théorème 3.6) et $Z_n = 0$ si $n \ge T$, et comme $0 < s < 1$, il vient

$$s^{Z_n} = s^{Z_n} \mathbb{1}_{\{T=\infty\}} + s^{Z_n} \mathbb{1}_{\{T<\infty\}} \xrightarrow{n \to \infty} \mathbb{1}_{\{T<\infty\}}.$$

Par convergence dominée on obtient $s = \mathbb{E}(s^{Z_0}) = \mathbb{E}(s^{Z_n}) \to \mathbb{P}(T < \infty)$.

## 3.2 Étude des trois cas possibles

### Cas sous-critique

Si $m < 1$ alors $\mathbb{P}(T < \infty) = 1$ et $Z_n = Z_{n \wedge T} \to Z_T = 0$ p.s. (théorème 3.7) et $\mathbb{E}(Z_n) = m^n \to 0$ et $\mathrm{Var}(Z_n) \to 0$ si $\sigma^2 < \infty$ (théorème 3.3).

**Théorème 3.11** (de Yaglom). Si $m < 1$ alors $\mathrm{Loi}(Z_n | Z_n > 0)$ converge lorsque $n \to \infty$ vers une loi $\mu$ sur $\mathbb{N}^*$ dont la fonction génératrice h vérifie

$$(h-1) \circ g = m(h-1).$$

*Démonstration.* Soit $h_n$ la fonction génératrice de $\mu_n := \mathrm{Loi}(Z_n | Z_n > 0)$. La suite $(h_n(1))_{n \ge 1}$ est constante et égale à 1 et converge donc vers $h(1) := 1$. Pour tout $s \in [0, 1[$, on a

$$1 - h_n(s) = 1 - \frac{\mathbb{E}(s^{Z_n} \mathbb{1}_{\{Z_n > 0\}})}{\mathbb{P}(Z_n > 0)} = 1 - \frac{\mathbb{E}(s^{Z_n}) - \mathbb{P}(Z_n = 0)}{\mathbb{P}(Z_n > 0)} = \frac{1 - g_n(s)}{1 - g_n(0)}$$

car $\mathbb{P}(Z_n > 0) = 1 - \mathbb{P}(Z_n = 0) = 1 - g_n(0)$. On rappelle que $g_{n+1} = g \circ g_n$, et que $g_n(s) \to 1$ et $g_n(0) \to 1$ quand $n \to \infty$ car 1 est l'unique point fixe de $g$ car $m < 1$ (théorème 3.7). Comme les fonctions $g_n$ et

$$s \mapsto r(s) := \frac{1 - g(s)}{1 - s}$$

sont croissantes sur $[0, 1[$, on a

$$\frac{1 - h_{n+1}(s)}{1 - h_n(s)} = \frac{1 - g_{n+1}(s)}{1 - g_n(s)} \frac{1 - g_n(0)}{1 - g_{n+1}(0)} = \frac{r(g_n(s))}{r(g_n(0))} \ge 1.$$
Par conséquent, la suite positive $(1-h_n(s))_{n \ge 1}$ est croissante, et comme elle est majorée par 1, elle converge vers une limite $1-h(s)$. On a

$$1 - h_n(g(s)) = \frac{1 - g_{n+1}(0)}{1 - g_n(0)} \frac{1 - g_{n+1}(s)}{1 - g_{n+1}(0)}.$$

Comme $g_n(0) \nearrow \mathbb{P}(T < \infty) = 1$ on en déduit que

$$\frac{1 - g_{n+1}(0)}{1 - g_n(0)} = \frac{g(1) - g(g_n(0))}{g(1) - g_n(0)} \rightarrow g'(1) = m.$$

Donc $(1-h) \circ g = m(1-h)$ sur $[0, 1[$ et donc sur $[0, 1]$. Reste à établir que $h$ est la fonction génératrice d'une loi $\mu$ sur $\mathbb{N}^*$ et que $(\mu_n)_{n \ge 1}$ converge (étroitement) vers $\mu$. Comme $(h_n)_{n \ge 1}$ converge ponctuellement sur $[0, 1[$ vers $h$, il est bien classique d'établir que $\mu_n(z)$ converge vers une limite $\mu(z) \in [0, 1]$ pour tout $z \in \mathbb{N}^*$, dont la fonction génératrice est égale à $h$ sur $[0, 1[$. Le fait que la sous-probabilité $\mu$ est une loi de probabilité peut se déduire de l'équation fonctionnelle vérifiée par $h$ en considérant la limite en 1. $\square$

## Cas critique

Si $m = 1$ alors $\mathbb{P}(T < \infty) = 1$ et $Z_n = Z_{n \wedge T} \rightarrow Z_T = 0$ p.s. (théorème 3.7) et $\mathbb{E}(Z_n) = 1$ et $\text{Var}(Z_n) \rightarrow \infty$ si $\sigma^2 < \infty$ (théorème 3.3). La «largeur» de l'arbre $\sup_{n \ge 0} Z_n$ n'est pas intégrable car cela entraînerait par convergence dominée que $1 = \lim_{n \rightarrow \infty} \mathbb{E}(Z_n) = \mathbb{E}(\lim_{n \rightarrow \infty} Z_n) = 0$ ce qui est absurde. Les arbres critiques sont donc souvent très larges mais leur profondeur est finie p.s. : une folie des grandeurs passagère rattrapée irrémédiablement par un manque de fertilité. Le cas est critique ! Notons par ailleurs que si $m = 1$ alors $(Z_n)_{n \ge 0} = (Y_n)_{n \ge 0}$ et on retrouve au passage que $Y_\infty = 0$ p.s.

**Théorème 3.12 (Cas critique).** Si $m = 1$ et $\sigma^2 < \infty$ alors

$$1. \lim_{n \to \infty} n \mathbb{P}(Z_n > 0) = 2\sigma^{-2}$$

$$2. \lim_{n \to \infty} \frac{1}{n} \mathbb{E}(Z_n | Z_n > 0) = \frac{1}{2} \sigma^2$$

$$3. \text{Loi}(n^{-1}Z_n | Z_n > 0) \text{ converge quand } n \rightarrow \infty \text{ vers la loi } \text{Exp}(2\sigma^{-2}).$$

Le 2. n'est pas une conséquence directe du 3. car la convergence en loi n'entraîne pas la convergence des moments, en particulier n'entraîne pas la convergence des espérances. Un contre-exemple est fourni par $(Z_n)_{n \ge 1}$ qui converge p.s. vers 0 donc en loi vers $\delta_0$ mais $1 = \mathbb{E}(Z_n)$ ne converge pas vers la moyenne de $\delta_0$ qui est 0. Le théorème affirme cependant qu'il y a convergence de l'espérance de $n^{-1}Z_n$ vers l'espérance $2\sigma^{-2}$ de la limite en loi de $n^{-1}Z_n$. La convergence en distance de Wasserstein d'ordre $p$ est équivalente à la convergence en loi ainsi que la convergence des moments jusqu'à l'ordre $p$. La convergence des moments joue un rôle important dans la preuve du théorème de Wigner du chapitre 21.
Démonstration. On a

$$
n\mathbb{P}(Z_n > 0) = n(1 - g_n(0)) = \left( \frac{1}{n} \left( \frac{1}{1 - g_n(0)} - 1 \right) + \frac{1}{n} \right)^{-1}.
$$

La formule de Taylor avec reste intégral en 1 à l'ordre 2 donne

$$
g(s) = s + \frac{1}{2}(1-s)^2\sigma^2 + (1-s)^2\alpha(s)
$$

avec $\alpha$ bornée sur $[0, 1]$ et $\lim_{s \to 1} \alpha(s) = 0$. Il en découle que

$$
\begin{align*}
\frac{1}{1-g(s)} - \frac{1}{1-s} &= \frac{g(s)-s}{(1-g(s))(1-s)} \\
&= \frac{\frac{1}{2}\sigma^2 + \alpha(s)}{1 - \frac{1}{2}(1-s)\sigma^2 - (1-s)\alpha(s)} = \frac{\sigma^2}{2} + \beta(s)
\end{align*}
$$

où $\beta$ est comme $\alpha$. Comme $(g_k)_{k \ge 1}$ converge uniformément vers 1, il vient

$$
\lim_{n \to \infty} \frac{1}{n} \left( \frac{1}{1 - g_n(s)} - \frac{1}{1 - s} \right) = \lim_{n \to \infty} \frac{1}{n} \sum_{k=0}^{n-1} \left( \frac{1}{1 - g_k(s)} - \frac{1}{1 - g_k(s)} \right) = \frac{\sigma^2}{2}
$$

uniformément pour tout $s \in [0, 1[$. De même, comme $Z_n 1_{\{Z_n>0\}} = Z_n$, on a

$$
\mathrm{E}(n^{-1}Z_n | Z_n > 0) = \frac{\mathrm{E}(Z_n 1_{\{Z_n > 0\}})}{n\mathrm{P}(Z_n > 0)} = \frac{\mathrm{E}(Z_n)}{n(1 - g_n(0))} \to \frac{\sigma^2}{2}.
$$

Toujours de la même manière, on a pour tout $t \in \mathbb{R}_+^*$, en notant $s_n = e^{-t/n}$,

$$
\begin{align*}
\mathrm{E}(e^{-t \frac{1}{n} Z_n} | Z_n > 0) &= \frac{\mathrm{E}(s_n^{Z_n} 1_{\{Z_n > 0\}})}{\mathrm{P}(Z_n > 0)} \\
&= \frac{g_n(s_n) - g_n(0)}{1 - g_n(0)} = 1 - \frac{1 - g_n(s_n)}{1 - g_n(0)}
\end{align*}
$$

que l'on peut encore écrire

$$
1 - \frac{1}{n(1 - g_n(0))} \left( \frac{1}{n} \left( \frac{1}{1 - g_n(s_n)} - \frac{1}{1 - s_n} \right) + \frac{1}{n(1 - s_n)} \right)^{-1}
$$

On obtient donc

$$
\begin{align*}
\mathrm{E}(e^{-t \frac{1}{n} Z_n} | Z_n > 0) &\rightarrow 1 - \frac{\sigma^2}{2} \left( \frac{\sigma^2}{2} + \frac{1}{t} \right)^{-1} \\
&= \frac{1}{1 + \frac{\sigma^2}{2} t} \\
&= \frac{2}{\sigma^2} \int_0^\infty e^{-tx} e^{-\frac{2}{\sigma^2} x} dx.
\end{align*}
$$

□
Cas sur-critique

Si $m > 1$ alors $0 < \mathbb{P}(T < \infty) < 1$ (théorème 3.7) avec $Z_n \to 0$ sur l'événement $\{T < \infty\}$ et $Z_n \to \infty$ sur $\{T = \infty\}$ (théorème 3.6). D'autre part $\mathbb{E}(Z_n) = m^n \to \infty$ et $\mathrm{Var}(Z_n) \to \infty$ si $\sigma^2 < \infty$ (théorème 3.3). Enfin, si $m > 1$, on sait que sur $\{T < \infty\}$ on a $Z_n \to 0$ tandis que sur $\{Y_\infty > 0\}$ on a $Z_n \sim_{n \to \infty} m^n Y_\infty$. On a aussi $\{T < \infty\} \subset \{Y_\infty = 0\}$ p.s. et le théorème suivant, fort agréable, affirme que cette inclusion p.s. est une égalité p.s.

**Théorème 3.13** (Explosion dans le cas sur-critique). Si $\mathbb{E}(Y_\infty) = 1$ alors $\{Y_\infty = 0\} = \{T < \infty\}$ p.s., et donc p.s.
— soit $Y_\infty = 0$ et $\lim_{n \to \infty} Z_n = 0$;
— soit $Y_\infty > 0$ et $Z_n \sim_{n \to \infty} m^n Y_\infty \nearrow +\infty$.

Démonstration. Comme $\mathbb{E}(Y_\infty) = 1$ et $Y_\infty \ge 0$ on a $\mathbb{P}(Y_\infty > 0) > 0$. Sur $\{Y_\infty > 0\}$ on a $Z_n \sim_{n \to \infty} m^n Y_\infty \to \infty$ et on retrouve $\mathbb{P}(T < \infty) < 1$. Pour établir que l'inclusion p.s. $\{Y_\infty > 0\} \subset \{T = \infty\}$ est une égalité p.s., nous allons montrer que

$$ \mathbb{P}(Y_{\infty} = 0) = \mathbb{P}(T < \infty). $$

En effet, pour tout $z \in \mathbb{N}^*$, par les propriétés de Markov et de branchement,

$$ \begin{aligned} \mathbb{P}(Y_{\infty} = 0 | Z_1 = z) &= \mathbb{P}(\lim_{n \to \infty} Y_n = 0 | Z_1 = z) \\ &= \mathbb{P}(\lim_{n \to \infty} Y_n = 0)^z = \mathbb{P}(Y_{\infty} = 0)^z, \end{aligned} $$

et comme $Z_1 \sim P$, on a $\mathbb{P}(Y_\infty = 0) = g(\mathbb{P}(Y_\infty = 0))$, et donc $\mathbb{P}(Y_\infty = 0)$ est point fixe de $g$. Or comme $\mathbb{P}(Y_\infty = 0) < 1$ on obtient $\mathbb{P}(Y_\infty = 0) = \mathbb{P}(T < \infty)$ grâce au théorème 3.7, ce qui achève la preuve. $\square$

Notons que le lemme de Fatou donne $\mathbb{E}(Y_\infty) \le \lim \inf_{n \to \infty} \mathbb{E}(Y_n) = 1$, ce qui assure que $Y_\infty$ est intégrable, mais la convergence de $(Y_n)_{n \ge 0}$ vers $Y_\infty$ n'a pas forcément lieu dans $L^1$. Enfin, le lemme de Scheffé nous dit que la convergence a lieu dans $L^1$ si et seulement si $\mathbb{E}(Y_\infty) = 1$.

**Théorème 3.14** (Loi de $Y_\infty$ dans le cas sur-critique). Si $m > 1$ et $\sigma^2 < \infty$ alors la martingale $(Y_n)_{n \ge 0}$ converge p.s. et dans $L^2$ vers une variable aléatoire $Y_\infty \ge 0$ de moyenne $\mathbb{E}(Y_\infty) = 1$ et de variance $\mathrm{Var}(Y_\infty) = \sigma^2/(m^2 - m)$. De plus, la transformée de Laplace $t \in \mathbb{R}_+ \mapsto L_\infty(t) = \mathbb{E}(e^{-tY_\infty})$ de $Y_\infty$ est caractérisée par les propriétés suivantes :

$$ L'_{\infty}(0) = -1 \quad \text{et} \quad L_{\infty}(mt) = g(L_{\infty}(t)) \quad \text{pour tout } t \in \mathbb{R}_{+}. $$

Démonstration. La martingale $(Y_n)_{n \ge 0}$ est bornée dans $L^2$ car

$$ \mathbb{E}(Y_n^2) = \frac{\mathrm{Var}(Z_n) + \mathbb{E}(Z_n)^2}{m^{2n}} = \frac{\sigma^2}{m^2 - m} - \frac{\sigma^2}{m^n(m^2 - m)} + 1 $$
(théorème 3.3) qui converge car $m > 1$. Par conséquent, $(Y_n)_{n \ge 0}$ converge p.s. et dans $L^2$ vers une v.a.r. $Y_\infty$ dont les deux premiers moments sont la limite de ceux de $Y_n$. Il est possible de procéder directement sans faire appel à un théorème de martingales, grâce au fait que la convergence $L^2$ est ici assez rapide. En effet, par le théorème 3.3 on obtient, pour tout $n, k \ge 0$,

$$E((Y_{n+k} - Y_n)^2) = \frac{\sigma^2 (1 - m^{-k})}{m^n (m^2 - m)}.$$

Comme $m > 1$, ceci montre que $(Y_n)_{n \ge 0}$ est une suite de Cauchy dans $L^2$. Comme $L^2$ est complet, elle converge vers une v.a.r. $Y_\infty \in L^2$. La série $\sum_{n=0}^\infty E((Y_n - Y_\infty)^2)$ converge également grâce à la borne géométrique en $m^{-n}$ sur $E((Y_\infty - Y_n)^2)$ obtenue en faisant $k \to \infty$. Par convergence monotone, on obtient $E(\sum_{n=0}^\infty (Y_n - Y_\infty)^2) < \infty$ et donc $(Y_n)_{n \ge 0}$ converge p.s. vers $Y_\infty$. Les deux premiers moments de $Y_\infty$ s'obtiennent facilement.

On a $L'_\infty(0) = -E(Y_\infty) = -1$. De plus, la transformée de Laplace $t \in \mathbb{R}_+ \mapsto L_n(t) = E(e^{-tY_n})$ de $Y_n$ vérifie pour tout $n \ge 0$

$$L_{n+1}(mt) = g_{n+1}(e^{-\frac{mt}{m^{n+1}}}) = g(g_n(e^{-\frac{t}{m^n}})) = g(L_n(t)),$$

d'où $\lim_{n \to \infty} L_\infty(mt) = g(L_\infty(t))$ car $L_\infty = \lim_{n \to \infty} L_n$ et $g$ est continue. $\square$

## 3.3 Taille de l'arbre en régimes critique et sous-critique

Le théorème 3.3 fournit la moyenne de la population totale au temps $n$ :

$$E(Z_0 + \cdots + Z_n) = \frac{1 - m^{n+1}}{1 - m} \mathbb{1}_{m \ne 1} + (n + 1) \mathbb{1}_{m=1}.$$

On peut obtenir une formule similaire pour la variance (exercice !). On se place dans cette section en régime critique ou sous-critique $m \le 1$. Nous savons que la population s'éteint presque sûrement, et la population totale (ou taille de l'arbre) est donc donnée par

$$N = \lim_{n \to \infty} Z_0 + \cdots + Z_n \quad (= Z_0 + \cdots + Z_{T-1}),$$

d'où, par convergence monotone,

$$E(N) = \begin{cases} \frac{1}{1-m} & \text{si } m < 1, \\ \infty & \text{si } m = 1. \end{cases}$$

Comme $Z_n \ge 1$ si $n < T$ il vient $T \le Z_0 + \cdots + Z_{T-1} = N$ d'où l'inégalité $E(T) \le E(N) = 1/(m-1)$. Dans le cas critique, la population totale $N$ est finie p.s. mais n'est pas intégrable.
Nous allons caractériser la loi de N en fonction de la loi de reproduction P. Tout d'abord, nous pouvons exploiter la propriété de branchement : comme l'individu racine donne naissance à X$_{1,1}$ arbres de Galton-Watson i.i.d., la loi de N vérifie

$$
N \stackrel{\text{loi}}{=} 1 + \sum_{i=1}^{X_{1,1}} N^{(i)}
$$

où les variables aléatoires $(N^{(i)})_{i \ge 1}$ sont i.i.d. de même loi que $N$. Cette égalité en loi permet de retrouver la formule $E(N) = (1-m)^{-1} \mathbb{1}_{m<1} + \infty \mathbb{1}_{m=1}$, et fournit plus généralement le lemme suivant.

**Lemme 3.15** (Fonction génératrice de N). Si $g$ et $f$ sont les fonctions géné-
ratrices respectives de $X_{1,1}$ et $N$, alors la fonction $f$ est solution de l'équation

$$
f(s) = s(g \circ f)(s) \quad \text{pour } s \in [0, 1].
$$

**Exemple 3.16** (Reproduction géométrique). *Si P = Geo<sub>N</sub>(p) = Σ<sub>n≥0</sub> q^n p^n δ_n avec p ≥ 1/2, alors f(s) est solution de l'équation qf(s)² - f(s) + sp = 0, et*

$$
f(s) = \frac{1 - \sqrt{1 - 4pq_s}}{2q} \quad \text{pour } s \in [0, 1].
$$

Cette équation sur la fonction génératrice n'est pas toujours facile à utili-
ser. On peut aussi exprimer la loi de N avec des convolutions de la loi P

**Théorème 3.17** (Loi de la taille de l'arbre et marche aléatoire). On a

$N \stackrel{\text{loi}}{=} T_{-1},$

où $T_{-1} := \inf\{n \ge 1 : S_n = -1\}$ est le temps d'atteinte de $-1$ d'une marche
aléatoire $(S_n)_{n \ge 0}$ sur $\mathbb{Z}$ issue de $S_0 = 0$ et d'incréments $(U_i)_{i \ge 1}$ tels que
$1 + U_i \sim P$. De plus, pour tout $n \ge 1$,

$$
P(N = n) = \frac{\mathbf{P}(n, n-1)}{n} = \frac{P^{*n}(\{n-1\})}{n}.
$$

La loi de N peut bien sûr s'obtenir par un calcul direct, sans faire appel
à l'égalité en loi. Cependant, cette si belle identité en loi permet notamment
un contrôle de la queue de distribution, ce qui s'avère utile pour l'étude du
graphe aléatoire de Erdős-Rényi par exemple, voir théorème 16.14.

Démonstration. L'idée consiste à associer bijectivement un arbre fini à une portion de trajectoire de marche aléatoire. Étant donné un arbre fini de taille $n$, on numérote ses sommets en partant de la racine (notée 1) et de gauche à droite pour des individus d'une même génération. On note ensuite $X^{(i)}$ le nombre d'enfants de l'individu $i$ et $U_i = X^{(i)} - 1$ pour $1 \le i \le n$, et on pose

$$
S_0 = 0 \quad \text{et} \quad S_{i+1} = S_i + U_{i+1} \quad \text{pour } 0 \le i \le n-1.
$$
<figure><img src="image_12.png" /><figcaption>Fig. 3.2. Arbre et marche aléatoire associée.</figcaption></figure>

La figure 3.2 donne un exemple d'association. Le mode de numérotation étant fixé, l'arbre se reconstruit aisément à partir de la trajectoire de S. La suite $(S_i)_{0 \le i \le n}$ a la loi d'une marche aléatoire d'accroissement $(U_i)_{i \ge 1}$ issue de 0 arrêtée au temps d'atteinte $T_{-1}$ de $-1$. Comme les accroissements sont de moyenne négative $m-1$ et que les sauts négatifs de la marche sont d'amplitude 1, ce temps est fini presque sûrement. Cette bijection fournit l'égalité en loi $N \stackrel{\text{loi}}{=} T_{-1}$. Enfin, la loi de $T_{-1}$ est fournie par le lemme 3.18.

**Lemme 3.18** (Principe de rotation). *Soit $(S_n)_{n \ge 0}$ une marche aléatoire issue de 0 d'incréments $(U_n)_{n \ge 1}$ i.i.d. à valeurs entières, et*

$$T_{-1} := \inf\{n \ge 1 : S_n = -1\}.$$

Alors pour tout $n \ge 1$,

$$P(T_{-1} = n) = \frac{1}{n}P(S_n = -1).$$

*Démonstration du lemme 3.18.* Soit $n \ge 1$ et $U_1, \dots, U_n$ tels que $S_n = -1$. Pour tout entier $k$, notons $\sigma(k)$ l'entier compris entre 1 et $n$ égal à $k$ modulo $n$. Pour tout $l = 1, \dots, n$, on définit $S^{(l)}$ par

$$S_0^{(l)} = 0 \quad \text{et} \quad S_{k+1}^{(l)} = S_k^{(l)} + U_{\sigma(k+1)+l}.$$

Remarquons que pour tout $l = 1, \dots, n$, $S_n^{(l)} = S_n = -1$ et que les trajectoires $S^{(n)}$ et $S$ coïncident. La figure 3.3 fournit un exemple avec $n = 8$.

La trajectoire $S$ atteint son minimum en un ou plusieurs instants. Notons $l_0$ le plus petit d'entre eux (dans l'exemple de la figure 3.3, $l_0 = 4$). Alors $S^{(l_0)}$ est la seule trajectoire parmi $S^{(1)}, \dots, S^{(n)}$ qui reste positive ou nulle jusqu'à l'instant $n-1$. On a donc bien le résultat attendu. $\square$

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>
<figure><img src="image_15.png" /><figcaption>Fig. 3.3. Une marche parmi $n$ reste positive avant d'atteindre $-1$ (ici $S^{(4)}$).</figcaption></figure>

**Exemple 3.19** (Reproduction poissonnienne). Si $P = \text{Poi}(\lambda)$ avec $\lambda < 1$, alors $U_1 \sim \text{Poi}(\lambda) * \delta_{-1}$ et, pour tout $n \ge 1$,

$$P(N = n) = e^{-\lambda n} \frac{(\lambda n)^{n-1}}{n!}$$

puisque $S_n \sim \text{Poi}(n\lambda) * \delta_{-n}$. D'autre part, la série génératrice $f$ de $N$ est solution de l'équation fonctionnelle peu commode $f(s) = s e^{\lambda(f(s)-1)}$.

## 3.4 Immigration

Le processus de Galton-Watson avec immigration $(Z_n)_{n \ge 0}$ issu de $Z_0$ est

$$Z_{n+1} := I_{n+1} + \sum_{k=1}^{Z_n} X_{n+1,k}$$

pour tout $n \ge 0$, où $(X_{n,k})_{n \ge 1, k \ge 1}$ sont i.i.d. de loi $P$ sur $\mathbb{N}$, $(I_n)_{n \ge 1}$ i.i.d. de loi $P_+$ sur $\mathbb{N}$, toutes ces variables formant avec $Z_0$ une famille indépendante. On suppose que $P$ et $P_+$ ont pour moyenne $m$ et $m_+$. On note $\sigma^2$ et $\sigma_+^2$ leur variance lorsqu'elle existe. On suppose que $Z_0 = 1$. Soit $\mathcal{F}_n$ la tribu engendrée par $Z_0, (X_{i,j})_{1 \le i \le n, j \ge 1}, I_1, \dots, I_n$. Pour tout $n \ge 0$,

$$E(Z_{n+1} | \mathcal{F}_n) = mZ_n + m_+$$

d'où on tire (récurrence linéaire) que pour tout $n \ge 1$,

$$E(Z_n) = \left(m^n + \frac{m^n - 1}{m-1} m_+\right) \mathbb{1}_{m \neq 1} + (1 + nm_+) \mathbb{1}_{m=1}.$$

Pour la variance, on a
$$
E(Z_{n+1}^2 | \mathcal{F}_n) = Z_n(\sigma^2 + m^2) + Z_n(Z_n - 1)m^2 + 2Z_n m m_+ + \sigma_+^2 + m_+^2
$$

ce qui donne

$$
\mathrm{Var}(Z_{n+1}) = \mathrm{Var}(Z_n)m^2 + \sigma^2 \mathrm{E}(Z_n) + \sigma_+^2.
$$

Si $m > 1$ alors l'espérance de $Z_n$ est d'ordre $m^n$ et sa variance d'ordre $m^{2n}$. Si $m < 1$ alors

$$
\mathrm{E}(Z_n) \rightarrow \frac{m_+}{1-m} \quad \text{et} \quad \mathrm{Var}(Z_n) \rightarrow \frac{\sigma^2 m_+}{1-m} + \frac{\sigma_+^2}{1-m^2}.
$$

Notons que $Z_n = Z_{n,0} + \sum_{k=1}^n Z_{n,k}$ où $Z_{n,0}$ est le nombre de descendants à l'instant $n$ de l'individu présent au temps 0 (processus de sans immigration!), tandis que $Z_{n,k}$ avec $1 \le k \le n$ est le nombre de descendants à l'instant $n$ des individus immigrés à l'instant $k$. Toutes ces variables sont indépendantes. On observe que $Z_{n,k}$ a la même loi que la somme de $I_k$ copies indépendantes de $Z_{n-k,0}$. Bien qu'il soit possible d'utiliser ces observations pour étudier le cas $m \le 1$, nous nous contentons par souci de simplicité du cas $m > 1$.

**Théorème 3.20** (Cas sur-critique avec immigration). Si $m > 1$ alors $(Y_n)_{n \ge 0} = (Z_n/m^n)_{n \ge 0}$ converge p.s. vers une v.a.r. $Y_\infty \ge 0$. Si de plus $\sigma < \infty$ et $\sigma_+ < \infty$ alors la convergence a également lieu dans $L^2$ et<fnref n="1" />

$$
\mathrm{E}(Y_{\infty}) = 1 + \frac{m_{+}}{m-1}.
$$

Démonstration. La suite $(Y_n)_{n \ge 0}$ est une sous-martingale pour $(\mathcal{F}_n)_{n \ge 0}$ car

$$
\mathrm{E}(Y_n | \mathcal{F}_{n-1}) = Y_{n-1} + m^{-n} m_+ \ge Y_{n-1}.
$$

On a $\mathrm{E}(Y_0) = 1$ et $\mathrm{E}(Y_n) = \mathrm{E}(Y_{n-1}) + m^{-n}m_+$ pour $n \ge 1$ d'où

$$
\mathrm{E}(Y_n) = 1 + (m^{-1} + \dots + m^{-n})m_+.
$$

Comme $m > 1$ et $Y_n \ge 0$, on obtient $\sup_n \mathrm{E}(|Y_n|) = \sup_n \mathrm{E}(Y_n) < \infty$. En tant que sous-martingale bornée dans $L^1$, la suite $(Y_n)_{n \ge 0}$ converge p.s. vers une v.a.r. $Y_\infty \ge 0$ intégrable, et la convergence a lieu dans $L^1$ si la suite est uniformément intégrable. Supposons que $\sigma < \infty$ et $\sigma_+ < \infty$ et montrons que la convergence a lieu dans $L^2$. On a

$$
\mathrm{E}(Y_n^2) = m^{-2n} \mathrm{E}(Z_n^2) = m^{-2n} \mathrm{Var}(Z_n) + m^{-2n} \mathrm{E}(Z_n)^2.
$$

Or on sait que si $m > 1$ alors l'espérance de $Z_n$ est d'ordre $m^n$ et sa variance d'ordre $m^{2n}$, d'où $\ell := \lim_{n \to \infty} \mathrm{E}(Y_n^2) < \infty$. Enfin, pour tous $n, k \ge 1$,

$$
\mathrm{E}((Y_{n+k} - Y_n)^2) = \mathrm{E}(Y_{n+k}^2) + \mathrm{E}(Y_n^2) - 2\mathrm{E}(Y_{n+k}Y_n)
$$

<footnote n="1">1. Il est également possible de calculer $\mathrm{Var}(Y_\infty)$ (exercice !).</footnote>
$$
\begin{align*}
&= E(Y_{n+k}^2) + E(Y_n^2) - 2E(E(Y_{n+k} | \mathcal{F}_n)Y_n) \\
&= E(Y_{n+k}^2) - E(Y_n^2) - 2(m^{-n-k} + \dots + m^{-n-1})m_+ E(Y_n) \\
&= \ell + o_{n \to \infty}(1) - \ell - o_{n \to \infty}(1) + o_{n \to \infty}(1).
\end{align*}
$$

Par conséquent, $(Y_n)_{n \ge 0}$ est de Cauchy dans $L^2$ et converge donc dans $L^2$. On peut aussi alternativement se contenter d'invoquer directement le théorème de convergence des martingales bornées dans $L^2$. $\square$

3.5 Pour aller plus loin

C'est vers 1875 que Francis Galton et Henri William Watson écrivent leur
article sur l'évolution du nombre de noms de familles aristocratiques anglaises.
Ils ne connaissaient sans doute pas les travaux antérieurs de Irénée-Jules Bie-
naymé sur le même sujet. L'étude du processus de Galton-Watson peut être
considérablement raffinée. Le modèle lui même peut être enrichi et modifié afin
de tenir compte de diverses situations d'intérêt : existence de sexes différents,
survance des individus à plusieurs générations, etc. L'étude des processus
de branchement au moyen de la fonction génératrice est due semble-t-il à
Stanisław Ulam, découverte effectuée à Los Alamos dans le cadre du projet
Manhattan, le processus de branchement modélisant l'évolution du nombre
de neutrons lors d'une réaction nucléaire en chaîne. On trouvera de nombreux
développements mathématiques dans les livres de Theodore Harris [Har02],
de Khrishna Athreya et Peter Ney [AN04], de Jean-François Delmas et Ben-
jamin Jourdain [DJ06], et de Patasy Haccou, Peter Jagers, et Vladimir Va-
toutin [HJV07]. Les processus de branchement ont beaucoup été étudiés par
l'école française de calcul des probabilités, notamment par Jacques Neveu,
Jean-François Le Gall, Jean Bertoin, et leurs descendants.

Dans le théorème 3.13 (explosion dans le cas critique), si $E(Y_\infty) \neq 1$ alors $E(Y_n) < 1$ grâce au lemme de Fatou. De plus Harry Kesten et Bernt P. Stigum on montré dans [KS66] que soit $P(Y_\infty = 0) = P(T < \infty)$ soit $P(Y_\infty = 0) = 1$ et les propriétés suivantes sont équivalentes :

1. $P(Y_{\infty} = 0) = P(T < \infty)$;

2. $E(Y_\infty) = 1$;

3. $(Y_n)_{n \ge 1}$ converge dans $L^1$;

4. $E(X_{1,1} \log(X_{1,1})) < \infty$ c'est-à-dire que $z \in \mathbb{N} \mapsto z \log(z) \in L^1(P)$.

Une étude du processus avec immigration se trouve dans le livre collectif [Rug01] ou encore dans le livre [AN04] de Athreya et Ney. Le théorème 3.11 de Akiva Yaglom constitue un bon point de départ pour l'étude plus générale des distributions quasi-stationnaires des processus de populations, présentée dans le survol de Sylvie Méléard et Denis Villemonais [MV12].

Le lemme 3.18 est obtenu dans un article de Aryeh Dvoretzky et Theo-
dore Motzkin [DM47]. L'expression pour la taille d'un arbre de Galton-Watson
est établie dans un article de Meyer Dwass [Dwa69] avant que le lien entre
les deux situations ne soit fait. On pourra consulter l'habilitation à diriger
des recherches [Mar04] de Jean-François Marckert ainsi que l'article de syn-
thèse autour du théorème du scrutin de Luigi Addario-Berry et Bruce Reed
[ABR08]. Au-delà du théorème 3.17, la combinatoire foisonne de bijections
entre collections d'objets de natures différentes.
<figure><img src="image_16.png" /></figure>
# Permutations, partitions, et graphes

**Mots-clés.** Loi uniforme; simulation; permutation; partition; graphe; arbre; nombres de Catalan; nombres de Bell.

**Outils.** Groupe symétrique; marche aléatoire; loi discrète.

## Difficulté. *

Ce chapitre présente des algorithmes de simulation de loi uniforme sur quelques ensembles remarquables de permutations, partitions, et graphes. La portée des concepts et techniques abordés dépasse le cadre considéré, qui a le mérite d'être élémentaire.

## 4.1 Algorithme basique pour les lois discrètes

Considérons le problème de la simulation d'une réalisation d'une loi discrète $\mu = \sum_{a \in E} \mu(a) \delta_a$ où $E$ est fini ou dénombrable. Nous pouvons numérotter les éléments de $E$ avec une bijection $\varphi : E \to \{1, 2, \dots\}$. Soit $a_k := \varphi^{-1}(k)$. Si on partitionne l'intervalle réel $[0, 1]$ en blocs de mesures de Lebesgue respectives $\mu(a_1), \mu(a_2)$, etc, par exemple en utilisant les intervalles

$$I_1 = [0, \mu(a_1)], \quad I_2 = [\mu(a_1), \mu(a_1) + \mu(a_2)], \quad \dots,$$

et si $U$ est une variable aléatoire de loi uniforme sur l'intervalle $[0, 1]$, alors $\mathbb{P}(U \in I_{\varphi(a)}) = \mu(a)$ pour tout $a \in E$. L'algorithme basique de simulation de $\mu$ est alors le suivant : on génère une réalisation $u$ de $U$, ensuite si $u \le \mu(a_1)$ alors on décide $a_1$; sinon, si $u \le \mu(a_1) + \mu(a_2)$, alors on décide $a_2$, etc. Si $F$ est la fonction de répartition de la loi $\mu \circ \varphi^{-1}$ sur $\{1, 2, \dots\} \subset \mathbb{R}$, d'inverse généralisé $F^{-1}$, alors $(\varphi^{-1} \circ F^{-1})(U) \sim \mu$. Il s'agit d'un cas spécial de la méthode de simulation par inversion. Le coût de cet algorithme est le nombre $N$ de tests utilisés. Ce nombre est aléatoire, de loi $\mu \circ \varphi^{-1}$. En particulier, $\mathbb{P}(N < \infty) = 1$, et le coût moyen est
$$E(N) = \sum_{a \in E} \varphi(a)\mu(a),$$

qui peut très bien être infini si $\mu \circ \varphi^{-1}$ n'a pas d'espérance (ne peut se produire que si $E$ est infini)! Si la numérotation $\varphi$ minimise le coût moyen $E(N)$ alors

$$\mu(a_1) \geq \mu(a_2) \geq \dots$$

Pour la loi géométrique (de moyenne quelconque) et pour la loi de Poisson (de moyenne $\le 1$), la numérotation naturelle est à poids décroissants. D'autre part, si $\text{card}(E)$ est petit, alors on peut déterminer l'ordre à poids décroissants en utilisant un algorithme de tri (qui a un coût).

Les lois discrètes usuelles (binomiale, géométrique, Poisson, etc.) sont sipmulables par divers algorithmes dédiés tirant partie de leurs propriétés spéciales. À ce sujet, signalons qu'il est possible de simuler la loi de Poisson de moyenne quelconque $\lambda$ à partir d'un générateur de la loi de Poisson de moyenne 1. Il suffit en effet d'utiliser un amincissement<fnref n="1" />. Plus précisément, on simule $\lceil \lambda \rceil$ variables aléatoires $X_1, \dots, X_{\lceil \lambda \rceil}$ i.i.d. de loi Poi(1), puis, conditionnellement à leur somme $S = X_1 + \dots + X_{\lceil \lambda \rceil}$, on simule $S$ variables aléatoires i.i.d. de loi de Bernoulli de moyenne $\lambda/\lceil \lambda \rceil$, et on tire parti du fait que $B_1 + \dots + B_S \sim \text{Poi}(\lambda)$ (mélange poissonnien de binomiales<fnref n="2" />).

Simuler la loi uniforme sur un ensemble $E$ fini peut être très simple : $\varphi^{-1}(\lceil \text{card}(E)U \rceil)$ suit cette loi ! Cependant, cet algorithme basique est impraticable lorsque $E$ est difficile à énumérer et donc $\varphi$ est difficile d'accès, ou lorsque $\text{card}(E)$ est très grand. Nous étudions par la suite des exemples de ce type faits de permutations, de partitions, et de graphes, pour lesquels nous présentons des algorithmes spécifiques efficaces et exacts.

## 4.2 Permutations aléatoires

Certaines situations nécessitent de permuter aléatoirement une liste finie d'objets : construction de plans d'expérience dans les sciences expérimentales, anonymisation, etc. Cela conduit au problème de la simulation de la loi uniforme $\sum_{\sigma \in S_n} \text{card}(S_n)^{-1}\delta_\sigma$ sur l'ensemble fini $S_n$ des permutations de $\{1, \dots, n\}$ (groupe symétrique). Or $\text{card}(S_n) = n! \sim \sqrt{2\pi n(n/e)^n}$ est un nombre à environ $n \log(n)$ chiffres, et cette réalité combinatoire disqualifie très vite l'algorithme basique de simulation des lois discrètes. Il est possible de simuler la loi uniforme sur $S_n$ en réordonnant un désordre symétrique : si $U_1, \dots, U_n$ sont des variables aléatoires i.i.d. de loi uniforme sur $[0, 1]$ et si $\sigma$ est une permutation aléatoire telle que $U_{\sigma(1)} \le \dots \le U_{\sigma(n)}$, alors $\sigma$ suit la loi uniforme sur $S_n$. La complexité est celle de l'algorithme de tri utilisé<fnref n="3" />.

<footnote n="1">1. « Thinning » en anglais.</footnote>

<footnote n="2">2. Si $X \sim \text{Poi}(\lambda)$ et $\text{Loi}(Y|X=n) = \text{Bin}(n,p)$ pour tout $n$ alors $Y \sim \text{Poi}(p\lambda)$.</footnote>

<footnote n="3">3. De l'ordre de $n \log(n)$ avec grande probabilité et $n^2$ au pire pour l'algorithme de tri rapide (« quick sort » en anglais).</footnote>
Un algorithme naïf pour simuler une permutation $\sigma$ uniforme consiste à tirer uniformément et sans remise les valeurs de $\sigma(1), \dots, \sigma(n)$ dans $\{1, \dots, n\}$. Cet algorithme d'apparence séduisante a une complexité plus élevée que celui du tri, car il faut tenir compte dans l'implémentation des éléments déjà tirés. Un bon algorithme de simulation (exacte !) de la loi uniforme sur $S_n$ est connu sous le nom d'algorithme de Fisher-Yates-Knuth<fnref n="4" />. Il nécessite $n-1$ variables aléatoires indépendantes de loi uniforme sur $\{1, 2\}, \dots, \{1, 2, \dots, n\}$ respectivement, soit de l'ordre de $\sum_{k=2}^{n} \log(k) = \log(n!) \approx n \log(n)$ bits i.i.d.

**Théorème 4.1** (Permutations et algorithme de Fisher-Yates-Knuth). *Si* $U_1, \dots, U_n$ sont des variables aléatoires indépendantes avec $U_i$ de loi uniforme sur $\{1, \dots, i\}$ pour tout $1 \le i \le n$ alors la permutation formée par le produit de transpositions aléatoires $(1, U_1) \cdots (n, U_n)$ suit la loi uniforme sur $S_n$.*

L'inversion dans $S_n$ étant bijective, et les transpositions étant leur propre inverse, il en découle que le produit renversé $(n, U_n) \cdots (1, U_1)$ suit également la loi uniforme sur $S_n$. La transposition $(1, U_1)$ est triviale (élément neutre de $S_n$) et il n'est pas nécessaire d'en tenir compte si $n \ge 2$ (elle rend cependant la formule valable pour $n = 1$). L'algorithme de Fisher-Yates-Knuth pour permuter un vecteur v s'écrit en pseudo-code :

```
for k from length(v) downto 2 do
    swap(v[ceil(k*rand)], v[k])
```

*Démonstration du théorème 4.1.* On procède par récurrence sur $n$. La propriété est triviale pour $n = 1$. Supposons qu'elle est vraie pour $n \ge 1$. Pour tout $\sigma \in S_n$, on note encore $\sigma$ l'élément de $S_{n+1}$ obtenu à partir de $\sigma$ en ajoutant le cycle $(n+1)$ (point fixe). Supposons que $\sigma_n = (1, U_1) \cdots (n, U_n)$ suit la loi uniforme sur $S_n$. Soit $U_{n+1}$ une variable aléatoire indépendante de $\sigma_n$, de loi uniforme sur $\{1, \dots, n+1\}$. Montrons que $\sigma_{n+1} = \sigma_n(n+1, U_{n+1})$ suit la loi uniforme sur $S_{n+1}$. Pour tout $\sigma \in S_{n+1}$, on a

$$ 
\begin{align*}
P(\sigma_{n+1} = \sigma) &= \sum_{i=1}^{n+1} P(\sigma_n = \sigma(n+1, i)) P(U_{n+1} = i) \\
&= \frac{1}{n+1} \sum_{i=1}^{n+1} P(\sigma_n = \sigma(n+1, i)).
\end{align*} 
$$

Comme $n+1$ est point fixe de $\sigma_n$, et n'est point fixe de $\sigma(n+1, i)$ que pour une et une seule valeur de $i$, notée $i_\sigma$, image réciproque de $n+1$ par $\sigma$, il en découle finalement que

$$ P(\sigma_{n+1} = \sigma) = \frac{1}{n+1} P(\sigma_n = \sigma(n+1, i_\sigma)) = \frac{1}{n+1} \frac{1}{n!} = \frac{1}{(n+1)!}. $$

□

<footnote n="4">4. « Fisher-Yates shuffle » ou « Knuth shuffle » en anglais.</footnote>
On dit que $\sigma \in S_n$ est un dérangement lorsqu'il n'a pas de point fixe : $\sigma(i) \neq i$ pour tout $1 \le i \le n$. Les points fixes de $\sigma$ sont les cycles de longueur 1 dans sa décomposition en cycles disjoints. La loi uniforme sur l'ensemble $\mathcal{D}_n \subset S_n$ des dérangements peut être simulée avec l'algorithme du rejet, car le rapport des cardinaux $\text{card}(\mathcal{D}_n)/\text{card}(S_n)$ est élevé.

**Théorème 4.2** (Loi uniforme sur les dérangements). Si $\sigma$ est une permutation aléatoire de loi uniforme sur $S_n$ alors

$$p_n := \mathbb{P}(\sigma \in \mathcal{D}_n) = \frac{\text{card}(\mathcal{D}_n)}{\text{card}(S_n)} \underset{n \to \infty}{\longrightarrow} \frac{1}{e} \approx 0.37.$$

Si $(\sigma_k)_{k \ge 1}$ est une suite de permutations aléatoires indépendantes et identiquement distribuées de même loi uniforme sur $S_n$ et si

$$T := \inf\{k \ge 1 : \sigma_k \in \mathcal{D}_n\}$$

alors la permutation aléatoire $\sigma_T$ suit la loi uniforme sur $\mathcal{D}_n$ et la variable $T$ suit la loi géométrique de paramètre $p_n$ d'espérance $1/p_n \underset{n \to \infty}{\longrightarrow} e \approx 2.72$.

On note parfois $!n = \text{card}(\mathcal{D}_n)$, et on a $!(n+1) = (n+1) \times !n + (-1)^{n+1}$, analogue de $(n+1)! = (n+1) \times n!$.

On peut améliorer la performance en stoppant à chaque étape de proposition l'algorithme de Fisher-Yates-Knuth dès qu'un point fixe apparaît.

**Démonstration.** Si $\sigma$ suit la loi uniforme sur $S_n$ alors $\{\sigma \notin \mathcal{D}_n\} = \cup_{i=1}^n A_i$ où $A_i = \{\sigma(i) = i\}$, et donc, grâce au principe d'inclusion-exclusion

$$\mathbb{P}(\sigma \in \mathcal{D}_n) = 1 - \mathbb{P}(\cup_{1 \le i \le n} A_i) = 1 - \sum_{p=1}^{n} (-1)^{p+1} \sum_{1 \le i_1 < \dots < i_p \le n} \mathbb{P}(A_{i_1} \cap \dots \cap A_{i_p}).$$

Or pour tout $1 \le p \le n$,

$$\sum_{1 \le i_1 < \dots < i_p \le n} \mathbb{P}(A_{i_1} \cap \dots \cap A_{i_p}) = \sum_{1 \le i_1 < \dots < i_p \le n} \frac{(n-p)!}{n!} = \binom{n}{p} \frac{(n-p)!}{n!} = \frac{1}{p!} \\ \text{d'où } \mathbb{P}(\sigma \in \mathcal{D}_n) = 1 - \sum_{p=1}^{n} \frac{(-1)^{p+1}}{p!} \to e^{-1}. \quad \square$$

## 4.3 Partitions aléatoires

Un appariement 5 de 2n points est une partition de {1, ..., 2n} en n parties de cardinal 2, chacune constituant un « couple de points appariés ». On note $\mathcal{A}_{2n}$ l'ensemble des appariements de 2n points. L'ensemble $\mathcal{A}_{2n}$ est en bijection avec l'ensemble des dérangements involutifs de {1, ..., 2n}, c'est-à-dire

<footnote n="5">5. « Matching » en anglais.</footnote>
l'ensemble des éléments de $S_{2n}$ sans point fixe et qui sont leur propre inverse, autrement dit l'ensemble des éléments de $S_{2n}$ obtenus en faisant le produit de $n$ transpositions à supports deux à deux disjoints. On a la formule d'Isserlis

$$ \mathrm{card}(\mathcal{A}_{2n}) = \frac{(2n)!}{2^n n!} $$

C'est aussi le produit des nombres impairs inférieurs ou égaux à $2n - 1$, noté $(2n - 1)!!$ (double factorielle). Le rapport $\mathrm{card}(\mathcal{A}_{2n})/\mathrm{card}(S_{2n})$ est petit, ce qui incite à trouver une alternative à la méthode de simulation par rejet. Voici donc un algorithme de simulation de la loi uniforme sur $\mathcal{A}_{2n}$.

**Théorème 4.3** (Loi uniforme sur les appariements). *Si $\sigma$ suit la loi uniforme sur $S_{2n}$ alors l'appariement aléatoire $\{\{\sigma(1), \sigma(n+1)\}, \dots, \{\sigma(n), \sigma(n+n)\}\}$ suit la loi uniforme sur $\mathcal{A}_{2n}$.*

<figure><img src="image_17.png" /><figcaption>**Fig. 4.1.** Appariement de $\{1, \dots, 6\}$ obtenu avec un élément de $S_6$ (ici $n = 3$).</figcaption></figure>

*Démonstration.* Pour tout appariement $\{\{a_1, a_{n+1}\}, \dots, \{a_n, a_{n+n}\}\}$ on a $n!$ façons de permuter les $n$ blocs et $2^n$ façons de permuter leur contenu, d'où

$$ \begin{aligned} \mathrm{P}(\{\{\sigma(1), \sigma(n+1)\}, \dots, \{\sigma(n), \sigma(n+n)\}\}) &= \{\{a_1, a_{n+1}\}, \dots, \{a_n, a_{n+n}\}\}) \\ &= 2^n n! \mathrm{P}(\sigma(1) = a_1, \dots, \sigma(2n) = a_{2n}) = \frac{2^n n!}{(2n)!} \end{aligned} $$

qui ne dépend pas de l'appariement et qui vaut précisément $1/\mathrm{card}(\mathcal{A}_{2n})$. $\square$

La décomposition en cycles d'une permutation aléatoire de loi uniforme sur $S_n$ fournit une partition aléatoire de $\{1, \dots, n\}$. La loi de cette partition n'est pas uniforme sur l'ensemble des partitions $\Pi_n$ de $\{1, \dots, n\}$ (remarque 14.6). Intéressons-nous à la simulation de la loi uniforme sur $\Pi_n$. Cette loi affecte le même poids $1/B_n$ à chaque élément de $\Pi_n$, où $B_n = \mathrm{card}(\Pi_n)$. En combinatoire, la suite $(B_n)_{n \ge 1}$ constitue les nombres de Bell. On a $B_1 = 1$, $B_2 = 2$, et plus généralement, en utilisant la convention $B_0 = 1$, on a la formule de récurrence triangulaire

$$ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k, $$

où $k$ s'interprète comme le nombre d'éléments qui ne sont pas dans le bloc de $n + 1$. Il en découle que la série formelle $G(X) = \sum_{n=0}^{\infty} \frac{B_n}{n!} X^n$ vérifie
$G'(X) = \exp(X)G(X)$, d'où la formule $G(X) = \exp(\exp(X)-1)$. On reconnaît la transformée de Laplace de la loi Poi(1). Les nombres de Bell sont donc les moments de cette loi, d'où la formule dite de Dobinski :

$$B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}.$$

Elle intervient dans un algorithme de simulation de la loi uniforme sur $\Pi_n$.

**Théorème 4.4** (Algorithme de Stam). *Soit $n \ge 1$. Soit $K$ un entier aléatoire valant $k$ avec probabilité $k^n/(k!eB_n)$ pour tout $k \ge 0$. Sachant $K$, soient $C_1, \dots, C_n$ des variables aléatoires i.i.d. de loi uniforme sur $\{1, \dots, K\}$. Soit $P$ la partition aléatoire de $\{1, \dots, n\}$ obtenue en décidant que $i, j$ sont dans le même bloc ssi $C_i = C_j$. Alors $P$ suit la loi uniforme sur $\Pi_n$.*

La loi de $K$ est bien définie grâce à la formule de Dobinski. Il est commode d'interpréter $C_1, \dots, C_n$ comme des couleurs, les blocs de $P$ regroupant donc les éléments par couleur. L'entier aléatoire $K$ peut être simulé avec l'algorithme basique pour les lois discrètes.

*Démonstration.* Si $p \in \Pi_n$ possède $b$ blocs alors

$$ \begin{aligned} \mathbb{P}(P = p) &= \sum_{k=b}^{\infty} \mathbb{P}(P = p | K = k)\mathbb{P}(K = k) \\ &= \sum_{k=b}^{\infty} \frac{k(k-1)\cdots(k-b+1)}{k^n} \frac{k^n}{k!eB_n} = \frac{1}{B_n}. \end{aligned} $$

□

## 4.4 Graphes aléatoires

Dans toute cette section on pose $V = \{1, \dots, n\}$. Un graphe fini

$$G = (V, E)$$

est un couple où $E \subset \{\{i, j\} : i, j \in V, i \neq j\}$. Les éléments de $V$ sont les sommets<fnref n="6" /> du graphe tandis que les éléments de $E$ sont les arêtes<fnref n="7" /> du graphe. Il existe au plus une arête entre deux sommets distincts (absence d'arêtes multiples), et aucune entre un sommet et lui même (absence de boucles). Les arêtes ne sont pas orientées. On reprend la terminologie concernant les graphes finis introduite dans le chapitre 16 : *chemins*, *boucles*, etc. La matrice d'adjacence $A$ de $G$ est la matrice symétrique $n \times n$ définie par $A_{j,k} = \mathbb{1}_{\{j,k\} \in E}$.

<footnote n="6">6. On dit aussi *sites*, « *vertices* » en anglais, d'où la notation $V$.</footnote>

<footnote n="7">7. On dit aussi *liens* en français, et en anglais « *edges* », d'où la notation $E$.</footnote>
**Théorème 4.5** (Loi uniforme sur graphes finis). *Pour tout $n \ge 1$, la loi uniforme sur l'ensemble $\mathcal{G}_n$ des graphes finis de sommets $\{1, \dots, n\}$ s'obtient en rendant les $\binom{n}{2} = \frac{1}{2}n(n-1)$ arêtes indépendantes et identiquement distribuées de loi de Bernoulli $\text{Ber}(1/2)$.*

Un graphe aléatoire qui suit la loi uniforme sur $\mathcal{G}_n$ est appelé graphe aléatoire de Erdős-Rényi de taille $n$ et de paramètre $p = \frac{1}{2}$.

*Démonstration.* L'ensemble $\mathcal{G}_n$ est en bijection avec l'ensemble des matrices $n \times n$ symétriques à coefficients dans $\{0,1\}$ et à diagonale nulle, lui même en bijection avec l'ensemble produit $\{0,1\}^{n(n-1)/2}$. Or la loi uniforme sur un ensemble produit est le produit des lois uniformes sur les facteurs, et la loi uniforme sur $\{0,1\}$ est la loi de Bernoulli $\text{Ber}(1/2)$. $\square$

Dans un graphe fini $G = (V, E)$, le degré d'un sommet $i \in V$ est le nombre noté $d_i$ de sommets reliés à $i$ directement par une arête, autrement dit

$$d_i := \text{card}\{j \in V : \{i, j\} \in E\}.$$

On dit que $G$ est un graphe $d$-régulier, où $d \ge 0$ est un entier fixé, lorsque $d_i = d$ pour tout $i \in V$. Les graphes 0-réguliers sont constitués de sommets isolés et ne comportent aucune arête. Les graphes 1-réguliers sont constitués d'arêtes déconnectées les unes des autres. Les graphes finis 2-réguliers sont constitués de cycles déconnectés les uns des autres.

Si $G$ est un graphe de sommets $\{1, \dots, n\}$ de sorte que $d_1 \ge \dots \ge d_n$ alors les deux propriétés suivantes ont lieu :

1. l'entier $d_1 + \dots + d_n$ est pair;

2. pour tout $1 \le k \le n$,

$$d_1 + \dots + d_k \le k(k-1) + \min(k, d_{k+1}) + \dots + \min(k, d_n).$$

La parité de la somme vient du fait que chaque arête compte deux fois, tandis que la quantité $k(k-1) + \min(d_{k+1}, k) + \dots + \min(d_n, k)$ est la contribution maximale à $d_1 + \dots + d_k$ des arêtes liées aux sommets 1 à $k$: on a au plus $\binom{k}{2} = k(k-1)/2$ arêtes (comptent double) entre les sommets 1 à $k$, et au plus $\min(k, d_{k+i})$ arêtes entre le sommet $i > k$ et les sommets 1 à $k$.

Un théorème de Erdős-Gallai affirme que pour tous $d_1 \ge \dots \ge d_n \ge 0$, il existe un graphe à $n \ge 1$ sommets de degrés $d_1, \dots, d_n$ si et seulement si les deux conditions ci-dessus sont vérifiés. On dit que $d_1, \dots, d_n$ est la suite de degrés<fnref n="8" /> du graphe. Pour un graphe $d$-régulier de sommets $\{1, \dots, n\}$, $nd$ est pair et $d \le n-1$ (égalité atteinte pour le graphe complet).

Les multigraphes sont obtenus à partir de la définition des graphes en relaxant deux contraintes : on accepte les arêtes multiples entre sommets ainsi que les boucles. Soient $d_1 \ge \dots \ge d_n \ge 0$ des entiers vérifiant les conditions de Erdős-Gallai, et $M_{d_1, \dots, d_n}$ l'ensemble des multigraphes de sommets $\{1, \dots, n\}$

<footnote n="8">8. «Degree sequence» en anglais.</footnote>
de degrés prescrits $d_1, \dots, d_n$. Soit $\sigma \in \mathcal{A}_{2n}$ un appariement de $2n$ points. On construit un élément $M_\sigma \in \mathcal{M}_{d_1, \dots, d_n}$ à partir de $\sigma$ comme suit :

— pour tout $1 \le k \le n$, on dispose $d_k$ demi-arêtes sur le sommet $k$, soit au total $2(d_1 + \dots + d_n)$ demi-arêtes numérotées;

— on associe les $2n$ demi-arêtes en utilisant l'appariement $\sigma$.

Soit $\mathcal{G}_{d_1, \dots, d_n} \subset \mathcal{M}_{d_1, \dots, d_n}$ l'ensemble des graphes de $\mathcal{M}_{d_1, \dots, d_n}$. L'algorithme des configurations permet de simuler la loi uniforme sur $\mathcal{G}_{d_1, \dots, d_n}$ en utilisant le multigraphe $M_\sigma$ pour un appariement aléatoire $\sigma$, et la méthode du rejet.

**Théorème 4.6** (Algorithme des configurations de Bollobás). $\text{Si } (\sigma_k)_{k \ge 1} \text{ est une suite d'appariements aléatoires de loi uniforme sur } \mathcal{A}_{2n}, \text{ et si } T \text{ est le plus petit entier } k \ge 1 \text{ tel que } M_{\sigma_k} \in \mathcal{G}_{d_1, \dots, d_n} \text{ c'est-à-dire que le multigraphe } M_{\sigma_k} \text{ n'a ni arêtes multiples ni boucles, alors } T \text{ est fini presque sûrement et suit une loi géométrique, et } M_{\sigma_T} \text{ suit la loi uniforme sur } \mathcal{G}_{d_1, \dots, d_n}.$

On dit que le multigraphe aléatoire $M_{\sigma_1}$ est le modèle des configurations à degrés prescrits. Les appariements aléatoires de loi uniforme peuvent être obtenus en utilisant le théorème 4.3.

*Idée de la preuve.* Tout d'abord $\mathbb{P}(M_{\sigma_1} \in \mathcal{G}_{d_1, \dots, d_n}) > 0$ car le support de la loi de $M_{\sigma_1}$ est $\mathcal{M}_{d_1, \dots, d_n}$. L'algorithme du rejet stoppe en un temps géométrique $T$ fini presque sûrement.

On peut montrer que $M \mapsto \mathbb{P}(M_{\sigma_1} = M)$ est constante sur $\mathcal{G}_{d_1, \dots, d_n}$. Ainsi la loi conditionnelle de $M_{\sigma_1}$ sachant $\{M_{\sigma_1} \in \mathcal{G}_{d_1, \dots, d_n}\}$ est la loi uniforme sur $\mathcal{G}_{d_1, \dots, d_n}$. Or cette loi conditionnelle est la loi de $M_{\sigma_T}$ (méthode du rejet). $\square$

Notons que $M_{\sigma_1}$ ne suit pas la loi uniforme sur $\mathcal{M}_{d_1, \dots, d_n}$ car l'application $M \mapsto \mathbb{P}(M_{\sigma_1} = M)$ n'est pas constante sur $\mathcal{M}_{d_1, \dots, d_n}$ : si deux multigraphes ne diffèrent que par le nombre d'arêtes multiples entre deux sommets précis alors ils n'ont pas la même probabilité d'apparaître car ces arêtes sont indistinguishables donc permutables (idem pour les boucles).

## 4.5 Arbres aléatoires

Une structure d'arbre très courante est celle d'arbre binaire : chaque sommet possède 0 ou 2 enfants, c'est-à-dire 1 ou 3 voisins si l'arbre est vu comme un graphe. On s'intéresse à des arbres enracinés : il y a donc un nombre impair de sommets. On s'intéresse à des arbres planaires : on numérote les sommets de gauche à droite pour des individus d'une même génération, en partant de la racine, numérotée 1 et figurée en bas, comme sur la figure 4.2. On note $\mathcal{T}_n$ l'ensemble des arbres numérotés de ce type possédant $2n + 1$ sommets.

Il est possible de coder chaque élément de $\mathcal{T}_n$ par une trajectoire de la marche aléatoire simple. Plus précisément, étant donné un élément de $\mathcal{T}_n$, soit $x^{(i)}$ le nombre d'enfants du sommet $i$ et $u_i = x^{(i)} - 1$ pour $1 \le i \le 2n + 1$. On pose $s_0 = 0$ et $s_{i+1} = s_i + u_{i+1}$ pour tout $0 \le i \le 2n$. La figure 4.2 donne
un exemple d'association. On peut établir par récurrence qu'on a toujours $s_{2n+1} = -1$ et $\min(s_1, \dots, s_{2n}) \ge 0$. Grâce à la convention de numérotation, l'arbre se reconstruit aisément à partir du morceau de trajectoire $(s_i)_{1\le i\le 2n}$. On vérifie que cette construction définit une bijection entre l'ensemble $\mathcal{T}_n$ et

<figure><img src="image_18.png" /><figcaption>Fig. 4.2. Élément de $\mathcal{T}_2$ et trajectoire de la marche aléatoire associé.</figcaption></figure>

l'ensemble $\mathcal{P}_n$ des trajectoires de longueur $2n$ de la marche aléatoire simple sur $\mathbb{Z}$, valant $0$ au temps $0$ et au temps $2n$, et restant positives ou nulles entre ces deux temps. Il s'agit d'un cas particulier de la bijection de la preuve du théorème 3.17. Comme cette bijection est explicite et calculable, la simulation de la loi uniforme sur $\mathcal{T}_n$ se déduit de la simulation de la loi uniforme sur $\mathcal{P}_n$, pour laquelle on peut procéder comme suit.

**Théorème 4.7** (Algorithme de Arnold-Sleep). Soit $s = (s_i)_{0\le i\le 2n}$ le chemin aléatoire à valeurs dans $\mathcal{P}_n$ dont la loi est donnée par $s_0 = s_{2n} = 0$ et pour tout $0 \le k \le 2n-1$,

$$ 
\begin{aligned}
\mathbb{P}(s_{k+1} - s_k = -1 | s_0, \dots, s_k) &= 1 - \mathbb{P}(s_{k+1} - s_k = 1 | s_0, \dots, s_k) \\
&= \frac{s_k(2n + k + s_k + 2)}{2(2n - k)(s_k + 1)}.
\end{aligned}
$$

Alors s suit la loi uniforme sur $\mathcal{P}_n$, et donc l'arbre binaire associé suit la loi uniforme sur $\mathcal{T}_n$.

**Démonstration.** Construisons progressivement un chemin $(s_i)_{1\le i\le 2n}$ de loi uniforme sur $\mathcal{P}_n$. Supposons que $s_0, \dots, s_{2n-k}$ sont déjà construits. Le nombre de manières de prolonger ce début de trajectoire en un élément de $\mathcal{P}_n$ ne dépend que de $k$ et $r = s_{2n-k}$, et nous le notons $N(r, k)$. Le nombre de manières de le faire en commençant par un incrément $+1$ vaut $N(r+1, k-1)$, tandis que le nombre de manières de le faire en commençant par un incrément $-1$ vaut $N(r-1, k-1)$. On a donc $N(r, k) = N(r+1, k-1)+N(r-1, k-1)$, et
$$
P(s_{2n-k+1} = s_{2n-k} - 1 | s_0, \dots, s_{2n-k}) = \frac{N(r-1, k-1)}{N(r, k)} \quad \text{où} \quad r = s_{2n-k}.
$$

Le nombre $N(r, k)$ est également le nombre de chemins de la marche reliant
$(0, r)$ et $(k, 0)$ en restant positifs ou nuls. On a forcément $k \ge r$. Chaque
chemin de ce type comporte $t \ge r$ incréments $-1$ et $k - t = t - r$ incréments
+1, d'où $2t = k + r$, ce qui fait que $k + r$ est pair. En utilisant les notations
et résultats de la preuve du théorème du scrutin 2.6, il vient

$$
N(r, k) = P_{k+1, r+1}^{+} = \frac{r+1}{k+1} \binom{k+1}{t+1} = \frac{r+1}{t+1} \binom{k}{t}.
$$

Il en découle que

$$
P(s_{2n-k+1} = s_{2n-k} - 1 | s_0, \dots, s_{2n-k}) = \frac{r(k+r+2)}{2k(r+1)} \quad \text{où } r = s_{2n-k}.
$$

Enfin le changement de variable $2n-k \to k$ fournit le résultat annoncé. Notons
que si $r=k$ alors $P(s_{2n-k+1} = s_{2n-k} - 1 | s_0, \dots, s_{2n-k}) = 1$. $\square$

D'après le théorème 2.5, le cardinal de $\mathcal{P}_n$ et de $\mathcal{T}_n$ est le nombre de Catalan $C_{n-1}$. Les ensembles $\mathcal{T}_n$ et $\mathcal{P}_n$ sont également en bijection avec l'ensemble des parenthésages constitués de $n$ paires de parenthèses. Il suffit en effet de recoder la suite des incréments du chemin de la marche aléatoire par des parenthèses. Ainsi par exemple la suite d'incréments $+1, +1, -1, -1$ correspondant à la trajectoire $(s_i)_{0 \le i \le 4}$ de la figure 4.2 se traduit par le parenthésage ($\emptyset$). Cette interprétation apparaît dans la preuve du théorème de Wigner 21.9.

4.6 Pour aller plus loin

Il arrive que la structure de l'ensemble d'intérêt ne fournisse pas d'al-
gorithme séduisant de simulation de la loi uniforme, et que la méthode du
rejet à partir d'un ensemble plus gros ne soit pas praticable. Dans ce cas,
il est souvent possible d'utiliser des algorithmes markoviens comme celui de
Metropolis-Hasting ou de Propp-Wilson, abordés dans le chapitre 5.

Une analyse probabiliste de la complexité de l’algorithme de tri rapide
randomisé se trouve par exemple dans le livre de Rajeev Motwani et Prabhakar
Raghavan [MR95]. Le livre monumental de Donald Knuth [Knu05] constitue
une référence incontournable pour l’analyse des algorithmes et la simulation
de la loi uniforme sur les ensembles classiques comme les permutations ou
les partitions. C’est dans la première édition de ce livre datant des années
1960 que Knuth a popularisé l’algorithme de simulation de la loi uniforme
sur les permutations, reprenant un article antérieur de Richard Durstenfeld
[Dur64]. L’algorithme remonte en fait à Ronald Fisher et Frank Yates [FY48].
Il est implémenté en standard dans les logiciels de calcul. Cet algorithme
correspond exactement au processus des restaurants chinois du chapitre 14, et la loi uniforme sur $S_n$ coïncide avec la loi d'Ewens de paramètre $\theta = 1$.

Pour tout $n \ge 1$ fixé, la marche aléatoire sur $S_n$ dont les pas sont i.i.d. de loi uniforme sur l'ensemble des transpositions, étudiée par Persi Diaconis et Mehrdad Shahshahani [DS81], converge vers la loi uniforme sur $S_n$ de manière abrupte après environ $n \log(n)$ étapes, comme pour celle du mélange de cartes du chapitre 2. Si $\sigma \in S_n$ et $\tau = (i, j)$ est une transposition, alors la décomposition en cycles de $\sigma\tau$ s'obtient à partir de celle de $\sigma$ en fusionnant les cycles de $\sigma$ contenant $i$ et $j$ s'ils sont différents, ou bien en fissionnant le cycle de $\sigma$ contenant $i$ et $j$ dans le cas contraire. La chaîne de Diaconis et Shahshahani, traduite sur $\Pi_n$ en considérant la partition des supports des cycles, est une chaîne de fragmentation-coalescence. Il est possible de concevoir son noyau de transition de la manière suivante : sachant que la chaîne est en $P \in \Pi_n$, on tire au hasard uniformément et avec remise $i$ et $j$ dans $\{1, \dots, n\}$, puis on fusionne les blocs de $P$ contenant $i$ et $j$ s'ils sont différents, ou bien on fissionne uniformément le bloc de $P$ contenant $i$ et $j$ dans le cas contraire. Cette chaîne sur $\Pi_n$ est considérée dans un article de Persi Diaconis, Eddy Mayer-Wolf, Ofer Zeitouni, et Martin Zerner [DMWZZ04]. Plus généralement, au-delà des transpositions aléatoires, Nathanaël Berestycki, Oded Schramm, et Ofer Zeitouni ont établi dans [BSZ11] que pour tout $n \ge k \ge 2$, la marche aléatoire sur $S_n$ dont les pas sont des $k$-cycles i.i.d. uniformes converge vers la loi uniforme sur $S_n$ après environ $(1/k)n \log(n)$ étapes.

L'algorithme de Aart Stam de simulation de la loi uniforme sur les partitions se trouve dans [Sta83] et dans le livre de Knuth [Knu05, Volume 4A]. On prendra garde à ne pas confondre les partitions d'un ensemble fini avec la notion de partition d'entier, qui est reliée aux diagrammes de Alfred Young ou de Norman Ferrers. Le théorème de Paul Erdős et Tibor Gallai figure dans [EG60], et a été redémontré par plusieurs auteurs, dont Claude Berge [Ber76]. Une preuve courte et constructive se trouve par exemple dans un article de Amitabha Tripathi, Sushmita Venugopalan, et Douglas West [TVW10]. L'algorithme des configurations remonte à Béla Bollobás [Bol80], et a été raffiné et étendu notamment par Brendan McKay et Nicholas Wormald [MW90]. Il est abordé dans les cours de Charles Bordenave [Bor14a] et de Remco van der Hofstad [vdH14]. À ce sujet, soit $M_n$ le multigraphe aléatoire du modèle des configurations de sommets $\{1, \dots, n\}$ pour la suite de degrés $d_{n,1}, \dots, d_{n,n}$, et $p_{n,k} = (1/n) \sum_{i=1}^n 1_{\{d_{n,i}=k\}}$ la proportion de sommets de degré $k$, et supposons qu'il existe une loi $(p_k)_{k \ge 1}$ telle que $\lim_{n \to \infty} p_{n,k} = p_k$, et telle que les deux premiers moments convergent :

$$ 
\begin{align*} 
\mu &= \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^{n} d_{n,i} = \lim_{n \to \infty} \sum_{k=1}^{\infty} \frac{k}{n} \sum_{i=1}^{n} 1_{\{d_{n,i}=k\}} \\ 
&= \lim_{n \to \infty} \sum_{k=1}^{\infty} k p_{n,k} = \sum_{k=1}^{\infty} k p_k < \infty 
\end{align*} 
$$

et
$$ \nu = \lim_{n \to \infty} \sum_{i=1}^{n} \frac{d_{n,i}(d_{n,i}-1)}{\sum_{j=1}^{n} d_{n,j}} = \frac{1}{\mu} \sum_{k=1}^{\infty} k(k-1)p_k < \infty, $$

alors on peut établir que la probabilité que $M_n$ soit un graphe tend vers $e^{-\frac{1}{2}\nu-\frac{1}{4}\nu^2}$ quand $n \to \infty$. Ainsi la méthode de simulation par rejet du théorème 4.6 du modèle des configurations reste raisonnable si $n \gg 1$.

La structure d'arbre, bien que cas particulier de la structure de graphe, est très riche. On trouvera des panoramas dans les livres de Donald Knuth [Knu05, Volume 4A] et de Michael Drmota [Drm09]. L'algorithme de David Arnold et Ronan Sleep se trouve dans l'article [AS80], ainsi que dans l'article de survol de Jarmo Siltaneva et Erkki Mäkinen [SM02] sur les algorithmes de simulation d'arbres binaires aléatoires. La loi uniforme sur l'ensemble des arbres binaires plans $\mathcal{T}_n$ peut également être simulée grâce à un algorithme récursif séduisant dû à Jean-Luc Rémy [Ré85] : partant d'un élément de $\mathcal{T}_{n-1}$, on fabrique un élément de $\mathcal{T}_n$ en choisissant aléatoirement uniformément un sommet dans l'arbre, si c'est une feuille on lui attribue deux enfants qui seront donc des feuilles, sinon ce sommet est remplacé par un nouveau sommet dont un des enfants est une feuille et l'autre enfant est le sommet d'origine. Toujours à propos d'arbres aléatoires, on peut évoquer l'algorithme de David Wilson [Wil96] pour générer un arbre couvrant de loi uniforme, l'algorithme de Luc Devroye [Dev12] pour simuler un arbre de Galton-Watson conditionné à avoir une taille fixe, etc. On pourra consulter avec profit le livre de Russel Lyons et Yuval Peres [LP15] sur les probabilités sur les arbres et les réseaux.
# Mesures de Gibbs

**Mots-clés.** Mesure de Gibbs; algorithme de Metropolis-Hastings; échantillonneur de Gibbs; algorithme du recuit simulé; algorithme de Propp-Wilson.

**Outils.** Chaîne de Markov; transformée de Laplace; entropie de Boltzmann.

## Difficulté. *

Ce chapitre est consacré à des algorithmes génériques de simulation de mesures de probabilité, grâce aux chaînes de Markov. Le contexte choisi est celui des mesures de probabilités discrètes finies. Dans tout le chapitre E désigne un ensemble fini, typiquement de très grand cardinal, comme par exemple un groupe symétrique. Les méthodes et concepts abordés dépassent largement ce cadre restrictif, qui a le mérite de nécessiter peu de technologie.

## 5.1 Mesures de Gibbs

Soit $H: E \to \mathbb{R}$ une fonction appelée énergie ou hamiltonien. Pour tout $\beta \in \mathbb{R}$, la mesure de Gibbs $\mu_\beta$ est la mesure de probabilité sur E donnée pour tout $x \in E$ par

$$ \mu_{\beta}(x) = \frac{1}{Z_{\beta}} e^{-\beta H(x)}, \quad \text{où} \quad Z_{\beta} = \sum_{y \in E} e^{-\beta H(y)}. $$

La constante de normalisation $Z_\beta$ est appelée fonction de partition. Quitte à accepter que $H$ prenne la valeur $+\infty$, toute mesure de probabilité $\mu$ sur E est une mesure de Gibbs avec $\beta = 1$ et $H(x) = -\log(\mu(x))$ pour tout $x \in E$, ce qui donne $^1 H(x) = +\infty$ si et seulement si $\mu(x) = 0$.

<footnote n="1">1. Avec les conventions naturelles $\log(0) = -\infty$ et $\exp(-\infty) = 0$.</footnote>
Lorsque $\beta > 0$, la probabilité $\mu_\beta(x)$ est d'autant plus grande que l'énergie $H(x)$ est petite (par rapport aux autres valeurs de $H$), la mesure de probabilité $\mu_\beta$ favorise donc les configurations de faible énergie, et ce d'autant plus que $\beta$ est grand. Lorsque $\beta = 0$ on obtient la mesure de probabilité uniforme sur $E$.

Voici quelques exemples, parmi d'autres, de mesures de Gibbs :

— Modèle d'Ising. Dans ce modèle $E = \{-1, 1\}^A$ où $\emptyset \neq \Lambda \subset \mathbb{Z}^d$. Chaque $x \in E$ représente la configuration magnétique des atomes d'un morceau de métal. Pour tout site $i \in \Lambda$ dans le réseau, la valeur $x_i \in \{-1, 1\}$ est l'orientation magnétique de l'atome situé au site $i$, appelée parfois spin. L'énergie de la configuration $x \in E$ est de la forme

$$H(x) = J \sum_{|i-j|_1=1} x_i x_j + h \sum_{i \in \Lambda} x_i$$

où $|i-j|_1 := |i_1 - j_1| + \cdots + |i_d - j_d|$, où $J$ est une constante de couplage, et où $h$ modélise un champ magnétique extérieur;

— Loi d'Ewens. Dans ce modèle $E = S_n$ est le groupe symétrique, et l'énergie $H(\sigma) = |\sigma|$ de la permutation $\sigma \in E$ est donnée par le nombre de cycles $|\sigma|$ de $\sigma$ (théorème 14.3, $\beta = -\log(\theta)$);

— Graphes aléatoires. Dans ce modèle $E$ est l'ensemble des graphes à $n$ sommets, et l'énergie $H(g)$ d'un graphe $g \in E$ est donnée par le nombre d'arêtes dans $g$. Cela donne la loi du graphe aléatoire d'Erdős-Rényi (théorème 16.14, $\beta = -\log(p) - \log(1-p)$). On peut considérer d'autres énergies, comme par exemple le nombre de cycles du graphe, etc;

— Champ libre gaussien. Dans ce modèle $E = \mathbb{R}^A$ avec $\emptyset \neq \Lambda \subset \mathbb{Z}^d$, et l'énergie $H(x)$ du «champ» ou «interface» $x \in E$ est donnée par

$$H(x) = \sum_{|i-j|_1=1} (x_i - x_j)^2,$$

avec $|i-j|_1 := |i_1 - j_1| + \cdots + |i_d - j_d|$, et par convention $x_i = 0$ si $i \notin \Lambda$. Il s'agit d'un exemple où $E$ est infini et continu, étudié notamment dans le chapitre 2 en liaison avec la marche aléatoire simple sur $\mathbb{Z}^d$;

— Polymères dirigés. On pourra se reporter au chapitre 19.

Il se trouve que les mesures de Gibbs ont la propriété remarquable de maximiser l'entropie de Boltzmann à énergie moyenne fixée. Rappelons tout d'abord que si $\mu$ est une mesure de probabilité sur $E$, son entropie de Boltzmann notée $\text{Ent}(\mu)$ est définie par, avec la convention $0 \log(0) = 0$,

$$\text{Ent}(\mu) = - \sum_{x \in E} \mu(x) \log(\mu(x)).$$

**Théorème 5.1** (Maximum d'entropie à énergie fixée). Soit $H: E \to \mathbb{R}$ une fonction de minimum $h_-$ et de maximum $h_+$, et soit $m \in [h_-, h_+]$, avec $m \notin \{h_-, h_+\}$ si $h_- \neq h_+$. Soit $\mathcal{M} = \{\mu : \mathbb{E}_{\mu}(H) = m\}$ l'ensemble des mesures de probabilité sur $E$ d'énergie moyenne $m$. Alors il existe $\beta \in \mathbb{R}$ tel que $\mu_\beta \in \mathcal{M}$, et $\text{Ent}(\mu) \leq \text{Ent}(\mu_\beta)$ pour tout $\mu \in \mathcal{M}$, avec égalité ssi $\mu = \mu_\beta$.
Démonstration. Considérons la fonction

$$
f : \beta \in \mathbb{R} \mapsto \mathbb{E}_{\mu_{\beta}}(H) = \sum_{x \in E} H(x) \mu_{\beta}(x) = \sum_{x \in E} H(x) \frac{1}{Z_{\beta}} e^{-\beta H(x)}.
$$

Si $h_{-} = h_{+}$ alors $H$ est constante et égale à $m = h_{-} = h_{+}$, $\mu_{\beta}$ est la mesure uniforme sur $E$ quelque soit $\beta \in \mathbb{R}$, et $M$ est égal à l'ensemble des mesures de probabilités sur $E$. Si $h_{-} \neq h_{+}$, alors $f$ est strictement décroissante puisque<fnref n="2" />

$$
\begin{align*}
f'(\beta) &= -\frac{1}{Z_{\beta}} \sum_{x \in E} H(x)^2 e^{-\beta H(x)} + \left( \frac{1}{Z_{\beta}} \sum_{x \in E} H(x) e^{-\beta H(x)} \right)^2 \\
&= -\mathrm{Var}_{\mu_{\beta}}(H) < 0,
\end{align*}
$$

car $H$ n'est pas constante et le support de $\mu_\beta$ est plein. De plus, dans ce cas,
en notant $M = \{x \in E : H(x) = h_-\}$, il vient, pour tout $x \in E$,

$$
\mu_{\beta}(x) = \frac{e^{-\beta(H(x)-h_{-})}}{|M| + \sum_{y \notin M} e^{-\beta(H(y)-h_{-})}} \underset{\beta \to +\infty}{\longrightarrow} \begin{cases} |M|^{-1} & \text{si } x \in M, \\ 0 & \text{sinon,} \end{cases}
$$

et donc $\mu_\beta$ converge vers la mesure uniforme sur $M$ quand $\beta \to +\infty$, et il en
découle que l'image de $\mathbb{R}$ par la fonction $f$ est l'intervalle $]h_-, h_+[$.

Si $\mu$ est une probabilité sur $E$ ayant même énergie moyenne que $\mu_\beta$, alors

$$
\begin{align*}
\operatorname{Ent}(\mu_\beta) - \operatorname{Ent}(\mu) &= \sum_{x \in E} (\log(Z_\beta) + \beta H(x)) \mu_\beta(x) + \sum_{x \in E} \mu(x) \log(\mu(x)) \\
&= \sum_{x \in E} (\log(Z_\beta) + \beta H(x)) \mu(x) + \sum_{x \in E} \mu(x) \log(\mu(x)) \\
&= - \sum_{x \in E} \mu(x) \log(\mu_\beta(x)) + \sum_{x \in E} \mu(x) \log(\mu(x)) \\
&= \sum_{x \in E} \mu(x) \log \left( \frac{\mu(x)}{\mu_\beta(x)} \right) \\
&= \sum_{x \in E} \Phi \left( \frac{\mu(x)}{\mu_\beta(x)} \right) \mu_\beta(x) \\
&\ge \Phi \left( \sum_{x \in E} \frac{\mu(x)}{\mu_\beta(x)} \mu_\beta(x) \right) = \Phi(1) = 0,
\end{align*}
$$

où on a utilisé l'inégalité de Jensen pour la loi $\mu_\beta$ et pour la fonction convexe

$x \ge 0 \mapsto \Phi(x) := x \log(x).$

Comme $\Phi$ est strictement convexe, il y a égalité si et seulement si $\mu = \mu_\beta$. $\square$

<footnote n="2">2. Ce calcul est typique des «familles exponentielles» de la statistique.</footnote>
## 5.2 Algorithme de Metropolis-Hastings

On s'intéresse dans cette section au problème de la simulation d'une mesure de Gibbs sur un espace fini E, d'énergie $H: E \to \mathbb{R}$ et de paramètre $\beta > 0$, définie pour tout $x \in E$ par

$$ \mu_{\beta}(x) = \frac{1}{Z_{\beta}} e^{-\beta H(x)}, \quad \text{où} \quad Z_{\beta} = \sum_{x \in E} e^{-\beta H(x)}. $$

Même si $\beta$ et $H$ sont connus, il est souvent difficile voire impossible d'évaluer numériquement la constante de normalisation $Z_\beta$ car $E$ est trop gros ou trop complexe à parcourir. En revanche, le rapport

$$ \frac{\mu_{\beta}(x)}{\mu_{\beta}(y)} = e^{\beta H(y) - \beta H(x)} $$

ne dépend que de la différence d'énergie $H(y) - H(x)$, dont l'évaluation en pratique est même souvent moins coûteuse que l'évaluation de $H(x)$ et $H(y)$ séparément. L'algorithme de Metropolis-Hastings permet de construire et de simuler une chaîne de Markov récurrente apériodique $(X_t)_{t \in \mathbb{N}}$ sur $E$ de loi invariante $\mu_\beta$, dont la matrice de transition ne fait intervenir $\mu_\beta$ qu'à travers les rapports $\mu_\beta(x)/\mu_\beta(y)$. Comme $E$ est fini, la condition de Doeblin ou le théorème de Perron-Frobenius fournissent une convergence exponentielle de l'erreur<fnref n="3" /> de la forme : il existe $c > 0$ et $\eta < 1$ tel que, pour tout $t \in \mathbb{N}$,

$$ d_{VT}(\text{Loi}(X_t), \mu_\beta) \le c\eta^t. $$

On dispose ainsi d'un générateur approché de $\mu_\beta$ : pour $t \gg 1$,

$$ \mu_\beta \approx \text{Loi}(X_t). $$

Le théorème 5.2 fournit une construction du noyau de transition $\mathbf{P}$ de $(X_t)_{t \in \mathbb{N}}$.

**Théorème 5.2 (Metropolis-Hastings).** Soit $\mathbf{Q}: E \times E \to [0, 1]$ un noyau de transition irréductible sur $E$, vérifiant, pour tous $x, y \in E$,

$$ \mathbf{Q}(x, y) = 0 \quad \text{ssi} \quad \mathbf{Q}(y, x) = 0. $$

Soit $\alpha: \mathbb{R}_+ \to ]0, 1]$ une fonction vérifiant, pour tout $u \in \mathbb{R}_+$,

$$ \alpha(u) = u\alpha\left(\frac{1}{u}\right). $$

Soit $\mathbf{P}: E \times E \to \mathbb{R}$ défini, pour tous $x, y \in E$, par

$$ \mathbf{P}(x, y) = \begin{cases} \mathbf{Q}(x, y)\rho(x, y) & \text{si } x \neq y, \\ 1 - \sum_{z \neq x} \mathbf{P}(x, z) & \text{si } x = y, \end{cases} $$

<footnote n="3">3. En pratique ces bornes sont rarement utiles, en dehors de certains cas spéciaux.</footnote>
où

$$ \rho(x, y) = \alpha \left( \frac{\mu_{\beta}(y) \mathbf{Q}(y, x)}{\mu_{\beta}(x) \mathbf{Q}(x, y)} \right) 1_{\mathbf{Q}(x,y)>0}. $$

Alors $\mathbf{P}$ est un noyau de transition sur $E$, irréductible récurrent positif, de loi invariante réversible $\mu_{\beta}$; apériodique si $\alpha < 1$ ou si $\mathbf{Q}$ est apériodique.

Les deux choix les plus classiques pour $\alpha$ sont donnés par

$$ \alpha(u) = \min(1, u) \quad \text{et} \quad \alpha(u) = \frac{u}{1+u}, \quad u \in \mathbb{R}_{+}. $$

Le premier possède une interprétation intuitive. Le second assure que $\alpha < 1$.

Si la mesure $\mu_{\beta}$ est réversible pour le noyau $\mathbf{Q}$, et c'est le cas par exemple lorsque $\mu_{\beta}$ est la mesure uniforme sur $E$ et $\mathbf{Q}(x, y) = \mathbf{Q}(y, x)$ pour tous $x, y \in E$, alors la construction de Metropolis-Hastings revient tout simplement à prendre $\mathbf{P} = (1 - \varepsilon)\mathbf{Q} + \varepsilon\mathbf{I}$, où $0 < \varepsilon < 1$ assure l'apériodicité.

Démonstration du théorème 5.2. On a $0 \le \mathbf{P}(x, y) \le \mathbf{Q}(x, y)$ pour tous $x, y$ dans $E$ avec $x \ne y$, et donc $\mathbf{P}$ est un noyau de transition. Comme $\alpha > 0$, le noyau $\mathbf{P}$ hérite du squelette de $\mathbf{Q}$, et il est donc irréductible, et apériodique si $\mathbf{Q}$ l'est. Si $\alpha < 1$ alors $\mathbf{P}(x, x) > 0$ pour tout $x \in E$ et donc $\mathbf{P}$ est apériodique. Comme $\mathbf{P}$ est irréductible sur $E$ fini, il possède une unique loi invariante. La propriété de $\alpha$ donne, pour tous $x, y \in E$, $x \ne y$, $\mathbf{Q}(x, y) \ne 0$,

$$ \begin{align*} \mu_{\beta}(x)\mathbf{P}(x, y) &= \mu_{\beta}(x)\mathbf{Q}(x, y)\alpha\left(\frac{\mu_{\beta}(y)\mathbf{Q}(y, x)}{\mu_{\beta}(x)\mathbf{Q}(x, y)}\right) \\ &= \mu_{\beta}(x)\mathbf{Q}(x, y)\frac{\mu_{\beta}(y)\mathbf{Q}(y, x)}{\mu_{\beta}(x)\mathbf{Q}(x, y)}\alpha\left(\frac{\mu_{\beta}(x)\mathbf{Q}(x, y)}{\mu_{\beta}(y)\mathbf{Q}(y, x)}\right) \\ &= \mu_{\beta}(y)\mathbf{P}(y, x). \end{align*} $$

Ainsi $\mu_{\beta}$ est réversible pour $\mathbf{P}$, et c'est donc la loi invariante de $\mathbf{P}$. $\square$

L'algorithme de Metropolis-Hastings consiste à simuler les trajectoires de la chaîne $(X_t)_{t \in \mathbb{N}}$ de noyau $\mathbf{P}$. Cela se ramène au problème de la simulation de la loi discrète $\mathbf{P}(x, \cdot)$ pour un $x$ quelconque. Pour ce faire, soit $Y$ une variable aléatoire sur $E$ de loi $\mathbf{Q}(x, \cdot)$, et $U$ une variable aléatoire de loi uniforme sur $[0, 1]$, indépendante de $Y$. Soit $Z$ la variable aléatoire définie par $Z = Y$ si $U < \rho(x, Y)$ et $Z = x$ sinon. Alors $Z \sim \mathbf{P}(x, \cdot)$ car pour tous $y \ne x$,

$$ \mathbf{P}(Z = y) = \mathbf{P}(U < \rho(x, Y), Y = y) = \rho(x, y)\mathbf{Q}(x, y) = \mathbf{P}(x, y). $$

Autrement dit la proposition $Y$ de loi $\mathbf{Q}(x, \cdot)$ est acceptée ou rejetée selon que $U < \rho(x, Y)$ ou pas. L'évaluation de $\mathbf{P}(x, x)$ n'est pas requise. On dit que $\rho$ est la fonction d'acceptation-rejet tandis que $\mathbf{Q}$ le noyau de proposition ou d'exploration. Le noyau $\mathbf{Q}$ doit être facile à simuler. En pratique, on utilise souvent le noyau de la marche aléatoire simple aux plus proches voisins sur le graphe associé à une distance naturelle sur $E$ :
$$ \mathbf{Q}(x, y) = \frac{\mathbb{1}_{y \in V_x}}{|V_x|} \quad \text{où} \quad V_x := \{y \in E : \text{dist}(x, y) = 1\}. $$

Si le graphe est régulier, c'est-à-dire que $|V_x| = |V_y|$ pour tous $x, y \in E$, et si $\mu_\beta$ est la mesure uniforme sur $E$, alors $\mathbf{P} = (1 - \varepsilon)\mathbf{Q} + \varepsilon\mathbf{I}$, où $0 < \varepsilon < 1$, et on peut prendre $\varepsilon = 0$ si $\mathbf{Q}$ est apériodique.

**Exemple 5.3** (Échantillonneur de Gibbs). Soit $F \subset \mathbb{Z}$ une partie finie et non vide de $\mathbb{Z}$, comme par exemple $F = \{-1, 1\}$ comme dans le modèle d'Ising évoqué dans l'introduction du chapitre. Soit également $\Lambda \subset \mathbb{Z}^d$ une partie finie et non vide de $\mathbb{Z}^d$. Soit enfin $E = F^\Lambda$. Un noyau d'exploration $\mathbf{Q}$ naturel sur $E$ consiste, à partir d'une configuration courante $x \in E$, à sélectionner un site $i \in \Lambda$ au hasard$^4$, puis à modifier $x_i$ en utilisant la loi conditionnelle

$$ \mu_{\beta}(x_i | x_{-i}) \quad \text{où} \quad x_{-i} := (x_j)_{j \neq i}. $$

Cette loi conditionnelle est facile à calculer et à simuler dans le cas par exemple du modèle d'Ising. Cela revient à prendre, pour tous $x, y \in E$,

$$ \mathbf{Q}(x, y) = \sum_{i \in \Lambda} q(i) \mu_{x,i}(y_i) \mathbb{1}_{\{x_{-i} = y_{-i}\}}, \quad \text{où} \quad \mu_{x,i} := \mu_{\beta}(x_i | x_{-i}) $$

et où $q$ est une loi sur $\Lambda$ chargeant tous les états comme par exemple la loi uniforme sur $\Lambda$. L'échantillonneur de Gibbs est le nom donné à l'algorithme de Metropolis-Hastings lorsque le noyau d'exploration $\mathbf{Q}$ est défini comme cela.

## 5.3 Algorithme du recuit simulé

L'algorithme du recuit simulé a pour objectif de minimiser une fonction $H: E \to \mathbb{R}$ sur $E$ fini. Pour ce faire, on considère la mesure de Gibbs $\mu_\beta$ d'énergie $H$ et de paramètre $\beta > 0$, définie pour tout $x \in E$ par

$$ \mu_{\beta}(x) = \frac{1}{Z_{\beta}} e^{-\beta H(x)}, \quad \text{où} \quad Z_{\beta} = \sum_{x \in E} e^{-\beta H(x)}. $$

Il est commode d'interpréter le paramètre $1/\beta$ comme une température ou une variance par analogie gaussienne. La loi $\mu_\beta$ favorise les configurations de faible énergie, d'autant plus que la température $1/\beta$ est basse. On a établi dans la démonstration du théorème 5.1 la convergence suivante$^5$ :

$$ \mu_{\infty}(x) := \lim_{\beta \to \infty} \mu_{\beta}(x) = \frac{\mathbb{1}_{x \in M}}{|M|} \quad \text{où} \quad M := \{y \in E : H(y) = \inf_{E} H\}. $$

La loi $\mu_\infty$ est uniforme sur l'ensemble $M$ des minima globaux de $H$. On prendra garde à ne pas confondre $\mu_\infty$ avec la loi $\mu_0$ qui est uniforme sur $E$.

<footnote n="4">4. On préfère parfois balayer méthodiquement les sites les uns après les autres.</footnote>

<footnote n="5">5. Il s'agit d'une instance très simple du principe de Laplace.</footnote>
Cela conduit à un algorithme stochastique pour simuler $\mu_\infty$ appelé *algorithme du recuit simulé*<fnref n="6" />, qui consiste à utiliser l’algorithme de Metropolis-Hastings mais avec une température $1/\beta = 1/\beta_t$ décroissante au cours du temps $t$. La chaîne de Markov de Metropolis-Hastings $(X_t)_{t \in \mathbb{N}}$ ainsi modifiée n’est plus homogène en temps. Considérons par exemple le cas où $\alpha(u) = \min(1, u)$ pour tout $u \in \mathbb{R}$, et où $\mathbf{Q}$ est tel que $\mathbf{Q}(x, y) = \mathbf{Q}(y, x)$ pour tous $x, y \in E$. La fonction d’acceptation-rejet dépend du temps et est donnée par

$$ \rho_t(x, y) = \alpha \left( \frac{\mu_{\beta_t}(y)}{\mu_{\beta_t}(x)} \right) = \alpha \left( e^{-\beta_t(H(y)-H(x))} \right) = e^{-\beta_t \max(0, H(y)-H(x))}. $$

Sachant que la chaîne (ou l’algorithme) se trouve en l’état $x$ au temps $t$, on simule une proposition $y$ de loi $\mathbf{Q}(x, \cdot)$, qu’on accepte ssi $U < \rho_t(x, y)$ où $U$ est une variable aléatoire uniforme sur $[0, 1]$ indépendante, c’est-à-dire avec probabilité 1 si $H(y) \le H(x)$ et probabilité $e^{-\beta_t(H(y)-H(x))}$ sinon (vaut 0 si $1/\beta_t = 0$). L’algorithme explore le graphe de $H$, accepte toujours une transition qui abaisse l’énergie $H$ et accepte une transition qui l’augmente avec une probabilité décroissant vers zéro au fur et à mesure que la température baisse. Contrairement à une méthode de type descente de gradient, le recuit simulé peut «remonter la pente» et ainsi échapper, au début, aux minima locaux. Il reste cependant à régler la température : un refroidissement trop brusque peut piéger la trajectoire près d’un minimum local tandis qu’un refroidissement trop lent peut empêcher l’algorithme de se concentrer près de l’ensemble $M$. Un résultat théorique assure que pour un schéma de décroissance de la température $1/\beta_t$ de la forme $c/\log(t)$ quand $t \to \infty$, la chaîne s’accumule sur des points de $M$. Ce théorème remarquable est toutefois peu utile en pratique ! La performance de l’algorithme dépend beaucoup de la régularité du graphe de $H$ par rapport à la structure de voisinage de l’exploration.

Considérons à présent le problème du voyageur de commerce pour $n$ villes positionnées dans l'espace en $v_1, \dots, v_n$, qui consiste à trouver une tournée de longueur minimale, c'est-à-dire une permutation $x \in S_n$ dans le groupe symétrique $S_n$ qui minimise la fonction

$$ x \in S_n \mapsto H(x) := \sum_{i=1}^{n} \text{dist}(v_{x(i)}, v_{x(i+1)}) \quad \text{où} \quad x(n+1) := x(1). $$

La longueur d'une tournée joue le rôle d'énergie ici. Le cardinal de $E = S_n$ est énorme : $n!$. À coût total fixé, on ne pourra qu'explorer une partie restreinte $F \subset E$ et retenir le minimum de $H$ sur $F$ comme approximation du minimum de $H$ sur $E$. La génération d'une partie $F \subset E$ peut se faire de manière déterministe<fnref n="7" />, ou de manière stochastique par exemple avec l'algorithme du

<footnote n="6">6. «Simulated annealing» en anglais.</footnote>

<footnote n="7">7. L’algorithme (déterministe) de Steinhaus-Johnson-Trotter permet de lister les éléments de $S_n$ sans comparaison aux éléments déjà produits. Algébriquement, il correspond à parcourir un graphe de Cayley de $S_n$, tandis que géométriquement, il correspond à parcourir les sommets adjacents du polytope appelé permutaèdre.</footnote>
recuit simulé. On peut choisir par exemple pour noyau d'exploration **Q** celui de la marche aléatoire simple sur $S_n$ associée aux transpositions, donné par

$$ \mathbf{Q}(x, y) = \begin{cases} \frac{2}{n(n-1)} & \text{si } y = x\tau \text{ pour une transposition } \tau, \\ 0 & \text{sinon.} \end{cases} $$

Puisque les transpositions engendrent le groupe symétrique $S_n$, le noyau de transition **Q** est irréductible. On peut bien entendu choisir un noyau d'exploration plus riche, qui, par exemple, échange $k$ villes tirées au hasard.

L'étude de l'ordre de grandeur de $H(x)$ lorsque les positions $v_1, \dots, v_n$ des $n$ villes sont aléatoires i.i.d. et $n$ est grand fait l'objet du chapitre 20.

<figure><img src="image_19.png" /><figcaption>Fig. 5.1. Étapes de l'algorithme du recuit pour le voyageur de commerce ($n = 10$).</figcaption></figure>
## 5.4 Algorithme de Propp-Wilson

L'algorithme de Metropolis-Hastings permet une simulation approchée d'une mesure de Gibbs $\mu_\beta$ sur E fini, au moyen d'une chaîne de Markov de noyau $\mathbf{P}$ qui admet $\mu_\beta$ comme loi invariante et réversible (théorème 5.2). Nous présentons à présent un algorithme de simulation exacte de $\mu_\beta$.

Soit $\mathbf{P}$ un noyau markovien irréductible sur E de probabilité invariante $\mu_\beta$. Adoptons l'interprétation des chaînes de Markov sous forme de suites récurrentes aléatoires. Soit donc $g: E \times [0, 1] \to E$ une fonction telle que $g(x, U) \sim \mathbf{P}(x, \cdot)$ pour tout $x \in E$, où $U$ est une variable aléatoire de loi uniforme sur $[0, 1]$. On note $G: E \to E$ la fonction aléatoire définie par $G(x) = g(x, U)$. Soit $(G_n)_{n \ge 0}$ une suite i.i.d. de fonctions aléatoires de E dans E, de même loi que G, construites à la manière de G en utilisant une suite $(U_n)_{n \ge 0}$ de variables aléatoires i.i.d. de loi uniforme sur $[0, 1]$. Pour tout $n$, on construit les applications aléatoires $A_n: E \to E$ et $B_n: E \to E$ par composition de la manière suivante :

$$A_n = G_n \circ \dots \circ G_1 \quad \text{et} \quad B_n = G_1 \circ \dots \circ G_n.$$

On convient que $A_0$ et $B_0$ sont égales à l'application identité de E. Pour tout $x \in E$ et tout $n$, les variables aléatoires $A_n(x)$ et $B_n(x)$ suivent la loi $\mathbf{P}^n(x, \cdot)$. Les suites $(A_n(x))_{n \ge 0}$ et $(B_n(x))_{n \ge 0}$ ont les mêmes lois marginales de dimension 1, mais n'ont pas la même loi en tant que suites. La suite $(A_n(x))_{n \ge 0}$ est une chaîne de Markov sur E de noyau $\mathbf{P}$ et de loi initiale $\delta_x$. En revanche, $(B_n(x))_{n \ge 0}$ n'est pas une chaîne de Markov car le temps est «inversé». On définit les temps de contraction $T_A$ et $T_B$ à valeurs dans $\mathbb{N} \cup \{\infty\}$ par

$$T_A = \inf\{n \ge 0 : \mathrm{card}(A_n(E)) = 1\} \quad \text{où} \quad A_n(E) = \{A_n(x) : x \in E\}$$

et de même,

$$T_B = \inf\{n \ge 0 : \mathrm{card}(B_n(E)) = 1\} \quad \text{où} \quad B_n(E) = \{B_n(x) : x \in E\}.$$

On dit que G est contractante lorsque $p = \mathbb{P}(\mathrm{card}(G(E)) = 1) > 0$.

**Théorème 5.4** (Convergence à la coalescence pour la suite renversée). Si G est contractante alors $\mathbb{P}(T_B < \infty) = 1$, pour tout $x \in E$, $B_{T_B}(x) \sim \mu_\beta$, et $B_n(x) = B_{T_B}(x)$ pour tout $n \ge T_B$.

Notons que $(A_n(x))_{n \ge 0}$ converge en loi vers $\mu$ tandis que $(B_n(x))_{n \ge 0}$ converge p.s. vers une variable aléatoire de loi $\mu$.

*Démonstration.* Les événements $C_n = \{\mathrm{card}(G_n(E)) = 1\}$ sont indépendants et de même probabilité $p = \mathbb{P}(\mathrm{card}(G(E)) = 1) > 0$. Par le lemme de Borel-Cantelli, presque sûrement, $\mathrm{card}(G_n(E)) = 1$ pour une infinité de valeurs de $n$, et en particulier $\mathbb{P}(T_B < \infty) = 1$. Le temps aléatoire $T_B$ définit presque sûrement un singleton aléatoire $\{x_B\}$ tel que $B_{T_B}(x) = x_B$ pour tout $x \in E$. Il en découle que $B_n(x) = x_B$ pour tout $x \in E$ et tout $n \ge T_B$ car
$$B_n(x) = B_{T_B}((G_{T_B+1} \circ \cdots \circ G_n)(x)) = x_B.$$

Il y a coalescence des trajectoires de $(B_n(x))_{n \ge 0}$ quel que soit l'état initial $x$. Soit $\mu_B$ la loi de $x_B$. Par convergence dominée, pour tout $x \in E$ et toute fonction bornée $f : E \to \mathbb{R}$,

$$\lim_{n \to \infty} \mathbb{E}(f(B_n(x))) = \lim_{n \to \infty} \mathbb{E}(f(B_n(x))1_{\{T_B \le n\}}) = \mathbb{E}(f(x_B)) = \mu_B f.$$

Or $\mathbb{E}(f(B_n(x))) = \mathbf{P}^n(x, \cdot) f = \sum_{y \in E} \mathbf{P}^n(x, y) f(y)$, d'où, pour tous $x, y \in E$,

$$\lim_{n \to \infty} \mathbf{P}^n(x, y) = \mu_B(y).$$

Ainsi $\mu_B = \mu_\beta$, ce qui achève la preuve. $\square$

Si $G$ est contractante alors on a aussi $\mathbb{P}(T_A < \infty) = 1$ et $T_A$ définit presque sûrement un singleton aléatoire $\{x_A\}$, vérifiant $A_{T_A}(x) = x_A$ pour tout $x \in E$, mais rien n'assure que $A_n(x) = x_A$ pour $n > T_A$ et tout $x \in E$, ni que $x_A$ suit la loi $\mu_\beta$. Pour tous $x, y \in E$, la suite $((A_n(x), A_n(y)))_{n \ge 0}$ est un couplage coalescent : les deux composantes sont des chaînes de même noyau et qui restent collées après leur première rencontre. On dit que $((B_n(x), B_n(y)))_{n \ge 0}$ est un *couplage coalescent par le passé*<fnref n="8" />.

Lorsque $G$ n'est pas contractante, on peut utiliser le noyau $\mathbf{P}^r$, $r \ge 1$, qui admet également $\mu_\beta$ comme loi invariante. En pratique, il n'est pas commode de déterminer le temps de couplage (ou coalescence) par le passé $T_B$ car il fait intervenir tous les états initiaux possibles. Il est toutefois possible de contrôler ce temps lorsque le noyau $\mathbf{P}$ possède une propriété de monotonie par rapport à un ordre sur l'espace d'états $E$, en se ramenant à un état minimal et à un état maximal, comme le montre l'exemple détaillé dans la section 5.5.

## 5.5 Modélisation d'un composé chimique

Dans cette section nous mettons en place un algorithme de type Metropolis-Hastings et un algorithme de simulation exacte pour obtenir une réalisation d'une mesure de Gibbs modélisant la répartition de deux composés chimiques que l'on dira de type +1 et de type -1 en répulsion forte. Le système est supposé ouvert et le nombre de particules de chaque composé est donc libre. Pour simplifier, on suppose que les composés sont répartis sur une surface plane assimilée à un carré discret $\Lambda = \{1, \dots, L\}^2 \subset \mathbb{Z}^2$. Chaque site $i \in \Lambda$ est soit vierge, soit occupé par un composé chimique de type +1 ou -1. La répulsion entre composés de types différents est prise en compte en interdisant que deux composés de types différents soient voisins, c'est-à-dire à distance 1 sur le quadrillage. L'ensemble des configurations est donc le suivant

$$E = \{x \in \{-1, 0, +1\}^A : \forall i, j \in \Lambda, |i - j|_1 = 1 \Rightarrow x_i x_j \neq -1\}.$$

<footnote n="8">8. En anglais : « coupling from the past ».</footnote>
On considère l'énergie

$$x \in E \mapsto H(x) = \mathrm{card}\{i \in \Lambda : |x_i| = 1\}$$

qui compte le nombre de composés présents et la mesure de Gibbs associée

$$\mu_{\beta} = \frac{1}{Z_{\beta}} e^{-\beta H(x)}, \quad x \in E, \quad \beta \in \mathbb{R}, \quad Z_{\beta} = \sum_{x \in E} e^{-\beta H(x)}.$$

Plus le réel $\beta$ est petit (respectivement grand) et plus la loi $\mu_\beta$ favorise les configurations denses (respectivement clairsemées).

**Remarque 5.5** (Méthode du rejet). Voici une première méthode permettant de simuler de manière exacte $\mu_\beta$. On attribue indépendamment à chaque site de $\Lambda$ une valeur $-1, 0$ ou $+1$ avec probabilités respectives

$$\frac{e^{-\beta}}{1 + 2e^{-\beta}}, \quad \frac{1}{1 + 2e^{-\beta}}, \quad \text{et} \quad \frac{e^{-\beta}}{1 + 2e^{-\beta}}.$$

La configuration obtenue est retenue si elle appartient à E. Dans le cas contraire, on répète la procédure. Cette méthode simple s'avère impraticable car E est tout petit dans $\{-1, 0, +1\}^\Lambda$.

Construisons à présent un algorithme de type Metropolis-Hastings. Pour tous $u \in [-1, 1], i \in \Lambda$, soit

$$h_{i,u} : E \to \{-1, 0, +1\}^{\Lambda}$$

la fonction définie pour tous $x \in E$ et $j \in \Lambda$ par

$$(h_{i,u}(x))_j = \begin{cases} x_j & \text{si } j \neq i; \\ -1 & \text{si } j = i \text{ et } u < -1/(1 + 2e^{-\beta}); \\ 0 & \text{si } j = i \text{ et } -1/(1 + 2e^{-\beta}) \le u \le 1/(1 + 2e^{-\beta}); \\ +1 & \text{si } j = i \text{ et } u > 1/(1 + 2e^{-\beta}). \end{cases}$$

Enfin, on pose

$$g_{i,u}(x) = \begin{cases} h_{i,u}(x) & \text{si } h_{i,u}(x) \in E, \\ x & \text{sinon.} \end{cases}$$

Soient $(U_n)_{n \ge 1}$ et $(V_n)_{n \ge 1}$ des suites indépendantes de variables aléatoires i.i.d. de loi uniforme sur $[-1, 1]$ et sur $\Lambda$ respectivement, et $G_n := g_{V_{n+1}, U_{n+1}}$. On définit enfin la suite récurrente aléatoire $(X_n)_{n \ge 0}$ définie par

$$X_{n+1} = G_n(X_n).$$

**Théorème 5.6.** La suite $(X_n)_{n \in \mathbb{N}}$ est une chaîne de Markov sur E, irréductible, récurrente, apériodique et de loi invariante réversible $\mu_\beta$.
Démonstration. La suite $(X_n)_{n \in \mathbb{N}}$ est chaîne de Markov, écrite sous la forme d'une suite récurrente aléatoire sur $E$ fini. Toutes les configurations mènent à la configuration nulle (aucun composé présent) et réciproquement. La chaîne est donc irréductible et récurrente. Soit $\mathbf{P}$ le noyau de transition de $(X_n)_{n \in \mathbb{N}}$. Si $x$ et $y$ sont deux éléments de $E$ alors $\mathbf{P}(x, y)$ est strictement positif si $x$ et $y$ coïncident sur en tous les sites sauf un. On vérifie au cas par cas la relation de réversibilité. Supposons par exemple que $x$ et $y$ sont dans $E$ et, pour $i_0 \in \Lambda$,

$$x_{i_0} = +1, \quad y_{i_0} = 0 \quad \text{et} \quad x_i = y_i \quad \text{pour } i \neq i_0.$$

Alors $H(x) = H(y) + 1$ et ainsi

$$\begin{align*}
\mu_{\beta}(x)\mathbf{P}(x, y) &= \mu_{\beta}(y)e^{-\beta} \frac{2}{L^2(1 + 2e^{-\beta})} \\
&= \mu_{\beta}(y) \frac{1}{L^2} \left( 1 - \frac{1}{1 + 2e^{-\beta}} \right) = \mu_{\beta}(y)\mathbf{P}(y, x).
\end{align*}$$

□

À partir de cette suite récurrente aléatoire, on peut également mettre en place un algorithme de simulation parfaite. Doit-on vraiment, dans l'algorithme de Propp-Wilson, suivre toutes les trajectoires paramétrées par les points de $E$ vus comme des conditions initiales ? La propriété fondamentale ci-dessous va permettre de simplifier grandement ce problème : deux suffisent !

**Lemme 5.7 (Monotonie).** *Pour tous $u \in [-1, 1]$ et $i \in \Lambda$, la fonction $x \in E \mapsto g_{i,u}(x)$ est croissante pour l'ordre (partiel) sur $E$ défini par*

$$x \le y \quad \text{ssi} \quad x_i \le y_i \quad \text{pour tout } i \in \Lambda.$$

*De plus, la configuration, notée $-1$ (respectivement $+1$), constituée uniquement de $-1$ (respectivement $+1$), est un plus petit (respectivement grand) élément pour cet ordre partiel.*

À présent, la monotonie fournit l'encadrement

$$G_n(-1) \le G_n(x) \le G_n(+1),$$

indiquant que la coalescence partant de $x$ quelconque a lieu avant la coalescence partant de $\pm 1$. D'un point de vue pratique, il suffit donc d'itérer l'algorithme jusqu'à l'instant de coalescence des trajectoires issues de $\pm 1$.

Enfin, le noyau $\mathbf{P}$ n'est pas contractant au sens du théorème 5.4 mais $\mathbf{P}^{L^2}$ l'est puisque, pour tout $x \in E$, $\mathbf{P}^{L^2}(x, \cdot)$ charge la configuration nulle.

## 5.6 Pour aller plus loin

Pour une introduction à la physique statistique, qui est un point de contact très important entre physique et mathématique, et notamment à des exemples