$$
\begin{align*}
&= 4 \sum_{k=2}^{n} \left( \frac{1}{k^2} + \frac{1}{(k-1)^2} - \frac{2}{k(k-1)} \right) \\
&= 8 \sum_{k=1}^{n-1} \frac{1}{k^2} + \frac{4}{n^2} - 4 - 8 \left( 1 - \frac{1}{n} \right).
\end{align*}
$$

On a $\mathrm{Var}(W_n) \nearrow \frac{4\pi^2}{3} - 12 \approx 1.16$ (notons que $\mathrm{Var}(T_2) = 1$). Il est possible d'obtenir une expression explicite de la densité de $W_n$ en remarquant que $\mathbb{P}(W_n \le t) = \mathbb{P}(A_n(t) = 1)$ et en calculant la matrice de transition du processus ancestral (assez peu passionnant).

On appelle arbre généalogique d'un groupe de $n$ individus l'ensemble de tous leurs ancêtres toutes générations comprises, eux compris, jusqu'au premier ancêtre commun à tous les individus. On note $L_n$, et l'on appelle longueur de l'arbre généalogique la variable aléatoire égale à la somme des temps de vie de tous les individus de l'arbre. La longueur de l'arbre $L_n$ s'exprime en fonction des temps d'apparition des ancêtres communs :

$$L_n = 2T_2 + \dots + nT_n.$$

En particulier, comme $T_2, \dots, T_n$ sont indépendantes avec $T_k \sim \mathrm{Exp}((\frac{k}{2}))$,

$$\mathrm{E}(L_n) \sim 2 \log(n) \quad \text{et} \quad \mathrm{Var}(L_n) \sim \frac{2\pi^2}{3}.$$

