Probabilités

La percolation

Le seuil critique des modèles aléatoires

L'idée en une phrase

On ouvre au hasard les cases d'une grille, chacune avec la même probabilité p ; tant que p est petit, on n'obtient que des îlots ; au-delà d'une valeur précise, le seuil critique p_c, un chemin traverse soudain la grille de part en part.

Le mot vient du latin percolare, « filtrer à travers » : c'est ce que fait l'eau dans la mouture d'une cafetière. Le hasard est local (chaque case décide seule, sans regarder ses voisines), mais le résultat est global (existe-t-il un passage d'un bord à l'autre ?). Toute la richesse du sujet tient dans ce contraste : des décisions indépendantes et minuscules produisent un basculement collectif brutal, comme l'eau qui gèle d'un coup à 0 °C. Les physiciens appellent cela une transition de phase.

La grille respire : p oscille lentement autour du seuil. case ouverte plus grand amas amas qui relie la gauche à la droite.

probabilité d'ouverture p—

plus grand amas (part des cases)—

traversée gauche → droite—

Le vocabulaire, une fois pour toutes

Mot	Sens
Site	Une case (ou un nœud) de la grille. En percolation par sites, ce sont les cases qu'on ouvre au hasard.
Lien	Un trait reliant deux nœuds voisins. En percolation par liens, ce sont les traits qu'on ouvre au hasard.
Amas	Un groupe de sites ouverts qui se touchent (par un côté, pas par un coin) : on peut aller de l'un à l'autre sans sortir des cases ouvertes.
Amas traversant	Un amas qui touche deux bords opposés de la grille : l'eau peut passer.
Seuil critique p_c	La valeur de p qui sépare, sur une grille infinie, le régime « îlots seulement » du régime « un amas infini existe ».

Ouvrir les cases une à une

Question : que se passe-t-il, concrètement, quand on augmente p petit à petit ?

Chaque case reçoit une fois pour toutes un nombre tiré au hasard entre 0 et 1. Elle est ouverte si ce nombre est inférieur à p. Faire glisser le curseur ne retire donc jamais rien : augmenter p ne fait qu'ouvrir de nouvelles cases, et l'on voit les îlots grossir puis se souder. Ce procédé s'appelle le couplage : toutes les valeurs de p partagent le même tirage.

ouverte plus grand amas amas qui relie le haut au bas eau versée par le haut.

Pour ce tirage : part des cases occupée par le plus grand amas en fonction de p (bleu). La diagonale grise est la part de cases ouvertes. Le trait rouge marque le seuil p* de ce tirage, la barre grise la valeur actuelle du curseur.

côté L

cases ouvertes mesurées (attendu : p)—

nombre d'amas—

plus grand amas—

traversée haut → bas—

seuil p* de ce tirage—

eau—

Ce qu'il faut retenir. Sur la courbe de droite, le plus grand amas reste minuscule, puis bondit en un intervalle très court : c'est là que les îlots se soudent. Chaque tirage a son propre seuil p* (la traversée existe exactement quand p > p*), mais ces seuils se regroupent tous autour de 0,59 : refaites quelques tirages pour le constater. La planche suivante mesure ce regroupement.

Où se trouve le seuil ?

Question : sur une grille finie, le seuil varie d'un tirage à l'autre. Comment en déduire une valeur unique ?

L'ordinateur répète des milliers de fois l'expérience de la planche 1, sur des grilles de côté L = 16, 32, 64 et 128. Pour chaque tirage, il ouvre les cases dans un ordre aléatoire et note la proportion ouverte au moment exact où la traversée apparaît (algorithme de Newman et Ziff, 2000). La courbe tracée est la probabilité de traversée P_L(p) : la part des tirages qui traversent à la valeur p.

Probabilité de traversée selon p. L = 16 L = 32 L = 64 L = 128. Pointillé rouge : p_c = 0,592746.

Largeur de la zone de bascule (écart-type des seuils) en fonction de L, en échelles logarithmiques. Bleu : mesure et droite ajustée ; vert pointillé : pente théorique −3/4.

—

L = 16 : seuil moyen (écart-type)—

L = 32—

L = 64—

L = 128—

P₁₂₈(p_c) mesurée (limite : 1/2)—

pente mesurée (théorie −0,75)—

Deux faits apparaissent. D'abord, les courbes se resserrent : plus la grille est grande, plus la bascule est raide, et à la limite d'une grille infinie elle devient une marche d'escalier exactement en p_c. Ensuite, la largeur de la bascule diminue comme une puissance de la taille :

