226
16 Percolation
Soit θ > 0 tel que ϕ(θ) < 1. Pour tout r > 0, par l’inégalité de Markov,
P(T r) = P(ϕ(θ)
−T
ϕ(θ)
−r ) ϕ(θ)
r
E(ϕ(θ)
−T ) ϕ(θ)
r e
θ .
L’inégalité de convexité 1 + x e
x valable pour tout x ∈ R donne
ϕ(θ) = e
−θ (1 − p + pe
θ )
n−1 = e
−θ
1 +
λ(e
θ
− 1)
n
n−1
e
λ(e
θ −1)−θ
(notons que e
λ(e
θ −1) est la transformée de Laplace de Poi(λ)). La fonction
θ ∈ R → λ(e
θ
− 1) − θ atteint son minimum en θ ∗ = − log(λ) > 0, et
ϕ(θ ∗ ) = e
−α où α := 1 − λ + log(λ) > 0, d’où
P(T r) ϕ(θ ∗ )
r e
θ∗ = e
−rα+θ∗ = λ
−1 e
−αr .
Par conséquent, pour tout c > 0,
P(|G(v)| c log(n)) P(N c log(n)) = P(T c log(n)) λ
−1 n
−αc .
À présent, comme les v.a. (G(v)) v∈V sont identiquement distribuées, on a
P
max
v∈V
|G(v)| c log(n)
v∈V
P(|G(v)| c log(n))
= nP(|G(1)| c log(n))
λ
−1 n
1−αc ,
d’où le résultat en prenant c > 1/α.
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 facile en
principe l’étude de propriétés probabilistes. En informatique, en télécommunication, mais aussi en électricité, un réseau
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
6 .
Dans le cas euclidien, le graphe est également un réseau au sens de la géométrie
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
5. «Network» en anglais.
6. «Random networks» en anglais.
7. «Lattice» en anglais.