**Théorème 13.4** (Longueur de l'arbre ancestral). La v.a. $L_n$ suit la loi du maximum de $n-1$ v.a.r. i.i.d. de loi exponentielle de paramètre $1/2$. De plus,

$$\frac{L_n}{\log(n)} \xrightarrow{n \to \infty} 2 \quad \text{et} \quad \frac{L_n}{2} - \log(n) \xrightarrow{n \to \infty} \text{Gumbel}$$

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

*Démonstration.* La variable aléatoire $L_n$ est la somme des variables aléatoires indépendantes $2T_2, \dots, nT_n$ qui suivent les lois $\mathrm{Exp}(1/2), \dots, \mathrm{Exp}((n-1)/2)$. Le premier résultat découle alors de la propriété suivante : si $E_1, \dots, E_n$ sont des variables aléatoires indépendantes de lois $\mathrm{Exp}(\lambda), \mathrm{Exp}(2\lambda), \dots, \mathrm{Exp}(n\lambda)$ alors leur somme $S_n := E_1 + \dots + E_n$ à la même loi que $M_n := \max(F_1, \dots, F_n)$ où $F_1, \dots, F_n$ sont des v.a. i.i.d. de loi $\mathrm{Exp}(\lambda)$. La densité de $M_n$ est

$$
\begin{align*}
f_n(x) &:= (\mathbb{P}(M_n \le x))' \\
&= ((1 - e^{-\lambda x})^n \mathbb{1}_{\mathbb{R}_+}(x))' \\
&= n\lambda(1 - e^{-\lambda x})^{n-1} e^{-\lambda x} \mathbb{1}_{\mathbb{R}_+}(x).
\end{align*}
$$

Montrons $S_n$ a pour densité $f_n$. C'est vrai pour $n = 1$, et par récurrence, si cela est vrai pour $n$, alors la densité de $S_{n+1}$ est, en notant $g_\lambda$ celle de $\mathrm{Exp}(\lambda)$,
$$
\begin{align*}
f_n * g_{(n+1)\lambda}(y) &= (n+1)\lambda \int_{-\infty}^{y} f_n(x) e^{-\lambda(n+1)(y-x)} dx \\
&= \lambda(n+1)n\lambda e^{-\lambda(n+1)y} \int_{0}^{y} (e^{\lambda x} - 1)^{n-1} e^{\lambda x} dx \\
&= \lambda(n+1)e^{-\lambda(n+1)y}(e^{\lambda y} - 1)^n \\
&= \lambda(n+1)e^{-\lambda y}(1 - e^{-n\lambda y})^n = f_{n+1}(y).
\end{align*}
$$

En fait, cette propriété ne constitue qu'une partie du lemme de Rényi 11.3.

Pour établir le second résultat du théorème (convergence p.s.) on utilise
le fait suivant 2 : si $(X_n)_n$ sont des v.a.r. indépendantes et centrées vérifiant
$\sum_n E(X_n^2) < \infty$ alors $\sum_n X_n$ converge presque sûrement et dans $L^2$. Avec
$X_n = nT_n - E(nT_n) = nT_n - 2/(n-1)$ on a $E(X_n) = 0$ et

$$
\sum_{n \ge 2} \mathrm{E}(X_n^2) = \sum_{n \ge 2} \mathrm{Var}(X_n) = \sum_{n \ge 2} \frac{4}{(n-1)^2} < \infty
$$

donc $\sum_n X_n$ converge p.s. et donc

$$
\begin{align*}
\frac{L_n}{\log(n)} &= \frac{1}{\log(n)} \sum_{k=2}^{n} X_k + \frac{1}{\log(n)} \sum_{k=2}^{n} \mathrm{E}(kT_k) \\
&= \frac{1}{\log(n)} \sum_{k=2}^{n} X_k + \frac{2}{\log(n)} \sum_{k=1}^{n-1} \frac{1}{k} \xrightarrow{n \to \infty} 2.
\end{align*}
$$

Pour établir le troisième résultat (fluctuation Gumbel), on utilise le fait que
$L_n$ et $M_n$ ont même loi, puis on écrit, pour tout $t \in \mathbb{R}$,

$$
\begin{align*}
\mathbb{P}(L_n - 2 \log(n) \le 2t) &= \left(1 - e^{-\frac{1}{2}(2t+2 \log(n))}\right)^{n-1} \\
&= \left(1 - \frac{e^{-t}}{n}\right)^n \xrightarrow{n \to \infty} e^{-e^{-t}}.
\end{align*}
$$

□

13.3 Mutations

Pour rendre compte de la diversité des individus dans une population, il
faut tenir compte des possibilités de mutation de l'ADN, en particulier lors
de sa réplication. Les mutations entraînent une diversification génétique des
enfants d'un même individu. Le taux de mutation d'une base <fnref n="3" /> est très faible.
On suppose pour simplifier que ce taux ne dépend pas de la base concernée,

<footnote n="2">2. Cas particulier du théorème de convergence de martingale bornée dans $L^2$.</footnote>

<footnote n="3">3. Un brin d'ADN est constitué par une suite de lettres d'alphabet $\{A, C, G, T\}$.</footnote>
ni de sa position dans le brin d'ADN et qu'il est constant au cours du temps. Ainsi, à chaque génération, un individu a une probabilité $\mu$ d'avoir une mutation qui le différencie de son parent. Si l'on considère une séquence de $m$ bases, la probabilité que deux mutations aient lieu au même endroit est $1/m$. Comme les probabilités de mutation sont faibles, cela arrive très rarement. On fera donc l'hypothèse que l'on a une infinité d'allèles possibles et que chaque nouvelle mutation affecte un site différent. Ainsi, une mutation donne toujours un nouvel allèle. Le temps d'apparition d'une mutation dans la lignée ancestrale d'un individu est donc une loi géométrique de paramètre $\mu$. On pose $\theta = 2\mu N$ et on suppose que $\theta$ est d'ordre 1. Ainsi, lors du passage à la limite quand $N \to \infty$, le processus de mutation devient un processus de Poisson. Plus exactement, on munit chaque branche de l'arbre d'un processus de Poisson de paramètre $\theta/2$ qui comptera les mutations. Les deux processus de coalescence et mutation sont d'origines aléatoires différentes. Nous les considérerons indépendants.

**Théorème 13.5** (Loi du nombre d'allèles dans un échantillon). Si $K_n$ désigne le nombre d'allèles distincts dans un groupe de $n$ personnes alors

$$K_n \stackrel{\text{loi}}{=} \eta_1 + \dots + \eta_n$$

où $(\eta_k)_{k \ge 1}$ sont des v.a. indépendantes avec $\eta_k \sim \text{Ber}(\theta/(k - 1 + \theta))$, $k \ge 1$.

Notons que $\eta_1 = 1$ presque sûrement. La variable aléatoire $K_n$ correspond au nombre de tables dans le processus des restaurants chinois du chapitre 14. En particulier, on sait calculer les deux premiers moments, et on connaît le comportement asymptotique (convergence et fluctuation).

**Démonstration.** Pour un groupe de $n$ individus, on s'intéresse au premier temps (dans le passé) d'apparition d'une coalescence ou d'une mutation. Tout se passe comme si $U_n$ était le minimum entre $T_n$, premier temps de coalescence (de loi $\text{Exp}((n/2))$) et $R_1, \dots, R_n$ premiers temps de mutation des individus 1, \dots, $n$ de même loi $\text{Exp}(\theta/2)$. Puisque ces v.a.r. sont indépendantes, leur minimum suit la loi exponentielle de paramètre égal à (lemme 11.2)

$$\binom{n}{2} + n \frac{\theta}{2} = \frac{n(n-1+\theta)}{2},$$

et la probabilité que ce premier phénomène soit une coalescence vaut

$$\frac{\binom{n}{2}}{\frac{n(n-1+\theta)}{2}} = \frac{n-1}{n-1+\theta}.$$

De même, la probabilité pour que ce phénomène soit une mutation est donc

$$1 - \frac{n-1}{n-1+\theta} = \frac{\theta}{n-1+\theta}.$$
On pose $\eta_n = 1$ si ce premier phénomène est une mutation et $\eta_n = 0$ si c'est une coalescence. La variable aléatoire $\eta_n$ suit donc la loi de Bernoulli de paramètre $\theta/(n-1+\theta)$. Étudions ce qui se passe après ce temps $U_n$ :

— Si $\eta_n = 0$ alors le nombre d'ancêtres à l'instant $U_n$ est $n-1$ et le nombre d'allèles distincts dans ce groupe de $n-1$ individus est $K_{n-1} = K_n$.

— Si $\eta_n = 1$ alors l'individu qui a muté à l'instant $U_n$ est à l'origine d'un allèle différent. Il correspond, dans la population initiale de $n$ individus, à la présence d'un allèle distinct de tous les autres. De plus, cet allèle est présent une seule fois dans la population des $n$ ancêtres. On obtient donc une population de $n-1$ individus possédant $K_{n-1} = K_n - 1$ allèles distincts.

Dans tous les cas, on a obtenu $K_n = K_{n-1}+\eta_n$ et on considère à partir de l'instant $U_n$ une population de $n-1$ individus possédant $K_{n-1}$ allèles différents. Par récurrence, on obtient bien la décomposition de $K_n$ en somme de variables aléatoires de Bernoulli. La propriété de Markov du processus de coalescence et l'absence de mémoire du processus de mutation assure l'indépendance des variables aléatoires $(\eta_k)_k$. $\square$

On peut en fait décrire plus précisément la structure des allèles d'une population de $n$ individus. Dans le modèle à nombre d'allèles infini, un échantillon de taille $n$ peut être représenté par une configuration $c = (c_1, \dots, c_n)$ où $c_i$ est le nombre d'allèles représentés $i$ fois et $|c| = c_1 + 2c_2 + \dots + nc_n = n$. On notera $e_i = (0, 0, \dots, 0, 1, 0, \dots, 0)$ le $i$-ve vecteur unitaire. Il s'agit à présent d'établir une équation satisfaite par les probabilités ($q(c)$) où $q(c)$ est la probabilité qu'un échantillon de taille $|c|$ tiré sous la probabilité stationnaire ait la configuration $c$. On pose $q(e_1) = 1$. Supposons que la configuration soit $c$. En remontant la généalogie de l'échantillon jusqu'au premier changement, nous trouvons une mutation ou une coalescence (ancêtre commun à deux individus). Analysons ces deux événements :

— Le premier événement (mutation) a une probabilité (lemme 11.2)

$$ \frac{n\theta/2}{n\theta/2 + n(n-1)/2} = \frac{\theta}{\theta + n - 1}. $$

La configuration $b$ qui a conduit à la configuration $c$ est :

— $b = c$ si la mutation a eu lieu sur l'un des $c_1$ singletons (a lieu avec probabilité $c_1/n$),

— $b = c - 2e_1 + e_2$ si la mutation a eu lieu sur un des allèles représenté 2 fois (a lieu avec probabilité $2b_2/n = 2(c_2 + 1)/n$),

— $b = c - e_1 - e_{j-1} + e_j$ si la mutation a eu lieu sur un des allèles représenté $j$ fois (a lieu avec probabilité $jb_j/n = j(c_j + 1)/n$)

— Le second événement (coalescence) a lieu avec une probabilité qui vaut $(n-1)/(\theta+n-1)$ et dans ce cas, la configuration précédente était de la forme $b = c + e_j - e_{j+1}$ : un allèle présent $j$ fois (parmi les $c_j+1$) s'est dédoublé, ramenant de $c_j+1$ à $c_j$ le nombre d'allèles présent $j$.
fois et de $c_{j+1} - 1$ à $c_{j+1}$ le nombre d'allèles présent $j + 1$ fois. Cet événement a une probabilité de $jb_j/(n-1) = j(c_j + 1)/(n-1)$.

On retrouve le processus des restaurants chinois du chapitre 14, qui affirme que $\mathbf{c}$ suit la loi d'Ewens. On parle de formule d'échantillonnage d'Ewens en génétique<fnref n="4" /> : pour tous entiers $a_1, \dots, a_n$ vérifiant $a_1 + 2a_2 + \dots + na_n = n$,

$$ 
\begin{aligned}
q(\mathbf{c}) &= \mathbb{P}(c_1(n) = a_1, \dots, c_n(n) = a_n) \\
&= \frac{n!}{\theta(\theta+1) \dots (\theta+n-1)} \prod_{j=1}^{n} \left(\frac{\theta}{j}\right)^{c_j} \frac{1}{c_j}.
\end{aligned}
$$

## 13.4 Coalescent de Kingman

Le coalescent de Kingman est un processus à temps continu à valeurs dans l'ensemble $\mathcal{E}_n$ des relations d'équivalence sur $[n] = \{1, \dots, n\}$ c'est-à-dire l'ensemble des partitions de $[n]$. Il décrit la généalogie d'une population de taille $n$. Jusqu'à présent, nous avons proposé un modèle pour l'évolution temporelle du nombre d'ancêtres d'une population initiale donnée. Il s'agit à présent d'être plus précis en gardant trace des liens de parentés entre tous les individus. Numérotons les individus de 1 à $n$. À un instant $t$, on définit la relation d'équivalence $\sim$ sur $[n]$ par $i \sim j$ si et seulement si les individus $i$ et $j$ ont le même ancêtre commun au temps $t$. Chaque classe d'équivalence correspond à un ancêtre de la population initiale et les éléments de cette classe sont tous les descendants de cet individu. Soit $C(t)$ cette partition aléatoire.

Supposons que $C(0) = \alpha \in \mathcal{E}_n$ et notons $k$ le nombre de ses classes (on écrira $|\alpha| = k$). Lorsque $t$ augmente, nous progressons vers le passé et le processus reste constant jusqu'à l'apparition d'un ancêtre commun à deux des ancêtres de chaque classe. Lorsque ceci se produit, les deux ancêtres, et par conséquence tous leurs descendants, partagent cet ancêtre commun. Les deux classes d'équivalence sont donc regroupées (coalescent). Le taux d'apparition de cet événement est 1. Le processus $(C(t))_{t \ge 0}$ est le processus de Markov à temps continu sur $\mathcal{E}_n$ d'état initial $C(0) = \Delta = \{\{1\}, \{2\}, \dots, \{n\}\}$ (personne n'est rélié à personne), et de générateur $Q$

$$ Q(\alpha, \beta) = \begin{cases} -\binom{k}{2} & \text{si } \alpha = \beta \text{ et } |\alpha| = k, \\ 1 & \text{si } \alpha \sim \beta, \\ 0 & \text{sinon,} \end{cases} $$

où la notation $\alpha \sim \beta$ signifie que la partition $\beta$ peut être obtenue à partir de la partition $\alpha$ en fusionnant deux de ses classes d'équivalence. Le processus $C$ est appelé coalescent ou $n$-coalescent. Pour déterminer sa loi, il faut tout d'abord étudier la chaîne incluse $(C_k^{\text{inc}})_{k=n,n-1,\dots,1}$. Cette chaîne est issue de $\Delta$ et admet pour transitions :

<footnote n="4">4. «ESF : Ewens Sampling Formula» en anglais.</footnote>
$$
\mathbb{P}(C_{k-1}^{\text{inc}} = \beta | C_k^{\text{inc}} = \alpha) = \begin{cases} \frac{1}{\binom{k}{2}} & \text{si } \alpha \sim \beta \text{ et } |\alpha| = k, \\ 0 & \text{sinon.} \end{cases}
$$

Le processus C évolue donc selon une suite

$$
\Delta = C_n^{\text{inc}} \sim C_{n-1}^{\text{inc}} \sim \dots \sim C_1^{\text{inc}} = \Theta,
$$

où Θ est la partition triviale et passe en la partition $C_k^{\text{inc}}$ un temps exponentiel de paramètre $\binom{k}{2}$. Les taux de transition ne dépendent de la partition qu'au travers de son cardinal et

$$
|C(t)| = A_n(t),
$$

puisque les classes de $C(t)$ sont en bijection avec les ancêtres au temps $t$. Ainsi,
les processus $(A_n(t))_{t \ge 0}$ et $(C_k^{\text{inc}})_k$ sont indépendants et pour tout $t \ge 0$,

$$
C(t) = C_{A_n(t)}^{\text{inc}}.
$$

Plus précisément, on a

$$
\mathbb{P}(C(t) = \alpha) = \mathbb{P}(A_n(t) = |\alpha|)\mathbb{P}(C_{|\alpha|}^{\text{inc}} = \alpha).
$$

Théorème 13.6 (Loi du coalescent de Kingman). Soit $1 \le j \le n$ et $\alpha$
une partition de $[n]$ dont les classes d'équivalence admettent les cardinaux
$\lambda_1, \dots, \lambda_j$. Alors,

$$
\mathbb{P}(C_j^{\text{inc}} = \alpha) = \frac{(n-j)!j!(j-1)!}{n!(n-1)!} \lambda_1! \cdots \lambda_j!
$$

Démonstration. On procède par récurrence descendante. Le résultat est clair
pour $j=n$ (si $\alpha$ n’est pas la partition $\Delta$, sa probabilité d’apparition est nulle,
et $\Delta$ est la seule partition à $n$ classes, toutes singleton). Supposons que le
résultat soit vrai pour $j \ge 2$. Alors

$$
\begin{align*}
p_{j-1}(\beta) &:= \mathbb{P}(C_{j-1}^{\text{inc}} = \beta) \\
&= \sum_{\alpha \in \mathcal{E}_n} p_j(\alpha) \mathbb{P}(C_{j-1}^{\text{inc}} = \beta | C_j^{\text{inc}} = \alpha) \\
&= \sum_{\alpha \sim \beta} p_j(\alpha) \frac{2}{j(j-1)}.
\end{align*}
$$

Notons $\lambda_1, \dots, \lambda_{j-1}$ les tailles des classes d'équivalence de $\beta$. Celles de $\alpha$ sont

$$
\lambda_1, \dots, \lambda_{l-1}, m, \lambda_l - m, \lambda_{l+1}, \dots, \lambda_{j-1}
$$

pour un certain $1 \le l \le j-1$ et $1 \le m \le \lambda_l - 1$. Posons

$$
\pi_{l,m} := \lambda_1! \cdots \lambda_{l-1}! m! (\lambda_l - m)! \lambda_{l+1}! \cdots \lambda_{j-1}!
$$
Grâce à l'hypothèse de récurrence 5,

$$
\begin{align*}
p_{j-1}(\beta) &= \frac{1}{2} \sum_{l=1}^{j-1} \sum_{m=1}^{\lambda_l-1} \frac{2(n-j)!j!(j-1)!}{j(j-1)n!(n-1)!} \pi_{l,m} \binom{\lambda_l}{m} \\
&= \frac{(n-j)!(j-1)!(j-2)!}{n!(n-1)!} \lambda_1! \cdots \lambda_{j-1}! \sum_{l=1}^{j-1} \sum_{m=1}^{\lambda_l-1} 1 \\
&= \frac{(n-j+1)!(j-1)!(j-2)!}{n!(n-1)!} \lambda_1! \cdots \lambda_{j-1}!
\end{align*}
$$

$$
\mathrm{car} \sum_{l=1}^{j-1} \sum_{m=1}^{\lambda_l-1} 1 = \lambda_1 + \dots + \lambda_{j-1} - j + 1 = n - j + 1. \quad \square
$$

13.5 Pour aller plus loin

En biologie, la phylogénie est l'étude des relations de parenté entre êtres vivants. La modélisation stochastique en phylogénie est abordée par exemple dans les livres de Warren Ewens [Ewe04], de Rick Durrett [Dur08], et de Jean-François Delmas et Benjamin Jourdain [DJ06]. Les aspects statistiques sont abordés dans le cours de Simon Tavaré [Tav04]. John Kingman étudie le processus qui porte son nom dans [Kin93]. Son travail a donné lieu a de nombreux développements, notamment une théorie de la fragmentation et de la coalescence, en liaison avec les processus de branchement, les processus de Lévy, et les partitions aléatoires. On pourra consulter les livres de Nathanaël Berestycki [Ber09] et de Jean Bertoin [Ber06], ainsi que le cours de Saint-Flour de Jim Pitman [Pit06] et le cours de Sylvie Méléard [Mé13].

<footnote n="5">5. Le facteur 1/2 au début est dû à la permutation de *m* et *λ*<sub>*l*</sub> − *m*. Pour bien le comprendre, considérer les exemples *λ*<sub>*l*</sub> = 2 et *λ*<sub>*l*</sub> = 3.</footnote>
<figure><img src="image_41.png" /></figure>
Restaurants chinois

**Mots-clés.** Partition aléatoire ; permutation aléatoire ; loi d'Ewens ; algo-
rithme de Fisher-Yates-Knuth ; nombres de Bell ; nombres de Stirling.

**Outils.** Combinatoire ; groupe symétrique ; chaîne de Markov ; martin-
gale ; inégalité de Markov ; loi de Poisson.

Difficulté. **

Ce chapitre est consacré à l'étude de propriétés remarquables de la loi
d'Ewens, apparue dans le chapitre 13 comme la loi de la partition d'une po-
pulation en fonction des allèles d'un même gène dans un modèle à nombre
d'allèles infini. Les propriétés sont présentées sous la forme ludique du pro-
cessus dit des restaurants chinois mais ce sont bien les interactions avec la
biologie évoquées ci-dessus qui en sont la réelle motivation d'origine.

Pour tout entier $n \ge 1$, on note $S_n$ l'ensemble des permutations de $\{1, \dots, n\}$ (groupe symétrique). Le processus des restaurants chinois est une chaîne de Markov inhomogène $(\sigma_n)_{n \ge 1}$, d'espace d'états $\cup_{n \ge 1} S_n$, où $\sigma_n$ est à valeurs dans $S_n$ pour tout $n \ge 1$, de valeur initiale $\sigma_1 = (1)$, et de noyau de transition donné pour tous $(\sigma, \sigma') \in S_n \times S_{n+1}$ par

$$
P(\sigma_{n+1} = \sigma' | \sigma_n = \sigma) =
\begin{cases}
\frac{1}{\theta + n} & \text{si } \sigma' \text{ s'obtient en insérant } n+1 \text{ dans l'un des cycles de } \sigma; \\
\frac{\theta}{\theta + n} & \text{si } \sigma' \text{ s'obtient en ajoutant le cycle } (n+1) \text{ à } \sigma; \\
0 & \text{sinon;}
\end{cases}
$$
où $\theta \ge 0$ est un paramètre fixé qui ne dépend pas de $n$. Il s'agit bien d'un
noyau de transition car la somme des longueurs des cycles de $\sigma$ est $n$. Le
nom de ce processus provient de l'interprétation des cycles de $\sigma_n$ comme
les tables circulaires occupées par les $n$ clients d'un restaurant chinois, ces
restaurants où les gens s'attablent sans se connaître. Au temps initial 1, le
restaurant ne compte qu'une seule table occupée par un seul client numéroté
1. Par récurrence sur $n$, à l'instant $n+1$, et conditionnellement à tout le passé
$\sigma_1, \dots, \sigma_n$, un nouveau client, numéroté $n+1$, pénètre dans le restaurant, et
décide soit de rejoindre l'une des tables déjà occupées (cycles de $\sigma_n$) avec une
probabilité proportionnelle à la taille de la table (longueur du cycle), à une
place uniformément choisie, soit de s'asseoir à une table vide (créer un nouveau
cycle de longueur 1 contenant $n+1$). Cette interprétation gastronomique
suppose que les convives ne changent jamais de table, que les tables peuvent
avoir un nombre arbitrairement grand de convives, et que le restaurant peut
comporter un nombre arbitrairement grand de tables.

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

$$
\sigma_6 = (1, 6, 3)(2, 4)(5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 1 & 2 & 5 & 3 \end{pmatrix} \text{ et } \pi_6 = \{\{1, 6, 3\}, \{2, 4\}, \{5\}\}
$$

<caption>Fig. 14.1. Configuration avec $n = 6$ clients sur 3 tables dans le restaurant chinois.</caption>

Associons à la permutation aléatoire $\sigma_n$ la partition aléatoire $\pi_n$ de
$\{1, \dots, n\}$ donnée par le support des cycles. Chaque bloc de $\pi_n$ regroupe les
clients d'une table du restaurant. On a $\pi_1 = \{1\}$, et pour tout $n \ge 1$, $\pi_n$ est à
valeurs dans l'ensemble $\Pi_n$ des partitions de $\{1, \dots, n\}$. En général, l'image
d'une chaîne de Markov par une fonction n'est pas une chaîne de Markov<fnref n="1" />.
Cependant, il se trouve ici que $(\pi_n)_{n \ge 1}$ est une chaîne de Markov inhomogène
sur $\cup_{n \ge 1} \Pi_n$, de noyau de transition donné pour tous $(\pi, \pi') \in \Pi_n \times \Pi_{n+1}$ par

<footnote n="1">1. Un critère dû à Dynkin fournit une condition suffisante sur la fonction.</footnote>
$$
P(\pi_{n+1} = \pi' | \pi_n = \pi) =
\begin{cases}
\frac{|b|}{\theta + n} & \text{si } \pi' \text{ s'obtient en insérant } n+1 \\
& \text{dans le bloc } b \text{ de } \pi; \\[2ex]
\frac{\theta}{\theta + n} & \text{si } \pi' \text{ s'obtient en ajoutant} \\
& \text{le bloc singleton } \{n+1\} \text{ à } \pi; \\[2ex]
0 & \text{sinon;}
\end{cases}
$$

où $|b|$ désigne le cardinal de $b$. On a $\sum_{b \in \pi_n} |b| = n$ où $b \in \pi_n$ signifie que $b$ est un bloc de $\pi_n$.

**Remarque 14.1** (Cas extrêmes). Lorsque $\theta = 0$ on a $\pi_n = \{\{1, \dots, n\}\}$ tandis que si $\theta = \infty$ alors $\pi_n = \{\{1\}, \dots, \{n\}\}$. Les probabilités sont monotones en $\theta$. Plus $\theta$ est grand, plus les clients ont tendance à s'asseoir à une table vide plutôt que de rejoindre une table occupée.

**Remarque 14.2** (Remonter le temps). Sur ce début de trajectoire de $(\pi_n)_{n \ge 1}$,

$$
\begin{align*}
\pi_1 &= \{\{1\}\} \\
\pi_2 &= \{\{1\}, \{2\}\} \\
\pi_3 &= \{\{1, 3\}, \{2\}\} \\
\pi_4 &= \{\{1, 3\}, \{2\}, \{4\}\} \\
\vdots &\vdots
\end{align*}
$$

on remarque immédiatement qu'il est possible de remonter le temps. Par exemple, à partir de $\pi_4$, on en déduit $\pi_3$ en repérant le bloc contenant 4, puis on en déduit $\pi_2$ en repérant le bloc contenant 3, puis $\pi_1$ en repérant le bloc contenant 2. Plus généralement, pour tout $n \ge 1$ et tout $\pi' \in \Pi_{n+1}$, il existe un unique $\pi \in \Pi_n$ tel que $\mathbb{P}(\pi_{n+1} = \pi' | \pi_n = \pi) > 0$. L'information sur $\pi_n$ est intégralement contenue dans $\pi_{n+1}$ sans dégradation. Le processus transporte intégralement son passé.

**14.1 Lois d'Ewens**

On note $|\pi|$ le nombre de blocs de la partition $\pi \in \Pi_n$ et $|\sigma|$ le nombre de cycles de la permutation $\sigma \in S_n$. Ainsi on a $|\pi_n| = |\sigma_n|$ pour tout $n \ge 1$.

**Théorème 14.3** (Loi d'Ewens sur $S_n$). Pour tout $\sigma \in S_n$, on a

$$
P(\sigma_n = \sigma) = \frac{\theta^{|\sigma|}}{\theta(\theta+1) \cdots (\theta+n-1)}.
$$

Démonstration. La formule est vraie pour $n = 1$. Procédons par récurrence sur $n$ et supposons-la vraie pour $n \ge 1$. Soit $\sigma' \in S_{n+1}$. On observe tout
d'abord qu'il existe un unique $\sigma \in S_n$ tel que $P(\sigma_{n+1} = \sigma' | \sigma_n = \sigma) > 0$. Si $|\sigma'| = |\sigma| + 1$ alors $P(\sigma_{n+1} = \sigma' | \sigma_n = \sigma) = \theta/(\theta + n)$ et si $|\sigma'| = |\sigma|$ alors $P(\sigma_{n+1} = \sigma' | \sigma_n = \sigma) = 1/(\theta + n)$. Dans les deux cas, on a bien

$$ P(\sigma_{n+1} = \sigma') = P(\sigma_n = \sigma) P(\sigma_{n+1} = \sigma' | \sigma_n = \sigma) = \frac{\theta^{|\sigma'|}}{\theta(\theta+1)\cdots(\theta+n)}. $$

□

**Remarque 14.4** (Marche aléatoire, transpositions, et loi uniforme sur $S_n$). Conditionnellement à $\{\sigma_n = \sigma\}$, on peut construire $\sigma_{n+1}$ à partir de $\sigma$ en choisissant d'abord un élément aléatoire $K$ de $\{1, \dots, n+1\}$ valant $n+1$ avec probabilité $\theta/(\theta+n)$ et $1, \dots, n$ avec probabilité $1/(\theta+n)$, puis en ajoutant $n+1$ au cycle de $\sigma$ contenant $K$ si $K \le n$ ou en créant un nouveau cycle ($n+1$) si $K = n+1$. Ceci revient à fabriquer à partir de $\sigma$ un élément $\sigma'$ de $S_{n+1}$ en ajoutant à $\sigma$ le cycle ($n+1$), puis à calculer le produit $\sigma'\tau$ dans $S_{n+1}$ où $\tau$ est la transposition aléatoire ($n+1, K$). Ainsi

$$ (\sigma_n)_{n \ge 1} \stackrel{\text{loi}}{=} ((1, K_1) \cdots (n, K_n))_{n \ge 1} $$

où $(K_n)_{n \ge 1}$ est une suite de variables aléatoires indépendantes avec $K_1 = 1$ et pour tout $n \ge 1$, $K_{n+1}$ de loi $\frac{1}{\theta+n}\delta_1 + \dots + \frac{1}{\theta+n}\delta_n + \frac{\theta}{\theta+n}\delta_{n+1}$, et $(\sigma_n)_{n \ge 0}$ est une marche aléatoire sur $S_n$, non homogène en temps, sur le graphe de Cayley de $S_n$ engendré par les transpositions. Si $\theta = 1$ alors pour tout $n \ge 1$, $K_n$ suit la loi uniforme sur $\{1, \dots, n\}$, tandis que $\sigma_n$ suit la loi uniforme sur $S_n$, et on retrouve l'algorithme de Fisher-Yates-Knuth du théorème 4.1.

**Théorème 14.5** (Loi d'Ewens sur $\Pi_n$). Pour tout $\pi \in \Pi_n$, on a

$$ P(\pi_n = \pi) = \frac{\theta^{|\pi|}}{\theta(\theta+1)\cdots(\theta+n-1)} \prod_{b \in \pi} (|b| - 1)! $$

*Démonstration.* Le théorème 14.3 donne

$$ P(\pi_n = \pi) = \sum_{\sigma \in E_{\pi}} P(\sigma_n = \sigma) = \frac{\theta^{|\pi|}}{\theta(\theta+1)\cdots(\theta+n-1)} |E_{\pi}| $$

où $E_{\pi}$ est l'ensemble des $\sigma \in S_n$ dont la partition de la décomposition en cycles est $\pi$. Il y a $(k-1)!$ cycles de longueur $k$ d'un ensemble à $k$ éléments donc le cardinal de $E_{\pi}$ est donné par $\prod_{b \in \pi} (|b| - 1)!$. □

**Remarque 14.6** (Loi d'Ewens et loi uniforme sur $\Pi_n$). Pour $n \ge 3$, quel que soit $\theta$, la loi d'Ewens sur $\Pi_n$ n'est jamais la loi uniforme étudiée dans le cha-pitre 4. En effet, notons $\pi = \{\{1\}, \{2\}, \dots, \{n\}\}$, $\pi' = \{\{1, 2\}, \{3\}, \dots, \{n\}\}$, $\pi'' = \{\{1, 2, \dots, n\}\}$. Alors $P(\pi_n = \pi) = P(\pi_n = \pi')$ uniquement pour $\theta = 1$ et dans ce cas $P(\pi_n = \pi) \ne P(\pi_n = \pi'')$.
Pour tout temps $n \ge 1$ et tout $1 \le k \le n$, soit $A_{n,k}$ le nombre de tables de taille $k$ au temps $n$, c'est-à-dire le nombre de blocs de taille $k$ dans la partition aléatoire $\pi_n$. On a

$$n = A_{n,1} + 2A_{n,2} + \cdots + nA_{n,n} \quad \text{et} \quad |\pi_n| = A_{n,1} + \cdots + A_{n,n}.$$

**Théorème 14.7** (Loi d'Ewens sur les blocs). *Pour tout $n \in \mathbb{N}^*$ et tout $(a_1, \dots, a_n) \in \mathbb{N}$ vérifiant $a_1 + 2a_2 + \dots + na_n = n$, on a*

$$P(A_{n,1} = a_1, \dots, A_{n,n} = a_n) = \frac{n!}{\theta(\theta+1)\dots(\theta+n-1)} \prod_{j=1}^{n} \frac{1}{a_j!} \left(\frac{\theta}{j}\right)^{a_j}.$$

*Démonstration.* Le théorème 14.5 donne

$$P(A_{n,1} = a_1, \dots, A_{n,n} = a_n) = \frac{\theta^{a_1+\dots+a_n}}{\theta(\theta+1)\dots(\theta+n-1)} \prod_{j=1}^{n} ((j-1)!)^{a_j} |\Pi_n(a)|$$

où $\Pi_n(a)$ désigne l'ensemble des $\pi \in \Pi_n$ comportant $a_k$ blocs de taille $k$ pour tout $1 \le k \le n$. Or l'ensemble $\Pi_n(a)$ a pour cardinal

$$\frac{n!}{\prod_{j=1}^{n} (j!)^{a_j} a_j!},$$

d'où la formule.

□

**Remarque 14.8** (Apparition et maintient de petites tables). *Le processus des restaurants chinois permet l'apparition de petites tables et le maintient de leur présence au fil du temps car elles sont choisies au prorata de leur taille!*

## 14.2 Nombre de tables

Au temps $n \ge 1$, la salle du restaurant se compose de $|\pi_n|$ tables occupées.

**Théorème 14.9** (Nombre de tables). *Pour tout $n \ge 1$, on a*

$$E(|\pi_n|) = \sum_{k=0}^{n-1} \frac{\theta}{\theta + k} = \theta \log(n) + \mathcal{O}_{n \to \infty}(1) \underset{n \to \infty}{\sim} \theta \log(n),$$

et

$$\mathrm{Var}(|\pi_n|) = \sum_{k=1}^{n-1} \frac{\theta k}{(\theta + k)^2} = \theta \log(n) + \mathcal{O}_{n \to \infty}(1) \underset{n \to \infty}{\sim} \theta \log(n).$$
<figure><img src="image_43.png" /><figcaption>**Fig. 14.2.** Histogramme d'un échantillon de taille 5000 de la loi d'Ewens de taille $n = 1000$ et de paramètre $\theta = 1$.</figcaption></figure>

*Démonstration.* La suite markovienne $(\pi_n)_{n \ge 1}$ a la même loi que la suite récurrente aléatoire définie par $\pi_1 = \{\{1\}\}$ puis pour tout $n \ge 1$ par

$$ \pi_{n+1} = f_n(\pi_n, \varepsilon_{n+1}) $$

où $(\varepsilon_n)_{n \ge 1}$ sont des variables aléatoires i.i.d. de loi uniforme sur $[0, 1]$, et où $f_n(\pi, \varepsilon)$ est l'élément de $\Pi_{n+1}$ obtenu à partir de $\pi \in \Pi_n$ soit en ajoutant $n+1$ au bloc $b_k$ de $\pi$ si $\varepsilon \in [(|b_1| + \cdots + |b_{k-1}|)/(\theta + n), (|b_1| + \cdots + |b_k|)/(\theta + n)]$ avec $1 \le k \le |\pi|$, où $b_1, \dots, b_{|\pi|}$ sont les blocs de $\pi$, soit en ajoutant le bloc $\{n+1\}$ à la partition $\pi$ si $\varepsilon \in [n/(\theta + n), (\theta + n)/(\theta + n)]$. On rappelle que $n = |b_1| + \cdots + |b_{|\pi|}|$. On a alors $|\pi_n| = \xi_1 + \cdots + \xi_n$ pour tout $k \ge 1$, où

$$ \xi_k := 1\{\varepsilon_k \in [\frac{k-1}{\theta+k-1}, \frac{\theta+k-1}{\theta+k-1}]\}. $$

La suite $(\xi_k)_{k \ge 1}$ est constituée de variables aléatoires indépendantes de lois de Bernoulli, et pour tout $k \ge 1$

$$ P(\xi_k = 1) = 1 - P(\xi_k = 0) = \frac{\theta}{\theta + k - 1}. $$

L'événement $\{\xi_n = 1\}$ signifie que le client $n$ décide de créer sa propre table, tandis que l'événement $\{\xi_n = 0\}$ signifie qu'il décide de rejoindre une table
existante. En particulier, $\xi_1 = 1$ p.s. Cela donne pour $\mathrm{E}(|\pi_n|)$ et $\mathrm{Var}(|\pi_n|)$ les formules en sommes. À ce stade, on rappelle la comparaison série-intégrale suivante : si $f : \mathbb{R}_+ \to \mathbb{R}_+$ est une fonction continue et décroissante alors

$$ \int_0^{n+1} f(t) dt \le \sum_{k=0}^{n} f(k) \le f(0) + \int_0^n f(t) dt. $$

Donc $\mathrm{E}(|\pi_n|)$ et $\mathrm{Var}(|\pi_n|)$ valent $\theta \log(n) + \mathcal{O}_{n \to \infty}(1) \sim_{n \to \infty} \theta \log(n)$. $\square$

**Remarque 14.10** (Un jeu de pile ou face inhomogène). Par construction, $(|\pi_n|)_{n \ge 1}$ est p.s. croissante et ne fait que des sauts de +1. Elle constitue le processus de comptage partant de 1 de tops espacés par des durées aléatoires indépendantes. Cependant, ces durées ne sont pas de même loi, et ne sont pas de loi géométrique. Il s'agit plutôt d'un jeu de pile ou face où la probabilité de gagner change à chaque lancer. Bien que $(\pi_n)_{n \ge 1}$ soit croissante, elle est cependant de moins en moins croissante en quelque sorte puisque la quantité

$$ p_n = \mathbb{P}(|\pi_{n+1}| = |\pi_n| + 1) = \mathbb{P}(\xi_{n+1} = 1) = \theta(\theta + n)^{-1} $$

décroît quand n croît. Malgré tout, la moyenne et la variance de $|\pi_n|$ sont équivalentes à $\theta \log(n)$ lorsque n tend vers $\infty$. La situation diffère du cas du collectionneur de coupons du chapitre 1, pour lequel la probabilité de gagner change après chaque succès.

**Théorème 14.11** (Asymptotique du nombre de tables). On a

$$ \frac{|\pi_n|}{\log(n)} \xrightarrow{n \to \infty} \theta \quad \text{et en particulier} \quad \frac{|\pi_n|}{\log(n)} \xrightarrow{n \to \infty} \theta. $$

*Démonstration.* Grâce au théorème 14.9, quand $n \to \infty$,

$$ \begin{aligned} \mathrm{E} \left( \left( \frac{|\pi_n|}{\log(n)} - \theta \right)^2 \right) &= \frac{\mathrm{Var}(|\pi_n|) + (\mathrm{E}(|\pi_n|) - \theta \log(n))^2}{(\log(n))^2} \\ &= \mathcal{O} \left( \frac{1}{\log(n)} \right) = o(1). \end{aligned} $$

La convergence en probabilité s'obtient grâce à l'inégalité de Markov. $\square$

Le résultat suivant affirme que la convergence a lieu presque sûrement. La borne $\mathcal{O}(1/\log(n))$ obtenue par la méthode du second moment ci-dessus n'est pas sommable, ce qui ne permet pas d'obtenir la convergence presque sûre par application du lemme de Borel-Cantelli. Cela suggère cependant de considérer un moment d'ordre plus élevé. Alternativement, on peut chercher à se ramener à un résultat sur les martingales.

**Théorème 14.12** (Asymptotique du nombre de tables). On a

$$ \frac{|\pi_n|}{\log(n)} \xrightarrow{\text{p.s.}} \theta. $$
Démonstration. Soient $(\xi_n)_{n \ge 1}$ comme dans la preuve du théorème 14.9. Alors

$$ \left( \frac{|\pi_n|}{\log(n)} \right)_{n \ge 2} \stackrel{\text{loi}}{=} \left( \frac{1}{\log(n)} \sum_{k=1}^{n} \xi_k \right)_{n \ge 2} . $$

Notons que $\xi_1 = 1$ p.s. et donc $\xi_1 - E(\xi_1) = 0$. Pour tout $n \ge 2$, on a

$$ \frac{1}{\log(n)} \sum_{k=1}^{n} \xi_k = \frac{1}{\log(n)} \sum_{k=2}^{n} (\xi_k - E(\xi_k)) + \frac{1}{\log(n)} \sum_{k=1}^{n} E(\xi_k). $$

Le second terme du membre de droite converge vers $\theta$ quand $n \to \infty$ grâce au théorème 14.9. Il suffit donc d'établir que le premier terme du membre de droite converge presque sûrement vers 0. Or si

$$ S_n := \sum_{k=2}^{n} Y_k \quad \text{avec} \quad Y_k := \frac{\xi_k - E(\xi_k)}{\log(k)} $$

alors $(S_n)_{n \ge 2}$ est une martingale bornée dans $L^2$ car (théorème 14.9)

$$ E(S_n^2) = \sum_{k=2}^{n} \frac{\text{Var}(\xi_k)}{(\log(k))^2} \le \sum_{k=2}^{\infty} \frac{\theta}{(\theta + k - 1)(\log(k))^2} < \infty. $$

Il est utile de rappeler à ce stade que la série de Bertrand

$$ \sum_{k=2}^{\infty} \frac{1}{k(\log(k))^{\beta}} $$

converge ssi $\beta > 1$. Étant bornée dans $L^2$, la martingale $(S_n)_{n \ge 2}$ converge p.s. (et dans $L^2$) vers une variable aléatoire dans $L^2$ (donc finie p.s.). Le lemme de Kronecker² assure alors la convergence p.s. vers 0 quand $n \to \infty$ de

$$ \frac{1}{\log(n)} \sum_{k=2}^{n} \log(k) Y_k = \frac{1}{\log(n)} \sum_{k=2}^{n} (\xi_k - E(\xi_k)). $$

Notons qu'alternativement au théorème sur les martingales, on pourrait utiliser le théorème des séries centrées (théorème 10.3). □

**Théorème 14.13** (Asymptotique en loi du nombre de tables). On a

$$ \frac{|\pi_n| - E(|\pi_n|)}{\sqrt{\text{Var}(|\pi_n|)}} \xrightarrow{n \to \infty} \mathcal{N}(0, 1). $$

De plus $E(|\pi_n|)$ et $\text{Var}(|\pi_n|)$ peuvent être remplacés par $\theta \log(n)$.

2. Si $\sum_n x_n$ converge alors $\lim_{n \to \infty} b_n^{-1} \sum_{k=1}^n b_k x_k = 0$ lorsque $0 < b_n \nearrow \infty$.
Démonstration. Tout d'abord, on note que $\mathbb{E}(|\pi_n|)$ et $\mathrm{Var}(|\pi_n|)$ peuvent être remplacés par $\theta \log(n)$ en utilisant le lemme de Slutsky et le théorème 14.9.

Le résultat découle du théorème de Berry-Esseen de la section 1.6 utilisé avec $X_k = \xi_k$ de loi de Bernoulli de moyenne $\theta/(\theta + k - 1)$. On obtient même une vitesse de convergence uniforme pour les fonctions de répartition ! Le résultat peut également être obtenu en utilisant le théorème limite central de Lindeberg-Lévy pour les sommes de variables aléatoires indépendantes pas forcément de même loi, ou encore en utilisant le théorème limite central pour les martingales de carré intégrable avec normalisation par processus croissant.

Une preuve alternative peut être obtenue en utilisant l'inégalité de Le Cam renforcée de la section 1.6, avec $p_k = \theta/(\theta + k - 1)$. En effet, cela donne $d_{\mathrm{VT}}(\mu_n, \nu_n) = o_{n \to \infty}(1)$, et par conséquent, pour toute fonction continue et bornée $f: \mathbb{R} \to \mathbb{R}$, on a, avec $\sigma_n^2 = \mathrm{Var}(|\pi_n|)$,

$$ \left| \mathbb{E} \left( f \left( \frac{|\pi_n| - \lambda_n}{\sigma_n} \right) \right) - \mathbb{E} \left( f \left( \frac{P_n - \lambda_n}{\sigma_n} \right) \right) \right| \le 2 \|f\|_{\infty} d_{\mathrm{VT}}(\mu_n, \nu_n) \xrightarrow{n \to \infty} 0. $$

où $P_n$ désigne une variable aléatoire qui suit la loi de Poisson de moyenne $\lambda_n = p_1 + \cdots + p_n$. D'autre part, par le théorème limite central, le théorème 14.9 qui donne $\sqrt{\lambda_n}/\sigma_n \to 1$, et le lemme de Slutsky, on a

$$ \frac{P_n - \lambda_n}{\sigma_n} = \frac{P_n - \lambda_n}{\sqrt{\lambda_n}} \xrightarrow{n \to \infty} \mathcal{N}(0, 1). $$

□

La preuve précédente montre que la poissonisation est utile même si la moyenne diverge : $\lambda_n = p_1 + \cdots + p_n \to \infty$. D'autre part, on a $p_1^2 + \cdots + p_n^2 \not\to 0$ et donc l'inégalité de Le Cam $d_{\mathrm{VT}}(\mu_n, \nu_n) = \mathcal{O}(p_1^2 + \cdots + p_n^2)$ ne suffit pas.

## 14.3 Tables extrêmes

À l'instant $n$ le restaurant compte $A_{n,1}$ tables réduites à un seul client. La combinatoire permet d'obtenir la loi de $A_{n,1}$. Contentons-nous ici des deux premiers moments.

**Théorème 14.14 (Clients solitaires).** Pour tout temps $n \ge 1$, le nombre $A_{n,1}$ de tables réduites à un seul client vérifie

$$ \mathbb{E}(A_{n,1}) = \frac{n\theta}{n + \theta - 1} \quad \text{et} \quad \mathrm{Var}(A_{n,1}) = \frac{n(n-1)(n-2+2\theta)\theta}{(n+\theta-2)(n+\theta-1)^2}. $$

En particulier, si $\theta = 1$ alors $\mathbb{E}(A_{n,1}) = \mathrm{Var}(A_{n,1}) = 1$ pour tout $n \ge 1$, tandis que pour tout $\theta$,

$$ \lim_{n \to \infty} \mathbb{E}(A_{n,1}) = \theta \quad \text{et} \quad \lim_{n \to \infty} \mathrm{Var}(A_{n,1}) = \theta. $$
Notons que pour $\theta = 1$, la permutation aléatoire $\sigma_n$ suit la loi uniforme sur $S_n$, et possède $|\sigma_n| = |\pi_n| \sim \log(n)$ cycles, et en moyenne $E(A_{n,1}) = 1$ point fixe pour tout $n \ge 1$.

*Démonstration.* Il s'agit de décrire la loi de la première composante $A_{n,1}$ d'un vecteur aléatoire $A_n$ de $\mathbb{N}^n$ qui suit la loi d'Ewens. Il est cependant plus commode de voir $A_{n,1}$ comme le nombre de blocs de taille 1 dans $\pi_n$. On a $A_{1,1} = 1$ et $0 \le A_{n,1} \le n$ pour tout $n \in \mathbb{N}^*$. De plus, pour tous entiers $1 \le a_1, \dots, a_n \le n$ et $0 \le a_{n+1} \le n+1$ on a

$$P(A_{n+1,1} = a_{n+1} | A_{1,1} = a_1, \dots, A_{n,1} = a_n) = P(A_{n+1,1} = a_{n+1} | A_{n,1} = a_n)$$

qui vaut

$$ \begin{cases} \frac{\theta}{\theta + n} & \text{si } a_{n+1} = a_n + 1 \text{ (s'attabler seul à une table vide)}; \\ \frac{a_n}{\theta + n} & \text{si } a_{n+1} = a_n - 1 \text{ (rejoindre la table d'un solitaire)}; \\ \frac{n - a_n}{\theta + n} & \text{si } a_{n+1} = a_n \text{ (rejoindre une table comptant 2 clients ou +)}; \\ 0 & \text{sinon.} \end{cases} $$

En particulier, $(A_{n,1})_{n \ge 1}$ est une chaîne de Markov inhomogène d'espace d'états $\mathbb{N}$. On obtient la remarquable formule affine<fnref n="3" />

$$E(A_{n+1,1} | A_{n,1} = a) = \frac{a(\theta + n - 1) + \theta}{\theta + n}.$$

Cela donne $(n+\theta)m_{n+1} = (\theta+n-1)m_n + \theta$ où $m_n := E(A_{n,1})$. La formule annoncée pour $m_n$ s'en déduit. Pour la variance, les calculs sont semblables mais plus lourds, et utilisent la formule

$$\mathrm{Var}(X) = \mathrm{E}(\mathrm{Var}(X | Y)) + \mathrm{Var}(\mathrm{E}(X | Y))$$

où $\mathrm{Var}(X | Y) := \mathrm{E}(X^2 | Y) - \mathrm{E}(X | Y)^2$ est la variance conditionnelle. $\square$

L'entier $A_{n,n}$ représente le nombre de tables comportant $n$ clients, autrement dit le nombre de blocs de taille $n$ dans $\pi_n$. Lorsqu'une telle table existe, elle regroupe tous les clients, et on dit donc qu'il s'agit d'une table unique. On a $A_{n,n} = 1$ si et seulement si $|\pi_n| = 1$. Le théorème suivant précise les choses, et montre en particulier qu'asymptotiquement, le modèle des restaurants chinois ne fait pas apparaître de table unique.

<footnote n="3">3. Une martingale se cache dans la chaîne de Markov !</footnote>
**Théorème 14.15** (Table unique). On a $A_{1,1} = 1$ et $A_{n,n} \in \{0,1\}$ pour tout $n \ge 1$. Pour tout $n \ge 2$, la probabilité qu'il n'y ait qu'une seule table vaut

$$P(A_{n,n} = 1) = \prod_{k=1}^{n-1} \frac{k}{\theta + k}.$$

Enfin, la suite $(A_{n,n})_{n \ge 1}$ décroît presque sûrement vers 0.

**Démonstration.** Les premières assertions du théorème découlent directement de la définition de $\pi_n$. L'expression de la probabilité $P(A_{n,n} = 1)$ s'obtient en notant que $P(A_{n,n} = 1) = P(\xi_2 = 0, \dots, \xi_n = 0) = P(\xi_2 = 0) \cdots P(\xi_n = 0)$. Pour la convergence presque sûre, on remarque d'abord que, puisque $\theta > 0$, le produit infini $\prod_{k=1}^{\infty} (1 + \theta k^{-1})$ diverge car la série harmonique diverge, et par conséquent $\lim_{n \to \infty} P(A_{n,n} = 1) = 0$. D'autre part, la suite d'événements $(E_n)_{n \ge 1}$ définie par $E_n = \{A_{n,n} = 0\}$ est croissante, et donc

$$P\left(\lim_{n \to \infty} A_{n,n} = 0\right) = P\left(\bigcup_{n=1}^{\infty} E_n\right) = \lim_{n \to \infty} P(E_n) = 1 - \lim_{n \to \infty} P(A_{n,n} = 1) = 1.$$

En fait, $A_{n,n} = 1_{\{n<T\}}$ où $T := \inf\{n \ge 1 : \xi_n = 1\}$ est l'instant de premier succès dans un jeu de pile ou face dont la probabilité de gagner change à chaque lancer, et décroît vers 0 au fil du temps. La décroissance est cependant suffisamment lente pour assurer un succès certain. En effet $\{T < \infty\} = \bigcup_{n=1}^{\infty} E_n$ et donc $P(T < \infty) = 1$. Alternativement, on peut utiliser le lemme de Borel-Cantelli pour les événements indépendants $F_n = \{\xi_n = 1\}$ qui vérifient

$$\sum_{n \ge 1} P(F_n = 1) = \sum_{n \ge 1} \frac{\theta}{\theta + n} = \infty$$

et

$$\overline{\lim} F_n = \{ \sum_{n \ge 1} 1_{\{\xi_n = 1\}} = \infty \} \subset \{T < \infty\}.$$

□

## 14.4 Compléments de combinatoire

Le cardinal de $B_n$ est le $n$-ème nombre de Bell $B_n$ (chapitre 4). On a

$$B_n = \sum_{k=1}^{n} \binom{n}{k}$$

où la notation entre accolades désigne le nombre de Stirling de seconde espèce, qui compte le nombre de partitions à $k$ blocs de $\{1, \dots, n\}$. On dispose de la formule de récurrence
$$ \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} + k \begin{pmatrix} n-1 \\ k \end{pmatrix} $$

avec conditions au bord

$$ \begin{pmatrix} n \\ 1 \end{pmatrix} = 1 \quad \text{et} \quad \begin{pmatrix} n \\ n \end{pmatrix} = 1 $$

car pour choisir une partition de $\{1, \dots, n\}$ ayant $k$ blocs il faut et il suffit soit de choisir une partition de $\{1, \dots, n-1\}$ ayant $k-1$ blocs et de la compléter avec le bloc singleton $\{n\}$, soit d'ajouter l'élément $n$ à l'un des $k$ blocs d'une partition de $\{1, \dots, n-1\}$ ayant $k$ blocs. Si $X$ est une variable aléatoire de loi de Poisson de paramètre $\lambda$ alors

$$ \mathbb{E}(X^n) = \sum_{k=1}^{n} \begin{pmatrix} n \\ k \end{pmatrix} \lambda^k \quad \text{en particulier} \quad \mathbb{E}(X^n) = B_n \quad \text{si } \lambda = 1. $$

On dispose également de la formule explicite suivante :

$$ \begin{pmatrix} n \\ k \end{pmatrix} = \frac{1}{k!} \sum_{j=1}^{k} (-1)^{k-j} \binom{k}{j} j^n $$

qui peut s'obtenir grâce au principe d'inclusion-exclusion car le nombre de Stirling de seconde espèce est égal au nombre de surjections de $\{1, \dots, n\}$ dans $\{1, \dots, k\}$ divisé par $k!$.

Une partition de $\{1, \dots, n\}$ prescrit le support des cycles mais ne précise pas la structure interne de chaque cycle. Il peut donc y avoir plusieurs permutations pour chaque partition. Le nombre de permutations de $\{1, \dots, n\}$ qui possèdent exactement $k$ cycles est donné par le nombre de Stirling de première espèce non signé, noté

$$ \begin{bmatrix} n \\ k \end{bmatrix}, $$

égal au coefficient de $x^k$ dans le polynôme de Pochhammer

$$ x_{(n)} = x(x+1)\cdots(x+n-1). $$

## 14.5 Pour aller plus loin

L'essentiel de ce chapitre est tiré de l'article didactique [CDM13]. Warren Ewens est un professeur de biologie mathématique né en 1937 en Australie. C'est à la fin des années 1960 qu'il découvre la loi qui porte aujourd'hui son nom, en étudiant un problème d'échantillonnage en génétique des populations, lié au modèle de Wright-Fisher, abordé dans le chapitre 12. Le paramètre $\theta$
apparaît comme un taux de mutation des allèles, comme expliqué dans le cha-
pitre 13. Une synthèse sur le sujet se trouve dans son livre [Ewe04], ainsi que
dans ceux de John Kingman [Kin80] et de Rick Durrett [Dur08], ou encore
dans le cours de Sylvie Méléard [Mé13]. De nombreux aspects statistiques sont
abordés dans le cours de Simon Tavaré [Tav04]. Le travail d’Ewens a engendré
un nombre considérable de travaux en biologie quantitative et en probabilités.
La loi d’Ewens apparaît dans une large gamme de structures aléatoires dis-
crètes dites logarithmiques, allant de la combinatoire à la théorie des nombres.
On pourra consulter à ce sujet le livre de Richard Arratia, Andrew Barbour,
et Simon Tavaré [ABT03]. Il semble que le processus des restaurants chinois
doive son nom à Jim Pitman. Il apparaît sous ce nom dans un cours de David
Aldous [Ald85]. Fred Hoppe a montré dans [Hop84] qu’on peut le relier à un
modèle d’urne de type Pólya. On peut aussi le relier aux processus de Diri-
chlet et aux partitions aléatoires de [0, 1] (voir ci-dessous). De nos jours, le
processus des restaurants chinois et la loi d’Ewens font partie du folklore d’une
théorie plus générale de la (fragmentation et de la) coalescence. On pourra à
ce sujet consulter les livres de Kingman [Kin93], de Jean Bertoin [Ber06], de
Pitman [Pit06], ainsi que de Nathanaël Berestycki [Ber09].

Voici deux autres représentations remarquables de la loi d'Ewens :

1. Si $Z_1, \dots, Z_n$ sont des variables aléatoires indépendantes de lois de Poisson de moyennes $\theta/1, \dots, \theta/n$ alors

$$
\text{Loi}(Z_1, \dots, Z_n | Z_1 + 2Z_2 + \dots + nZ_n = n) \sim \text{Ewens}(n, \theta);
$$

2. Soit $(P_r)_{r \ge 1}$ la loi sur $\mathbb{N}^*$ aléatoire générée à partir de la partition aléatoire suivante de l'intervalle $[0, 1]$ conçu comme un bâton de craie<fnref n="4" /> :

$$
P_1 = W_1, \quad P_2 = (1 - W_1)W_2, \quad P_3 = (1 - W_1)(1 - W_2)W_3, \dots
$$

où $(W_r)_{r \ge 1}$ sont des variables aléatoires i.i.d. de loi Beta$(1, \theta)$ de densité $w \mapsto \theta(1-w)^{\theta-1} \mathbb{1}_{[0,1]}(w)$. Conditionnellement à $(P_r)_{r \ge 1}$, soient $X_1, \dots, X_n$ des variables aléatoires i.i.d. sur $\mathbb{N}^*$ de loi $(P_r)_{r \ge 1}$. La suite $X_1, \dots, X_n$ fait apparaître au plus $n$ entiers différents. Il se trouve que leurs effectifs suit la loi $\text{Ewens}(n, \theta)$ !

Signalons enfin qu’il est possible d’établir que pour tous $0 \le k \le n$,

$$
P(|\pi_n| = k) = \binom{n}{k} \frac{\theta^k}{\theta(\theta+1) \cdots (\theta+n-1)}
$$

et d'obtenir une formule du même genre pour la loi du couple $(A_n, |\pi_n|)$, voir
l'article de Ewens et Tavaré dans [JKB97].

<footnote n="4">4. Cette construction est connue sous le nom de « stick breaking » en anglais.</footnote>
<figure><img src="image_44.png" /></figure>
# Renforcement

**Mots-clés.** Renforcement ; urne ; graphe aléatoire ; attachement préférentiel ; loi de puissance.

**Outils.** Chaîne de Markov ; martingale ; marche aléatoire ; échangeabilité ; loi exponentielle.

## Difficulté. **

Le phénomène du renforcement est très présent dans la nature, notamment en génétique, en physique statistique, en sociologie, en psychologie, et en neurosciences. Ce chapitre présente trois modèles emblématiques du phénomène : l’urne de Pólya, le graphe aléatoire à attachement préférentiel de Barabási-Albert, et une marche aléatoire renforcée. Il se termine par un théorème de Rubin sur les urnes de Pólya généralisées. D’autres instances se trouvent par exemple dans les modèles de Wright-Fisher et de Moran (chapitre 12), de Ewens (chapitre 14), dans certains modèles de croissance (chapitre 6), et dans le modèle d’Ehrenfest (chapitre 9). Dans les modèles markoviens, le phénomène du renforcement apparaît souvent en liaison avec une propriété de monotonie partielle dans une récurrence aléatoire.

## 15.1 Urne de Pólya

L’urne de Pólya est un modèle simple de renforcement, qui modélise par exemple le fait que le succès ou la richesse s’auto-amplifie au cours du temps.

Au temps $n = 0$, on prépare une urne contenant $a > 0$ boules argentées et $b > 0$ boules blanches. Pour fabriquer la configuration de l’urne au temps $n = 1$, on tire au hasard une boule dans l’urne, puis on remet la boule tirée dans l’urne, ainsi qu’une nouvelle boule de même couleur. On répète ce mécanisme de manière indépendante pour fabriquer la configuration de l’urne en tout temps $n \in \mathbb{N}$. Notons $M_n \in [0, 1]$ la proportion de boules argentées à l’instant
$n \in \mathbb{N}$. Alors, à l'instant $n \in \mathbb{N}$, l'urne contient $a + b + n$ boules dont $(a + b + n)M_n$ sont argentées. Conditionnellement à $M_n$, une boule argentée est ajoutée au temps $n + 1$ avec probabilité $M_n$. Ainsi, $M_0 = a/(a + b)$, et

$$M_{n+1} = \frac{(a+b+n)M_n + \mathbb{1}_{U_{n+1} \le M_n}}{a+b+n+1}$$

où $(U_n)_{n \ge 1}$ est une suite de variables aléatoires indépendantes et identiquement distribuées de loi uniforme sur $[0, 1]$, l'événement $\{U_{n+1} \le M_n\}$ correspondant à l'ajout d'une boule argentée. La suite récurrente aléatoire $(M_n)_{n \ge 0}$ est à la fois une chaîne de Markov non homogène d'espace d'états $[0, 1]$ et une martingale. Codons le résultat du $n^e$ tirage par une variable aléatoire $X_n$ à valeurs dans $\{\alpha, \beta\}$ où $\alpha$ et $\beta$ indiquent respectivement que la boule tirée est argentée ou blanche. Notons enfin $Y_n$ et $Z_n$ les nombres respectifs de boules argentées et blanches ajoutées après les $n$ premiers tirages. À l'instant $n$, l'urne contient $a + Y_n + b + Z_n = a + b + n$ boules, dont $a + Y_n = a + \sum_{k=1}^n \mathbb{1}_{\{X_k=\alpha\}} = (a + b + n)M_n$ boules argentées et $b + Z_n = b + \sum_{k=1}^n \mathbb{1}_{\{X_k=\beta\}}$ boules blanches. On a $Y_n + Z_n = n$. La suite $(X_n, Y_n, Z_n)_{n \ge 1}$ vérifie la récurrente aléatoire

$$(X_{n+1}, Y_{n+1}, Z_{n+1}) = \begin{cases} (\alpha, Y_n + 1, Z_n) & \text{si } U_{n+1} \le \frac{a+Y_n}{a+b+n}, \\ (\beta, Y_n, Z_n + 1) & \text{si } U_{n+1} > \frac{a+Y_n}{a+b+n}, \end{cases}$$

avec la convention $Y_0 = 0$ et $Z_0 = 0$ (il est inutile de définir $X_0$).

**Théorème 15.1** (Martingale). La suite $(M_n)_{n \ge 0}$ est une martingale à valeurs dans $[0, 1]$ pour la filtration $(\mathcal{F}_n)_{n \ge 0}$ définie par $\mathcal{F}_n = \sigma(U_1, \dots, U_n)$, et en particulier la proportion moyenne de boules argentées est conservée au cours du temps : pour tout $n \in \mathbb{N}$,

$$\mathbb{E}(M_n) = \mathbb{E}(M_0) = \frac{a}{a+b}.$$

De plus, il existe une variable aléatoire $M_\infty$ sur $[0, 1]$ telle que

$$\lim_{n \to \infty} M_n = M_\infty$$

p.s. et dans $L^p$ pour tout $p \ge 1$. En particulier $\mathbb{E}(M_\infty) = \mathbb{E}(M_0) = \frac{a}{a+b}$.

**Démonstration.** Pour tout $n \in \mathbb{N}$, $M_n$ est $\mathcal{F}_n$-mesurable, à valeurs dans $[0, 1]$ donc bornée donc intégrable, et

$$\mathbb{E}(M_{n+1} | \mathcal{F}_n) = \mathbb{E}(M_{n+1} | M_n) = \frac{(a+b+n)M_n + M_n}{a+b+n+1} = M_n.$$

Ainsi $(M_n)_{n \ge 0}$ est une martingale pour $(\mathcal{F}_n)_{n \ge 0}$. Le théorème de convergence des martingales uniformément bornées donne $M_n \to M_\infty$ presque sûrement et dans $L^p$ où $M_\infty$ est une variable aléatoire à valeurs dans $[0, 1]^1$. $\square$

<footnote n="1">1. La martingale est uniformément intégrable. Alternativement, on peut utiliser le théorème de convergence des martingales positives pour obtenir la convergence presque sûre puis le théorème de convergence dominée pour la convergence dans $L^p$.</footnote>
**Théorème 15.2 (Équilibre).** La variable aléatoire $M_\infty$ qui apparaît dans le théorème 15.1 suit la loi Beta sur $[0, 1]$ de paramètre $(a, b)$ de densité

$$u \in [0, 1] \mapsto \frac{u^{a-1}(1-u)^{b-1}}{\text{Beta}(a, b)} \quad \text{où} \quad \text{Beta}(a, b) := \int_0^1 p^{a-1}(1-p)^{b-1} dp.$$

En particulier, si $a = b = 1$ alors $M_\infty$ suit la loi uniforme sur $[0, 1]$.

*Démonstration.* Rappelons tout d'abord que

$$\text{Beta}(a, b) = \frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)} \quad \text{où} \quad \Gamma(x) := \int_0^\infty t^{x-1}e^{-x} dx.$$

À présent, pour tous $c$ et $k$ on note

$$c^{(k)} = c(c+1)\cdots(c+k-1) = \frac{(c+k-1)!}{(c-1)!} = \frac{\Gamma(c+k)}{\Gamma(c)}.$$

Pour tous $x_1, \dots, x_n$ dans $\{0, 1\}$, on a, en notant $k = x_1 + \dots + x_n$,

$$\mathbb{P}(\mathbb{1}_{\{X_1=\alpha\}} = x_1, \dots, \mathbb{1}_{\{X_n=\alpha\}} = x_n) = \frac{a^{(k)} b^{(n-k)}}{(a+b)^{(n)}}.$$

Cette probabilité est invariante par permutation des $x_1, \dots, x_n$ : la loi du vecteur aléatoire $(\mathbb{1}_{\{X_1=\alpha\}}, \dots, \mathbb{1}_{\{X_n=\alpha\}})$ est échangeable. Ainsi le nombre (aléatoire) $Y_n = \sum_{k=1}^n \mathbb{1}_{\{X_k=\alpha\}}$ de boules argentées tirées au cours des $n$ premiers tirages vérifie, pour tout $k \in \{0, 1, \dots, n\}$,

$$\begin{align*}
\mathbb{P}(Y_n = k) &= \binom{n}{k} \frac{a^{(k)} b^{(n-k)}}{(a+b)^{(n)}} \\
&= \binom{n}{k} \frac{\Gamma(a+k)\Gamma(b+n-k)\Gamma(a+b)}{\Gamma(a)\Gamma(b)\Gamma(a+b+n)} \\
&= \binom{n}{k} \frac{\text{Beta}(a+k, b+n-k)}{\text{Beta}(a, b)} \\
&= \int_0^1 \binom{n}{k} p^k (1-p)^{n-k} \frac{p^{a-1}(1-p)^{b-1}}{\text{Beta}(a, b)} dp.
\end{align*}$$

On dit que $Y_n$ suit la loi Beta-binomiale, qui est un mélange de lois binomiales de taille $n$ dont le paramètre $p$ suit la loi Beta de paramètre $(a, b)$. On a $M_n = (a + Y_n)/(a + b + n)$ avec $Y_0 = 0$. Lorsque $a = b = 1$, la formule pour la loi de $Y_n$ indique que $Y_n$ est uniforme sur $\{0, 1, \dots, n\}$, et donc $M_n$ est uniforme sur $\{1/(n+2), \dots, (n+1)/(n+2)\}$, ce qui entraîne que $M_\infty$ est uniforme sur $[0, 1]$. Dans le cas général, on peut établir, en utilisant la correspondance Beta-binomiale (chapitre 1), que pour tout $t \in [0, 1]$,

$$\mathbb{P}(M_\infty \le t) = \lim_{n \to \infty} \mathbb{P}(Y_n \le (a+b+n)t - a)$$
<figure><img src="image_45.png" /><figcaption>Fig. 15.1. Quelques trajectoires de l'urne de Pólya.</figcaption></figure>

$$= \cdots = \frac{1}{\text{Beta}(a, b)} \int_{0}^{t} u^{a-1} (1-u)^{b-1} du.$$

□

Les théorèmes 15.1 et 15.2 s'étendent au cas où a et b sont réels > 0, ce qui motive en particulier l'usage des fonctions Gamma et Beta plutôt que des factorielles. Dans ce cas, on peut remplacer le concept d'urne par le concept de partition d'intervalle.

**Remarque 15.3** (Urne de Pólya généralisée). Généralisons le mécanisme de renforcement comme suit : on se donne un entier $r \ge -1$, et, à chaque tirage, on remet dans l'urne $1+r$ boules de la couleur tirée.

— si $r = 1$ on retrouve l'urne de Pólya que nous avons étudiée, pour laquelle $Y_n$ suit la loi Beta-binomiale;

— si $r = 0$, alors on a des tirages avec remise et $Y_n$ est binomiale;

— si $r = -1$ alors on a des tirages sans remise et $Y_n$ est hypergéométrique;

— de manière générale, pour tout $r \ge -1$ et tout $k \in \{0, 1, \dots, n\}$, on a

$$P(Y_n = k) = \frac{a^{(r,k)} b^{(r,k)}}{(a+b)^{(r,k)}} \quad \text{où} \quad c^{(r,k)} := c(c+r) \cdots (c+(k-1)r).$$

On obtient dans ce cas que $M_\infty$ suit la loi Beta de paramètre $(a/r, b/r)$. Il est possible de considérer un nombre arbitraire de couleurs, ce qui fournit un modèle incluant le modèle d'échantillonnage de la loi hypergéométrique multitypes. De nombreux modèles de renforcement peuvent être obtenus comme une version généralisée de l'urne de Pólya.
**Remarque 15.4 (Matrice de remise).** Soit $A = (a_{i,j})_{1\le i,j\le k}$ une matrice $k \times k$ de nombres entiers. Considérons une urne de Pólya généralisée à k couleurs qui évolue comme suit : on tire une boule au hasard dans l'urne, on repère sa couleur, notée i, puis on remet dans l'urne $a_{i,j}$ boules de couleur j pour tout $1 \le j \le k$. On dit que $A$ est la matrice de remise de l'urne. Pour l'urne de Pólya standard que nous avons étudiée on a $k = 2$ et $A = 2I_2$.

## 15.2 Graphe de Barabási-Albert

Les graphes aléatoires permettent de modéliser un certain nombre de phénomènes naturels, comme les structures d'amitié dans les réseaux sociaux, les structures des liens entre pages dans le World Wide Web, les structures de collaboration dans les productions artistiques et scientifiques, les structures de régulation entre protéines, les liaisons entre machines dans le réseau Internet, etc. Les arbres de type Galton-Watson du chapitre 3 constituent un modèle de graphe aléatoire adapté aux structures de filiations. Le modèle le plus célèbre et le plus simple de graphe aléatoire est sans doute celui de Erdős-Rényi, évoqué dans le chapitre 16 : il se construit récursivement en ajoutant un nouveau site puis en tirant à pile ou face de manière indépendante sa connexion avec chacun des sites existants. Ce modèle ne colle pas avec la réalité de graphes aléatoires sociaux, pour lesquels les nouveaux sites se connectent préférentiellement aux sites existants les plus importants au sens de la connectivité (degré). Il y a là une instance du phénomène de renforcement dont il faut tenir compte spécifiquement.

Le graphe aléatoire à attachement préférentiel de Barabási-Albert est défini de la manière suivante : au temps $n \ge 1$, le graphe contient $n$ sites (sommets) et un certain nombre de liens non orientés (arêtes) entre ces sites (voir la figure 15.2). Le degré d'un sommet est le nombre d'arêtes pointant vers ce sommet. Au temps $n = 1$, le site 1 est relié à lui même. Cette initialisation assure de belles formules, mais n'a rien de canonique, et d'autres initialisations sont possibles. Le degré du site 1 à l'instant 1 est donc 2. Pour faire évoluer récursivement le graphe, du temps $n$ au temps $n + 1$, on considère les degrés $d_{n,1}, \dots, d_{n,n}$ des $n$ sites du graphe au temps $n$, et la loi de probabilité associée

$$p_{n,k} = \frac{d_{n,k}}{d_{n,1} + \dots + d_{n,n}},$$

puis on connecte le nouveau site $n + 1$ à un site choisi aléatoirement et indépendamment parmi les $n$ sites existants, avec la loi de probabilité $p_{n,\cdot}$. Avec ce mécanisme, on obtient $d_{1,1} = 2$, $d_{2,1} = 3$, $d_{2,2} = 1$, et pour tout $n \ge 1$, $d_{n,1} + \dots + d_{n,n} = 2n$ (soit $n$ arêtes).

**Remarque 15.5 (Urne).** On peut réaliser cette construction de la suite $(d_{n,\cdot})_{n \ge 1}$ (en perdant la géométrie du graphe) comme un modèle d'urne de Pólya généralisée : au temps $n \ge 1$ l'urne contient $2n$ boules dont les couleurs
peuvent aller de 1 à n, on tire alors une boule au hasard, et si k est sa couleur, on remet dans l'urne 2 boules de couleur k ainsi qu'une boule nouvelle de couleur $n+1$ ce qui correspond à renforcer le site de couleur k et à introduire un nouveau site de couleur $n+1$, autrement dit le graphe gagne un sommet ($n+1$) et une arête ($k \leftrightarrow n+1$).

<figure><img src="image_46.png" /><figcaption>**Fig. 15.2.** Réalisation d'un graphe à attachement préférentiel de Barabási-Albert.</figcaption></figure>

Si l'on omet l'arête reliant 1 à lui-même, le graphe à attachement préférentiel de Barabási-Albert n'a pas de cycles : c'est un arbre.

**Théorème 15.6 (Loi de puissance).** Fixons $k > 1$. Soit $d_{n,k}$ le degré du site $k$ dans le graphe aléatoire à attachement préférentiel de Barabási-Albert à n sites avec $n \ge k$. Alors la proportion $d_{n,k}/(d_{n,1} + \cdots + d_{n,k})$ converge presque sûrement quand $n \to \infty$ vers une variable aléatoire de loi Beta de paramètre $(1, 2k-1)$ sur $[0, 1]$ de densité $u \in [0, 1] \mapsto (2k-1)(1-u)^{2(k-1)}$.

La loi de puissance qui apparaît dans ce modèle à attachement préférentiel correspond bien aux réseaux sociaux réels, et diffère du comportement sous-exponentiel de la loi de Poisson des modèles de graphes aléatoires de Erdős-Rényi à attachement non préférentiel<fnref n="2" />.

<footnote n="2">2. Dans un graphe de Erdős-Rényi de paramètre $(n, p)$, chaque sommet possède un nombre de voisins aléatoire de loi binomiale $Bin(n - 1, p)$, qui converge vers</footnote>
**Démonstration.** Comme dans la remarque 15.5, on code l'évolution de la suite des degrés (sans souci de la structure de graphe sous-jacente) par un modèle d'urne. Au temps $k$, on décide d'une coloration parallèle : les $2k-1$ boules de couleur inférieure à $k$ sont blanches tandis que la $2k$-ième est argentée. Au temps $n > k$, on ne suit que l'évolution des boules de ces couleurs là. Elle correspond à une urne de Pólya avec une composition initiale de $a = 1$ et $b = 2k-1$. On peut utiliser alors le théorème 15.2. □

**Théorème 15.7** (Loi de puissance à degré fixé). *Pour tous $n, d \ge 1$, si $N(n, d)$ désigne le nombre de sites de degré $d$ au temps $n$ dans le graphe aléatoire à attachement préférentiel de Barabási-Albert à $n$ sites, alors*

$$ \lim_{n \to \infty} \mathbb{E} \left( \frac{N(n, d)}{n} \right) = \frac{4}{d(d+1)(d+2)}. $$

Ainsi, dans un très grand graphe à attachement préférentiel ($n \gg 1$), la probabilité qu'une arête soit de degré $d$ a une décroissance polynomiale en $d^{-3}$ quand $d \to \infty$. La queue lourde de la loi du degré moyen est liée à la présence, due au renforcement, de sites fortement connectés.

**Démonstration.** La suite $(N(n, \cdot))_{n \ge 1}$ est une chaîne de Markov. Conditionnellement à $N(n, \cdot)$, pour créer un nouveau site de degré $d$, il faut ajouter une arête à un site de degré $d-1$, ce qui se produit avec probabilité $(d-1)N(n, d-1)/(2n)$, tandis qu'un site de degré $d$ disparaît si on lui ajoute une arête, ce qui se produit avec probabilité $dN(n, d)/(2n)$. Enfin, un site de degré 1 est créé à chaque étape par construction. Aussi, le nombre moyen $m_n(d) := \mathbb{E}(N(n, d))$ de sites de degré $d$ au temps $n$ vérifie une équation de récurrence linéaire, qualifiée d'équation maîtresse par Dorogovstev, Mendes, et Samukhin : pour tout $n, d \ge 1$ :

$$ m_{n+1}(d) - m_n(d) = -\frac{d}{2n}m_n(d) + \frac{d-1}{2n}m_n(d-1) + \mathbb{1}_{d=1}, $$

avec pour condition initiale $m_1 = \mathbb{1}_{d=2}$. Pour $d=1$, l'équation s'écrit

$$ m_{n+1}(1) = c + \left(1 - \frac{b}{n}\right)m_n(1) \quad \text{avec } c = 1 \text{ et } b = 1/2, $$

ce qui donne

$$ \begin{aligned} m_{n+1}(1) &= c + \left(1 - \frac{b}{n}\right)c + \left(1 - \frac{b}{n}\right)\left(1 - \frac{b}{n-1}\right)m_{n-1}(1) \\ &= c \sum_{k=1}^{n} \prod_{j=k+1}^{n} \left(1 - \frac{b}{j}\right) + \underbrace{m_1(1)}_{=0} \prod_{k=1}^{n} \left(1 - \frac{b}{k}\right). \end{aligned} $$

<footnote>la loi de Poisson Poi($\lambda$) si $np \to \lambda$ quand $n \to \infty$. Or si $X \sim$ Poi($\lambda$) alors on a $P(X \ge r) \le C \exp(-cr \log(r))$ pour $r \gg 1$ où $c > 0$ et $C > 0$ sont des constantes.</footnote>
Or

$$ \prod_{j=k+1}^{n} \left(1 - \frac{b}{j}\right) \approx \exp\left(-\sum_{k=k+1}^{n} \frac{b}{j}\right) \approx \exp\left(-b(\log(n) - \log(k))\right) = \left(\frac{k}{n}\right)^{b}, $$

d'où

$$ m_n(1) \approx cn^{-b} \int_{0}^{n} s^b ds = cn^{-b} \frac{n^{b+1}}{b+1} = \frac{cn}{b+1}, $$

de sorte que

$$ \lim_{n \to \infty} \frac{m_n(1)}{n} = \frac{c}{b+1} = \frac{2}{3}. $$

Plus généralement, pour tout $d > 1$, on a

$$ m_{n+1}(d) = c_n(d) + \left(1 - \frac{b(d)}{n}\right) m_n(d) $$

où

$$ b(d) = d/2 \quad \text{et} \quad c_n(d) = \frac{d-1}{2} \frac{m_n(d-1)}{n}, $$

et on montre par récurrence sur $d$ que $c(d) = \lim_{n \to \infty} c_n(d)$ existe et

$$ \frac{m_n(d)}{n} \underset{n \to \infty}{\longrightarrow} \frac{c(d)}{b(d) + 1}. $$

Ensuite, en posant

$$ \ell(d) := \lim_{n \to \infty} \frac{m_n(d)}{n} $$

on obtient $\ell(1) = 2/3$, tandis que pour tout $d > 1$,

$$ \ell(d) = \frac{\frac{(d-1)}{2} \ell(d-1)}{\frac{d}{2} + 1} = \frac{d-1}{d+2} \ell(d-1). $$

Enfin, la solution de cette récurrence en $d$ est (facile à vérifier !)

$$ \ell(d) = \frac{4}{d(d+1)(d+2)}. $$

□

## 15.3 Marche aléatoire renforcée

Le phénomène du renforcement est à l'œuvre dans l'apparition des chemins empruntés par les passants dans les montagnes ou par les fourmis sur le sol. Considérons deux chemins distincts $\alpha$ et $\beta$ reliant les mêmes points de départ et d'arrivée, empruntés par des passants successifs. Pour tout $n \ge 1$, on code
<figure><img src="image_47.png" /><figcaption>Fig. 15.3. Occupation d'un chemin pour la marche renforcée géométriquement.</figcaption></figure>

par une variable aléatoire $X_n$ à valeur dans $\{\alpha, \beta\}$ le chemin emprunté lors
du n-ième passage. On code par des v.a. $A_n$ et $B_n$ l'attractivité des chemins
$\alpha$ et $\beta$ au moment du $(n+1)^e$ passage : pour les humains, il peut s'agir par
exemple de la raréfaction de l'herbe, tandis que pour les fourmis, il peut s'agir
de la quantité de phéromone. On se donne $(A_0, B_0)$, ainsi qu'une fonction
$r: ]0, \infty[ \to ]0, \infty[$ appelée fonction de renforcement telle que $r(x) \ge x$ pour
tout $x > 0$, et on modélise $(X_n)_{n \ge 1}$ par

$$
(X_{n+1}, A_{n+1}, B_{n+1}) = \begin{cases} (\alpha, r(A_n), B_n) & \text{si } U_{n+1} \le \frac{A_n}{A_n+B_n}; \\ (\beta, A_n, r(B_n)) & \text{si } U_{n+1} > \frac{A_n}{A_n+B_n}, \end{cases}
$$

où $(U_n)_{n \ge 1}$ est une suite de variables aléatoires indépendantes et identi-
quement distribuées de loi uniforme sur $[0, 1]$. La suite récurrente aléatoire
$((X_n, A_n, B_n))_{n \ge 0}$ est une chaîne de Markov (la valeur de $X_0$ ne joue aucun
rôle dans la récurrence). Lorsque $A_0, B_0$, et $r$ prennent des valeurs entières,
tout se passe comme si nous avions une urne contenant, à tout instant $n$, $A_n$
boules argentées et $B_n$ boules blanches : on tire une boule au hasard dans
cette urne, puis on introduit dans l'urne $r(A_n)$ boules de la même couleur, de
sorte qu'on obtient le cas des tirages sans remise si $r(x) = x$, l'urne de Pólya
si $r(x) = x + 1$, et une sorte d'urne de Pólya non-linéaire dans le cas général.

La suite $(X_n)_{n \ge 1}$ constitue une marche aléatoire non markovienne sur
l'ensemble à deux points $\{\alpha, \beta\}$. Ses transitions dépendent les unes des autres
via le mécanisme de renforcement lié au temps passé sur chaque site. On parle
de *marche aléatoire renforcée par sites*. Le mécanisme de renforcement peut également être vu comme une sorte d'algorithme stochastique.

Pour simplifier, on suppose que $A_0 = B_0 = 1$ ($X_0$ est inutile). Le nombre de passages par le chemin $\alpha$ et par le chemin $\beta$ à l'instant $n$ sont donnés par

$$Y_n = \sum_{k=1}^{n} 1_{\{X_k=\alpha\}} \quad \text{et} \quad Z_n = \sum_{k=1}^{n} 1_{\{X_k=\beta\}}.$$

On pose par commodité $Y_0 = 0$ et $Z_0 = 0$ de sorte que $Y_n + Z_n = n$ pour tout $n \in \mathbb{N}$. Le théorème suivant précise le comportement de ces deux suites pour trois cas de fonction de renforcement $r$.

**Théorème 15.8** (Comportement asymptotique presque sûr quand $n \to \infty$).

— Absence de renforcement. Si $r(x) = x$ pour tout $x > 0$, alors presque sûrement $\liminf |Y_n - Z_n| = 0$, et

$$Y_n \sim \frac{n}{2}, \quad Z_n \sim \frac{n}{2}, \quad \limsup \frac{|Y_n - Z_n|}{\sqrt{2n \log(\log(n))}} = 1.$$

— Renforcement linéaire. Si $r(x) = x + 1$ pour tout $x > 0$ alors il existe une variable aléatoire $U$ uniforme sur $[0, 1]$ telle que presque sûrement,

$$\frac{Y_n}{n} \to U \quad \text{et} \quad \frac{Z_n}{n} \to 1 - U.$$

— Renforcement géométrique. Si $r(x) = px$ pour tout $x > 0$ où $p > 1$ est une constante alors presque sûrement la suite aléatoire $(X_n)_{n \ge 0}$ est constante à partir d'un certain rang sur $n$, et sa valeur limite suit la loi de Bernoulli symétrique sur $\{\alpha, \beta\}$.

En l'absence de renforcement ou dans le cas du renforcement linéaire, la fréquence d'emprunt de chacun des deux chemins converge au fil du temps vers $1/2$ dans le premier cas et vers un nombre aléatoire uniforme sur $[0, 1]$ dans le second. Intuitivement, un renforcement sur-linéaire pourrait forcer la fréquence d'emprunt des chemins à converger vers les valeurs extrêmes $0$ ou $1$. Cela est confirmé pour le renforcement géométrique, pour lequel au bout d'un certain temps, l'un des deux chemins est emprunté systématiquement.

Le modèle du renforcement linéaire coïncide avec l'urne de Pólya étudiée précédemment. Le modèle du renforcement géométrique est particulièrement attrayant, car il fait apparaître un chemin privilégié, choisi aléatoirement au fil du renforcement. Il s'agit en quelque sorte d'une urne de Pólya généralisée non-linéaire, plus précisément sur-linéaire. Le théorème 15.9 de Rubin ci-après fournit un critère sur le renforcement pour que ce phénomène apparaisse.

*Démonstration.* On traite les trois cas séparément.
— Absence de renforcement. Dans ce cas $(A_n)_{n \ge 0}$ et $(B_n)_{n \ge 0}$ sont des suites constantes et égales à 1. On retrouve les tirages avec remise, le processus de Bernoulli (jeu de pile ou face). La suite $(Y_n)_{n \ge 0}$ est un processus de Bernoulli sur $\mathbb{N}$ issu de 0 dont les incréments sont de loi de Bernoulli sur $\{0, 1\}$ de paramètre $A_0/(A_0 + B_0) = 1/2$. D'après la loi forte des grands nombres, presque sûrement, $Y_n/n \to 1/2$ et $Z_n/n = 1 - Y_n/n \to 1/2$ quand $n \to \infty$. La suite $(Y_n - Z_n)_{n \ge 0}$ est une marche aléatoire sur $\mathbb{Z}$ issue de 0 dont les incréments sont de loi de Rademacher sur $\{-1, 1\}$ de paramètre $1/2$. C'est une chaîne de Markov irréductible récurrente : presque sûrement chaque état est visité une infinité de fois, et en particulier l'état 0, d'où $\lim_{n \to \infty} |Y_n - Z_n| = 0$ p.s. Le résultat sur $\lim_{n \to \infty}$ provient de la loi du logarithme itéré de Strassen;

— Renforcement linéaire. Dans ce cas $A_n = 1 + Y_n$ et $B_n = 1 + Z_n$ pour tout $n \in \mathbb{N}$. On retrouve l'urne de Pólya et le résultat attendu découle alors directement du cas uniforme dans le théorème 15.2. Effectuons malgré tout le raisonnement allégé avec les notations actuelles. La relation $Y_n + Z_n = n$ réduit le problème à l'étude de $Y_n$. Soit $(\mathcal{F}_n)_{n \ge 0}$ la filtration définie par $\mathcal{F}_n = \sigma(U_1, \dots, U_n)$. On a

$$ 
\begin{align*} 
\mathbb{E}(1 + Y_{n+1} | \mathcal{F}_n) &= 1 + Y_n + \mathbb{E}(1_{\{X_{n+1}=\alpha\}} | \mathcal{F}_n) \\
&= 1 + Y_n + \mathbb{E}(1_{\{U_{n+1} \le \frac{1+Y_n}{n+2}\}} | \mathcal{F}_n) \\
&= 1 + Y_n + \frac{1+Y_n}{n+2} = (2+(n+1))\frac{1+Y_n}{2+n}, 
\end{align*} 
$$

et donc $((1 + Y_n)/(n + 2))_{n \ge 0}$ est une martingale pour $(\mathcal{F}_n)_{n \ge 0}$. À valeurs dans $[0, 1]$, elle est uniformément bornée et converge donc presque sûrement (et en moyenne) vers une variable aléatoire $U$ à valeurs dans $[0, 1]$. On montre enfin par récurrence sur $n$ que $(1 + Y_n)/(n + 2)$ suit la loi uniforme sur $\{1/(n + 2), \dots, (n + 1)/(n + 2)\}$;

— Renforcement géométrique. Dans ce cas $A_n = \rho^{Y_n}$ et $B_n = \rho^{Z_n}$ pour tout $n \in \mathbb{N}$. La variable aléatoire $\Delta_n := Y_n - Z_n$ vérifie $\Delta_0 = 0$ et

$$ \Delta_{n+1} = \Delta_n + \mathbb{1}_{\{U_{n+1} \le 1/(1+\rho^{-\Delta_n})\}} - \mathbb{1}_{\{U_{n+1} > 1/(1+\rho^{-\Delta_n})\}}. $$

Posons $\mathcal{F}_n = \sigma(U_1, \dots, U_n)$. Il en découle que

$$ \mathbb{P}(|\Delta_{n+1}| = |\Delta_n| + 1 | \mathcal{F}_n) = \frac{\rho^{|\Delta_n|}}{1 + \rho^{|\Delta_n|}} \mathbb{1}_{\{\Delta_n \neq 0\}} + \mathbb{1}_{\{\Delta_n = 0\}} $$

$$ \mathbb{P}(|\Delta_{n+1}| = |\Delta_n| - 1 | \mathcal{F}_n) = \frac{1}{1 + \rho^{|\Delta_n|}} \mathbb{1}_{\{\Delta_n \neq 0\}}. $$

Si $f: \mathbb{N} \to \mathbb{R}$ vérifie $f(1) \ge f(0)$ et pour tout $n \ge 1$,

$$ \rho^n(f(n+1) - f(n)) = f(n) - f(n-1), $$

alors
$$E(f(|\Delta_{n+1}|) | \mathcal{F}_n) = f(|\Delta_n|) + 1_{\{\Delta_n=0\}} \ge f(|\Delta_n|),$$

et $(f(|\Delta_n|))_{n \ge 0}$ est une sous-martingale. Considérons maintenant le cas spécial où $f(0) = 0$ et, pour tout $n \ge 1$,

$$f(n) = \sum_{k=0}^{n-1} \rho^{-\frac{k(k+1)}{2}}.$$

Comme $f$ est bornée, il en découle que la sous-martingale $f(|\Delta|)$ est uniformément bornée : elle converge donc p.s. (et en moyenne). Comme $f$ est injective et comme $|\Delta|$ prend ses valeurs dans $\mathbb{N}$, les valeurs prises par $f(|\Delta|)$ sont discrètes. Comme $f(|\Delta|)$ converge p.s., elle ne peut converger que vers le seul point d'accumulation de $f(\mathbb{N})$, qui est $\lim_{n \to \infty} f(n) = \sum_{k=0}^{\infty} \rho^{-\frac{k(k+1)}{2}}$. Ainsi p.s. $\lim_{n \to \infty} |\Delta_n| = \infty$. À pré- sent, pour tous $N, d \ge 0$, la probabilité que la suite $|\Delta|$ soit croissante à partir du rang $N$ sachant que $|\Delta_N| = d$ vaut

$$P(\forall n \ge N : |\Delta_{n+1}| = |\Delta_n| + 1 | |\Delta_N| = d) = \prod_{k=d}^{\infty} \frac{1}{1 + \rho^{-k}} =: p_d.$$

La probabilité $p_d$ ne dépend pas de $N$, et tend en croissant vers 1 lorsque $d \to \infty$. Ainsi la probabilité que $|\Delta|$ soit croissante à partir d'un certain rang (aléatoire) s'écrit

$$P(\exists N \ge 0, \forall n \ge N : |\Delta_{n+1}| = |\Delta_n| + 1)$$

Elle est supérieure à

$$\sup_{N \ge 0} P(\forall n \ge N, |\Delta_{n+1}| = |\Delta_n| + 1) = \sup_{N \ge 0} \sum_{d=0}^{\infty} p_d P(|\Delta_N| = d).$$

Or pour tout $d \ge 0$, on a $\lim_{N \to \infty} P(|\Delta_N| = d) = 0$ car nous savons que $\lim_{N \to \infty} |\Delta_N| = \infty$ p.s. Par conséquent, pour tout $D \ge 0$,

$$\sup_{N \ge 0} \sum_{d=0}^{\infty} p_d P(|\Delta_N| = d) \ge \sup_{N \ge 0} \sum_{d=D}^{\infty} p_d P(|\Delta_N| = d) \ge p_D.$$

Comme $P_D \to 1$ quand $D \to \infty$, il en découle que presque sûrement $|\Delta|$ est croissante à partir d'un certain rang, et donc la suite $X$ est absorbée par $\alpha$ ou par $\beta$. La loi de la limite de $X$ est symétrique par symétrie du modèle en $\alpha$ et $\beta$ car $A_0 = B_0$.

□

## 15.4 Théorème de Rubin

Cette section est consacrée à un théorème de Rubin sur les urnes de Pó- lya généralisées. On se donne deux fonctions croissantes $S_\alpha, S_\beta : \mathbb{N} \to \mathbb{R}_+$
telles que $S_\alpha(0) > 0$ et $S_\beta(0) > 0$. On construit une suite récurrente aléatoire $(X_n)_{n \ge 1}$ à valeurs dans $\{\alpha, \beta\}$ comme suit : pour tout $n \in \mathbb{N}$, conditionnellement à $X_1, \dots, X_n$, en notant $Y_n = \sum_{k=1}^n 1_{\{X_k=\alpha\}}$ le nombre de $\alpha$ et $Z_n = n - Y_n$ le nombre de $\beta$,

$$ (X_{n+1}, Y_{n+1}, Z_{n+1}) = \begin{cases} (\alpha, Y_n + 1, Z_n) & \text{si } U_{n+1} \le \frac{S_\alpha(Y_n)}{S_\alpha(Y_n) + S_\beta(Z_n)}, \\ (\beta, Y_n, Z_n + 1) & \text{si } U_{n+1} > \frac{S_\alpha(Y_n)}{S_\alpha(Y_n) + S_\beta(Z_n)}, \end{cases} $$

où $(U_n)_{n \ge 1}$ est une suite de variables aléatoires i.i.d. de loi uniforme sur $[0, 1]$. La suite $(X_n)_{n \ge 1}$ ainsi construite code les tirages successifs d'une urne de Pólya généralisée. Le modèle du théorème 15.8 dans le cas où $(A_0, B_0)$ est déterministe s'obtient avec $(S_\alpha(0), S_\beta(0)) = (A_0, B_0)$, et $S_\alpha(n) = S_\beta(n) = r(n)$ pour tout $n > 0$. Si $r$ est linéaire alors on retrouve l'absence de renforcement (tirages avec remise). Si $r$ est affine alors on retrouve le renforcement linéaire (urne de Pólya standard). Enfin, si $r$ est une fonction puissance, alors on retrouve le renforcement géométrique.

Pour étudier le cas général, on introduit la probabilité $p_\alpha$ (respectivement $p_\beta$) que la suite $(X_n)_{n \ge 1}$ ne comporte qu'un nombre fini de $\beta$ (respectivement de $\alpha$) c'est-à-dire que des $\alpha$ (respectivement que des $\beta$) à partir d'un certain rang sur $n$. Ces probabilités sont données par les formules suivantes :

$$ p_{\alpha} = \mathbb{P}(\cup_n \cap_{k \ge n} \{X_k = \alpha\}) \quad \text{et} \quad p_{\beta} = \mathbb{P}(\cup_n \cap_{k \ge n} \{X_k = \beta\}). $$

On a $p_\alpha + p_\beta \le 1$. Les nombres suivants dans $[0, \infty]$ vont jouer un rôle crucial :

$$ \varphi_\alpha = \sum_{n=0}^{\infty} \frac{1}{S_\alpha(n)} \quad \text{et} \quad \varphi_\beta = \sum_{n=0}^{\infty} \frac{1}{S_\beta(n)}. $$

**Théorème 15.9 (de Rubin).** Les valeurs de $p_\alpha, p_\beta$ sont liées à $\varphi_\alpha, \varphi_\beta$ :

$$ \begin{array}{c|c|c} \varphi_\beta < \infty & \varphi_\beta = \infty \\ \frac{\varphi_\alpha < \infty}{\varphi_\alpha = \infty} & \substack{p_\alpha > 0, p_\beta > 0, p_\alpha + p_\beta = 1 \\ p_\beta = 1 \text{ (donc } p_\alpha = 0\text{)}} \\ \end{array} \quad \begin{array}{c} p_\alpha = 1 \text{ (donc } p_\beta = 0\text{)} \\ p_\alpha = 0, p_\beta = 0 \end{array} $$

Ainsi, la trivialité des probabilités $p_\alpha$ et $p_\beta$ ne dépend que du comportement asymptotique des fonctions de renforcement $S_\alpha$ et $S_\beta$, et les cas critiques sont liés à la condition de Riemann. En absence de renforcement ($S_\alpha$ et $S_\beta$ sont linéaires) ainsi que dans le cas d'un renforcement linéaire ($S_\alpha$ et $S_\beta$ sont affines) on a $\varphi_\alpha = \varphi_\beta = \infty$ car la série harmonique diverge. Dès que le renforcement est sur-linéaire, alors $\varphi_\alpha < \infty$ et $\varphi_\beta < \infty$, en particulier pour le cas du renforcement quadratique, et bien sûr le cas du renforcement géométrique.

**Démonstration.** Soient $(E_n^\alpha)_{n \ge 0}$ et $(E_n^\beta)_{n \ge 0}$ deux suites indépendantes de variables aléatoires indépendantes de loi exponentielle avec, pour tout $n \ge 0$,

$$ \mathbb{E}(E_n^\alpha) = \frac{1}{S_\alpha(n)} \quad \text{et} \quad \mathbb{E}(E_n^\beta) = \frac{1}{S_\beta(n)} $$
À présent, on définit les ensembles aléatoires

$$
\mathcal{A} = \left\{ \sum_{k=0}^{n} E_k^{\alpha} : n \ge 0 \right\} \quad \text{et} \quad \mathcal{B} = \left\{ \sum_{k=0}^{n} E_k^{\beta} : n \ge 0 \right\} \quad \text{et} \quad \mathcal{G} = \mathcal{A} \cup \mathcal{B}.
$$

Soit $\xi_0 < \xi_1 < \dots$ les éléments de $\mathcal{G}$ rangés par ordre croissant. On considère
à présent la suite aléatoire $(X'_n)_{n \ge 1}$ à valeurs dans $\{\alpha, \beta\}$ définie par $X'_n = \alpha$
si $\xi_{n-1} \in \mathcal{A}$ et $X'_n = \beta$ si $\xi_{n-1} \in \mathcal{B}$. Les suites $(X'_n)_{n \ge 1}$ et $(X_n)_{n \ge 1}$ ont
même loi, et cela découle des propriétés des lois exponentielles dont l'absence
de mémoire. Examinons l'égalité en loi de $X_1$ et $X'_1$. Si $U$ et $V$ sont deux
variables aléatoires indépendantes de lois exponentielles de moyennes $1/u$ et
$1/v$ alors $\mathbb{P}(U < V) = u/(u+v)$ et $\mathbb{P}(V < U) = v/(u+v)$, ce qui fait que

$$
\mathbb{P}(X'_{1} = \alpha) = \mathbb{P}(\xi_{0} \in \mathcal{A}) = \mathbb{P}(E'_{0} \le E'_{0}) = \frac{S_{\alpha}(0)}{S_{\alpha}(0) + S_{\beta}(0)} = \mathbb{P}(X_{1} = \alpha).
$$

La même idée fournit (avec du labeur !) l'égalité en loi de $(X_n)_{n \ge 1}$ et $(X'_n)_{n \ge 1}$.

À présent une loi du zéro-un pour les lois exponentielles (théorème 11.5)
affirme que $p := \mathbb{P}(\sum_{n=0}^{\infty} E_n^{\alpha} < \infty) \in \{0, 1\}$, avec $p = 1$ ssi $\varphi_{\alpha} < \infty$. La même
propriété a lieu pour la suite $(E_n^{\beta})_{n \ge 0}$ avec $\varphi_{\beta}$. Par ailleurs, on a les formules
$p_{\beta} = \mathbb{P}(\sum_{n=0}^{\infty} E_n^{\alpha} < \sum_{n=0}^{\infty} E_n^{\beta})$ et $p_{\alpha} = \mathbb{P}(\sum_{n=0}^{\infty} E_n^{\beta} < \sum_{n=0}^{\infty} E_n^{\alpha})$. $\square$

15.5 Pour aller plus loin

Les urnes de Pólya sont étudiées notamment dans le livre de Hosam Mah-
moud [Mah09], dans celui de Norman Johnson et Samuel Kotz [JK77], et
dans les articles de survol de Samuel Kotz et Narayanaswamy Balakrishnan
[KB97] et de Robin Pemantle [Pem07]. Les urnes de Pólya portent le nom du
mathématicien hongrois George Pólya. L'école hongroise de mathématiques a
beaucoup développé les mathématiques discrètes aléatoires, avec notamment
les célèbres travaux de Paul Erdős et Alfréd Rényi des années 1950 sur les
graphes aléatoires. Le modèle de graphe aléatoire à attachement préférentiel
a été introduit par les physiciens hongrois Albert-László Barabási et Réka
Albert [AB99, AB02]. Voici leur heuristique pour le comportement en $d^{-3}$ :
si les degrés et le temps étaient continus, on aurait l'équation d'évolution

$$
\partial_t d_{t,k} = \frac{d_{t,k}}{\sum_k d_{t,k}} = \frac{d_{t,k}}{2t},
$$

qui donne la formule $d_{t,k} = (t/t_k)^{1/2}$ où $t_k$ est le temps d'apparition du
site $k$, et comme les sites sont ajoutés uniformément sur $[0, t]$, on obtient la
formule $\mathbb{P}(d_{t,k} > d) = \mathbb{P}(t_k < t/d^2) = 1/d^2$, d'où en dérivant, la formule
très simple $\mathbb{P}(d_{t,k} = d) = 2/d^3$, qui est le comportement polynomial (puis-
sance) suggéré par les simulations. Cette approche est peu rigoureuse, et la
constante 2 notamment n'est pas bonne. Le modèle de Barabási et Albert a été ensuite étudié par Béla Bollobás, Oliver Riordan, Joel Spencer, et Gábor Tusnády [BRST01]. Il peut être vu comme une instance du phénomène d'auto-organisation. Le sujet fait toujours l'objet de recherches à l'heure où nous écrivons ces lignes, comme en témoigne par exemple l'article [BMR14] de Sébastien Bubeck, Elchanan Mossel, et Miklós Rácz, ou encore l'article [CDKM14] de Nicolas Curien, Thomas Duquesne, Igor Kortchemski, et Ioan Manolescu. La partie de ce chapitre sur les graphes aléatoires à attachement préférentiel est inspirée du cours [Bod14] de Thierry Bodineau à l'École Polytechnique, ainsi que des livres de Remco van der Hofstad [vdH14] et de Rick Durrett [Dur10b]. Il est possible d'utiliser l'inégalité d'Azuma-Hoeffding du chapitre 20 pour établir que $N(n, d)$ (sans espérance) a un comportement polynomial en $d$ quand $n \to \infty$. Il est également possible de modifier la règle d'attachement préférentiel afin d'obtenir un comportement polynomial de degré différent de 3, ce qui correspond à considérer une urne de Pólya modifiée (non-linéaire). Le mécanisme d'attachement préférentiel est également présent dans le processus de branchement de Herbert Simon et Udny Yule. La loi discrète à décroissance polynomiale, version discrète de la loi de (Vilfredo) Pareto, est connue sous le nom de loi de (George Kingsley) Zipf.

La partie sur la marche aléatoire renforcée est inspirée d'un texte de Thierry Lévy. Nous renvoyons plus généralement au survol [Pem07] de Robin Pemantle sur les processus aléatoires renforcés, ainsi qu'à celui de Pierre Tarrès [Tar11] sur les marches aléatoires renforcées. Un résultat récent sur le renforcement se trouve par exemple dans l'article de Margherita Disertori, Christophe Sabot, et Pierre Tarrès [DST14]. Un modèle continu de renforcement est étudié par Michel Benaïm et Olivier Raimond dans [BR11]. Le théorème 15.9 de Herman Rubin figure dans un appendice d'un article de Burgess Davis [Dav90].

Au-delà des modèles évoqués, le phénomène de renforcement joue un rôle important dans la théorie de l'apprentissage. Il est également relié à une gamme d'algorithmes stochastiques comme l'algorithme d'approximation stochastic de Robbins-Monro, lié à la théorie des systèmes dynamiques et ses attracteurs. Les martingales constituent un outil privilégié de l'approche stochastic de la théorie des jeux et stratégies, présentée brièvement dans le livre de Michel Benaïm et Nicole El Karoui [BEK05].
<figure><img src="image_48.png" /></figure>
Percolation

**Mots-clés.** Percolation; phénomène de seuil; graphe aléatoire; arbre aléatoire; arbre de Bethe; réseau euclidien; graphe complet; graphe aléatoire de Erdős-Rényi.

**Outils.** Couplage; lemme de sous-additivité de Fekete; loi du zéro-un de Kolmogorov; marche aléatoire; processus de Galton-Watson; martingale; théorème d'arrêt; inégalité de Markov; transformée de Laplace.

Difficulté. **

La percolation désigne initialement le passage d'un fluide à travers un mi-lieu perméable, comme l'eau dans le café ou le pétrole dans la roche. Signalons qu'une des motivations de l'étude mathématique de ce phénomène était la modélisation d'un filtre de masque à gaz. On peut également utiliser la notion de percolation pour modéliser la propagation d'une information au sein d'un réseau social par exemple : chaque individu est connecté directement à plusieurs autres et l'on cherche à comprendre à qui il est relié dans la population globale via ces connections locales.

Nous commençons par introduire la notion de percolation sur un graphe général. Nous abordons ensuite le cas plutôt simple du graphe de Bethe (arbre), puis celui plus physique du graphe euclidien. Nous terminons par quelques mots sur un modèle de graphe complet. Ces trois cadres peuvent modéliser la transmission d'information dans une entreprise à très fort sens de la hiérarchie (pour le premier) ou dans un réseau social (pour le troisième) ou encore la circulation d'un fluide dans une roche perméable (pour le deuxième).

16.1 Percolation dans un graphe

Un graphe (non-orienté) est un couple $G = (V, E)$ où $V$ est un ensemble non-vide fini ou infini dénombrable, et où $E \subset P_2(V)$, où $P_2(V)$ est l'ensemble
des parties de $V$ à deux éléments. Les éléments de $V$ et $E$ sont respectivement appelés<fnref n="1" /> sommets et arêtes du graphe $G$. Si l'arête $\{x, y\}$ appartient à $E$, on dit que $x$ et $y$ sont voisins et on note $x \sim y$. L'exemple le plus immédiat est celui du graphe euclidien $\mathcal{E}_d = (V, E)$ pour lequel $V = \mathbb{Z}^d$ et

$$E = \{\{x, y\} : x, y \in \mathbb{Z}^d, |x - y|_1 := |x_1 - y_1| + \dots + |x_d - y_d| = 1\}.$$

Un chemin de longueur $n$ dans le graphe $(V, E)$ reliant un sommet $x$ à un sommet $y$ est une suite finie $x = x_0 \sim \dots \sim x_n = y$. S'il existe un chemin reliant $x$ à $y$, on dit que $x$ et $y$ communiquent (ou sont connectés) et on note $x \leftrightarrow y$. On n'a jamais $x \sim x$, mais on convient que $x \leftrightarrow x$ pour tout $x \in V$. La relation binaire $\leftrightarrow$ sur $V$ est une relation d'équivalence et la classe d'équivalence (ou composante connexe) du point $x$ est notée $C(x)$. Un chemin est dit auto-évitant si tous les sommets qui le composent sont distincts. Si $x \leftrightarrow y$ et $x \neq y$ alors il existe un chemin auto-évitant de $x$ à $y$, construit à partir d'un chemin quelconque en effaçant les boucles. Un chemin reliant un sommet à lui-même est appelé cycle. On dit que $(V, E)$ est un arbre lorsqu'il est connexe et n'a pas de cycles, ou de manière équivalente lorsque deux sommets distincts sont toujours reliés par un unique chemin auto-évitant.

Dans la suite $V$ est, sauf mention du contraire, infini dénombrable. Soit $F \subset E$. On dit qu'il y a percolation en $x \in V$ (pour $F$) si la classe $C(x)$ de $x$ dans le graphe $(V, F)$ est de taille infinie ($|C(x)| = \infty$), et on note $x \leftrightarrow \infty$. On identifie l'ensemble des parties de $E$ à l'ensemble

$$\Omega := \{0, 1\}^E.$$

Dans la suite, on choisit $F$ de manière aléatoire dans $\Omega$, et ainsi $(V, F)$ est un graphe aléatoire. On décide de fabriquer $F$ à partir de $E$ en tirant à pile ou face pour savoir si on conserve ou si on efface chaque arête de $E$. Cela revient à introduire la loi de probabilité

$$\mathbb{P}_p = \bigotimes_{e \in E} \mathrm{Ber}(p)$$

sur $\Omega$ muni de sa tribu cylindrique $\mathcal{F}$, où $p \in [0, 1]$ est un paramètre fixé. On note $E_p$ l'espérance sous $\mathbb{P}_p$. Pour étudier l'influence du paramètre $p$ sur le phénomène de percolation sous $\mathbb{P}_p$, on distingue un sommet particulier $\emptyset \in V$, que nous appelons *racine* – on dit qu'on enracine $(V, E)$ en $\emptyset$ – et on définit la *probabilité de percolation* sous $\mathbb{P}_p$ pour $\emptyset$ par

$$\theta(p) := \mathbb{P}_p(\emptyset \leftrightarrow \infty) = \mathbb{P}_p(|C(\emptyset)| = \infty).$$

**Lemme 16.1 (Monotonie).** La fonction $p \in [0, 1] \mapsto \theta(p)$ est croissante, et

$$\theta(0) = 0 \quad \text{et} \quad \theta(1) = 1.$$

<footnote n="1">1. On dit « vertices » et « edges » en anglais, d'où la notation.</footnote>
<figure><img src="image_49.png" /><figcaption>Fig. 16.1. Réalisation du graphe aléatoire (V, F) du graphe euclidien $\mathcal{E}_2$ sous $\mathbb{P}_{1/2}$.</figcaption></figure>

La monotonie de $\theta$ conduit à introduire la notion de *probabilité critique* :

$$p_c = \sup \{p \in [0, 1] : \theta(p) = 0\} \in [0, 1].$$

*Démonstration.* Si $p = 0$ alors $F$ est vide et donc $\theta(0) = 0$ tandis que si $p = 1$ alors $F = E$ et $\theta(1) = 1$. Pour établir la monotonie en $p$, on procède par un couplage de toutes les lois $(\mathbb{P}_p)_{p \in [0,1]}$. Soient $(U_e)_{e \in E}$ des v.a.r. i.i.d. de loi uniforme sur $[0, 1]$. Pour tout $p \in [0, 1]$ on réalise $\mathbb{P}_p$ comme la loi de $F_p := (\mathbb{1}_{\{U_e \le p\}})_{e \in E}$. Si $p \le p'$, alors $F_p \subset F_{p'}$. Toute arête de $(V, F_p)$ est aussi une arête de $(V, F_{p'})$. Si $x \leftrightarrow y$ pour $(V, F_p)$ alors c'est aussi le cas pour $(V, F_{p'})$. Par conséquent on obtient

$$\theta(p) = \mathbb{P}_p(\emptyset \leftrightarrow \infty) \le \mathbb{P}_{p'}(\emptyset \leftrightarrow \infty) = \theta(p').$$

□

**Remarque 16.2 (Couplage et monotonie).** *Munissons $\Omega$ de l'ordre partiel issu de l'inclusion dans $\mathcal{P}_2(V)$, ce qui signifie que $F \le F'$ ssi toute arête de $(V, F)$ est aussi une arête de $(V, F')$. Pour toute $f : \Omega \to \mathbb{R}$ bornée, l'argument de couplage utilisé dans la preuve du lemme 16.1 assure que si $f$ est croissante alors $p \in [0, 1] \mapsto \mathbb{E}_p(f)$ l'est aussi.*
## 16.2 Graphe de Bethe (arbre régulier)

On considère dans cette section le cas où $(V, E)$ est le graphe de Bethe $\mathcal{B}_r$ de degré $r \ge 2$, c'est-à-dire l'arbre infini dont chaque sommet a $r$ voisins sauf un qui n'en a que $r-1$, noté $0$ et appelé racine de l'arbre (voir la figure 16.2). Pour tout $p \in [0, 1]$, sous $\mathbb{P}_p$, le graphe aléatoire $(V, F)$ est un ensemble d'arbres qu'on appelle parfois forêt. La probabilité de percolation et la probabilité critique pour le sommet racine $\emptyset = 0$ dans $\mathcal{B}_r$ sous $\mathbb{P}_p$ sont respectivement notées

$$ \theta_r(p) := \mathbb{P}_p(0 \leftrightarrow \infty) = \mathbb{P}_p(|C(0)| = \infty), \\ p_c(r) := \sup \{p \in [0, 1] : \theta_r(p) = 0\}. $$

**Théorème 16.3** (Phénomène de seuil pour percolation sur graphe de Bethe). *Pour tout r $\ge 2$ et tout $p \in [0, 1]$ la quantité $\theta_r(p)$ est la plus grande racine en $\theta \in [0, 1]$ de l'équation*

$$ 1 - \theta = (1 - p\theta)^{r-1}, $$

tandis que

$$ p_c(r) = \frac{1}{r-1}. $$

*De plus, la fonction $\theta_r$ est continue, nulle sur $[0, p_c(r)]$, strictement croissante sur $[p_c(r), 1]$, et pour $r \ge 3$ on a*

$$ \lim_{p \to p_c(r)^+} \frac{\theta_r(p)}{p - p_c(r)} = \frac{2}{p_c(r)(1 - p_c(r))} = \frac{2(r-1)^2}{r-2}. $$

Si $r \ge 3$ alors $0 < p_c(r) < 1$ ce qui indique la présence d'un phénomène de seuil pour la percolation sur le graphe de Bethe $\mathcal{B}_r$.

*Démonstration.* Le graphe de Bethe $\mathcal{B}_r$ coïncide avec l'arbre de Galton-Watson de loi de reproduction $\delta_{r-1}$. Sous $\mathbb{P}_p$ on obtient un arbre aléatoire dans lequel chaque sommet de l'arbre est relié à chacun de ses $r-1$ enfants avec une probabilité $p$. Le nombre de ces connexions est distribué selon la loi de reproduction Bin$(r-1, p)$ de moyenne $m = (r-1)p$. D'après le chapitre 3, cet arbre est sous-critique si $m < 1$, critique si $m = 1$, et sur-critique si $m > 1$. D'après le théorème 3.7 la probabilité d'extinction de la population est la plus petite racine $s_p$ de l'équation $g_p(s) = s$ où $g_p$ est la fonction génératrice de la loi de reproduction : $g_p(s) = (ps + 1 - p)^{r-1}$ pour $s \in [0, 1]$. L'extinction de la population est synonyme de la finitude de la composante connexe de la racine. On a donc $\theta_r(p) = 1 - s_p$ et $\theta_r(p)$ est ainsi la plus grande racine dans $[0, 1]$ de l'équation $1 - \theta = (1 - p\theta)^{r-1}$.

Soit $h_p$ la fonction définie sur $[0, 1]$ par $h_p(\theta) = (1 - p\theta)^{r-1} - 1 + \theta$. Elle est nulle en 0, strictement positive en 1, strictement convexe si $r \ge 3$ et affine si $r = 2$. De plus $h'_p(0)$ a le signe de $1 - p(r - 1)$. Ainsi, pour $p(r - 1) \le 1$,
<figure><img src="image_50.png" /><figcaption>Fig. 16.2. Premières branches de $\mathcal{B}_4$ avec arêtes supprimées par $\mathbb{P}_p$ (en pointillé).</figcaption></figure>

$h_p$ ne s'annule qu'en 0 et $\theta_r(p) = 0$. En revanche, $h_p$ s'annule exactement une fois sur $]0, 1[$ dès que $p(r-1) > 0$. En conclusion, la probabilité $\theta_r(p)$ est nulle pour $p \le (r-1)^{-1}$ et strictement positive pour $p > (r-1)^{-1}$. La fonction $p \mapsto h_p(\theta)$ est strictement décroissante et continue. Ceci assure que la fonction $\theta_r$ est continue sur $[0, 1]$ et strictement croissante sur $[p_c(r), 1]$.

On a enfin $1 - \theta = 1 - (r-1)p\theta + \frac{1}{2}(r-1)(r-2)p^2\theta^2 + o(\theta^2)$. Puisque $\theta_r(p_c(r)) = 0$ et $\theta_r(p)$ est strictement positive pour $p > p_c = (r-1)^{-1}$, on obtient après simplification

$$ \theta_r(p) = 2 \frac{(r-1)p-1}{(r-1)(r-2)p^2} + o(\theta_r(p)) = \frac{2}{(r-2)p^2} (p-p_c) + o(\theta_r(p)). $$

On conclut en remarquant que $(r-2)p_c = 1 - p_c$. $\square$

<figure><img src="image_51.png" /><figcaption>Fig. 16.3. Percolation pour $\mathcal{B}_r$ avec $r = 3$ (trait plein) et $r = 4$ (trait en pointillé).</figcaption></figure>

**Remarque 16.4** (Caractère explicite des cas $r \le 4$). Pour $r = 2$, le graphe de Bethe $\mathcal{B}_2$ est identifiable au graphe de $\mathbb{N}$ et sous $\mathbb{P}_p$ la v.a. $|C(0)|$ suit la
loi géométrique de paramètre $1-p$, et $\theta_2 = 1_{1}$ et $p_c(2) = 1$. Pour $r = 3$ et $r = 4$ l'équation vérifiée par $\theta_r(p)$ fournie par le théorème 16.3 est résoluble explicitement (voir la figure 16.3) :

$$ \theta_3(p) = \frac{2p-1}{p^2} 1_{\{p>1/2\}} \quad \text{et} \quad \theta_4(p) = \frac{3p^2 - \sqrt{4p^3 - 3p^4}}{2p^3} 1_{\{p>1/3\}}. $$

**Remarque 16.5** (Taille moyenne de la composante de la racine). Reprenons la preuve du théorème 16.3, et supposons que $p \le p_c(r)$. Alors $|C(0)| < \infty$ p.s. car la lignée de la racine s'éteint p.s. De plus d'après la section 3.3 la fonction génératrice h de $|C(0)|$ est solution de l'équation

$$ h(s) = s(ph(s) + 1 - p)^{r-1}. $$

En particulier on obtient

$$ \mathbb{E}_p(|C(0)|) = \begin{cases} \frac{1}{1-p(r-1)} & \text{si } p < p_c(r), \\ \infty & \text{si } p = p_c(r). \end{cases} $$

D'autre part, si $p \in ]p_c, 1[$ alors il existe une infinité de classes de taille infinie car les individus non reliés à leur père sont les racines d'arbres aléatoires disjoints i.i.d. Cette situation, liée à la structure d'arbre, est très différente de celle du graphe euclidien étudié dans la suite.

## 16.3 Graphe euclidien (grille)

On considère dans cette section le cas où $(V, E)$ est le graphe euclidien $\mathcal{E}_d$ :

$$ V = \mathbb{Z}^d \quad \text{et} \quad E = \left\{ \{x, y\} \in \mathcal{P}_2(\mathbb{Z}^d) : |x - y|_1 = \sum_{i=1}^d |x_i - y_i| = 1 \right\}. $$

La probabilité de percolation et la probabilité critique pour le sommet racine $\emptyset = 0$ dans $\mathcal{E}_d$ sous $\mathbb{P}_p$ sont respectivement notées

$$ \theta_d(p) := \mathbb{P}_p(0 \leftrightarrow \infty) = \mathbb{P}_p(|C(0)| = \infty) \\ p_c(d) := \sup \{p \in [0, 1] : \theta_d(p) = 0\}. $$

Pour $d = 1$, le graphe $\mathcal{E}_1$ est identifiable au graphe $\mathbb{Z}$, pour tout $x \in \mathbb{Z}$, sous $\mathbb{P}_p$, la variable aléatoire $|C(x)|$ a la loi de $G_- + G_+ - 1$ où $G_-$ et $G_+$ sont des variables aléatoires indépendantes de loi géométrique de paramètre $1-p$. Ainsi pour $d = 1$ on obtient $\theta_1 = 1_1$ et $p_c(1) = 1$.

Dès que $d > 1$, la probabilité de l'évènement $\{x \leftrightarrow y\}$ pour $\mathcal{E}_d$ sous $\mathbb{P}_p$ n'est pas explicite même pour $x \sim y$ car toutes les arêtes du graphe sont susceptibles de jouer un rôle, contrairement au cas des graphes de Bethe. Du point de vue de la connectivité, la grille est beaucoup plus complexe qu'un arbre car la présence de cycles permet de faire des détours.
**Lemme 16.6 (Petite classe).** Pour tous $d \ge 1$, $x \in \mathbb{Z}^d$, $p \in [0, 1]$,

$$ P_p(C(x) = \{x\}) = (1-p)^{2d} \quad \text{et} \quad P_p(|C(x)| = 2) = p(1-p)^{2(2d-1)}. $$

*Démonstration.* On a $|C(x)| = 1$ si et seulement si $x$ n'est relié à aucun de ses $2d$ voisins, tandis que $|C(x)| = 2$ si et seulement si $x$ n'est relié qu'à un seul de ses $2d$ voisins, lui-même n'étant relié qu'à $x$. $\square$

**Théorème 16.7 (Phénomène de seuil pour percolation sur graphe euclidien).**
Pour tous $2 \le d \le d'$ on a $\theta_d \le \theta_{d'}$ et $p_c(d) \le p_c(d')$. De plus on a

$$ 0 < \frac{1}{2d-1} \le \frac{1}{\kappa(d)} \le p_c(d) \le 1 - \frac{1}{\kappa(2)} \le \frac{2}{3} < 1, $$

où la constante $\kappa(d)$ est définie dans le lemme 16.8.

La constante $\kappa(d)$ est appelée *constante de connectivité de $\mathcal{E}_d$*. Pour plus de clarté, la démonstration du théorème 16.7 est découpée en quatre lemmes.

**Lemme 16.8 (Constante de connectivité).** Pour tous $d \ge 2$ et $n \ge 1$ soit $\kappa_n(d)$ le cardinal de l'ensemble $C_n^d$ des chemins auto-évitants dans $\mathcal{E}_d$ de longueur $n$ issus de l'origine 0. On a

$$ d^n \le \kappa_n(d) \le 2d(2d-1)^{n-1}. $$

De plus, la suite $(\kappa_n(d)^{1/n})_{n \ge 1}$ converge et sa limite $\kappa(d)$ vérifie

$$ d \le \kappa(d) \le 2d - 1. $$

*Démonstration du lemme 16.8.* La première arête d'un chemin auto-évitant issu de 0 peut être choisie parmi les $2d$ arêtes issues de 0. Pour les pas suivants, les retours en arrière sont proscrits, d'où $\kappa_n(d) \le 2d(2d-1)^{n-1}$. La borne inférieure $\kappa_n(d) \ge d^n$ est obtenue en remarquant que tout chemin issu de 0 dont les coordonnées des sommets successifs sont croissantes est auto-évitant. La suite $(\kappa_n(d))_{n \ge 1}$ est sous-multiplicative : pour tous $n, m \ge 1$,

$$ \kappa_{n+m}(d) \le \kappa_n(d)\kappa_m(d), $$

car si $(0, x_1, \dots, x_{n+m}) \in C_{n+m}^d$ alors

$$ (0, x_1, \dots, x_n) \in C_n^d \quad \text{et} \quad (0, x_{n+1} - x_n, \dots, x_{n+m} - x_n) \in C_m^d. $$

La suite $(\log(\kappa_n(d)))_{n \ge 1}$ est donc sous-additive, et le lemme de Fekete<fnref n="2" /> donne

$$ \lim_{n \to \infty} \frac{\log(\kappa_n(d))}{n} = \lambda \quad \text{où} \quad \lambda := \inf_{n \ge 1} \frac{\log(\kappa_n(d))}{n} \in [-\infty, \infty]. $$

Ceci donne $\kappa(d) = e^\lambda$, et l'encadrement de $\kappa(d)$ découle de celui de $\kappa_n(d)$. $\square$

<footnote n="2">2. Si $u_{n+m} \le u_n + u_m$ pour tous $m, n \ge 1$ alors $\frac{u_n}{n} \xrightarrow{n \to \infty} \inf_{n \ge 1} \frac{u_n}{n} \in [-\infty, \infty[$.</footnote>
**Lemme 16.9 (Minoration).** *Pour tout $d \ge 2$ on a $p_c(d) \ge 1/\kappa(d)$.*

*Démonstration du lemme 16.9.* Soit $n \ge 1$ et $N_n$ la v.a. égale au nombre d'éléments de $C_n^d$ inclus dans l'ensemble aléatoire d'arêtes $C(0)$ sous $\mathbb{P}_p$. Si $|C(0)| = \infty$, alors $N_n \ge 1$. D'autre part, un élément de $C_n^d$ est issu de l'origine et possède exactement $n$ arêtes distinctes. Par indépendance, il a une probabilité $p^n$ d'avoir toutes ses arêtes dans $C(0)$. Ainsi

$$ \theta_d(p) \le \mathbb{P}_p(N_n \ge 1) = \mathbb{E}_p(\mathbb{1}_{N_n \ge 1}) \le \mathbb{E}_p(N_n) \le p^n \kappa_n(d). $$

Le lemme 16.8 donne $\kappa_n(d)^{1/n} = \kappa(d) + o_n(1)$, d'où $\theta_d(p) \le (p\kappa(d) + o_n(1))^n$. Par conséquent, si $p\kappa(d) < 1$ alors on obtient $\theta_d(p) = 0$ quand $n \to \infty$. $\square$

**Lemme 16.10 (Décroissance).** *Si $2 \le d \le d'$ alors $\theta_d \le \theta_{d'}$ et $p_c(d') \le p_c(d)$.*

*Démonstration du lemme 16.10.* L'idée est de procéder par couplage comme dans la preuve du lemme 16.1. Comme le graphe $\mathcal{E}_d$ est identifiable au graphe de $\mathcal{E}_{d'}$ correspondant par exemple aux $d$ premières coordonnées dans $\mathbb{Z}^{d'}$, on peut coupler, pour tout $p \in [0, 1]$ fixé, les graphes aléatoires $(\mathbb{Z}^d, F)$ et $(\mathbb{Z}^{d'}, F')$ de $\mathcal{E}_d$ et $\mathcal{E}_{d'}$ sous $\mathbb{P}_p$ de sorte que

$$ \theta_d(p) = \mathbb{P}_p(0 \leftrightarrow +\infty \text{ dans } \mathcal{E}_d) \le \mathbb{P}_p(0 \leftrightarrow +\infty \text{ dans } \mathcal{E}_{d'}) = \theta_{d'}(p). $$

Il en découle en particulier que $p_c(d) \le p_c(d')$. $\square$

**Lemme 16.11 (Majoration).** *Si $d=2$ alors $p_c(2) \le 1 - 1/\kappa(2)$.*

*Démonstration du lemme 16.11.* Le graphe dual $\mathcal{E}_2^* = (V^*, E^*)$ du graphe $\mathcal{E}_2 = (V, E)$ est le translaté de $\mathcal{E}_2$ par le vecteur $(1/2, 1/2)$ (voir la figure 16.3). Chaque arête $e$ du graphe initial rencontre une et une seule arête $e_*$ du graphe dual. On construit le graphe aléatoire $(V^*, F^*)$ de $\mathcal{E}_2^*$ à partir du graphe aléatoire $(V, F)$ de $\mathcal{E}_2$ sous $\mathbb{P}_p$ en décidant que $e_* \in F^*$ ssi $e \notin F$.

Une boucle auto-évitante (ou courbe de Jordan !) de longueur $n$ est un chemin $(x_0, x_1, \dots, x_n)$ tel que le chemin $(x_0, x_1, \dots, x_{n-1})$ est auto-évitant et $x_n = x_0$. Son complémentaire est formé de deux composantes connexes, l'une bornée (appelée *intérieur*) et l'autre pas.

Soit $\Lambda(m) := [-m, m]^2$. On introduit les évènements suivants :

$$ F_m := \{ \Lambda(m) \text{ est à l'intérieur d'une boucle} \\ \text{auto-évitante de } \mathcal{E}_2^* \text{ à arêtes dans } F^* \}, $$

et

$$ G_m := \{ \text{les arêtes reliant les sommets de } \Lambda(m) \text{ sont dans } F \}. $$

Il y a percolation en 0 sur l'événement $F_m^c \cap G_m$, et comme $F_m$ et $G_m$ concernent des ensembles d'arêtes disjoints, ils sont indépendants sur $\mathbb{P}_p$. Considérons à présent une boucle $\gamma$ dont l'intérieur contient $\Lambda(m)$. Sa longueur $n$ est nécessairement supérieure à $4m$. De plus, elle contient nécessairement au
moins un sommet de la forme $(1/2 + k, 1/2)$ avec $0 \le k \le n$. Soit $x_0$ le point de cette forme le plus à droite. On numérote les éléments de $\gamma$ en parcourant la courbe dans le sens trigonométrique de sorte que $\gamma = (x_0, x_1, \dots, x_{n-1})$. Ce chemin est auto-évitant. Il y a au plus $n\kappa_n(2)$ boucles auto-évitantes de longueur $n$ entourant $\Lambda(m)$. Donc si $M_n$ est le nombre de boucles auto-évitantes de longueur $n$ entourant $\Lambda(m)$ dont toutes les arêtes sont dans $F$, on a

$$ \mathbb{P}_p(F_m) \le \mathbb{P}_p \left( \sum_{n \ge 4m} M_n \ge 1 \right) \le \sum_{n \ge 4m} \mathbb{E}_p(M_n) \le \sum_{n \ge 4m} n\kappa_n(2)(1-p)^n. $$

Puisque $\kappa_n(2)^{1/n} = \kappa(2) + o_n(1)$, la série ci-dessus (membre de droite) est convergente dès que $\kappa(2)(1-p) < 1$ et par suite, pour $m$ assez grand, $\mathbb{P}_p(F_m) < 1/2$. Pour un tel $m$ on a

$$ \theta_2(p) \ge \mathbb{P}_p(F_m^c \cap G_m) = \mathbb{P}_p(F_m^c) \mathbb{P}_p(G_m) \ge \frac{1}{2} p^{4m^2} > 0. $$

Ainsi, si $(1-p)\kappa(2) < 1$ alors $\theta_2(p) > 0$, d'où $p_c(2) \le 1 - 1/\kappa(2)$. $\square$

<figure><img src="image_52.png" /><figcaption>**Fig. 16.4.** À gauche, le graphe euclidien $\mathcal{E}_2$ (trait plein) et son dual $\mathcal{E}_2^*$ (trait pointillé). À droite, une composante finie et sa boucle ceinturante.</figcaption></figure>

Dans le régime sur-critique $p > p_c(d)$, la classe $C(0)$ de l'origine 0 peut être infinie. Le théorème suivant complète ce résultat.

**Théorème 16.12 (Existence de la classe infinie).** Si $p > p_c(d)$, alors $\mathbb{P}_p$-p.s. il existe au moins une classe infinie.

*Démonstration.* L'événement $A :=\{$Il existe au moins une classe infinie$\}$ est dans la tribu terminale des événements $(A_e)_{e \in E}$ où $A_e := \{e \in F\}$. Or sous $\mathbb{P}_p$ ces événements sont indépendants, et donc $\mathbb{P}_p(A) = 0$ ou $\mathbb{P}_p(A) = 1$ par la loi du zéro-un de Kolmogorov. À présent si $p > p_c(d)$ alors $\mathbb{P}_p(|C(0)| = \infty) > 0$ et $\{|C(0)| = \infty\} \subset A$, d'où $\mathbb{P}_p(A) = 1$. $\square$
Toutefois, la situation est bien différente de celle du graphe de Bethe : on peut établir que la classe infinie est unique ! Cette démonstration dépasse le cadre de ce chapitre. Nous nous contentons d'une démonstration sur $\mathcal{E}_2$ en supposant connu le fait que $\theta_2(1/2) = 0$.

**Théorème 16.13** (Unicité de la classe infinie). *Supposons que $d = 2$ et que $\theta_2(1/2) = 0$ sur le graphe $\mathcal{E}_2$. Alors, pour tout $p > p_c(2)$, il existe $\mathbb{P}_p$-p.s. une unique classe infinie.*

*Démonstration.* Reprenons les notations de la preuve du lemme 16.11.

Pour $p = 1/2$, la percolation sur le graphe $\mathcal{E}_2$ et sur son graphe dual $\mathcal{E}_2^*$ sont de même nature : $\mathbb{P}_p$-p.s. il n'y a pas de composante infinie car $\theta_2(1/2) = 0$. Soit $\Lambda(m) = [-m, m]^2$. Il existe une boucle $\gamma_*$ auto-évitante dans $\mathcal{E}_2^*$ entourant $\Lambda(m)$ et dont les arêtes sont dans $F^*$ (donc les arêtes duales dans $\mathcal{E}_2$ ne sont pas dans $F$). Par le même argument, il existe une boucle $\gamma$ dans $\mathcal{E}_2$ qui contient $\gamma_*$ et donc $\Lambda(m)$. Par couplage, ceci est encore vrai pour tout $p > 1/2$. Si deux classes d'équivalence infinies intersectent $\Lambda(m)$ alors elles intersectent également $\gamma$ et sont donc confondues ! Puisque ceci est vrai pour tout $m$, il ne peut y avoir qu'une classe infinie. $\square$

## 16.4 Graphe complet et modèle de Erdős-Rényi

On considère dans cette section le cas où $(V, E)$ est le *graphe complet infini* $\mathcal{K}_\infty$, c'est-à-dire que $V$ est infini dénombrable et $E = \mathcal{P}_2(V)$. Ainsi $x \sim y$ pour tous $x \neq y$ dans $V$. Les sommets jouent tous le même rôle. Comme tous les sommets sont voisins dans $\mathcal{K}_\infty$, il n'y a donc pas de géométrie comme dans $\mathcal{B}_r$ ou dans $\mathcal{E}_d$. Sous $\mathbb{P}_p$ le graphe aléatoire $(V, F)$ est appelé modèle de Erdős-Rényi infini. Pour tous $p \in ]0, 1]$ et $x \in V$, le sommet $x$ a un nombre infini de voisins dans $(V, F)$ et $\mathbb{P}_p(|C(x)| = \infty) = 1$, d'où $\theta = \mathbb{1}_{[0,1]}$ et $p_c = 0$.

Pour rendre le modèle plus passionnant, on peut considérer le phénomène de la percolation dans le graphe complet fini $\mathcal{K}_n$ à $n$ sommets $V = \{1, \dots, n\}$ et faire dépendre de $n$ le paramètre $p$ de $\mathbb{P}_p$. On note $\mathcal{G}(n, p)$ la loi du graphe aléatoire $(V, F)$ sous $\mathbb{P}_p$. Dans ce modèle de Erdős-Rényi fini $\mathcal{G}(n, p)$, chaque sommet $x \in V$ possède un nombre aléatoire de voisins, qui suit la loi binomiale $\text{Bin}(n-1, p)$ de moyenne $(n-1)p \sim np$. Lorsque $n \to \infty$ avec $np \to \lambda > 0$ alors $p_n \sim \lambda/n \to 0$ et le nombre de voisins de chaque site converge en loi vers la loi de Poisson $\text{Poi}(\lambda)$ (loi des petits nombres).

**Théorème 16.14** (Phénomène de seuil et composante connexe géante). *Soit $\lambda > 0$ un paramètre réel fixé, et $\alpha := \lambda - 1 - \log(\lambda) > 0$. Soit $(G_n)_{n \ge 1}$ une suite de graphes de Erdős-Rényi définis sur un même espace de probabilité, avec $G_n = (V_n, F_n)$ de loi de Erdős-Rényi $\mathcal{G}(n, p)$ avec $p = \lambda/n$. Pour tout $v \in V_n$, soit $G_n(v)$ la composante connexe du sommet $v$.*

1. Si $\lambda < 1$ alors pour tout $c > 1/\alpha$,
$$ \lim_{n \to \infty} \mathbb{P} \left( \max_{v \in V_n} |G_n(v)| \ge c \log(n) \right) = 0. $$

2. Si $\lambda > 1$ alors

$$ \frac{\max_{v \in V_n} |G(v)|}{n} \xrightarrow{n \to \infty} 1 - \rho $$

où $\rho \in ]0,1[$ est la probabilité d'extinction d'un processus de branche-ment de Galton-Watson de loi de reproduction Poi($\lambda$). De plus, il existe un réel $c > 0$ tel que presque sûrement la seconde composante connexe (en taille) a une taille au plus $c \log(n)$.

En substance, si $\lambda < 1$ alors la connectivité du graphe aléatoire est si faible qu'il ne comporte pas de composante connexe plus grande que $O(\log(n))$. Le graphe est émietté. Si $\lambda > 1$ alors la connectivité du graphe aléatoire est si forte qu'il contient une unique composante connexe géante contenant une fraction strictement positive des sommets tandis que les autres composantes connexes ont une taille qui n'excède pas $O(\log(n))$.

**Démonstration.** Par souci de simplicité, nous nous contentons d'établir la première propriété seulement. Pour ce faire, on explore $G(v)$ en utilisant un algorithme de parcours en largeur$^3$, qui consiste à explorer les voisins de $v$, qui constituent la première génération, puis leurs voisins qui n'ont pas déjà été visités, qui constituent la seconde génération, etc. Cela donne un arbre fini couvrant$^4$ $G(v)$, similaire à celui de la figure 3.2. En forçant l'absence de cycles, cette approche fournit également un couplage avec un arbre aléatoire de Galton-Watson de loi de reproduction Bin($n-1, p$), sous-critique car $(n-1)p \le \lambda < 1$, dont la taille totale $N$ vérifie $N \ge |G(v)|$ (l'arbre est plus gros par absence de cycles). Or le théorème 3.17 affirme que

$$ N \stackrel{\text{loi}}{=} T \quad \text{où} \quad T := \inf\{k \ge 1 : S_k = -1\} $$

est le temps d'atteinte de $-1$ d'une marche aléatoire $(S_k)_{k \ge 0}$ sur $\mathbb{Z}$ issue de $S_0 = 0$ et d'incréments $(U_i)_{i \ge 1}$ i.i.d. tels que $1 + U_i \sim \text{Bin}(n-1, p)$. Fixons $\theta > 0$ quelconque et posons

$$ M_k = e^{\theta S_k} \varphi(\theta)^{-k} \quad \text{où} \quad \varphi(\theta) = \mathbb{E}(e^{\theta U_1}) $$

est la transformée de Laplace de la loi des incréments de $(S_k)_{k \ge 0}$. La suite $(M_k)_{k \ge 0}$ est une martingale positive pour la filtration naturelle de $(S_k)_{k \ge 0}$, et $T$ est un temps d'arrêt fini p.s. On a $\lim_{n \to \infty} M_{T \wedge n} = M_T$ p.s. de sorte que grâce au lemme de Fatou et au théorème d'arrêt,

$$ e^{-\theta} \mathbb{E}(\varphi(\theta)^{-T}) = \mathbb{E}(M_T) = \mathbb{E}(\lim_{n \to \infty} M_{T \wedge n}) \le \lim_{n \to \infty} \mathbb{E}(M_{T \wedge n}) = \mathbb{E}(M_0) = 1. $$

<footnote n="3">3. « Breadth-First Search » en anglais (BFS).</footnote>

<footnote n="4">4. « Spanning tree » en anglais et on parle de « Minimal Spanning Tree » (MST).</footnote>
Soit $\theta > 0$ tel que $\varphi(\theta) < 1$. Pour tout $r > 0$, par l'inégalité de Markov,

$$ \mathbb{P}(T \ge r) = \mathbb{P}(\varphi(\theta)^{-T} \ge \varphi(\theta)^{-r}) \le \varphi(\theta)^r \mathbb{E}(\varphi(\theta)^{-T}) \le \varphi(\theta)^r e^{\theta}. $$

L'inégalité de convexité $1 + x \le e^x$ valable pour tout $x \in \mathbb{R}$ donne

$$ \varphi(\theta) = e^{-\theta}(1 - p + pe^{\theta})^{n-1} = e^{-\theta} \left( 1 + \frac{\lambda(e^{\theta} - 1)}{n} \right)^{n-1} \le e^{\lambda(e^{\theta} - 1) - \theta} $$

(notons que $e^{\lambda(e^{\theta} - 1)}$ est la transformée de Laplace de Poi($\lambda$)). La fonction $\theta \in \mathbb{R} \mapsto \lambda(e^{\theta} - 1) - \theta$ atteint son minimum en $\theta_* = -\log(\lambda) > 0$, et $\varphi(\theta_*) = e^{-\alpha}$ où $\alpha := 1 - \lambda + \log(\lambda) > 0$, d'où

$$ \mathbb{P}(T \ge r) \le \varphi(\theta_*)^r e^{\theta_*} = e^{-r\alpha + \theta_*} = \lambda^{-1} e^{-\alpha r}. $$

Par conséquent, pour tout $c > 0$,

$$ \mathbb{P}(|G(v)| \ge c \log(n)) \le \mathbb{P}(N \ge c \log(n)) = \mathbb{P}(T \ge c \log(n)) \le \lambda^{-1} n^{-\alpha c}. $$

À présent, comme les v.a. $(G(v))_{v \in V}$ sont identiquement distribuées, on a

$$ \begin{aligned} \mathbb{P}\left(\max_{v \in V} |G(v)| \ge c \log(n)\right) &\le \sum_{v \in V} \mathbb{P}(|G(v)| \ge c \log(n)) \\ &= n \mathbb{P}(|G(1)| \ge c \log(n)) \\ &\le \lambda^{-1} n^{1-\alpha c}, \end{aligned} $$

d'où le résultat en prenant $c > 1/\alpha$. $\square$

## 16.5 Pour aller plus loin

La géométrie des arbres réguliers (graphe de Bethe) et des graphes complets est plus simple que celle du graphe euclidien (grille), ce qui facilite en principe l'étude de propriétés probabilistes. En informatique, en télécommUNICATION, mais aussi en électricité, un réseau<fnref n="5" /> est un graphe muni d'une marque ou d'un poids sur chaque arête, représentant une conductance, une résistance, une longueur, un coût, etc, dans notre cas 0 (arête indisponible) ou 1 (arête disponible). En ce sens, nos graphes aléatoires sont des réseaux aléatoires<fnref n="6" />. Dans le cas euclidien, le graphe est également un réseau au sens de la géométrie<fnref n="7" />, c'est-à-dire un sous-groupe discret de l'espace vectoriel euclidien.

Le phénomène de la percolation est un classique de la physique statistique, qui peut être étudié sur tout graphe aléatoire. Le mécanisme de la percolation possède par ailleurs de nombreuses variantes : percolation orientée (les arêtes

<footnote n="5">5. « Network » en anglais.</footnote>

<footnote n="6">6. « Random networks » en anglais.</footnote>

<footnote n="7">7. « Lattice » en anglais.</footnote>
sont orientées), percolation de premier passage, de dernier passage, percolation par sommets (ce sont les sommets et non les arêtes qui sont déclarés ouverts ou fermés), etc. Une bonne partie de ce chapitre est inspirée des notes de cours de Thierry Lévy [Lé08]. La théorie mathématique de la percolation, développée depuis le milieu du vingtième siècle par John Hammersley et Harry Kesten notamment, constitue depuis lors un domaine très actif des probabilités. Un panorama sur le sujet se trouve dans les livres [Gri99, Gri10] de Geoffrey Grimmett, dont la thèse soutenue en 1974 sous la direction de Hammersley et Dominic Welsh (ancien élève de Hammersley également) portait déjà sur les champs et graphes aléatoires! Le théorème 16.14 date des travaux du milieu du vingtième siècle de Paul Erdős et Alfréd Rényi [ER59, ER61b] et de Edgar Gilbert [Gil59]. La preuve du théorème 16.14 est inspirée des notes de cours de Charles Bordenave [Bor14a]. Plus généralement, on peut établir ce qui suit :

<table><thead><tr><th>Condition sur (n, p)</th><th>Comportement p.s. du graphe aléatoire G(n, p) quand n → ∞</th></tr></thead><tbody><tr><td>np &lt; (1 - ε) log(n)</td><td>existence de sommets isolés (donc graphe non connexe)</td></tr><tr><td>np &gt; (1 + ε) log(n)</td><td>graphe connexe (donc np ~ log(n) est un seuil de connectivité)</td></tr><tr><td>np &lt; 1</td><td>pas de composante connexe de taille &gt; O(log(n))</td></tr><tr><td>np = 1</td><td>plus grande composante connexe de taille ≈ n<sup>2/3</sup></td></tr><tr><td>np → λ &gt; 1</td><td>unique composante connexe géante (fraction ≈ 0 des sommets)</td></tr><tr><td></td><td>aucune autre composante connexe n'est &gt; O(log(n)).</td></tr></tbody></table>

On renvoie à ce sujet à [Bor14a] et au livre de Remco van der Hofstad [vdH14]. On y trouvera la démonstration du second point du théorème 16.14.

Le lemme 16.8 sur la constante de connectivité du graphe euclidien est l'une des clés de la démonstration du théorème 16.7. Toutefois, la valeur exacte de cette constante $\kappa(d)$ est inconnue pour tout $d \ge 2$. Hugo Duminil-Copin et Stanislav Smirnov ont montré dans [DCS12] qu'elle vaut $\sqrt{2} + \sqrt{2}$ pour le graphe hexagonal sur $Z^2$. La démonstration du théorème 16.13, tirée de l'article de synthèse [HJ06], est due à Theodore Harris [Har60]. Dans ce travail, Harris établit également que $\theta_2(1/2) = 0$ c'est-à-dire que $p_c(2) \ge 1/2$. Il faudra attendre le travail de Kesten [Kes80] pour que l'égalité $p_c(2) = 1/2$ soit démontrée. Pour les autres valeurs de $d$, la valeur de la probabilité critique n'est pas connue. On peut toutefois établir que $\theta_d$ est de classe $C^\infty$ sur l'intervalle $]p_c(d), 1[$.
<figure><img src="image_53.png" /></figure>
# Croissance et fragmentation

**Mots-clés.** Modèle de croissance et de fragmentation; processus de Markov déterministe par morceaux; générateur infinitésimal; processus de Yule.

**Outils.** Processus de Poisson; couplage; distance de Wasserstein; processus autorégressif; loi exponentielle; loi géométrique; fonction génératrice; transformée de Laplace.

**Difficulté.** **

## 17.1 Processus TCP window-size en informatique

Le débit instantané maximal sortant d'un ordinateur connecté à un réseau TCP/IP<fnref n="1" /> comme Internet est régulé par l'algorithme suivant : le débit maximal est augmenté de manière déterministe d'une unité à chaque pas de temps, et en cas de signal de congestion, il est multiplié par un facteur entre [0, 1[, typiquement 1/2. Ce mécanisme simple permet à la fois une bonne exploitation du réseau et une réaction efficace en cas de congestion.

Nous allons étudier un modèle markovien idéalisé de ce mécanisme. Si on admet que, pendant une durée donnée, chacun des autres ordinateurs du réseau provoque une congestion avec une petite probabilité, indépendamment des autres, alors la loi des petits nombres suggère que les signaux de congestion suivent un processus de Poisson. Soit $N = (N_t)_{t \ge 0}$ un processus de Poisson issu de 0 et d'intensité $\lambda$ comptant les signaux de congestion, de temps de saut successifs $(T_n)_{n \ge 0}$, où $T_0 := 0$. Si $E_n := T_n - T_{n-1}$ pour tout $n \ge 1$ alors

$$T_n = E_1 + \dots + E_n,$$

<footnote n="1">1. Pour « Transmission Control Protocol » et « Internet Protocol ».</footnote>
et la suite $E = (E_n)_{n \ge 1}$ est constituée de variables aléatoires i.i.d. de loi exponentielle de moyenne $1/\lambda$. Pour tout $t \in \mathbb{R}_+$ on a

$$N_t = \sum_{n \ge 1} 1_{[0,t]}(T_n).$$

Soit $Q = (Q_n)_{n \ge 1}$ une suite de variables aléatoires indépendantes à valeurs dans $[0, 1[$ de même loi $Q$. Soit $X_0$ une variable aléatoire positive. On suppose que $X_0, E, \text{et } Q$ sont indépendants. On définit le processus $X = (X_t)_{t \ge 0}$ à temps continu et à espace d'états $\mathbb{R}_+$ de la manière suivante :

$$X_t = \begin{cases} X_{T_n} + t - T_n & \text{si } T_n \le t < T_{n+1}, \\ Q_{n+1}(X_{T_n} + T_{n+1} - T_n) & \text{si } t = T_{n+1}, \end{cases}$$

où $n = N_t \in \mathbb{N}$ est le nombre de sauts avant l'instant $t$. Les trajectoires de $X$ sont affines de pente 1 par morceaux, continues à droite avec limite à gauche, et chaque saut correspond à une multiplication par un nombre dans $[0, 1[$. On dit qu'il s'agit d'un processus de Markov déterministe par morceaux² et plus particulièrement un processus à croissance linéaire et décroissance multiplicative³. Le processus $X$ est connu sous le nom de processus de taille de fenêtre TCP⁴ car en informatique, le débit maximal sortant est réglé par une taille de « fenêtre TCP ».

<figure><img src="image_54.png" /><figcaption>Fig. 17.1. Allure d'une trajectoire typique du processus $X$.</figcaption></figure>

**Théorème 17.1** (Générateur infinitésimal). Le générateur infinitésimal du processus $X$ est donné, pour toute fonction $f \in C^1(\mathbb{R}_+, \mathbb{R})$ et tout $x \ge 0$, par

$$L(f)(x) := \lim_{t \to 0^+} \frac{\mathbb{E}(f(X_t) | X_0 = x) - f(x)}{t} \\ = f'(x) + \lambda \int_0^1 (f(qx) - f(x)) \mathcal{Q}(dq).$$

2. « Piecewise Deterministic Markov Processes (PDMP) » en anglais.

3. « Additive Increase Multiplicative Decrease (AIMD) » en anglais.

4. « TCP window-size process » en anglais.
Le processus $X$ n'explose pas car $N$ n'explose pas. L'espérance condition-
nelle $E(f(X_t) | X_0 = x)$ a un sens car sur $\{X_0 = x\}$, on a $X_t \le x + t$, et
comme $f$ est $C^1$, la v.a.r. $f(X_t)$ est bornée.

Démonstration. Soit $f \in C^1(\mathbb{R}_+, \mathbb{R})$ et $t \le 1$. Par définition de $X$ et $N$,

$$
\begin{align*}
\mathrm{E}(f(X_t)1_{\{N_t=0\}} | X_0 = x) &= f(x+t)\mathrm{P}(N_t = 0) = f(x+t)e^{-\lambda t} \\
&= (f(x) + f'(x)t + o(t))(1 - \lambda t + o(t)) \\
&= f(x) + t(f'(x) - \lambda f(x)) + o(t).
\end{align*}
$$

Conditionnellement à $\{N_t = 1\}$, $T_1$ suit la loi uniforme sur $[0, t]$, donc

$$
\begin{align*}
\mathrm{E}(f(X_t) | X_0 = x, N_t = 1) &= \mathrm{E}(f(Q_1(x + T_1) + t - T_1) | N_t = 1) \\
&= \int_0^t \frac{ds}{t} \int_0^1 \mathcal{Q}(dq) f(q(x + s) + t - s) \\
&= \int_0^1 \mathcal{Q}(dq) f(qx) + o(1)
\end{align*}
$$

où le $o(1)$ (quand $t \to 0$) provient de la continuité de $f$, et donc

$$
\begin{align*}
\mathrm{E}(f(X_t)1_{\{N_t=1\}}|X_0=x) &= \mathbb{P}(N_t=1)\left(\int_0^1 \mathcal{Q}(dq)f(xq) + o(1)\right) \\
&= \lambda t \int_0^1 \mathcal{Q}(dq)f(xq) + o(t).
\end{align*}
$$

Troisièmement, sur $\{X_0 = x\}$ on a $X_t \le x + t$ et donc comme $t \le 1$, on a

$$
|\mathrm{E}(f(X_t)1_{\{N_t \ge 2\}} | X_0 = x)| \le \left( \sup_{u \in [0, x+1]} |f(u)| \right) \mathrm{P}(N_t \ge 2) = \mathcal{O}(t^2).
$$

Finalement, la collecte des trois termes donne bien le résultat voulu. □

Pour tout $t \ge 0$ on considère l'opérateur linéaire $P_t$ qui à toute fonction
$f : \mathbb{R}_+ \to \mathbb{R}$ mesurable et bornée associe la fonction mesurable et bornée

$$
x \in \mathbb{R}_{+} \mapsto P_{t}f(x) = \mathrm{E}(f(X_{t}) | X_{0} = x).
$$

Cette quantité fait encore sens pour $f$ mesurable et localement bornée (par exemple continue) car conditionnellement à $X_0 = x$, $X_t$ prend ses valeurs dans l'intervalle borné $[0, x + t]$. On a $P_0 = I$ et la propriété de Markov entraîne que $(P_t)_{t \ge 0}$ est un semi-groupe :

$P_{t+s} = P_{s+t} = P_t \circ P_s.$

On dit que ce semi-groupe est markovien car il préserve la positivité et l'unité :
$P_t(f) \ge 0$ si $f \ge 0$ et $P_t(1) = 1$. On dit qu'une fonction mesurable et bornée
$f : \mathbb{R}_+ \to \mathbb{R}$ appartient au domaine du générateur $L$ du processus lorsque la limite suivante existe pour tout $x \ge 0$ :

$$L(f)(x) = \lim_{t \to 0^+} \frac{P_t(f)(x) - f(x)}{t} = \partial_{t=0} P_t(f)(x).$$

Tout se passe comme si « $P_t = e^{tL}$ ». On peut établir que la propriété de semi-groupe donne, pour tout $t \ge 0$ et toute fonction $f$ de classe $C^1$,

$$\partial_t P_t(f) = \lim_{\epsilon \to 0} P_t\left(\frac{P_\epsilon f - f}{\epsilon}\right) = P_t(Lf)$$

$$\partial_t P_t(f) = \lim_{\epsilon \to 0} \frac{P_\epsilon(P_t f) - P_t f}{\epsilon} = L(P_t f).$$

On dit qu'il s'agit des équations de Chapman-Kolmogorov progressive et rétrograde respectivement (« forward » et « backward » en anglais).

Le théorème 17.1 affirme que le domaine du générateur $L$ contient les fonctions de classe $C^1$. Il se trouve de plus que le générateur conserve les polynômes sans augmenter leur degré. Cela permet de calculer les moments de manière récursive.

**Théorème 17.2** (Moments et loi invariante). *Pour tout $n \in \mathbb{N}$, tout $x \ge 0$ et tout $t \ge 0$, le moment d'ordre $n$ de la loi de $X_t$ sachant $\{X_0 = x\}$ vérifie*

$$\mathrm{E}(X_t^n | X_0 = x) = \frac{n!}{\prod_{k=1}^n \theta_k} + n! \sum_{m=1}^n \left( \sum_{k=0}^m \frac{x^k}{k!} \prod_{\substack{j=k \\ j \neq m}}^n \frac{1}{\theta_j - \theta_m} \right) e^{-\theta_m t}$$

où $\theta_p := \lambda(1 - \mathrm{E}(Q_1^p))$. De plus, conditionnellement à $\{X_0 = x\}$, la variable $X_t$ converge en loi quand $t \to \infty$ vers la loi $\mu$ sur $\mathbb{R}_+$ dont les moments sont

$$\int x^n \mu(dx) = \frac{n!}{\prod_{k=1}^n \theta_k}$$

pour tout $n \ge 0$. Enfin, tous les moments de $X_t$ convergent vers ceux de $\mu$.

**Démonstration.** Posons $\alpha_n(t) = \mathrm{E}(X_t^n | X_0 = x) = P_t(f_n)(x)$ où $f_n(x) = x^n$. Pour tout $n \ge 1$, le théorème 17.1 donne

$$L f_n(x) = n x^{n-1} + \lambda x^n \int_0^1 (q^n - 1) Q(dq) = n f_{n-1}(x) - \theta_n f_n(x)$$

et donc, en utilisant l'équation de Chapman-Kolmogorov progressive,

$$\begin{aligned} \alpha'_n(t) &= \partial_t P_t(f_n)(x) = P_t(Lf_n)(x) = P_t(nf_{n-1} - \theta_n f_n)(x) \\ &= n\alpha_{n-1}(t) - \theta_n \alpha_n(t). \end{aligned}$$

Comme $\alpha_0$ est constante égale à 1, on obtient l'équation différentielle ordinaire $\alpha'_1(t) = 1 - \theta_1 \alpha_1(t)$ qui donne $\alpha_1$. Une récurrence sur $n$ (système triangulaire !) fournit la formule annoncée pour $(\alpha_n)_{n \ge 0}$.
Comme $\theta_p \le \theta_1$ pour $p \ge 1$, les moments de $\mu$ sont majorés par ceux d'une loi exponentielle de paramètre $\theta_1$. Ceci entraine que sa transformée de Laplace est finie sur $]-\infty, \theta_1[$. Elle est donc holomorphe sur un voisinage (dans $\mathcal{C}$) de l'origine. En particulier, la fonction caractéristique de $\mu$ est analytique sur un voisinage (dans $\mathbb{R}$) de l'origine. Le théorème 21.7 assure alors que la loi $\mu$ est caractérisée par ses moments.

Ainsi, conditionnellement à $\{X_0 = x\}$, chaque moment de $X_t$ converge quand $t \to \infty$ vers une limite finie. Le fait que cette suite de limites soit la suite des moments d'une loi et que $X_t$ converge en loi vers cette loi découle d'une étude similaire à celle menée dans la preuve du théorème de Wigner par la méthode des moments dans le chapitre 21. On prendra garde au fait qu'on se trouve ici sur $\mathbb{R}_+$ et non pas sur $\mathbb{R}$ tout entier. $\square$

**Remarque 17.3** (Décomposition spectrale). *Pour tous $n \ge 0$ et $t \ge 0$, les opérateurs $L$ et $P_t$, restreints à l'ensemble $\mathbb{R}_n[X]$ des polynômes de degré inférieur ou égal à $n$, sont des endomorphismes dont les valeurs propres sont respectivement $(-\theta_k)_{0 \le k \le n}$ et $(e^{-t\theta_k})_{0 \le k \le n}$.*

**Remarque 17.4** (Croissance-annihilation⁵). *Si $Q = \delta_0$ alors le moment d'ordre $n$ de la loi invariante $\mu$ de $X$ vaut $n!/\lambda^n$ ce qui assure que $\mu$ est la loi exponentielle de paramètre $\lambda$.*

**Remarque 17.5** (Loi du processus à un instant donné). *Plaçons-nous dans le cas où $Q = \delta_q$ avec $0 < q < 1$ et conditionnellement à $\{X_0 = x\}$ avec $x \ge 0$. Alors pour tout $t > 0$, il existe une loi absolument continue $\mu_t$ portée par l'intervalle $[0, qx + t]$ telle que*

$$ \text{Loi}(X_t) = e^{-\lambda t} \delta_{x+t} + (1 - e^{-\lambda t}) \mu_t $$

et $\text{dist}(x + t, \text{supp}(\mu_t)) = (1 - q)x$. En effet, conditionnellement à $\{N_t = n\}$,

$$ X_t = \begin{cases} x+t & \text{si } n=0, \\ q^n x + \sum_{k=1}^{n+1} q^{n-k+1} (U_k - U_{k-1}) & \text{si } n>0, \end{cases} $$

où $0 = U_0 < U_1 < \dots < U_n < U_{n+1} = t$ est une statistique d'ordre uniforme sur $[0, t]$. Ainsi, $\text{Loi}(X_t | N_t = 0) = \delta_{x+t}$ tandis que $\text{Loi}(X_t | N_t = n)$ est absolument continue si $n > 0$, portée par $[q^n(x+t), q^n x + t]$. D'où le résultat avec $\mu_t = \text{Loi}(X_t | N_t > 0)$. Ceci montre que $X$ est asymptotiquement régularisant car la masse de la partie atomique de $\mu_t$ tend vers 0 quand $t \to \infty$. C'est le mécanisme de sauts, seul source d'aléa, qui en est responsable.

**Remarque 17.6** (Irréductibilité). *Pour tout $x \ge 0$ et conditionnellement à l'événement $\{X_0 = x\}$, le processus $X$ entre dans tout intervalle en un temps fini avec probabilité positive. En d'autres termes, sa trajectoire coupe toute bande horizontale en un temps fini avec probabilité positive. Cela est immédiat si la bande est au-dessus de $x$. Si la bande est en dessous de $x$, il suffit de considérer une trajectoire en dents de scie.*
<figure><img src="image_55.png" /><figcaption>Fig. 17.2. Histogramme d'un échantillon de $X_t$ pour $t = 100$, $\lambda = 1$, $Q = \delta_{1/2}$.</figcaption></figure>

Soit $p \ge 1$ un réel fixé. Si $(E, d)$ est un espace métrique et $\mu$ une loi sur $E$, alors la quantité $\int d(x, y)^p \mu(dy)$ est soit infinie pour tout $x \in E$, soit finie pour tout $x \in E$ et on dit dans ce cas que $\mu$ a un moment d'ordre $p$ fini. La distance de Wasserstein $W_p$ sur l'ensemble des lois sur $E$ possédant un moment d'ordre $p$ fini est définie par

$$W_p(\mu_1, \mu_2) = \inf_{\substack{(X,Y) \\ X_1 \sim \mu_1 \\ X_2 \sim \mu_2}} \mathbb{E}(d(X, Y)^p)^{1/p} = \inf_{\pi \in \Pi(\mu_1, \mu_2)} \left[ \int_{E \times E} d(x, y)^p \pi(dx, dy) \right]^{1/p}$$

où $\Pi(\mu_1, \mu_2)$ est l'ensemble convexe des lois de probabilité sur $E \times E$ qui ont pour lois marginales $\mu_1$ et $\mu_2$. Il contient la loi produit $\mu_1 \otimes \mu_2$. Un élément $\pi$ de cet ensemble constitue un couplage de $\mu_1$ et $\mu_2$. Ici on prend $E = \mathbb{R}$ et $d(x, y) = |x - y|$. On peut montrer qu'une suite $(\mu_n)_n$ converge vers $\mu$ pour $W_p$ si et seulement si elle converge faiblement pour $C_b$ et si tous les moments d'ordre inférieur ou égal à $p$ de $\mu_n$ convergent vers ceux de $\mu$.

**Théorème 17.7** (Comportement en temps long par couplage). Soit $\nu P_t$ la loi au temps $t$ du processus TCP de loi initiale $\nu$ et de paramètres $\lambda$ et $Q$. Alors, pour toutes mesures de probabilités $\nu_1$ et $\nu_2$ sur $\mathbb{R}_+$ possédant un moment d'ordre $p \ge 1$ fini, pour tout $t \ge 0$, en posant $\theta_p := \lambda(1 - \mathbb{E}(Q_1^p))$, on a

$$W_p(\nu_1 P_t, \nu_2 P_t) \le W_p(\nu_1, \nu_2) \exp \left( - \frac{\theta_p t}{p} \right).$$

<footnote n="5">5. « Growth-collapse » en anglais.</footnote>
Démonstration. Considérons un couple (X, Y) où X et Y partent de x et y mais utilisent le même N et le même Q (mêmes temps de sauts et coefficients multiplicateurs). Remarquablement, la quantité $|X_t - Y_t|$ reste constante entre deux sauts et au $k^e$ saut elle est multipliée par $Q_k$. Par conséquent, pour tout $t \ge 0$, on a

$$
\begin{align*}
\mathrm{E}(|X_t - Y_t|^p) &= \sum_{k=0}^{\infty} \mathrm{E}(|X_t - Y_t|^p \mathbf{1}_{\{N_t=k\}}) \\
&= \sum_{k=0}^{\infty} \mathrm{E}(|x-y|^p Q_1^p \dots Q_k^p \mathbf{1}_{\{N_t=k\}}) \\
&= |x-y|^p \sum_{k=0}^{\infty} \mathrm{E}(Q_1^p)^k \mathbf{P}(N_t=k) \\
&= |x-y|^p e^{-\lambda t (1-\mathrm{E}(Q_1^p))}.
\end{align*}
$$

Par conséquent, si X et Y sont deux processus TCP de paramètres λ et Q et
de lois initiales respectives ν₁ et ν₂, alors pour tout couplage π de ν₁ et ν₂,
pour tout t ≥ 0 et tout p ≥ 1,

$$
W_p(\nu_1 P_t, \nu_2 P_t)^p \le e^{-\theta_p t} \int_{\mathbb{R}_+ \times \mathbb{R}_+} |x-y|^p \pi(dx, dy).
$$

Il ne reste plus qu’à prendre l’infimum sur le couplage $\pi$ de $\nu_1$ et $\nu_2$ pour conclure la preuve du théorème. $\square$

La chaîne incluse $\hat{X} := (\hat{X}_n)_{n \ge 0} = (X_{T_n})_{n \ge 0}$ de $X$ est le processus pris
aux instants de saut. Il s'agit d'une chaîne de Markov homogène à temps
discret et à espace d'états continu $\mathbb{R}_+$. Elle vérifie $\hat{X}_0 = X_0$ et constitue un
processus autoregressif linéaire :

$$
\hat{X}_{n+1} = Q_{n+1}(\hat{X}_n + E_{n+1}).
$$

Le noyau de transition $\hat{K}$ de $\hat{X}$ vaut, pour tout $f \in C_b(\mathbb{R}_+, \mathbb{R})$ et $x \ge 0$,

$$
\hat{K}(x, f) = \mathrm{E}(f(\hat{X}_{n+1}) | \hat{X}_n = x) = \lambda \int_{[0,1] \times \mathbb{R}_+} e^{-\lambda y} f(q(x+y)) Q(dq) dy.
$$

**Théorème 17.8 (Convergence en loi de la chaîne incluse).** *Quel que soit* $X_0$
*la chaîne incluse* $(\hat{X}_n)_{n \ge 0}$ *converge en loi vers* $\hat{\mu} = \mathrm{Loi}(\sum_{n=1}^{\infty} Q_1 \cdots Q_n E_n)$.

Démonstration. La formule autoregressive et les hypothèses d'indépendance et de stationnarité, donnent, par récurrence sur $n$,

$$
\hat{X}_n = Q_n \cdots Q_1 X_0 + \sum_{k=1}^{n} Q_n \cdots Q_{n-k+1} E_{n-k+1}
$$
$$ \stackrel{\text{loi}}{=} Q_1 \cdots Q_n X_0 + \sum_{k=1}^{n} Q_1 \cdots Q_k E_k. $$

On a $E(Q_1 \cdots Q_n) = E(Q)^n$. Or $E(Q) < 1 \text{ car } \mathbb{P}(0 \le Q < 1) = 1$ et donc par convergence monotone $E(\sum_n Q_1 \cdots Q_n) = \sum_n E(Q)^n < \infty$, donc $\mathbb{P}(\sum_n Q_n < \infty) = 1$ et donc $\mathbb{P}(Q_1 \cdots Q_n \to 0) = 1$. Par conséquent, $Q_1 \cdots Q_n X_0 \to 0 \text{ p.s. D'autre part, par convergence monotone,}$

$$ \sum_{k=1}^{n} Q_1 \cdots Q_k E_k \xrightarrow{n \to \infty} \sum_{n=1}^{\infty} Q_1 \cdots Q_n E_n \sim \hat{\mu}. $$

Par conséquent, la chaîne incluse converge en loi vers $\hat{\mu}$ quel que soit $X_0$. $\square$

La loi $\hat{\mu}$ a pour moyenne $\lambda^{-1}E(Q_1)/E(1 - Q_1)$. Pour la chaîne incluse, l'oubli de la condition initiale apparaît clairement sur la formule suivante :

$$ E(\hat{X}_n) = E(Q)^n E(X_0) + E(Q_1) \frac{1 - E(Q_1)^n}{\lambda(1 - E(Q_1))}. $$

La loi $\hat{\mu}$ vérifie l'équation en loi

$$ F \stackrel{\text{loi}}{=} Q_1(F + E_1) $$

où $F \sim \hat{\mu}$ est indépendante de $Q_1, E_1$.

## 17.2 Intensité des sauts variable selon la position

Il est possible de faire dépendre l'intensité de sauts du chemin parcouru par le processus. On considère une fonction localement intégrable $\lambda : x \in \mathbb{R}_+ \mapsto \lambda(x) \in \mathbb{R}_+$ et une suite $(E_n)_{n \ge 1}$ de v.a.r. i.i.d. de loi exponentielle de paramètre 1. On construit la trajectoire du processus $(X_t)_{t \ge 0}$ partant de $X_0 = x_0$ en posant $X_s = x_0 + s$ pour tout $0 \le s < T_1$ où le premier temps de saut $T_1$ est défini par l'équation (instant ou l'∫ atteint $E_1$)

$$ \int_{0}^{T_1} \lambda(X_s) \, ds = \int_{0}^{T_1} \lambda(x_0 + s) \, ds = E_1. $$

Ensuite on pose $X_{T_1} = Q_1 X_{T_1^-} = Q_1(x_0 + T_1)$, et plus généralement, on pose

$$ X_t = \begin{cases} X_{T_n} + t - T_n & \text{si } T_n \le t < T_{n+1}, \\ Q_{n+1}(X_{T_n} + T_{n+1} - T_n) & \text{si } t = T_{n+1}, \end{cases} $$

où la suite croissante des temps de saut $(T_n)_{n \ge 0}$ est définie par $T_0 = 0$ et

$$ \int_{T_n}^{T_{n+1}} \lambda(X_s) \, ds = \int_{0}^{T_{n+1}-T_n} \lambda(X_{T_n} + s) \, ds = E_{n+1}. $$
Par exemple, le cas spécial $\lambda(x) = x$ donne

$$T_{n+1} - T_n = \sqrt{2E_{n+1} + (X_{T_n})^2} - X_{T_n}.$$

Cette construction fournit la trajectoire $t \mapsto X_t$ sur l'intervalle $[0, T_\infty[$ où $T_\infty := \lim_{n\to\infty} T_n$ est le temps d'explosion du processus. Si $\lambda$ est une fonction bornée, alors par comparaison au cas constant, on obtient $P(T_\infty = \infty) = 1$ et on dit que le processus n'explose pas. Lorsque $\lambda$ n'est pas bornée, par exemple $\lambda(x) = x$, ce sont les propriétés de $\mathcal{Q}$ qui permettent d'établir la non explosion éventuelle. On peut montrer que le générateur du processus $(X_t)_{t\ge0}$ est

$$L(f)(x) = f'(x) + \lambda(x) \int_0^1 (f(qx) - f(x)) \mathcal{Q}(dq).$$

Le même procédé permet plus généralement de construire les trajectoires d'un processus de générateur infinitésimal

$$L(f)(x) = G(f)(x) + \lambda(x) \int (f(y) - f(x)) K(x, dy)$$

où $K$ est un noyau markovien, où $\lambda$ est une fonction positive localement intégrable, et où $G$ est le générateur d'un processus quelconque, qui «agit» entre les temps de sauts.

## 17.3 Branchement et croissance-fragmentation

Le processus TCP permet de modéliser bien plus de choses que la taille de fenêtre TCP du protocole TCP/IP. On peut penser par exemple à la taille ou masse d'une cellule, qui grossit linéairement puis subit une division. On peut également penser à un polymère⁶ dont la longueur augmente linéairement au cours du temps puis subit une dislocation. Du point de vue de la masse, la division ou la dislocation constituent une fragmentation qui conserve la masse. Supposons pour simplifier que les fragments obtenus sont toujours au nombre de deux et évoluent selon le même processus, de manière indépendante. Intéressons-nous à la taille $N_t$ de la population à l'instant $t \ge 0$. Cela revient à étudier un arbre binaire où la longueur des segments de branches sont i.i.d. de loi exponentielle de paramètre $\lambda$. À l'instant $t \ge 0$, l'arbre possède $N_t$ branches, et $N_0 = 1$. Le processus $(N_t)_{t\ge0}$ est appelé processus de Yule de paramètre $\lambda$. Il s'agit d'un processus de Galton-Watson à temps continu de loi de reproduction $\delta_2$. C'est aussi un processus de vie pur à temps continu.

**Théorème 17.9 (Taille de la population).** Pour tout $t \ge 0$ la taille de la population $N_t$ suit la loi géométrique sur $\mathbb{N}^*$ de paramètre $e^{-\lambda t}$. En particulier,

$$\mathbb{E}(N_t) = e^{\lambda t} \quad \text{et} \quad \text{Var}(N_t) = (1 - e^{-\lambda t})e^{2\lambda t}.$$

6. Molécule constituée d'une chaîne de molécules identiques (monomères).
<figure><img src="image_56.png" /><figcaption>Fig. 17.3. Début de l'arbre binaire définissant le processus N.</figcaption></figure>

Démonstration. La propriété d'absence de mémoire des lois exponentielles permet d'établir que $(N_t)_{t \ge 0}$ est le processus de comptage issu de $N_0 = 1$ de la suite de v.a.r. $(S_n)_{n \ge 1}$ où $S_n = F_1 + \cdots + F_n$ avec $(F_n)_{n \ge 1}$ suite de v.a.r. indépendantes et $F_n$ de loi exponentielle de paramètre $n\lambda$ pour tout $n \ge 1$. On a $N_t - 1 = \sum_{n=1}^{\infty} 1_{[0,t]}(S_n)$. Or d'après le lemme de Rényi 11.3, la v.a.r. $S_n$ a la loi de $\max(E_1, \ldots, E_n)$ où $E_1, \ldots, E_n$ sont i.i.d. de loi exponentielle de paramètre $\lambda$. Donc, pour tout entier $n \ge 0$,

$$ \mathbb{P}(N_t - 1 \ge n) = \mathbb{P}(S_n \le t) = \mathbb{P}(E_1 \le t) \cdots \mathbb{P}(E_n \le t) = (1 - e^{-\lambda t})^n. $$

□

Considérons le cas où chaque fragmentation donne lieu à $k + 1$ fragments où $k \ge 1$ est fixé. On note $(N_t^{(k)})_{t \ge 0}$ le processus de comptage associé. Pour tout $n \ge 2$, le processus issu de $n$ est la somme de $n$ copies i.i.d. du processus issu de 1. C'est la propriété de superposition ou de branchement. On dit que $(N_t^{(k)})_{t \ge 0}$ est un processus de Yule de loi de reproduction $\delta_{k+1}$. Il s'agit d'un processus de Markov homogène à temps continu d'espace d'état $\mathbb{N}$ et de générateur infinitésimal $L^{(k)}$ donné pour tous $f: \mathbb{N} \to \mathbb{R}$ et $n \in \mathbb{N}$ par

$$ L^{(k)}(f)(n) = \lim_{t \to 0^+} \frac{\mathbb{E}(f(N_t^{(k)}) | N_0^{(k)} = n) - f(n)}{t} = n\lambda(f(n+k) - f(n)). $$

À comparer, au passage, avec le générateur $\lambda(f(n+1) - f(n))$ du processus de Poisson. Si $f(n) = n$ et $\alpha_n(t) = \mathbb{E}(N_t^{(k)} | N_0^{(k)} = n) = P_t^{(k)}(f)(n)$ alors $(L^{(k)}f)(n) = k\lambda n = k\lambda f(n)$ et l'équation de Chapman-Kolmogorov progressive (forward) donne l'équation différentielle ordinaire

$$ \partial_t \alpha_n(t) = \partial_t P_t^{(k)}(f) = P_t(L^{(k)}f) = k\lambda P_t^{(k)}(f) = k\lambda \alpha_n(t). $$

La condition initiale $\alpha_n(0) = n$ donne alors $\mathbb{E}(N_t^{(k)} | N_0^{(k)} = n) = ne^{k\lambda t}$. L'exploitation systématique de cette méthode conduit au résultat suivant.
**Théorème 17.10** (Processus de Yule). Supposons que $N_0^{(k)} \sim \delta_1$. Pour tout réel $t \ge 0$ et tout entier $k \ge 1$, si $Z_1, \dots, Z_k$ sont copies i.i.d. de $N_t^{(k)}$ alors

$$ \frac{Z_1 + \dots + Z_k}{k} \sim \text{Geo}(e^{-k\lambda t}). $$

En particulier, la moyenne et la variance de $N_t^{(k)}$ sont données par

$$ \mathbb{E}(N_t^{(k)}) = e^{k\lambda t} \quad \text{et} \quad \text{Var}(N_t^{(k)}) = k(1 - e^{-k\lambda t})e^{2k\lambda t}. $$

De plus, il existe une v.a. $M_\infty \in L^2$ de loi Gamma$(1/k, 1/k)$ de densité

$$ x \mapsto \frac{(1/k)^{1/k}}{\Gamma(1/k)} x^{1/k-1} e^{-x/k} \mathbb{1}_{\mathbb{R}_+}(x) $$

telle que

$$ e^{-k\lambda t} N_t^{(k)} \underset{t \to \infty}{\longrightarrow} M_\infty \quad \text{p.s. et dans } L^2. $$

**Démonstration.** On se ramène à $\lambda = 1$ par changement de temps. Fixons à présent $s \in [0, 1]$ et considérons la fonction $f(n) = s^n$. On a $P_t^{(k)}(f)(n) = \mathbb{E}(s^{N_t^{(k)}} | N_0^{(k)} = n)$. On s'intéresse à la fonction génératrice

$$ g_t(s) := \mathbb{E}(s^{N_t^{(k)}} | N_0^{(k)} = 1) = P_t^{(k)}(f)(1). $$

Par la propriété de branchement, $P_t^{(k)}(f)(n) = (P_t^{(k)}(f)(1))^n = g_t(s)^n$, d'où

$$ L^{(k)}(P_t^{(k)}(f))(n) = n(P_t^{(k)}(f)(n+k) - P_t^{(k)}(f)(n)) = n(g_t(s)^{n+k} - g_t(s)^n). $$

L'équation de Chapman-Kolmogorov rétrograde donne à présent l'É.D.O.

$$ \partial_t g_t(s) = \partial_t P_t^{(k)}(f)(1) = L^{(k)}(P_t^{(k)}(f))(1) = g_t(s)^{k+1} - g_t(s). $$

La condition initiale $g_0(s) = s$ donne enfin

$$ g_t(s) = s e^{-t} (1 - (1 - e^{-kt}) s^k)^{-1/k}. $$

En particulier, $g_t^k$ est la fonction génératrice de $kG$ où $G$ est une v.a.r. de loi géométrique sur $\mathbb{N}^*$ de paramètre $e^{-kt}$. Pour la convergence en loi, pour $\theta < 0$, la transformée de Laplace

$$ \begin{aligned} \mathbb{E} \left( \exp \left( \theta e^{-kt} N_t^{(k)} \right) \right) &= \exp \left( \theta e^{-kt} \right) e^{-t} \left( 1 - (1 - e^{-kt}) \exp \left( \theta k e^{-kt} \right) \right)^{-1/k} \\ &= \left( e^{kt} \exp \left( -\theta k e^{-kt} \right) - e^{kt} + 1 \right)^{-1/k} \end{aligned} $$

qui converge quand $t \to \infty$ vers

$$ (1 - k\theta)^{-1/k} = \left( \frac{1/k}{1/k - \theta} \right)^{1/k}, $$

qui est la transformée de Laplace au point $\theta$ de la loi Gamma$(1/k, 1/k)$. Enfin $(e^{-k\lambda t} N_t^{(k)})_{t \ge 0}$ est une martingale bornée dans $L^2$, et converge donc p.s. et dans $L^2$, lorsque $t \to \infty$, vers une v.a. de loi Gamma$(1/k, 1/k)$. $\square$
La fragmentation serait bien sûr modélisable plus généralement en utilisant une loi sur les partitions de $[0, 1]$ avec un nombre possiblement infini de morceaux. Cela mène à la théorie probabiliste de la fragmentation.

Supposons que le mécanisme de fragmentation en $k+1$ fragments consiste en une division équitable de la masse. À l'instant $t \ge 0$, la population de fragments est constituée de $N_t^{(k)}$ individus, positionnés sur un arbre $k+1$ régulier (chaque individu fait $k+1$ enfants puis meurt). Pour numéroter les individus, on procède comme dans le chapitre 22, et on introduit les étiquettes $\mathcal{U} = \cup_{r=0}^{\infty} (\mathbb{N}^*)^r$ avec la convention $(\mathbb{N}^*)^0 = \emptyset$, et où $(\mathbb{N}^*)^r$ sert à numéroter les individus de la génération $r$. Les individus vivant à un instant $t$ donné peuvent appartenir à différentes générations. La population à l'instant $t$ est un sous-ensemble aléatoire $G_t$ de $\mathcal{U}$, et vérifie $N_t^{(k)} = |G_t|$. Si $X_{u,t}$ représente la taille de l'individu $u \in G_t$ vivant à l'instant $t$ alors la répartition des masses à l'instant $t$ dans la population est capturée par la mesure empirique

$$ \mu_t = \frac{1}{N_t^{(k)}} \sum_{u \in G_t} \delta_{X_{u,t}} $$

Cette loi aléatoire donne la masse d'un individu choisi uniformément parmi ceux vivant à l'instant $t$. Pour une fonction test $f: \mathbb{R}_+ \to \mathbb{R}$, on a

$$ \mathbb{E}\left(\int f d\mu_t\right) = \mathbb{E}\left(\frac{1}{N_t^{(k)}} \sum_{u \in G_t} f(X_{u,t})\right) = \mathbb{E}(f(X_{U_t,t})) $$

où $U_t$ est de loi uniforme sur $G_t$. Intuitivement, l'évolution de la masse le long d'une branche quelconque de l'arbre suit le processus TCP. En réalité, il faut préciser ce que l'on entend par « branche quelconque » car un phénomène de biais par la taille peut apparaître$^7$.

## 17.4 Pour aller plus loin

Le véritable modèle de taille de fenêtre TCP est plus complexe et incorporated notamment une taille maximale de fenêtre. Il est étudié par Teunis Ott et Johannes Kamperman dans [OK08], et par Vincent Dumas, Fabrice Guillemin, et Philippe Robert dans [DGR02]. Un lien avec les fonctionnelles exponentielles des processus de Lévy est mené par Fabrice Guillemin, Philippe Robert, et Bert Zwart dans [GRZ04]. Le processus est enfin abordé dans les écrits pédagogiques de Philippe Robert [Rob05, Rob10]. Le comportement en temps long est étudié dans l'article [CMP10]. Des aspects graphiques sont explorés dans l'article [GR10] de Carl Graham et Philippe Robert. La version branchante est étudiée par Vincent Bansaye, Jean-François Delmas, Laurence

<footnote n="7">7. Il s'agit d'un biais d'échantillonnage classique en statistique : un individu tiré au hasard a plus de chance d'être issu d'une famille nombreuse.</footnote>
Marsalle, et Viet Chi Tran dans [BDMT11] ainsi que par Bertrand Cloez dans [Clo13]. Le processus de Yule doit son nom à Udny Yule et est étudié dans les livres [Har02, AN04]. Un lien avec des équations d'évolution de transport-fragmentation se trouve dans le livre de Benoît Perthame [Per07] et dans le travail de Bertrand Cloez [Clo13]. Une théorie de la fragmentation se trouve dans le livre de Jean Bertoin [Ber06].

Les distances de Wasserstein sont également connues sous le nom de dis-
tances de couplage, de transport, de Kantorovich, de Mallows, ou de Fréchet.
Ces multiples noms témoignent de leur utilité dans des domaines variés. Ces
distances sont au cœur de la théorie du transport optimal de la mesure, dé-
veloppée notamment par Cédric Villani [Vil03]. Si $E = \mathbb{R}$ et $d(x,y) = |x - y|$
alors, en notant $F_{\mu}^{-1}$ l'inverse généralisé de la fonction de répartition de $\mu$, on
montre que $W_p$ est une distance $L^p$ inter-quantiles en ce sens que

$$
W_p(\mu_1, \mu_2) = \left( \int_0^1 |F_{\mu_1}^{-1}(x) - F_{\mu_2}^{-1}(x)|^p dx \right)^{1/p} = \|F_{\mu_1} - F_{\mu_2}\|_p.
$$
<figure><img src="image_57.png" /></figure>
# Ruine d'une compagnie d'assurance

**Mots-clés.** Actuariat; temps de ruine; temps d'atteinte; processus de Markov à temps continu.

**Outils.** Processus de Poisson composé; transformée de Laplace; fonction caractéristique; martingale; marche aléatoire; loi des grands nombres; loi du logarithme itéré.

## Difficulté. *

Ce chapitre est consacré essentiellement à un modèle simple et classique de risque en assurance, connu sous le nom de modèle de Cramér-Lundberg. Une nouvelle compagnie d'assurance veut entrer sur le marché. Elle souhaite évaluer sa probabilité de faillite en fonction du capital initial investi et du prix de ses polices d'assurance. On suppose que la compagnie a un capital initial $c$ et on note $R_t$ sa réserve à l'instant $t$. La compagnie d'assurance

- perçoit des cotisations de ses clients que l'on supposera mensualisées, uniformément réparties sur l'année et constantes au cours du temps : les recettes de la compagnie pendant un temps $t$ sont donc égales à $pt$ où $p$ est le taux de cotisations par unité de temps;

- verse des primes à ses assurés sinistrés en fonction des dommages subis.

On modélise l'apparition et les coûts des sinistres de la manière suivante :

- les coûts des sinistres $(X_k)_{k \ge 1}$ sont des v.a.r. aléatoires indépendantes, de même loi $\nu$, d'espérance commune $\lambda$ et de variance finie $a - \lambda^2$;

- les temps d'apparition $(T_n)_{n \ge 1}$ des sinistres sont distribués selon un processus de Poisson $(N_t)_{t \ge 0}$ d'intensité $\mu$. Les intervalles de temps entre deux sinistres, notés $(\Delta_n)_{n \ge 1}$ avec $\Delta_n = T_n - T_{n-1}$, sont des v.a.r. i.i.d. de loi exponentielle $\text{Exp}(\mu)$.

- la suite $(X_k)_{k \ge 1}$ et le processus $(N_t)_{t \ge 0}$ sont indépendants.

La réserve de la compagnie d'assurance à l'instant $t$ est par conséquent :

$$R_t = c + pt - \sum_{k=1}^{N_t} X_k.$$
<figure><img src="image_58.png" /><figcaption>Fig. 18.1. Une trajectoire menant à la ruine au temps $\tau(c)$ avec un découvert $Y(c)$.</figcaption></figure>

Pour simplifier légèrement les calculs, on considérera plutôt la quantité

$$ \tilde{R}_t = c - R_t = \sum_{k=1}^{N_t} X_k - pt. $$

La ruine survient lorsque la réserve $R$ descend sous 0 ou que $\tilde{R}$ excède $c$. L'instant de ruine, ou de défaut, de la compagnie est défini par

$$ \tau(c) = \inf\{t \ge 0 : R_t < 0\} = \inf\{t \ge 0 : \tilde{R}_t > c\}. $$

La probabilité de ruine de la compagnie est donnée par

$$ \psi(c) = \mathbb{P}\left(\sup_{t \ge 0} \tilde{R}_t > c\right) = \mathbb{P}(\tau(c) < \infty). $$

On notera enfin $Y(c)$ le découvert en cas de ruine (voir figure 18.1) :

$$ Y(c) = -R_{\tau(c)} = \tilde{R}_{\tau(c)} - c. $$

**Remarque 18.1** (Processus de Markov et générateur infinitésimal). On peut montrer que $\tilde{R}$ est un processus de Markov sur $\mathbb{R}$ de générateur infinitésimal

$$ Lf(x) = -pf'(x) + \mu \int_{0}^{\infty} (f(x+y) - f(x)) \nu(dy). $$

Ce processus évolue de manière déterministe entre ses temps de saut. On parle de processus de Markov déterministe par morceaux.
## 18.1 Processus de Poisson composé

Rappelons qu'il est facile d'estimer l'intensité d'un processus de Poisson à partir d'une de ses trajectoires comme le montre le résultat suivant.

**Lemme 18.2 (Temps long).** La loi des grands nombres et le théorème limite central suivants ont lieu :

$$ \frac{N_t}{t} \xrightarrow{p.s.} \mu \quad \text{et} \quad \sqrt{t} \left( \frac{N_t}{t} - \mu \right) \xrightarrow{\text{loi}} \mathcal{N}(0, \mu), $$

*Démonstration.* Pour tout $i \in \mathbb{N}^*$, posons $Y_i = N_i - N_{i-1}$. La variable $Y_i$ re présente le nombre de sauts du processus de Poisson dans l'intervalle de temps $[i-1, i]$. Le processus de Poisson est à accroissements stationnaires et indé pendants. En particulier, les variables aléatoires $(Y_i)_{i \ge 1}$ sont indépendantes de même loi de Poisson de paramètre $\mu$. Donc, en vertu de la loi des grands nombres, $N_{[t]}/[t] \to \mu$ p.s. On remarque ensuite l'encadrement suivant

$$ \frac{N_{[t]}}{[t]} \frac{[t]}{t} \le \frac{N_t}{t} \le \frac{N_{[t]+1}}{[t]+1} \frac{[t]+1}{t} $$

qui entraîne que $N_t/t \xrightarrow{p.s.} \mu$. La convergence en loi se déduit du calcul expli-cite de la fonction caractéristique de $\sqrt{t}(N_t/t - \mu)$ puisque $N_t \sim \text{Poi}(\mu t)$. $\square$

Le processus $C = (C_t)_{t \ge 0}$ défini par

$$ C_t = \sum_{k=1}^{N_t} X_k, $$

est appelé processus de Poisson composé de paramètre $\mu$ et de loi de saut $\nu$.

**Lemme 18.3 (Fonction caractéristique).** Pour tous $t \ge 0$ et $u \in \mathbb{R}$,

$$ \varphi_{C_t}(u) := \mathbb{E}(e^{iuC_t}) = \exp(\mu t(\varphi_{\nu}(u) - 1)), $$

où $\varphi_{\nu}$ est la fonction caractéristique de $\nu$. Si les deux premiers moments $\lambda$ et $a$ de $\nu$ existent, alors les deux premiers moments de $C_t$ existent et vérifient

$$ \mathbb{E}(C_t) = \mu\lambda t \quad \text{et} \quad \text{Var}(C_t) = \mu at, $$

et de plus

$$ \frac{C_t}{t} \xrightarrow{p.s.} \mu\lambda \quad \text{et} \quad \sqrt{t} \left( \frac{C_t}{t} - \mu\lambda \right) \xrightarrow{\text{loi}} \mathcal{N}(0, \mu a). $$

Les moments de $C_t$ peuvent aussi être calculés grâce au lemme de Wald.

*Démonstration.* L'expression des moments de $C_t$ et le résultat de convergence en loi découlent de l'expression de la fonction caractéristique de $C_t$. La conver-gence p.s. s'obtient en utilisant le lemme 18.2 et la loi des grands nombres. $\square$
## 18.2 La ruine est-elle presque sûre ?

Comme les trajectoires de $\tilde{R}$ sont décroissantes entre les sauts, le franchis- sement du niveau $c$ ne peut intervenir qu'à un instant de saut. Définissons la suite $(S_n)_{n\ge 0}$ par $S_n = \tilde{R}_{T_n}$. On dit que $(S_n)_{n\in\mathbb{N}}$ est la chaîne incluse de $(\tilde{R}_t)_{t\in\mathbb{R}_+}$. Par construction, puisque $\Delta_k = T_k - T_{k-1}$ pour $k \ge 1$,

$$S_0 = 0 \text{ et } \forall n \ge 1, \quad S_n = \sum_{k=1}^{n} (X_k - p\Delta_k).$$

En particulier, $S_n$ s'écrit comme la somme de $n$ variables aléatoires i.i.d. de moyenne $\lambda - p/\mu$. La quantité $\lambda\mu$ représente le montant moyen des sinistres par unité de temps et sa position par rapport à $p$ dicte, comme le montre le résultat suivant, la valeur de la probabilité de ruine qui s'écrit encore

$$\psi(c) = \mathbb{P}\left(\sup_{n\ge 0} S_n > c\right).$$

Notons $\tilde{\tau}(c) = \inf\{n \in \mathbb{N} : S_n > c\}$. Par construction, on a

$$\tilde{\tau}(c) = n \Leftrightarrow \tau(c) = T_n \text{ et } \tilde{\tau}(c) < +\infty \Leftrightarrow \tau(c) < +\infty.$$

**Théorème 18.4 (Caractérisation de la ruine presque sûre).**

$$p \le \lambda\mu \iff \forall c \ge 0, \psi(c) = 1.$$

*Démonstration.* Si $p < \lambda\mu$, le résultat découle de la loi des grands nombres appliquée à la suite $(X_k - p\Delta_k)_{k\ge 1}$. Si $p = \lambda\mu$, la loi du logarithme itéré de Strassen appliquée aux variables aléatoires i.i.d. $(X_k - p\Delta_k)_{1\le k\le n}$ centrées et de variance $\sigma^2 = a - \lambda^2 + p^2/\mu^2$ donne

$$\liminf_{n \to \infty} \frac{S_n}{\sigma \sqrt{2n \log(\log(n))}} = -1 \quad \text{p.s.}$$

et

$$\limsup_{n \to \infty} \frac{S_n}{\sigma \sqrt{2n \log(\log(n))}} = +1 \quad \text{p.s.}$$

Enfin, si $p > \lambda\mu$, la loi des grands nombres assure ici que $S_n \to -\infty$ p.s. Sup- posons que le temps d'arrêt $\tau_1 = \inf\{n > 0 : S_n > c\}$ soit fini p.s. La marche aléatoire $(S_{n+\tau_1} - S_{\tau_1})_{n\ge 0}$ est de même loi que $(S_n)_{n\ge 0}$. Par conséquent, le temps d'arrêt $\tau_2 = \inf\{n > 0 : S_{n+\tau_1} - S_{\tau_1} > c\}$ est lui aussi fini p.s. En itérant le procédé, on montre que $\limsup S_n = \infty$, d'où la contradiction. $\square$

**Remarque 18.5 (Condition de profit net).** Comme le suggère l'intuition, la compagnie doit s'assurer que $p > \lambda\mu$ pour éviter une ruine p.s. Les lemmes 18.2 et 18.3 permettent, à partir d'un historique des sinistres, d'esti- mer les paramètres $\lambda$ et $\mu$, ce qui peut ensuite aider à choisir $p$.
## 18.3 Expression de la probabilité de ruine

On suppose dans la suite que la condition, dite de profit net, $p > \lambda\mu$ est
satisfaite et on cherche à exprimer la probabilité de ruine $\psi(c)$. On introduit
la transformée de Laplace $H$ de la loi des sinistres $\nu$ :

$$ \forall x \in \mathbb{R}, \quad H(x) = \mathbb{E}(e^{xX_1}) \in [0, +\infty]. $$

La fonction $H$ est finie sur un intervalle $I$ qui contient $]-\infty, 0]$ car $X_1$ est une variable aléatoire positive. De plus, $H$ est de classe $C^\infty$ et strictement convexe sur l'intérieur de $I$.

**Lemme 18.6 (Transformé de Laplace des sinistres).** *Supposons que l'intervalle $I$ sur lequel la transformée de Laplace $H$ est finie soit un ouvert qui contient $0$. Alors la fonction*

$$ x \mapsto H(x) - \frac{px}{\mu} - 1 $$

s'annule en 0 et en un unique réel $u > 0$.

Le réel $u$ est appelé coefficient d'ajustement.

*Démonstration.* La fonction $x \mapsto H(x) - px/\mu - 1$ est strictement convexe sur $I$, nulle en 0 avec une dérivée strictement négative car $H'(0) = \mathbb{E}(X_1) = \lambda < p/\mu$. D'autre part, puisque $I$ est ouvert, la fonction $H$ tend vers $+\infty$ au bord droit de $I$, et, pour tout $x_0 > 0$ tel que $\mathbb{P}(X_1 \ge x_0) > 0$, et tout $x \in I$,

$$ H(x) \ge e^{x x_0} \mathbb{P}(X_1 \ge x_0). $$

Ainsi, la fonction $x \mapsto H(x) - px/\mu - 1$ tend vers $+\infty$ au bord droit de $I$. $\square$

**Théorème 18.7 (Probabilité de ruine).** *Sous les hypothèses du lemme 18.6, la probabilité de ruine est donnée par*

$$ \psi(c) = \frac{e^{-uc}}{\mathbb{E}(e^{uY(c)} | \tau(c) < +\infty)} $$

où $Y(c) = S_{\bar{\tau}(c)} - c$ est le découvert de la compagnie à l'instant de ruine.

*Démonstration.* La suite $(e^{uS_n})_{n \ge 0}$ est une martingale positive car

$$ \mathbb{E}(e^{uS_{n+1}} | \sigma(S_0, \dots, S_n)) = e^{uS_n} \mathbb{E}(e^{u(X_{n+1}-p\Delta_{n+1})}). $$

Comme $X_{n+1}$ et $\Delta_{n+1}$ sont indépendantes et comme $\Delta_{n+1}$ suit la loi Exp($\mu$),

$$ \mathbb{E}(e^{u(X_{n+1} - p\Delta_{n+1})}) = H(u) \frac{\mu}{\mu + pu} = 1. $$
Ainsi $E[e^{uS_n}] = 1$ pour tout $n \ge 0$. Si $n > 0$ alors $\tilde{\tau}(c) \wedge n$ est un temps d'arrêt borné et

$$1 = E(e^{uS_{\tilde{\tau}(c)} \wedge n}) = E(e^{uS_{\tilde{\tau}(c)}} 1_{\{\tilde{\tau}(c) \le n\}}) + E(e^{uS_n} 1_{\{\tilde{\tau}(c) > n\}}).$$

Sous l'hypothèse $p > \lambda\mu$, $S_n \xrightarrow{n \to \infty} -\infty$. De plus, sur $\{\tilde{\tau}(c) > n\}$, on a $S_n \le c$. Ainsi, par convergence dominée, la seconde espérance ci-dessus converge vers 0 lorsque $n \to +\infty$. La première espérance converge par convergence monotone. Par conséquent, on obtient

$$1 = E(e^{uS_{\tilde{\tau}(c)}} 1_{\{\tilde{\tau}(c) < +\infty\}}) = e^{uc} E(e^{uY(c)} | \tilde{\tau}(c) < +\infty) P(\tilde{\tau}(c) < +\infty),$$

ce qui fournit le résultat annoncé.

□

**Remarque 18.8** (Borne de Lundberg). Du théorème précédent, $\psi(c) \le e^{-uc}$.

La transformée de Laplace de la mesure de densité

$$x \mapsto \frac{e^{-x}}{1 + x^2} 1_{[0, \infty[}(x)$$

est finie au point $x$ si et seulement si $x \le 1$. Si $H(1) < 1 + p/\mu$, la fonction $x \mapsto H(x) - px/\mu - 1$ ne s'annule qu'en $0$: cette fonction, infinie sur $]1, +\infty[$, est strictement négative sur $]0, 1]$. Dans ce cas, le théorème 18.7 ne s'applique pas. Cependant, la suite $(e^{S_n})_{n \ge 0}$ est une sur-martingale :

$$E(e^{S_{n+1}} | \sigma(S_0, \dots, S_n)) = e^{S_n} \frac{H(1)}{1 + p/\mu} < e^{S_n}.$$

On en déduit, en procédant comme dans la preuve du théorème 18.7 que

$$\psi(c) \le \frac{e^{-c}}{E(e^{Y(c)} | \tilde{\tau}(c) < +\infty)}.$$

## 18.4 Sinistres exponentiels

La probabilité de ruine est explicite pour des coûts de sinistres exponentiellement distribués.

**Théorème 18.9** (Probabilité de ruine). Si la distribution des coûts des sinistres est la loi exponentielle de paramètre $1/\lambda$, ou de moyenne $\lambda$ avec $p > \lambda\mu$, alors, pour tout $c \ge 0$, on a

$$\psi(c) = \frac{\lambda\mu}{p} \exp\left(-\frac{p - \lambda\mu}{p\lambda}c\right).$$
Démonstration. Pour $x < 1/\lambda$, on a

$$H(x) = \frac{1}{1 - \lambda x} \quad \text{et} \quad u = \frac{p - \mu\lambda}{p\lambda} < \frac{1}{\lambda}.$$

Il suffit de montrer que, sachant que $\tilde{\tau}(c) < +\infty$, la variable $Y(c) = S_{\tilde{\tau}(c)} - c$ suit la loi exponentielle d'espérance $\lambda$. Si $\tilde{\tau}(c) = n$ alors

$$Y(c) = S_n - c = X_n - p\Delta_n + S_{n-1} - c,$$

d'où

$$ 
\begin{align*}
\mathbb{P}(Y(c) > y, \tilde{\tau}(c) = n) \\
&= \mathbb{P} \left( Y(c) > y, \max_{1 \le i \le n-1} S_i \le c, S_n > c \right) \\
&= \mathbb{P} \left( X_n > y + p\Delta_n + c - S_{n-1}, \max_{1 \le i \le n-1} S_i \le c \right) \\
&= \mathbb{P} \left( X_n > y, X_n > y + p\Delta_n + c - S_{n-1}, \max_{1 \le i \le n-1} S_i \le c \right).
\end{align*}
$$

La dernière égalité provient du fait que $X_n = Y(c) + c - S_{n-1} > y$ lorsque $Y(c) > y$ et $\max_{1 \le i \le n-1} S_i \le c$. À présent, puisque la variable aléatoire $X_n$ suit la loi Exp$(1/\lambda)$ et est indépendante de $(\Delta_n, S_1, \dots, S_{n-1})$, on a

$$ 
\begin{align*}
\mathbb{P}(Y(c) > y, \tilde{\tau}(c) = n) \\
&= \int_y^\infty \mathbb{P} \left( x > y + p\Delta_n + c - S_{n-1}, \max_{1 \le i \le n-1} S_i \le c \right) \lambda e^{-\lambda x} dx \\
&= e^{-\lambda y} \int_0^\infty \mathbb{P} \left( x > y + p\Delta_n + c - S_{n-1}, \max_{1 \le i \le n-1} S_i \le c \right) \lambda e^{-\lambda x} dx \\
&= e^{-y/\lambda} \mathbb{P} \left( S_n > c, \max_{1 \le i \le n-1} S_i \le c \right) = e^{-y/\lambda} \mathbb{P}(\tilde{\tau}(c) = n) .
\end{align*}
$$

Ainsi, $\mathbb{P}(Y(c) > y | \tilde{\tau}(c) < +\infty) = e^{-y/\lambda}$ pour tout $y > 0$. Ceci assure que

$$E(e^{uY(c)} | \tilde{\tau}(c) < +\infty) = H(u).$$

On conclut en appliquant le théorème 18.7. $\square$

Considérons deux compagnies qui assurent le même type de risques et pratiquent les mêmes politiques de tarif et d'indemnisation. Supposons que la clientèle de la seconde diffère d'un facteur multiplicatif $\rho$ de la première. Si $(\lambda, \mu, p)$ désigne les paramètres de la première compagnie, ceux de la seconde sont donnés par $(\lambda, \rho\mu, \rho p)$. On suppose que les sinistres sont toujours exponentiellement distribués. Par homogénéité, la probabilité de ruine de la compagnie $i = 1, 2$ est donnée par le théorème 18.9 :
$$ \psi(c_i) = \frac{\lambda\mu}{p} \exp\left(-\frac{p - \lambda\mu}{p\lambda} c_i\right). $$

Supposons à présent qu'elles s'unissent pour ne former qu'une seule compagnie. On supposera à nouveau que les sinistres assurés par chacune des compagnies sont indépendants. Les paramètres de la nouvelle entité sont $(\lambda, (1 + \rho)\mu, (1 + \rho)p)$ et le capital initial vaut $c_1 + c_2$. Une fois de plus, la probabilité de ruine est donc donnée par $\psi(c_1 + c_2)$ qui est inférieure aux probabilités de ruine de chacune des deux compagnies. Les assureurs ont donc intérêt à se regrouper pour mutualiser les risques.

## 18.5 Pour aller plus loin

La définition et les propriétés essentielles des processus de Poisson se trouve par exemple dans le livre de Dominique Foata et Aimé Fuchs [FF04], dans celui de James Norris [Nor98a], et dans celui de Christiane Cocozza-Thivent [CT97]. Les probabilités sont un des outils essentiels de l'actuariat, nom donné à la science de l'assurance. Le modèle présenté ici appelé modèle de Cramér-Lundberg a été introduit par Filip Lundberg vers 1903 puis popularisé par Harald Cramér dans les années 1930. On pourra notamment consulter les ouvrages de Søren Asmussen [Asm00], Thomas Mikosch [Mik09] ou encore de Arthur Charpentier et Michel Denuit [CD04]. Du point de vue de la théorie des processus stochastiques, le processus de Cramér-Lundberg est un processus de Markov déterministe par morceaux (un autre exemple est traité dans le chapitre 17). Un modèle plus sophistiqué prend en compte le fait que les assureurs placent l'argent des cotisations au fur et à mesure. Le générateur infinitésimal du processus décrivant la fortune de la compagnie s'écrit alors

$$ Lf(x) = (\gamma x + p)f'(x) + \mu \int_{0}^{\infty} (f(x - y) - f(x)) \nu(dy). $$

Les lois de franchissement d'un niveau sont alors plus difficiles à décrire.
# Polymères dirigés en environnement aléatoire

**Mots-clés.** Phénomène de seuil; transition de phase; inégalité FKG; espérance dépendant d'un paramètre; polymère dirigé; environnement aléatoire; mesure de Boltzmann-Gibbs.

**Outils.** Chaîne de Markov; transformée de Laplace; martingale; loi du zéro-un.

## Difficulté. ***

Un polymère est une longue molécule constituée de briques élémentaires identiques appelées monomères. On s'intéresse à la modélisation de la structure d'un polymère constitué de monomères hydrophiles, placé dans une émulsion d'huile et d'eau. L'huile est présente sous la forme de gouttelettes microscopiques. On suppose que les monomères sont régulièrement espacés et que le polymère se déroule dans une direction privilégiée. On dit que le polymère est dirigé. Par analogie avec les processus, cette dimension est dite temporelle, et le polymère est vu comme un chemin dans $Z^d$, c'est-à-dire une application de $\{0, 1, ..., n\}$ dans $Z^d$ où $n$ est la longueur du polymère. On positionne sur les points de $\mathbb{N} \times Z^d$ des variables aléatoires i.i.d. qui quantifient la sensibilité de chaque monomère du polymère à la présence d'huile ou d'eau sur chaque site. Dans tout le chapitre, l'entier $d$ est fixé supérieur ou égal à 1.

La sensibilité du polymère à son environnement est modélisée par un paramètre réel noté $\beta$ introduit par la suite. Toute la question est de déterminer pour quelles valeurs de ce paramètre le comportement du polymère est sensiblement différent d'une marche aléatoire simple qui modélise la structure d'un polymère indifférent à son environnement.

## 19.1 Modèle et résultats principaux

On modélise un polymère insensible à son environnement par une marche aléatoire simple sur $Z^d$, c'est-à-dire une suite $(S_n)_{n\ge0}$ avec $S_0 = 0$ et
$$S_n = \sum_{i=1}^{n} U_i, \quad n \ge 1,$$

où $(U_n)_{n \ge 1}$ est une suite de v.a. i.i.d. de loi uniforme sur $\{\pm e_i : 1 \le i \le d\}$, où $e_1, \dots, e_d$ est la base canonique de $\mathbb{Z}^d$. On note $(\mathcal{F}_n)_{n \ge 0}$ la filtration naturelle de $(S_n)_{n \ge 0}$, et $\mathcal{F}$ la tribu engendrée par les variables aléatoires $(U_n)_{n \ge 1}$.

Il est commode de représenter les $n+1$ premiers termes de $(S_n)_{n \ge 0}$ par la variable aléatoire $S_{0:n} = (S_0, S_1, \dots, S_n)$, qui prend ses valeurs dans $\Gamma_n$, l'ensemble des chemins issus de 0 et de longueur $n$ dans $\mathbb{Z}^d$, c'est-à-dire l'ensemble des $(n+1)$-uplets $\gamma = (\gamma_0, \gamma_1, \dots, \gamma_n)$ avec $\gamma_0, \dots, \gamma_n$ dans $\mathbb{Z}^d$, tels que $\gamma_0 = 0$ et $\gamma_{i+1} - \gamma_i \in \{\pm e_j : 1 \le j \le d\}$ pour tout $0 \le i \le n-1$.

On modélise l'environnement par des variables aléatoires réelles

$$(\eta(n, x))_{n \ge 1, x \in \mathbb{Z}^d}$$

i.i.d. non constantes. On suppose que $(U_n)_{n \ge 1}$ et $(\eta(n, x))_{n \ge 0, x \in \mathbb{Z}^d}$ sont indépendantes. On note $\mathcal{G}$ la tribu engendrée par $(\eta(i, x))_{i \ge 1, x \in \mathbb{Z}^d}$ et $\mathcal{G}_n$ la tribu engendrée par $(\eta(i, x))_{(i,x) \in \mathcal{E}_n}$ où $\mathcal{E}_n = \{(i, \gamma_i) : 1 \le i \le n, \gamma_i \in \Gamma_n\}$ est l'environnement vu par les chemins de longueur $n$.

Pour tout $\beta \ge 0$, on définit la mesure de probabilité aléatoire $\mu_n$ sur $\Gamma_n$ en posant, pour tout $\gamma \in \Gamma_n$,

$$\mu_n(\gamma) = \frac{1}{Z_n(\beta)} e^{\beta H_n(\gamma)} \mathbb{P}(S_{0:n} = \gamma),$$

avec

$$H_n(\gamma) = \sum_{i=1}^{n} \eta(i, \gamma_i) \quad \text{et} \quad Z_n(\beta) = \mathbb{E} \left( e^{\beta H_n(S_{0:n})} \mid \mathcal{G} \right).$$

La mesure de probabilité $\mu_n$ est une mesure de Gibbs (voir chapitre 5). La quantité $H_n(S_{0:n})$ représente l'affinité de la configuration du polymère dans son environnement. Plus elle est élevée, plus la configuration du polymère est probable. Le paramètre $\beta$ quantifie l'influence de l'environnement sur la structure du polymère. Il s'interprète comme l'inverse de la température. Si $\beta = 0$ (la température est infinie) alors tous les chemins de longueur $n$ ont le même poids : le polymère n'est pas sensible à l'environnement et se comporte comme la marche aléatoire simple. Si $\beta = +\infty$ (température nulle), le polymère ne charge que les chemins de longueur $n$ qui maximisent $H_n$.

La quantité $Z_n(\beta)$ est une constante de normalisation appelée fonction de partition du système. On pose $\eta = \eta(0, 0)$ et on suppose que la fonction suivante est bien définie :

$$\lambda : t \in \mathbb{R} \mapsto \lambda(t) = \log \mathbb{E}(e^{t\eta}) \in \mathbb{R}_+.$$

La fonction de partition normalisée est

$$W_n(\beta) = \mathbb{E} \left( e^{\beta H_n(S_{0:n}) - n\lambda(\beta)} \mid \mathcal{G} \right).$$
<figure><img src="image_59.png" /><figcaption>**Fig. 19.1.** Environnement Bernoulli : les points noirs représentent les sites où l'environnement vaut +1). Pour les chemins $\gamma$ et $\gamma'$, $H_8(\gamma) = 6$ et $H_8(\gamma') = 1$. Le premier est favorisé par rapport au second dès que $\beta > 0$.</figcaption></figure>

L'énergie libre du système et son espérance sont définies par

$$q_n(\beta) = \frac{1}{n} \log Z_n(\beta) \quad \text{et} \quad u_n(\beta) = \mathbb{E}(q_n(\beta)).$$

Les quantités $Z_n(\beta)$, $q_n(\beta)$, $W_n(\beta)$ et $\mu_n$ sont aléatoires, et nous allons étudier leur comportement asymptotique quand $n$ tend vers l'infini. Il y a plusieurs façons de mesurer l'influence de l'environnement sur la structure du polymère. Nous en présentons deux basées sur les comportements asymptotiques de $q_n(\beta)$ et $W_n(\beta)$. Les résultats sont présentés dans cette section, leurs démonstrations sont données dans les suivantes.

Nous commençons par le premier résultat significatif sur une dichotomie possible dans le comportement du polymère. Il est basé sur le comportement asymptotique de la fonction de partition normalisée $W_n(\beta)$.

**Théorème 19.1** (Phénomène de seuil). Il existe une v.a. $W_\infty(\beta)$ telle que

$$W_n(\beta) \xrightarrow{n \to \infty} W_\infty(\beta).$$

De plus, il existe une constante $\bar{\beta}_c \in [0, +\infty]$ telle que, p.s.

$$\begin{cases} W_\infty(\beta) > 0 & \text{si } \beta < \bar{\beta}_c, \text{ et on dit que le polymère est en « faible désordre »,} \\ W_\infty(\beta) = 0 & \text{si } \beta > \bar{\beta}_c, \text{ et on dit que le polymère est en « fort désordre »}. \end{cases}$$

Ce résultat sera démontré dans la section 19.2. Il donne la première notion de désordre. Présentons à présent l'autre notion de désordre. Elle s'appuie sur le résultat suivant.
**Théorème 19.2** (Phénomène de seuil). *Il existe une fonction u ≤ λ telle que*

$$u_n(\beta) \xrightarrow{n \to \infty} u(\beta).$$

De plus, il existe une constante $\beta_c \in [0, +\infty]$ telle que

$$ \begin{cases} u(\beta) = \lambda(\beta) & \text{si } \beta < \beta_c, \text{ (le polymère est en «très faible désordre»)}, \\ u(\beta) < \lambda(\beta) & \text{si } \beta > \beta_c, \text{ (le polymère est en «très fort désordre»)}. \end{cases} $$

Ce théorème est démontré dans la section 19.4. Les deux notions de désordre sont comparables.

**Lemme 19.3** (Le très fort désordre implique le fort désordre). *On a toujours*

$$0 \le \bar{\beta}_c \le \beta_c \le +\infty.$$

*Démonstration.* Si $\beta < \bar{\beta}_c$ alors $\mathbb{P}(\{W_\infty(\beta) > 0\}) = 1$ et par suite

$$(u - \lambda)(\beta) = \lim_{n \to \infty} \frac{1}{n} \log W_n(\beta) = 0.$$

En d'autres termes, $\beta \le \beta_c$.

□

Notons que la terminologie est délicate car le modèle peut être à la fois en très faible désordre et en fort désordre. Le tableau suivant résume les choses.

<table><thead><tr><th>β</th><th>(0, β̄<sub>c</sub>)</th><th>(β̄<sub>c</sub>, β<sub>c</sub>)</th><th>(β<sub>c</sub>, +∞)</th></tr></thead><tbody><tr><td>Fort Désordre</td><td>non</td><td>oui</td><td>oui</td></tr><tr><td>Très Fort Désordre</td><td>non</td><td>non</td><td>oui</td></tr></tbody></table>

Les deux questions essentielles sont les suivantes :

- ces phénomènes de seuil – on parle parfois en physique de transition de phase – ont-ils vraiment lieu, en d'autres termes, les paramètres critiques sont-ils finis et non nuls ?

- les deux paramètres critiques sont-ils différents ?

Les réponses à ces questions peuvent dépendre de la loi de l'environnement et de la dimension $d$ du polymère. Nous obtenons dans la section 19.3 une borne supérieure pour $\beta_c$ qui est finie ou non selon la loi de l'environnement et la dimension $d$. Dans la section 19.5, nous montrons que si $d \ge 3$ alors quel que soit l'environnement, $\bar{\beta}_c > 0$. On pourra se reporter à la section 19.6 pour le cas des petites dimensions qui s'avère beaucoup plus délicat.

Certaines démonstrations ci-dessous reposent sur la remarque simple suivante : si $f$ et $g$ sont croissantes, alors $f(X)$ et $g(X)$ sont positivement corrélatées. Cette propriété, appelée inégalité FKG<fnref n="1" /> est vraie pour des fonctions de plusieurs variables aléatoires indépendantes, comme l'affirme le lemme 19.4.

<footnote n="1">1. Pour Fortuin, Kasteleyn et Ginibre.</footnote>
**Lemme 19.4** (Inégalité FKG). Soient $X = (X_i)_{1\le i\le k}$ des v.a.r. indépendantes et $f,g: \mathbb{R}^k \to \mathbb{R}$ deux fonctions telles que $f(X)$ et $g(X)$ sont de carré intégrable, croissantes au sens où $f(x) \le f(y)$ si $x_i \le y_i$ pour tout $1 \le i \le k$. Alors $f(X)$ et $g(X)$ sont positivement corrélées :

$$ \mathbb{E}[f(X)g(X)] \ge \mathbb{E}[f(X)] \mathbb{E}[g(X)]. $$

*Démonstration.* Pour $k=1$, si $X'$ est une copie indépendante de $X$, on a

$$ \mathbb{E}(f(X)g(X)) - \mathbb{E}f(X)\mathbb{E}g(X) = \frac{1}{2}\mathbb{E}[(f(X) - f(X'))(g(X) - g(X'))] \ge 0. $$

Pour $k > 1$, on procède par récurrence en utilisant un conditionnement :

$$ \begin{aligned} \mathbb{E}(f(X)g(X)) - \mathbb{E}f(X)\mathbb{E}g(X) &= \mathbb{E}(\mathbb{E}(f(X)g(X)|X_1) - \mathbb{E}(f(X)|X_1)\mathbb{E}(g(X)|X_1)) \\ &\quad + \mathbb{E}(\mathbb{E}(f(X)|X_1)\mathbb{E}(g(X)|X_1)) - \mathbb{E}f(X)\mathbb{E}g(X) \\ &= \mathbb{E}\text{Cov}(f(X), g(X)|X_1) + \text{Cov}(\mathbb{E}(f(X)|X_1), \mathbb{E}(g(X)|X_1)). \end{aligned} $$

Le premier terme est positif par hypothèse de récurrence car à $x_1$ fixé les fonctions $f$ et $g$ sont croissantes comme fonctions des $k-1$ variables $(x_2, \dots, x_k)$. Le second l'est aussi car les fonctions $\mathbb{E}(f(X)|X_1 = \cdot)$ et $\mathbb{E}(g(X)|X_1 = \cdot)$ sont croissantes et la propriété est vraie au rang 1. $\square$

## 19.2 Fonction de partition normalisée

Cette section est consacrée à la preuve du théorème 19.1.

**Lemme 19.5** (Convergence). La suite $(W_n(\beta))_{n\ge 1}$ converge p.s. vers une variable aléatoire $W_\infty(\beta)$ qui est positive et d'intégrale inférieure à 1.

*Démonstration.* L'inégalité de Jensen assure que, pour $p \ge 1$,

$$ \mathbb{E}(W_n(\beta)^p) = \mathbb{E}\left(\mathbb{E}\left(e^{\beta H_n(S_{0:n}) - n\lambda(\beta)} \mid \mathcal{G}\right)^p\right) \le \mathbb{E}\left(e^{p\beta H_n(S_{0:n})}\right) e^{-pn\lambda(\beta)}. $$

Pour tout $\gamma \in \Gamma_n$, on a

$$ \mathbb{E}(e^{p\beta H_n(\gamma)}) = [\mathbb{E}(e^{p\beta\eta})]^n = e^{n\lambda(p\beta)}. $$

La variable aléatoire $W_n^p$ est donc intégrable et $\mathbb{E}(W_n(\beta)^p) \le e^{n(\lambda(p\beta) - p\lambda(\beta))}$. Pour $p=1$, la majoration est une égalité : $\mathbb{E}(W_n(\beta)) = 1$. Pour tout $n \ge 1$,

$$ \mathbb{E}(W_{n+1}(\beta) | \mathcal{G}_n) = \frac{e^{-(n+1)\lambda(\beta)}}{(2d)^{n+1}} \sum_{\gamma \in \Gamma_{n+1}} \mathbb{E} \left( e^{\beta \sum_{i=1}^{n+1} \eta(i, \gamma_i)} | \mathcal{G}_n \right) $$
$$
\begin{align*}
&= \frac{e^{-(n+1)\lambda(\beta)}}{(2d)^{n+1}} \sum_{\gamma \in \Gamma_{n+1}} e^{\beta \sum_{i=1}^{n} \eta(i, \gamma_i)} e^{\lambda(\beta)} \\
&= \frac{1}{(2d)^n} \sum_{\gamma \in \Gamma_n} e^{\beta H_n(\gamma) - n\lambda(\beta)} = W_n(\beta).
\end{align*}
$$

La suite $(W_n(\beta))_{n\ge 1}$ est donc une martingale positive pour la filtration $(\mathcal{G}_n)_n$.
Elle converge donc p.s. vers une variable aléatoire positive $W_\infty(\beta)$. De plus,
d'après le lemme de Fatou,

$$
\mathbb{E}(W_{\infty}(\beta)) = \mathbb{E}\left(\liminf_{n \to \infty} W_n(\beta)\right) \le \liminf_{n \to \infty} \mathbb{E}(W_n(\beta)) = 1,
$$

ce qui est le résultat annoncé.

□

Rien n'assure pour l'instant que la martingale converge dans $L^1$ ni que $W_\infty(\beta)$ soit d'intégrale 1. Le résultat suivant établit que $W_\infty(\beta)$ est soit nulle soit strictement positive presque sûrement.

**Lemme 19.6 (loi du zéro-un).** *Pour tout $\beta \ge 0$ et tout $\theta \in (0, 1)$,*

$$
\mathbb{P}(W_{\infty}(\beta) = 0) \in \{0, 1\} \quad \text{et} \quad \lim_{n \to \infty} \mathbb{E}(W_n(\beta)^{\theta}) = \mathbb{E}(W_{\infty}(\beta)^{\theta}).
$$

Démonstration. La propriété de Markov de la marche assure que

$$
W_{n+m}(\beta) = \mathbb{E} \left( e^{\beta H_n(S_{0:n}) - n\lambda(\beta)} Z_{n,m}^{S_n} e^{-m\lambda(\beta)} \mid \mathcal{G} \right)
$$

où, pour $x \in \mathbb{Z}^d$ et $n$ et $m$ entiers strictement positifs,

$$
Z_{n,m}^{x}(\beta) = \mathbb{E} \left[ \exp \left( \beta \sum_{i=1}^{m} \eta(n+i, x+S_i) \right) \middle| \mathcal{G} \right].
$$

Ainsi,

$$
W_{\infty}(\beta) = \lim_{m \to \infty} W_{n+m}(\beta) = \mathbb{E} \left( e^{\beta H_n(S_{0:n}) - n\lambda(\beta)} \lim_{m \to \infty} \left( Z_{n,m}^{S_n} e^{-m\lambda(\beta)} \right) \mid \mathcal{G} \right).
$$

Puisque $e^{\beta H_n(S_{0:n}) - n\lambda(\beta)}$ est strictement positif presque sûrement, l'événement

$$
\{W_{\infty}(\beta) = 0\} = \left\{ \lim_{m \to \infty} \left(Z_{n,m}^{x} e^{-m\lambda(\beta)}\right) = 0 : \forall x, \mathbb{P}(S_n = x) > 0 \right\}
$$

appartient à la tribu $\sigma(\eta(j, x), j \ge n, x \in \mathbb{Z}^d)$. Ceci est vrai pour tout $n$.
Il appartient donc à la tribu asymptotique $\bigcap_{n \ge 1} \sigma(\eta(j, x) : j \ge n, x \in \mathbb{Z}^d)$.
D'après la loi du zéro-un de Kolmogorov, tous les éléments de la tribu asymp-
totique sont de probabilité 0 ou 1. Puisque $W_n(\beta)$ est d'espérance 1, la suite
$(W_n(\beta)^\theta)_{n \ge 0}$ est bornée dans $L^{1/\theta}$. De plus, elle converge vers $W_\infty(\beta)^\theta$ p.s.
On a donc

$$
\lim_{n \to \infty} \mathbb{E}(W_n(\beta)^{\theta}) = \mathbb{E}(W_{\infty}(\beta)^{\theta}).
$$

Cette limite est nulle si et seulement si $W_\infty(\beta)$ est nul presque sûrement.

□
Il reste à établir une propriété de monotonie pour la dichotomie ci-dessus.

**Lemme 19.7 (Monotonie).** Pour tout $\theta \in ]0, 1[$, $\beta \mapsto \mathbb{E}(W_\infty(\beta)^\theta)$ décroît.

*Démonstration.* On remarque tout d'abord que

$$ \partial_{\beta} W_n(\beta) = \mathbb{E}((H_n(S_{0:n}) - n\lambda'(\beta))e^{\beta H_n(S_{0:n}) - n\lambda(\beta)} | \mathcal{G}). $$

On a donc, après dérivation sous l'espérance,

$$ \partial_{\beta} \mathbb{E}(W_n(\beta)^{\theta}) = \theta \mathbb{E} \left( W_n(\beta)^{\theta-1} \left( H_n(S_{0:n}) - n\lambda'(\beta) \right) e^{\beta H_n(S_{0:n}) - n\lambda(\beta)} \right). $$

L'inégalité FKG du lemme 19.4 appliquée à la mesure de probabilité de densité $e^{\beta H_n(\gamma) - n\lambda(\beta)}$ par rapport à $\mathbb{P}$ et aux fonctions $W_n(\beta)^{\theta-1}$ et $H_n(\gamma) - n\lambda'(\beta)$ – qui sont des fonctions respectivement décroissante et croissante des variables $(\eta(k, x))_{(k,x) \in E_n}$ – assure que

$$ \mathbb{E} \left( W_n(\beta)^{\theta-1} \left( H_n(\gamma) - n\lambda'(\beta) \right) e^{\beta H_n(\gamma) - n\lambda(\beta)} \right) $$

est inférieur à

$$ \mathbb{E} \left( W_n(\beta)^{\theta-1} e^{\beta H_n(\gamma) - n\lambda(\beta)} \right) \mathbb{E} \left( \left( H_n(\gamma) - n\lambda'(\beta) \right) e^{\beta H_n(\gamma) - n\lambda(\beta)} \right). $$

Pour conclure, on utilise alors que

$$ \mathbb{E} \left( (H_n(\gamma) - n\lambda'(\beta)) e^{\beta H_n(\gamma) - n\lambda(\beta)} \right) = \partial_{\beta} \mathbb{E}(W_n(\beta)) = 0. $$

□

On peut à présent conclure. Par passage à la limite $\theta \to 1$, on obtient que

$$ \beta \mapsto \mathbb{E}(W_{\infty}(\beta)) $$

est décroissante. Il existe donc $\bar{\beta}_c \in [0, +\infty]$ tel que, presque sûrement,

$$ \begin{cases} W_{\infty}(\beta) > 0 & \text{si } \beta < \bar{\beta}_c, \\ W_{\infty}(\beta) = 0 & \text{si } \beta > \bar{\beta}_c. \end{cases} $$

Ceci achève la démonstration du théorème 19.1.

## 19.3 Borne inférieure en grandes dimensions

On se place ici en dimension $d \ge 3$. Dans ce cas, la marche aléatoire simple $(S_n)_{n \ge 0}$ est transiente (voir le théorème 2.7). La probabilité qu'elle revienne en 0 est strictement inférieure à 1. Notons $\pi_d$ cette probabilité.
**Théorème 19.8** (Critère de non nullité). Si $d \ge 3$ et si

$$ \tau(\beta) = \lambda(2\beta) - 2\lambda(\beta) < \log(1/\pi_d) $$

alors $W_\infty > 0$ presque sûrement.

*Démonstration.* Pour tout $\beta \ge 0$, on a $\tau'(\beta) = 2(\lambda'(2\beta) - \lambda'(\beta)) > 0$ puisque $\lambda$ est strictement convexe car logarithme d'une transformée de Laplace. Il en découle que $\tau$ est donc strictement croissante. Soit à présent une suite $(U'_n)_{n \ge 1}$ de même loi que $(U_n)_{n \ge 1}$, de sorte que

$$ (U_n)_{n \ge 1}, \quad (U'_n)_{n \ge 1}, \quad (\eta(n, x))_{n \ge 0, x \in \mathbb{Z}^d} $$

soient indépendantes. Soit $(S'_n)_{n \ge 1}$ la suite construite à partir de $(U'_n)_{n \ge 1}$ à la manière de $(S_n)_{n \ge 1}$ à partir de $(U_n)_{n \ge 1}$. Par indépendance de $(S_n)$ et $(S'_n)$,

$$ \begin{aligned} W_n(\beta)^2 &= \mathbb{E}\left(\prod_{k=1}^n e^{\beta\eta(k,S_k)-\lambda(\beta)} \mid \mathcal{G}\right) \mathbb{E}\left(\prod_{k=1}^n e^{\beta\eta(k,S'_k)-\lambda(\beta)} \mid \mathcal{G}\right) \\ &= \mathbb{E}\left(\prod_{k=1}^n e^{\beta(\eta(k,S_k)+\eta(k,S'_k))-2\lambda(\beta)} \mid \mathcal{G}\right). \end{aligned} $$

Prenons l'espérance :

$$ \mathbb{E}(W_n^2) = \mathbb{E}\left[\mathbb{E}\left(\prod_{k=1}^n e^{\beta(\eta(k,S_k)+\eta(k,S'_k))-2\lambda(\beta)} \mid \mathcal{F}' \lor \mathcal{F}\right)\right]. $$

Or, pour tout $x, x' \in \mathbb{Z}^d$,

$$ \mathbb{E}\left(e^{\beta(\eta(k,x)+\eta(k,x'))-2\lambda(\beta)}\right) = \begin{cases} e^{\tau(\beta)} & \text{si } x = x', \\ 1 & \text{si } x \neq x'. \end{cases} $$

On a donc

$$ \mathbb{E}(W_n(\beta)^2) = \mathbb{E}(e^{\tau(\beta)I_n}) \quad \text{où} \quad I_n = \sum_{k=0}^{n} \mathbb{1}_{\{S_k=S'_k\}}. $$

On remarque alors que les suites $(S_k - S'_k)_{k \ge 0}$ et $(S_{2k})_{k \ge 0}$ ont même loi puisque $-U'_n$ et $U_n$ sont indépendantes et ont même loi. La variable aléatoire $I_n$ a donc même loi que le nombre $N_{2n}$ de retours en 0 de $S$ avant l'instant $2n$. Par convergence monotone,

$$ \mathbb{E}(e^{\tau(\beta)I_n}) = \mathbb{E}(e^{\tau(\beta)N_{2n}}) \underset{n \to \infty}{\longrightarrow} \mathbb{E}(e^{\tau(\beta)N_\infty}). $$

La propriété de Markov forte de $S$ assure que la loi de $N_\infty$ est la loi géométrique de paramètre $1 - \pi_d$ et que, pour tout $t \in \mathbb{R}$,
$$
\mathbb{E}(e^{tN_{\infty}}) = \sum_{k=1}^{\infty} (1 - \pi_d) \pi_d^{k-1} e^{tk} = \begin{cases} \frac{(1 - \pi_d)e^t}{1 - \pi_d e^t} & \text{si } t < -\log(\pi_d), \\ +\infty & \text{sinon.} \end{cases}
$$

On obtient ainsi une condition nécessaire et suffisante pour que la suite
$(W_n(\beta))_{n\ge 1}$ soit bornée dans $L^2$ :

$$
\sup_{n \ge 1} \mathbb{E}(W_n(\beta)^2) < \infty \iff \tau(\beta) < \log(1/\pi_d).
$$

Si $\tau(\beta) < \log(1/\pi_d)$, alors $(W_n(\beta))_{n\ge 1}$ est une martingale bornée dans $L^2$, elle converge donc p.s. et dans $L^2$ vers une variable aléatoire de carré intégrable $W_\infty(\beta)$. En particulier on a $\mathbb{E}(W_\infty(\beta)) = \lim_n \mathbb{E}(W_n(\beta)) = 1$ et donc $W_\infty(\beta) > 0$ p.s. grâce à la loi du zéro-un du lemme 19.6. $\square$

**Corollaire 19.9** (Critère de non nullité). *Si d $\geqq$ 3 alors pour tout environnement, $\bar{\beta}_c > 0$.*

*Démonstration.* La fonction $\tau$ est nulle en 0 et régulière sur $\mathbb{R}$. Elle est de plus strictement croissante car

$$
\tau'(\beta) = 2(\lambda'(2\beta) - \lambda'(\beta)) > 0,
$$

par stricte convexité de $\lambda$. La condition du théorème 19.8 est donc toujours
vérifiée pour $\beta$ assez petit et ce, quel que soit l'environnement. $\square$

**Exemple 19.10 (Environnement gaussien).** Si $\eta \sim \mathcal{N}(0, 1)$, alors $\tau(\beta) = \beta^2$ et $\tau(\beta) < \log(1/\pi_d)$ ssi $\beta < \sqrt{\log(1/\pi_d)}$. On a donc $\bar{\beta}_c > \sqrt{\log(1/\pi_d)}$.

**Exemple 19.11 (Environnement Bernoulli).** Si $\eta \sim \text{Ber}(p)$, alors

$$
\lambda(\beta) = \log(pe^{\beta} + 1 - p) \quad \text{et} \quad \lim_{\beta \to \infty} \tau(\beta) = -\log(p).
$$

Ainsi, dès que $p > \pi_d$, la condition du théorème 19.8 est satisfaite pour tout
$\beta \ge 0$, et $\bar{\beta}_c$ est infini.

19.4 Énergie libre moyenne

L'objet principal de cette section est de démontrer le théorème 19.2. On démontre tout d'abord que l'énergie libre moyenne converge.

**Lemme 19.12 (Convergence de l'énergie libre moyenne).** *Pour tout $\beta \ge 0$, il existe une constante $u(\beta)$ inférieure à $\lambda(\beta)$ telle que*

$$
u_n(\beta) \xrightarrow{n \to \infty} u(\beta).
$$
Démonstration. L'inégalité de Jensen assure que

$$u_n(\beta) = \frac{1}{n} \mathrm{E}(\log(Z_n(\beta))) \le \frac{1}{n} \log \mathrm{E}(Z_n(\beta)).$$

Puisque $\mathrm{E}(W_n(\beta)) = 1$, on a $\mathrm{E}(Z_n(\beta)) = e^{n\lambda(\beta)}$ et $u_n(\beta) \le \lambda(\beta)$.

Conditionnellement à $\mathcal{G}$, la propriété de Markov de la marche $S$ assure que

$$\mathrm{E}(e^{\beta H_{n+m}(S_{0:n+m})} | \mathcal{G}) = \mathrm{E}(e^{\beta H_n(S_{0:n})} Z_{n,m}^{S_n} | \mathcal{G}).$$

Par définition de $Z_n(\beta)$ et $\mu_n$, on a simplement

$$\begin{aligned} \mathrm{E}(e^{\beta H_n(S_{0:n})} Z_{n,m}^{S_n} | \mathcal{G}) &= \frac{\mathrm{E}(e^{\beta H_n(S_{0:n})} Z_{n,m}^{S_n} | \mathcal{G})}{\mathrm{E}(e^{\beta H_n(S_{0:n})} | \mathcal{G})} Z_n(\beta) \\ &= \mu_n(Z_{n,m}^{S_n}) Z_n(\beta). \end{aligned}$$

En d'autres termes,

$$\log(Z_{n+m}(\beta)) = \log(Z_n(\beta)) + \log \sum_{x \in \mathbb{Z}^d} \mu_n(S_n = x) Z_{n,m}^x.$$

L'inégalité de Jensen pour la mesure $\mu_n$ assure que

$$\log(Z_{n+m}(\beta)) \ge \log(Z_n(\beta)) + \sum_{x \in \mathbb{Z}^d} \mu_n(S_n = x) \log(Z_{n,m}^x).$$

La mesure aléatoire $\mu_n$ est $\mathcal{G}_n$-mesurable et $Z_{n,m}^x$ est indépendante de $\mathcal{G}_n$. On a donc

$$\mathrm{E} \left( \sum_{x \in \mathbb{Z}^d} \mu_n(S_n = x) \log(Z_{n,m}^x) \mid \mathcal{G}_n \right) = \sum_{x \in \mathbb{Z}^d} \mu_n(S_n = x) \mathrm{E} \left( \log(Z_{n,m}^x) \mid \mathcal{G}_n \right).$$

Les v.a. $Z_{n,m}^x$ et $Z_m$ ont même loi car les v.a. $(\eta(n, x))_{n,x}$ sont i.i.d. En prenant l'espérance, on obtient que la suite $(\mathrm{E}(\log(Z_m)))_{n \ge 1}$ est sur-additive, et donc, d'après le lemme de Fekete (voir page 223), la suite $(u_n(\beta))_{n \ge 1}$ converge dans $\mathbb{R} \cup \{+\infty\}$. Comme elle est bornée par $\lambda(\beta)$, sa limite $u(\beta)$ est finie. $\square$

Le phénomène de seuil va découler d'une propriété de monotonie.

**Lemme 19.13 (Monotonie).** La fonction $\beta \mapsto u(\beta) - \lambda(\beta)$ décroît sur $\mathbb{R}_+$.

Démonstration. Étudions les variations de $\beta \mapsto u_n(\beta) - \lambda(\beta)$. On a

$$\begin{aligned} \frac{\partial}{\partial \beta} \mathrm{E}(\log(Z_n(\beta))) &= \mathrm{E} \left( \frac{\mathrm{E}(H_n(S_{0:n}) e^{\beta H_n(S_{0:n})} | \mathcal{G})}{Z_n(\beta)} \right) \\ &= \frac{1}{(2d)^n} \sum_{\gamma \in \Gamma_n} \mathrm{E} \left( \frac{H_n(\gamma) e^{\beta H_n(\gamma)}}{Z_n(\beta)} \right). \end{aligned}$$
Remarquons que $H_n(\gamma)$ (respectivement $Z_n^{-1}(\beta)$) est une fonction croissante (respectivement décroissante) des variables $(\eta(i, x))_{(i,x)\in E_n}$. D'autre part, la mesure de densité $e^{\beta H_n(\gamma) - n\lambda(\beta)}$ par rapport à la mesure $P$ est une mesure de probabilité. L'inégalité FKG du lemme 19.4 assure donc

$$ 
\begin{aligned}
& \mathbb{E}\left(\frac{H_n(\gamma)}{Z_n(\beta)} e^{\beta H_n(\gamma) - n\lambda(\beta)}\right) \\
& \le \mathbb{E}\left(H_n(\gamma) e^{\beta H_n(\gamma) - n\lambda(\beta)}\right) \mathbb{E}\left(Z_n(\beta)^{-1} e^{\beta H_n(\gamma) - n\lambda(\beta)}\right).
\end{aligned}
$$

On obtient ainsi

$$ 
\begin{aligned}
\frac{\partial}{\partial \beta} \mathbb{E}(\log(Z_n(\beta))) & \le \frac{1}{(2d)^n} \sum_{\gamma \in \Gamma_n} e^{-n\lambda(\beta)} \mathbb{E}\left(\frac{e^{\beta H_n(\gamma)}}{Z_n(\beta)}\right) \mathbb{E}\left(H_n(\gamma) e^{\beta H_n(\gamma)}\right) \\
& \le n\lambda'(\beta) \mathbb{E}\left(\frac{1}{(2d)^n} \sum_{\gamma \in \Gamma_n} \frac{e^{\beta H_n(\gamma)}}{Z_n(\beta)}\right) \\
& \le n\lambda'(\beta).
\end{aligned}
$$

En d'autres termes, $(u_n - \lambda)'(\beta) \le 0$ : pour tout $n \ge 1$ la fonction $u_n - \lambda$ est décroissante. C'est encore vrai en passant à la limite quand $n \to \infty$ : la fonction $u - \lambda$ est décroissante sur $\mathbb{R}_+$.
□

Les fonctions $u$ et $\lambda$ sont nulles en 0. Il existe donc $\beta_c \in [0, +\infty]$ tel que

$$ 
\begin{cases} u(\beta) = \lambda(\beta) & \text{si } \beta < \beta_c, \\ u(\beta) < \lambda(\beta) & \text{si } \beta > \beta_c. \end{cases}
$$

## 19.5 Borne supérieure sur le paramètre critique

Le but de cette section est d'établir une borne supérieure sur $\beta_c$.

**Lemme 19.14.** Les fonctions $(q_n)_{n\ge 1}$ et $u$ vérifient les propriétés suivantes :

1. $q_n$ est strictement convexe, $q_n(0) = 0$ ; $u$ est convexe et nulle en 0.

2. $\beta \mapsto \beta^{-1}q_n(\beta)$ est croissante.

3. $\beta \mapsto \beta^{-1}(q_n(\beta) + \log(2d))$ est décroissante.

*Démonstration.* La fonction $\beta \mapsto nq_n(\beta)$ est le logarithme de la transformée de Laplace de la v.a.r. $H_n(S_{0:n})$ (les variables $\eta(\cdot, \cdot)$ étant fixées). La fonction $q_n$ est donc de classe $C^2$, convexe et nulle en 0. Ces propriétés sont stables par passage à l'espérance puis à la limite quand $n$ tend vers l'infini : $u$ est convexe sur $\mathbb{R}_+$ et nulle en 0. Puisque $q_n$ est convexe, la fonction (pente de la corde entre $(0,0)$ et $(\beta, q_n(\beta))$) $\beta \mapsto q_n(\beta)/\beta = (q_n(\beta) - q_n(0))/\beta$ est croissante.

Pour le point 3. on dérive pour obtenir
$$ \left( \frac{q_n(\beta) + \log(2d)}{\beta} \right)' = -\frac{1}{\beta^2} (q_n(\beta) + \log(2d)) + \frac{1}{n\beta} \mu_n(H_n). $$

Par ailleurs, l'entropie de $\mu_n$ définie par

$$ \begin{aligned} h_n(\mu_n) &= \sum_{\gamma \in \Gamma_n} \frac{e^{\beta H(\gamma)}}{Z_n(2d)^n} \log \left( \frac{e^{\beta H(\gamma)}}{Z_n(2d)^n} \right) \\ &= \beta \mu_n(H_n) - (\log(Z_n) + n \log(2d)) \end{aligned} $$

est négative. Ainsi,

$$ \left( \frac{q_n(\beta) + \log(2d)}{\beta} \right)' = \frac{1}{n\beta^2} h_n(\mu_n) \le 0. $$

La fonction $\beta \mapsto \beta^{-1}(q_n(\beta) + \log(2d))$ est décroissante sur $\mathbb{R}_+^*$.

□

Le lemme 19.14 fournit une majoration de $u$ et de $\beta_c$.

**Théorème 19.15 (Majorations).** Si la condition suivante est vérifiée :

$$ \lim_{\beta \to +\infty} \beta \lambda'(\beta) - \lambda(\beta) > \log(2d), $$

alors l'équation en $\beta$ suivante

$$ \beta \lambda'(\beta) = \lambda(\beta) + \log(2d) $$

admet une unique racine $\beta_1$ et, pour tout $\beta > \beta_1$,

$$ u(\beta) \le \frac{\beta}{\beta_1}(\lambda(\beta_1) + \log(2d)) - \log(2d), $$

Enfin, on a $\beta_c \le \beta_1$.

**Démonstration.** Puisque $\lambda$ est strictement convexe, $\beta \mapsto \beta\lambda'(\beta) - \lambda(\beta)$ est strictement croissante sur $\mathbb{R}_+$ (sa dérivée vaut $\beta \mapsto \beta\lambda''(\beta)$). Elle est de plus nulle en 0. L'équation $\beta\lambda'(\beta) = \lambda(\beta) + \log(2d)$ a donc au plus une solution. Elle existe si et seulement si la condition du théorème est satisfaite.

Le lemme 19.14 assure que la fonction $\beta \mapsto (u_n(\beta) + \log(2d))/\beta$ est décroissante. Comme de plus $u_n \le \lambda$, on obtient

$$ \begin{aligned} \frac{u_n(\beta) + \log(2d)}{\beta} &= \inf_{\alpha \in [0, \beta]} \frac{u_n(\alpha) + \log(2d)}{\alpha} \\ &\le \inf_{\alpha \in [0, \beta]} \frac{\lambda(\alpha) + \log(2d)}{\alpha}. \end{aligned} $$

La fonction $\alpha \mapsto (\lambda(\alpha) + \log(2d))/\alpha$ atteint son minimum sur $[0, \beta]$ en $\beta$ ou au point où sa dérivée s'annule à savoir en $\beta_1$. Donc, pour tout $\beta > \beta_1$,
$$u(\beta) \le \frac{(\lambda(\beta_1) + \log(2d))}{\beta_1} \beta - \log(2d).$$

Il reste à remarquer que pour $\beta > \beta_1$,

$$\frac{(\lambda(\beta_1) + \log(2d))}{\beta_1} \beta - \log(2d) < \lambda(\beta)$$

puisque $\lambda$ est strictement convexe et qu'il y a égalité en $\beta_1$. $\square$

**Exemple 19.16** (Environnement gaussien et environnement Bernoulli). Si $\eta \sim \mathcal{N}(0, 1)$ alors $\beta\lambda'(\beta) - \lambda(\beta) = \beta^2/2$, et dans ce cas $\beta_1 = \sqrt{2\log(2d)}$. En revanche, si $\eta \sim \text{Ber}(p)$ alors

$$\beta\lambda'(\beta) - \lambda(\beta) = \frac{p\beta e^{\beta}}{pe^{\beta} + 1 - p} - \log(pe^{\beta} + 1 - p) \underset{\beta \to \infty}{\sim} -\log(p),$$

et $\beta_1$ est fini si et seulement si $2dp < 1$.

## 19.6 Pour aller plus loin

Ce modèle de polymère dirigé en environnement aléatoire a été introduit par John Imbrie et Thomas Spencer [IS88]. La notion de fort désordre a été étudiée en détail par Erwin Bolthausen dans [Bol89], qui démontre en particulier les théorèmes 19.1 et 19.8. Plus tard la notion de très fort désordre a été étudiée notamment par Francis Comets et Nobuo Yoshida [CY06], qui démontrent le théorème 19.2. En utilisant une inégalité de concentration pour $q_n$ autour de sa moyenne, il est possible (voir [CH02, LW09]) d'améliorer les conclusions du théorème 19.2, en démontrant que pour tout $\beta \ge 0$,

$$q_n(\beta) \xrightarrow[n \to \infty]{\text{p.s.}} u(\beta) \quad \text{et} \quad q_n(\beta) \xrightarrow[n \to \infty]{L^1} u(\beta).$$

En dimension 1 et 2, on sait démontrer que $\beta_c = 0$. Philippe Carmona et Yueyun Hu ont établi dans [CH02] que $\bar{\beta}_c = 0$ pour $d = 1$ et $d = 2$ lorsque l'environnement est gaussien. Le cas général est traité par Francis Comets, Tokuzo Shiga et Nobuo Yoshida dans [CSY03]. Par la suite, Francis Comets et Vincent Vargas ont établi dans [CV06] que $\beta_c$ est nul pour $d = 1$. Enfin, Hubert Lacoin a démontré dans [Lac10] que c'est encore vrai pour $d = 2$. La question de l'égalité des deux paramètres critiques si $d \ge 3$ semble ouverte.

L'inégalité FKG, due à Cees Fortuin, Pieter Kasteleyn, et Jean Ginibre [FKG71], constitue un outil mathématique important en physique statistique. On peut par exemple consulter à ce sujet le livre de Thomas Liggett [Lig85] sur les systèmes de particules en interaction.

Pour conclure, signalons que par souci de clarté nous avons modifié légèrement les notations classiques utilisées dans les articles cités plus haut. En effet, la mesure de référence est en général écrite comme le produit de deux mesures, l'une pour l'environnement et l'autre pour la loi de la marche. Il faut alors introduire deux signes d'espérance, qui correspondent aux espérances conditionnelles par rapport aux tribus $\mathcal{F}$ et $\mathcal{G}$ dans le présent chapitre.
<figure><img src="image_60.png" /></figure>
# Problème du voyageur de commerce

**Mots-clés.** Optimisation combinatoire randomisée.

**Outils.** Inégalité d'Azuma-Hoeffding; sous-additivité; poissonisation; pro- cessus ponctuel de Poisson.

**Difficulté.** ***

Voici trois problèmes phares de l'optimisation combinatoire randomisée :

- problème du voyageur de commerce<fnref n="1" />;

- arbre couvrant minimal<fnref n="2" />;

- appariement euclidien minimal<fnref n="3" />.

Parmi les méthodes utilisées, on compte la sous-additivité, la concentration de la mesure, la poissonisation, et la méthode objective. Nous allons aborder le premier problème, et utiliser certaines techniques. Le problème du voyageur de commerce consiste à trouver une tournée, c'est-à-dire un chemin circulaire (circuit hamiltonien) de longueur minimale passant par des points prescrits $X_1, \dots, X_n \in \mathbb{R}^d, n, d \ge 2$. Cela revient à résoudre sur le groupe symétrique

$$ \min_{\sigma \in S_n} \sum_{k=1}^{n} |X_{\sigma(k)} - X_{\sigma(k+1)}| $$

où $|\cdot|$ désigne la norme euclidienne de $\mathbb{R}^d$, $S_n$ est le groupe symétrique de $\{1, \dots, n\}$ et avec la convention $\sigma(n+1) = \sigma(1)$. Il est clair que la notion de distance choisie a une influence sur la solution du problème. L'explosion combinatoire du groupe symétrique fait que dès que $n$ dépasse quelques dizaines, il n'est plus possible de tester toutes les permutations pour trouver la meilleure. Il est cependant possible d'utiliser un algorithme d'optimisation

<footnote n="1">1. En anglais : « *Traveling Salesman Problem*» ou TSP.</footnote>

<footnote n="2">2. En anglais : « *Minimum Spanning Tree*».</footnote>

<footnote n="3">3. En anglais : « *Minimum Euclidean Matching*».</footnote>
globale comme par exemple le *recuit simulé*, abordé dans la section 5.3, pour produire en un temps raisonnable une solution approchée : une permutation pour laquelle le minimum est (presque) atteint.

Plutôt que de rechercher une permutation optimale, nous nous intéressons
dans ce chapitre à la valeur du minimum, et à son comportement lorsque $n$
est grand et les points $X_1, \dots, X_n$ sont des variables aléatoires indépendantes
et de même loi $\mu$ sur $\mathbb{R}^d$. On note $L_n = L_n(X_1, \dots, X_n)$ la longueur minimale
de la tournée, qui est une fonction de $X_1, \dots, X_n$.

<figure><img src="image_61.png" /><figcaption>**Fig. 20.1.** Trajet le plus court pour $n = 20$ points uniformément répartis dans le carré unité obtenu par l'algorithmes stochastique du recuit simulé (chapitre 4).</figcaption></figure>

**Théorème 20.1** (Bearwood-Halton-Hammersley). *Il existe une constante $0 < \gamma_d < \infty$ qui dépend de $d \ge 2$ telle que si $\mu$ est à support compact et de densité $f : \mathbb{R}^d \to \mathbb{R}_+$ par rapport à la mesure de Lebesgue, alors*

$$
\frac{L_n(X_1, \dots, X_n)}{n^{(d-1)/d}} \xrightarrow{n \to \infty} \gamma_d \int_{\mathbb{R}^d} f(x)^{(d-1)/d} dx.
$$

En particulier $L_n(X_1, \dots, X_n)$ est d'ordre $\sqrt{n}$ en dimension $d=2$. Nous allons établir ce théorème lorsque $\mu$ est la loi uniforme sur le cube $[0,1]^d$. Nous allons montrer que la variable aléatoire $L_n(X_1, \dots, X_n)$ est d'autant plus concentrée autour de son espérance $E(L_n(X_1, \dots, X_n))$ que $n$ est grand, puis que cette espérance est d'ordre $n^{(d-1)/d}$.
<figure><img src="image_62.png" /><figcaption>Fig. 20.2. Tracé d'une approximation de $n \mapsto n^{-1/2}E(L_n)$ dans le cas uniforme, avec une méthode de Monte-Carlo et l'algorithme du recuit simulé (chapitre 5).</figcaption></figure>

## 20.1 Concentration pour le cas uniforme

**Théorème 20.2 (Concentration autour de la moyenne).** Si $\mu$ est la loi uniforme sur le cube $[0, 1]^d$ alors pour tout $n \ge 1$ et tout réel $t \ge 0$ on a

$$ P(|L_n - E(L_n)| \ge t) \le 2 \exp \begin{cases} -\frac{ct^2}{\log(n)} & \text{si } d=2, \\ -\frac{ct^2}{n^{(d-2)/d}} & \text{si } d>2, \end{cases} $$

où $c > 0$ est une constante qui ne dépend que de la dimension $d$. Ainsi,

$$ P\left(\left|\frac{L_n}{n^{(d-1)/d}} - E\left(\frac{L_n}{n^{(d-1)/d}}\right)\right| \ge t\right) \le 2 \exp \begin{cases} -\frac{cnt^2}{\log(n)} & \text{si } d=2, \\ -cnt^2 & \text{si } d>2. \end{cases} $$
La preuve du théorème 20.2 s’appuie sur deux lemmes.

On dit qu'une variable est concentrée lorsqu'elle reste proche de sa
moyenne avec grande probabilité. Une telle propriété peut être obtenue en
contrôlant la queue de distribution de la variable, par exemple au moyen de
moments, comme dans l'inégalité de Tchebychev basée sur la variance, et l'in-
égalité de Chernoff basée sur la transformée de Laplace (moments exponen-
tiels). L'inégalité d'Azuma-Hoeffding exploite une information sur l'oscillation
de la variable (diamètre du support). On a $\mathrm{osc}(f) \le 2\|f\|_\infty$ où

$$
\mathrm{osc}(f) := \sup f - \inf f = \mathrm{diam} \, \mathrm{tre}(\mathrm{support}(f)).
$$

**Lemme 20.3** (Inégalité de concentration d'Azuma-Hoeffding). *Considérons une variable aléatoire* Y : (Ω, F, P) → R intégrable, alors pour tout r ≥ 0,

$$
\mathbb{P}(|Y - \mathbb{E}(Y)| \ge r) \le 2 \exp \left( - \frac{2r^2}{\operatorname{osc}(d_1)^2 + \dots + \operatorname{osc}(d_n)^2} \right)
$$

pour la décomposition télescopique en somme de différences de martingale 4

$$
Y - \mathbb{E}(Y) = \sum_{k=1}^{n} \mathbb{E}(Y | \mathcal{F}_k) - \mathbb{E}(Y | \mathcal{F}_{k-1}) = \sum_{k=1}^{n} d_k
$$

associée à une filtration arbitraire d'interpolation

$$
\{\emptyset, \Omega\} = \mathcal{F}_0 \subset \mathcal{F}_1 \subset \cdots \subset \mathcal{F}_n = \mathcal{F}.
$$

Démonstration. Soit U une v.a.r. telle que E(U) = 0 et a ≤ U ≤ b. La convexité de u ↦→ e^u donne, pour tout t ≥ 0 et tout x ∈ [a, b],

$$
e^{tx} \le \frac{x-a}{b-a} e^{tb} + \frac{b-x}{b-a} e^{ta}.
$$

En posant $p = -a/(b-a)$ et $f(u) = -pu + \log(1-p+pe^u)$ il vient donc

$$
\mathrm{E}(e^{tU}) \le \frac{b}{b-a} e^{ta} - \frac{a}{b-a} e^{tb} = e^{ta} \left( (1-p) + p e^{t(b-a)} \right) = e^{f(t(b-a))}.
$$

À présent on a

$$
f'(u) = -p + \frac{pe^u}{1-p+pe^u} \quad \text{et} \quad f''(u) = p(1-p) \frac{e^u}{(1-p+e^u)^2} \le \frac{1}{4}.
$$

Comme $f(0) = f'(0) = 0$, on en déduit que $f(u) \le u^2/8$ et donc

$$
\mathrm{E}(e^{tU}) \le e^{\frac{t^2}{8}(b-a)^2}.
$$