largeur ∝ L^−1/ν, avec ν = 4/3 en dimension 2.

La pente mesurée sur la figure de droite est un peu moins raide que −3/4 (autour de −0,7) : les petites grilles subissent des corrections de taille finie, qui s'estompent quand L grandit. L'exposant ν, appelé exposant de longueur de corrélation, ne dépend pas de la forme du réseau : c'est le premier signe de l'universalité que l'on retrouvera en planche 5.

Ce qu'il faut retenir. Pour les sites d'une grille carrée, aucune formule ne donne p_c : on ne le connaît que par simulation, p_c ≈ 0,592746. On le cerne en faisant grandir la grille et en regardant où les courbes convergent. En p_c, une grande grille carrée est traversée une fois sur deux, par symétrie entre « haut-bas » et « gauche-droite ».

Le miroir des liens : pourquoi 1/2 exactement

Question : y a-t-il des cas où l'on connaît le seuil exactement, sans simulation ?

Oui, pour la percolation par liens sur la grille carrée : ce sont les traits entre nœuds voisins qui sont ouverts avec la probabilité p. L'astuce est de dessiner le réseau dual : un nœud rouge au centre de chaque carreau, et un trait rouge qui croise chaque trait bleu. On décide que le trait rouge est ouvert exactement quand le trait bleu qu'il croise est fermé.

Alors, une règle de bon sens s'impose : ou bien un chemin bleu relie la gauche à la droite, ou bien un mur rouge relie le haut au bas et le bloque, jamais les deux, jamais aucun des deux. Or le réseau rouge, tourné d'un quart de tour, est identique au bleu, et ses traits sont ouverts avec la probabilité 1 − p. Il en découle :

P(p) + P(1 − p) = 1, donc P(1/2) = 1/2 exactement.

liens ouverts du réseau (bleu épais : chemin gauche → droite) liens ouverts du dual (rouge épais : mur haut → bas). Les colonnes extrêmes, en bleu pâle, sont les bords gauche et droit ; les rangées extrêmes du dual, en rose, sont ses bords haut et bas.

taille n

ce tirage—

P(p) mesurée—

P(1 − p) mesurée—

somme (exact : 1)—

tirages « les deux » ou « aucun »—

écart à 1/2 en p = 1/2—

Ici la grille bleue a n + 1 colonnes et n rangées, la rouge n colonnes et n + 1 rangées : c'est ce léger décalage qui rend les deux réseaux exactement superposables après rotation, si bien que l'égalité vaut pour toute taille n, pas seulement à la limite.

Ce qu'il faut retenir. La dualité montre que la grille carrée à liens est son propre miroir, et que le point de symétrie p = 1/2 est le seul candidat pour le seuil. Le transformer en démonstration complète a demandé vingt ans : Harris (1960) a prouvé p_c ≥ 1/2, Kesten (1980) a prouvé p_c = 1/2. Le même argument donne p_c = 1/2 pour les sites du réseau triangulaire.

Un réseau sans boucles : l'arbre de Bethe

Question : existe-t-il un réseau sur lequel tout se calcule, seuil et amas infini compris ?

Dans l'arbre de Bethe, chaque nœud a z voisins et il n'y a aucune boucle : partant de la racine, chaque branche se divise en z − 1 branches nouvelles. Chaque lien est ouvert avec la probabilité p : explorer l'amas de la racine revient à suivre une généalogie où chaque individu a en moyenne m = p(z − 1) enfants. La famille survit à jamais seulement si m > 1, d'où le seuil exact :

p_c = 1 / (z − 1).

On calcule aussi la probabilité P_∞ que la racine appartienne à un amas infini. Si Q est la probabilité qu'une branche s'éteigne, une branche s'éteint quand chacune de ses z − 1 sous-branches est fermée ou s'éteint :

Q = (1 − p + pQ)^z−1, P_∞ = 1 − (1 − p + pQ)^z.

Les premiers étages de l'arbre (racine au centre). amas de la racine autres liens ouverts ; liens fermés en gris pâle.

P_∞ exacte (arbre infini) survie jusqu'à 25 étages, exacte (tirets) simulation de généalogies sur 25 étages, avec barres ± 2 écarts-types. Pointillé rouge : p_c.

voisins z

seuil exact 1/(z − 1)—

