Présentation du modèle Cas des arbres Cas du réseau carrébudzinski/tipe_slides.pdf · 2019. 9. 21. · Cas des arbres Cas du réseau carré Déﬁnitions Préliminaires probabilistes

Présentation du modèleCas des arbres

Cas du réseau carré

Percolation

Thomas Budzinski

Lycée Louis le Grand

18 Janvier 2012

Thomas Budzinski Percolation



Sommaire

1 Présentation du modèleDéfinitionsPréliminaires probabilistesTransition de phase

2 Cas des arbresDéfinitionCalcul de la probabilité critiquePourquoi les arbres ?

3 Cas du réseau carréThéorèmes sur les régimes sous-critique et sur-critiqueRéseau dualCalcul de la probabilité critique




DéfinitionsPréliminaires probabilistesTransition de phase

Objectifs

Modéliser un milieu aléatoire :Solide poreuxMélange conducteur-isolantFeux de forêt...

Etudier les transitions de phase :Changement d’étatsFerromagnétisme





Graphes

DéfinitionUn graphe (simple, non-orienté) G est un couple (V ,E), oùV est un ensemble et E un ensemble de parties de V decardinal 2.Les éléments de V sont appelés sommets, les élémentsde E sont appelés arêtes.Si {x , y} ∈ E , x et y sont dits voisins.Le degré de x est le nombre de ses voisins.On dit que x et y sont reliés si il existe x0 = x , x1, ..., xk = ytels que pour tout i ∈ [[0, k ]], xi et xi+1 sont voisins. On notealors d(x , y) le plus petit entier k tel qu’il existe de tels xi .Si x ∈ v , on notera Cx la composante connexe du graphecontenant x : c’est l’ensemble des sommets reliés à x .





Quelques exemples typiques

Réseau carré Réseau triangulaire

Réseau cubique Un exemple plus exotique





Qu’est-ce-que la percolation ?

On considère un graphe infini G = (V ,E), localement fini,connexe (en général assez régulier)On se fixe p ∈ [0,1]E ′ sous-ensemble aléatoire de E tel que chaque arêteappartient à E avec probabilité p, sans dépendance entreles arêtes.Les arêtes de E ′ sont dites ouvertes, les autres sont ditesfermées.Il y a percolation si (V ,E ′) admet une composanteconnexe infinie.On notera ψ(p) la probabilité qu’il y ait percolation et, sitous les sommets jouent le même rôle, θ(p) la probabilitéque la composante connexe contenant l’origine soit infinie.





Exemple

Réseau carré, p = 12





Inégalité de Boole

PropositionSoient A0,A1, ...,An, ... des évènements. Alors :

P(∃n ∈ N,An) ≤∑n∈N

P(An)

Démonstration.

P(∃n ∈ N,An) = P(A1) + P(A2\A1) + P(A3\(A1 ∪ A2)) + ...

≤ P(A1) + P(A2) + P(A3) + ...





Loi du 0-1 de Kolmogorov

ThéorèmeSoit A un évènement invariant si on change l’état d’un nombrefini d’arêtes. Alors P(A) ∈ {0,1}.

En théorie de la mesure, les évènements sont "engendrés"par une certaine famille d’évènements, ici ceux qui nedépendent que d’un nombre fini d’arêtes.Or, A est indépendant avec chacun de ces évènements. Aest donc indépendant avec lui-même, soit :

P(A) = P(A ∩ A) = P(A)2





Inégalité FKG

DéfinitionUn évènement est dit croissant si pour toute configuration où Ase produit et toute arête e fermée dans cette configuration, Ase produit toujours si e devient ouverte.

PropositionSoient A et B des évènements croissants. Alors :

P(A ∩ B) ≥ P(A)P(B)

Démonstration : on le montre par récurrence pour desévènements qui ne dépendent que d’un nombre fini n d’arêtes(par récurrence sur n), puis un théorème de convergencepermet de passer au cas général.





Transition de phase

ThéorèmeIl existe pc ∈ [0,1] tel que :

Si p < pc , alors ψ(p) = 0Si p > pc , alors ψ(p) = 1

De plus, si tous les sommets jouent le même rôle,pc = inf {p ∈ [0,1], θ(p) > 0}.pc (qui dépend du graphe) est appelée probabilité critique.