enfants par nœud m = p(z − 1)—

P_∞ exacte—

contrôle z = 3 : Q = ((1 − p)/p)²—

simulation : plus grand écart (en σ)—

amas de la racine dans la figure—

Juste au-dessus du seuil, P_∞ croît linéairement : P_∞ ∝ (p − p_c)^β avec β = 1. Sur la grille plane, on sait (Smirnov et Werner, 2001) que β = 5/36 ≈ 0,14 : l'amas infini naît avec une pente verticale, bien plus brutalement. L'arbre est le modèle « de champ moyen » : juste pour les dimensions 6 et plus, approximatif en dessous, parce que les boucles y comptent.

Ce qu'il faut retenir. Sans boucles, la percolation devient une histoire de survie de lignée, résolue en une équation. La simulation (orange) suit la courbe exacte à 25 étages (tirets), et non la courbe de l'arbre infini : près du seuil, une lignée met très longtemps à s'éteindre, et 25 générations ne suffisent pas pour trancher.

Au seuil, le hasard n'a plus d'échelle

Question : à quoi ressemble le monde exactement au point critique, et pourquoi s'y intéresser ?

Loin du seuil, il existe une taille typique : les îlots mesurent quelques cases (sous le seuil) ou les trous de l'amas géant mesurent quelques cases (au-dessus). Cette taille, la longueur de corrélation ξ, grandit sans limite quand p approche p_c. Au seuil, il n'y a donc plus aucune taille privilégiée : des amas de toutes les tailles coexistent, emboîtés comme une dentelle. Trois expériences le montrent.

Chaque case porte un arbre avec la probabilité d (la densité). On allume toute la colonne de gauche ; le feu passe d'un arbre à son voisin direct. Brûle-t-il un coin ou toute la forêt ?

arbre en feu brûlé.

Part des arbres brûlés selon la densité (moyenne de 20 forêts de 100 × 100 par point, en bleu). Le losange orange est la forêt en cours, le pointillé rouge p_c.

densité d

arbres brûlés—

durée de l'incendie—

bord droit atteint—