Démonstration.Si θ(p) > 0, ψ(p) ≥ θ(p) > 0 donc ψ(p) = 1 d’après la loidu 0-1.Si θ(p) = 0, ψ(p) ≤

∑x∈V P(|Cx | =∞) = 0





La fonction θ

p

θ(p)

0

1

1pc

PropositionSi les degrés des sommets sont bornés (par M), pc > 0.





pc > 0

Démonstration.Soit n ∈ N : si C0 est infinie, elle contient un cheminauto-évitant de longueur n issu de 0.Soit P(n) l’ensemble de ces chemins et σ(n) leur nombre :

θ(p) ≤ Pp(Il existe c ∈ P(n) ouvert)

≤∑

c∈P(n)

Pp(c est ouvert)

= σ(n)pn

≤ Mnpn

donc pour p < 1M , θ(p) = 0, d’où pc ≥ 1

M .




DéfinitionCalcul de la probabilité critiquePourquoi les arbres ?

Arbres

DéfinitionUn arbre est un graphe sans cycles.L’arbre régulier de degré d , noté Td est l’arbre dont tous lessommets sont de degré d .

Exemple (d = 3) :





Calcul de pc

Théorème

pc(Td) =1

d−1

Démonstration.On ne change pas la valeur de pc en supprimant une "branche"de l’arbre. On obtient ainsi l’arbre T ′d :

01 d − 1

2 3 . . . . .

. . . . .T ′d T ′d





Démonstration (suite)

Démonstration.

01

2d-1

. . . . .T ′d T ′d T ′d

Si C ensemble de sommets, r(C) = maxx∈Cd(0, x).Pour tout n, on pose un(p) = Pp(r(C0) < n).(un(p)) est croissante et majorée donc converge, et1− θ(p) = limn→∞ un(p).r(C0) < n ssi pour tout i ∈ [[1,d − 1]], l’arête {0, i} estfermée OU {0, i} est ouverte et ri(Ci) < n − 1, d’où :{

un+1(p) = (1− p + pun(p))d−1

un(0) = 0





Démonstration (fin)

Démonstration.

On pose donc f (x) = (1− p + px)d−1, définie sur [0,1].(un(p)) converge vers le plus petit point fixe de f , doncθ(p) > 0 ssi f admet un point fixe dans [0,1[.

0

1

1 0

1

1

f est convexe, f (0) > 0 donc θ(p) > 0 ssi f ′(1) > 1.f ′(1) = p(d − 1), donc θ(p) > 0 ssi p > 1

d−1 .





Pourquoi étudier les arbres ?

Intérêt en soi : arbres généalogiques :Probabilité d’extinction de la descendance d’un individu :13%Probabilité d’extinction de son nom de famille : 92%

Donne des informations sur la percolation sur d’autresgraphes : en grande dimension, les réseaux se comportentsouvent comme des arbres :

pc(Zd ) ∼ 12d

Exposants critiques : pour d ≥ 6, ils prennent la mêmevaleur pour Zd que pour les arbres. (conjecture)Autres processus aléatoires (marches aléatoires...)




Théorèmes sur les régimes sous-critique et sur-critiqueRéseau dualCalcul de la probabilité critique

Décroissance exponentielle et unicité de lacomposante connexe infinie

ThéorèmeSi p < pc , il existe ξ(p) > 0 tel que :

Pp(r(C0) ≥ n) = O(e−ξ(p)n)

Conséquence : Pp(|C| ≥ n) = O(e−ξ(p)√

(n))En particulier,

∑n∈N nPp(|C| = n) <∞ :

La taille moyenne des composantes connexes est finie.

ThéorèmeSi p > pc , la composante connexe infinie est presque sûrementunique.





Réseau dual

Etant donné un graphe planaire G, on peut définir songraphe dual G∗ :

Les sommets de G∗ sont les "faces" délimitées par lesarêtes de G.Deux sommets de G∗ seront reliés si les facescorrespondantes sont séparées par une arête.





Autodualité

Le réseau carré L2 est autodual :

De plus, à chaque arête e de L2, on peut associer une arête e∗

du dual L∗. Chaque sous-graphe G de L2 induit donc unsous-graphe G∗ de L∗, tel que e∗ est une arête de G∗ ssi en’est pas une arête de G.





pc ≤ 12

Si G est obtenu par percolation avec probabilité p, G∗ estun graphe obtenu par percolation avec probabilité 1− p.On pose S(n) = L2 ∩ [0,n + 1] ∗ [0,n] etS∗(n) = L∗ ∩ [−1

2 ,n + 12 ] ∗ [

12 ,n −

12 ].

On note An l’évènement : "Il existe un chemin ouverttraversant S(n) de haut en bas." et A∗n l’évènement : "Ilexiste un chemin ouvert dans le dual traversant S∗(n) degauche à droite."S(n) et S∗(n) sont isomorphes, donc P1−p(A∗n) = Pp(An)et, en particulier, P 1

2(A∗n) = P 1

2(An).

A∗n se produit ssi An ne se produit pas, d’où :

P 12(An) + P 1

2(A∗n) = 1





pc ≤ 12 (suite et fin)

On en déduit P 12(An) =

12 .

Cependant, pour tout k ∈ [[0,n]], si (k ,0) est relié à unsommet de la forme (l ,n + 1), alors r(C(k ,0)) ≥ n + 1,donc, si p < pc :

Pp(An) ≤n∑

k=0

Pp(r(C(k ,0)) ≥ n + 1)

≤ A(n + 1)e−ξ(p)n

→ 0

d’où pc ≤ 12





pc ≥ 12 (lemme)

On note T (n) = [[0,n]]2\{(0,0), (0,n), (n,0), (n,n)} et on noteAh(n) l’évènement : "Il existe un chemin ouvert infini partantd’un sommet (k ,n) avec 1 ≤ k ≤ n − 1 et ne repassant pasdans T(n)."

LemmeSi p > pc , Pp(Ah(n))→ 1 quand n→∞.

Démonstration.On définit de même Ab(n), Ag(n) et Ad(n) : quand n→∞ :

Pp(Ah(n) ∪ Ab(n) ∪ Ag(n) ∪ Ad(n))→ 1

De plus, Pp(Ah(n)) = Pp(Ab(n)) = Pp(Ag(n)) = Pp(Ad(n))





pc ≥ 12 (preuve du lemme)

Démonstration.

(1− Pp(Ah(n)))4 =∏

i∈{h,b,g,d}

Pp(Aci (n))

≤ Pp(⋂

i∈{h,b,g,d}

Aci (n))

= 1− Pp(Ah(n) ∪ Ab(n) ∪ Ag(n) ∪ Ad(n))→ 0

donc Pp(Ah(n))→ 1.

On suppose maintenant pc <12 . Alors pour p = 1

2 , il y apercolation sur L2 et sur L∗.





pc ≥ 12 (suite)

On pose T ∗(n) = T (n) + (12 ,

12) et on définit A∗h(n) etc...

Pour n assez grand :

P 12(Ah(n) ∩ Ab(n) ∩ A∗g(n) ∩ A∗d(n)) ≥

12

Ch

Cb

C∗g

C∗d





pc ≥ 12 (fin)

Par unicité de la composante connexe infinie dans L2, Chest presque sûrement relié à Cb et, par unicité dans L∗, C∗gest presque sûrement relié à C∗d .Cependant, dans ce cas, les "raccords" se "croisent" dansT (n), ce qui est impossible, d’où la contradiction, doncpc ≥ 1

2 .

Théorème

pc(L2) = 12


Annexe Bibliographie

Bibliographie

G. Grimmett.Percolation.Springer-Verlag, 1989.

A. Kolmogorov.Foundations of the Theory of Probability.AMS Chelsea Publishing, 1956.

W. WernerLacets et invariance conformeLeçons de mathématiques d’aujourd’hui, volume 3,p.139-164, Cassini, 2007

P.G. de Gennes.La percolation, un concept unificateur.La Recherche, 7, 921-926, 2000.


Documents

Présentation du modèle Cas des arbres Cas du réseau carrébudzinski/tipe_slides.pdf · 2019. 9. 21. · Cas des arbres Cas du réseau carré Déﬁnitions Préliminaires probabilistes