Sous 0,55, le feu ne brûle que quelques pour cent des arbres ; au-dessus de 0,65, plus de 90 %. Entre les deux, l'incendie dure le plus longtemps : en moyenne environ 210 étapes vers 0,60, contre environ 30 à 0,50 et 110 à 0,90, car le feu doit serpenter dans un amas critique tortueux. C'est ce ralentissement critique qui intéresse les forestiers, les épidémiologistes (densité de personnes susceptibles d'être contaminées) et les ingénieurs des matériaux (proportion de grains conducteurs dans un isolant).

Un tirage de 300 × 300 cases exactement en p_c, regardé à trois grossissements. Le plus grand amas est en rouge. À chaque zoom, on retrouve la même allure : des bras, des trous de toutes tailles, des culs-de-sac.

De gauche à droite : la grille entière, puis le carré central agrandi 2 fois, puis 4 fois. plus grand amas autres amas.

Masse M du plus grand amas en fonction de L, en échelles logarithmiques, pour L = 32, 64, 128 et 256. Bleu : mesures et droite ajustée ; vert pointillé : pente 91/48 ; gris : pente 2 d'un objet plein.

dimension mesurée D—

valeur exacte 91/481,8958

tirages accumulés—

plus grand amas du tirage—

Si l'amas était plein, doubler le côté de la grille quadruplerait sa masse (pente 2). Il la multiplie seulement par 2^1,896 ≈ 3,72 : l'amas critique est un fractal, de dimension D = 91/48, un objet entre la ligne et la surface.

On compte les amas d'une grille de 256 × 256 (repliée sur elle-même pour supprimer les bords) selon leur taille s, et l'on trace leur nombre par case n_s en échelles logarithmiques. Au seuil, on obtient une droite : une loi de puissance, sans taille typique.

n_s ∝ s^−τ, τ = 187/91 ≈ 2,055.

Bleu : n_s mesuré (tailles groupées par puissances de 2). Vert pointillé : pente −187/91. Ajustement sur les tailles 16 à 4 096.

τ mesuré—

τ exact 187/912,0549

grilles accumulées—

Écartez p du seuil : la droite se casse vers le bas au-delà d'une certaine taille. Cette coupure est la trace de la longueur de corrélation ξ : sous le seuil, aucun amas ne dépasse beaucoup ξ^D cases. Au seuil, la coupure recule jusqu'à la taille de la grille.

Ce qu'il faut retenir. Le seuil dépend du réseau (0,5927 pour les sites carrés, 1/2 pour les liens carrés, 0,3116 pour les sites cubiques), mais les exposants ν = 4/3, β = 5/36, D = 91/48, τ = 187/91 sont les mêmes pour tous les réseaux plans : c'est l'universalité. Au point critique, les détails microscopiques s'effacent et seule compte la dimension de l'espace.

Une table des seuils

Réseau	Percolation	Seuil p_c	Statut
Carré	liens	1/2	exact (Kesten, 1980)
Carré	sites	≈ 0,592746	numérique seulement
Triangulaire	sites	1/2	exact (dualité)
Triangulaire	liens	2 sin(π/18) ≈ 0,347296	exact (Sykes et Essam, 1964)
Hexagonal (nid d'abeilles)	liens	1 − 2 sin(π/18) ≈ 0,652704	exact (dual du triangulaire)
Hexagonal	sites	≈ 0,697043	numérique
Cubique (3 D)	sites	≈ 0,311608	numérique
Cubique (3 D)	liens	≈ 0,248812	numérique
Arbre de Bethe, z voisins	liens ou sites	1/(z − 1)	exact
Graphe aléatoire d'Erdős-Rényi	arêtes	c = 1 (degré moyen)	exact (1960)

Repères historiques

1957Broadbent et Hammersley inventent le modèle et le mot : ils étudiaient comment un gaz traverse le charbon actif d'un masque à gaz.
1960Harris démontre que le seuil des liens carrés vaut au moins 1/2. Erdős et Rényi décrivent la naissance de la composante géante dans un graphe aléatoire.
1964Sykes et Essam obtiennent par dualité les seuils exacts des réseaux triangulaire et hexagonal.
1980Kesten démontre que le seuil des liens carrés vaut exactement 1/2.
1992Cardy prédit la formule exacte de la probabilité de traversée d'un rectangle au seuil, quelle que soit sa forme.
2000Newman et Ziff publient l'algorithme qui fournit toute la courbe de traversée en un seul passage par tirage, utilisé en planche 2.
2001Smirnov démontre la formule de Cardy pour les sites triangulaires ; avec Werner, il en déduit les exposants β = 5/36 et ν = 4/3. Médailles Fields pour Werner (2006), Smirnov (2010) et Duminil-Copin (2022), tous trois en partie pour ces travaux.

En trois idées

Un basculement brutal

Des ouvertures indépendantes produisent une transition nette : en dessous de p_c, des îlots ; au-dessus, un amas infini. Sur une grille finie, la bascule a une largeur qui décroît comme L^−3/4.

Quelques seuils exacts

Quand le réseau est son propre miroir (liens carrés, sites triangulaires), la dualité impose p_c = 1/2. Quand il n'a pas de boucles (arbre de Bethe), une équation de survie donne p_c = 1/(z − 1).

Au seuil, l'universalité

Au point critique, plus d'échelle : l'amas est fractal (D = 91/48), les tailles suivent une loi de puissance (τ = 187/91), et ces nombres sont les mêmes pour tous les réseaux plans.

Pour aller plus loin

Les exposants critiques en dimension 2. Près du seuil : P_∞ ∝ (p − p_c)^5/36, ξ ∝ |p − p_c|^−4/3, taille moyenne des amas finis ∝ |p − p_c|^−43/18. Ces exposants sont reliés entre eux : par exemple D = 2 − β/ν = 2 − (5/36)/(4/3) = 91/48, et τ = 1 + 2/D = 187/91.

La formule de Cardy. Au seuil, la probabilité de traverser un rectangle ne dépend que du rapport de ses côtés, et elle est invariante par toute transformation qui conserve les angles (invariance conforme). Pour un carré, elle vaut 1/2.

Au-dessus de six dimensions, les boucles deviennent négligeables et les exposants sont ceux de l'arbre de Bethe : β = 1, ν = 1/2, τ = 5/2.

Liens avec d'autres pages du cahier. La composante géante du graphe d'Erdős-Rényi (théorie des graphes) est la percolation sur un graphe sans géométrie ; le modèle d'Ising (physique) présente une transition de phase de même nature : Fortuin et Kasteleyn ont montré que la percolation et le modèle d'Ising sont deux membres (q = 1 et q = 2) d'une même famille, le modèle des amas aléatoires.