Probabilité que Z² soit recouvert percolation

Bonjour,

J'étudie un modèle d'automate cellulaire, le modèle de la bootstrap percolation, dont la définition est la suivante :

Présentation du modèle :
- Au temps t=0, indépendamment, chaque site de $\mathbb{Z}^d$ est dit actif avec une probabilité p.
- Si un site est actif au temps t, il le restera au temps $t+1$. Si un site est inactif au temps $t$, il devient actif au temps $t+1$ si et seulement si au moins $k$ de ses voisins sont actifs.

On appelle voisin de $x$ tout élément de $V(x)=\{y\in\mathbb{Z}^d, ||x-y||=1\}$, avec $||.||$ la norme euclidienne.

Je m'intéresse ici tout d'abord au cas $d=k=2$.

Ma question :
Si l'on note $S_t$ l'ensemble des sites de $\mathbb{Z}^2$ actifs à un instant $t$, alors comment montrer que $S_{\infty} = \mathbb{Z}^2$ presque sûrement ?

Les papiers sur le sujet que j'ai trouvé ont tous posés ce même formalisme :
- On note $P_p$ la mesure de probabilité produit de paramètre p associé à la tribu produit de $\{0;1\}^{\mathbb{Z}^2}$.
- Si l'on fixe une boite de taille $L$, alors on note $I(p,L)$ la probabilité que la configuration finale soit égale à la boite (qu'elle soit entièrement "recouverte"par des sites actifs). Je n'ai pas trouvé de définition plus précise malheureusement.

Je pense que l'on peut utiliser deux méthodes : utiliser $I(p,L)$ et montrer que sa limite lorsque $L\rightarrow \infty$ est nulle. Ou alors ne pas l'utiliser.

J'aimerai à terme montrer la même propriété pour $d$ quelconque et $k\leqslant d$.

Ce sur quoi je bloque :

- Formaliser le problème clairement. Les publications que j'ai lues se dispensent du formalisme et montrent d'autre résultats.
- Savoir si les deux méthodes sont possibles et choisir entre les deux.

Je vous remercie par avance.

Réponses

  • Pour la formalisation, tu peux faire comme ceci :
    • Pour tout $x \in \Z^d$, on note $S_t(x)$ l'état du site $x$ à l'instant $t$ : $0$ si le site est inactif, $1$ s'il est actif.
    • Par monotonie, chaque $t\mapsto S_t(x)$ converge presque sûrement vers un certain état $S_\infty(x)$, qui est à priori aléatoire.
    Il reste à montrer qu'en fait $S_\infty(x) = 1$ presque sûrement pour tout $x \in \Z^d$.

    Pour éviter les ennuis, il faudrait que tu précises ta définition de voisins ainsi que la règle d'activation : faut-il qu'exactement $k$ voisins soient actifs ?
  • Merci pour vos réponses.

    J'ai corrigé les imprécisions sur le modèle, mentionnées maintenant en gras.

    @Siméon : Merci pour ces formulations. Cela m'aide à voir plus clair, mais je ne sais pas comment montrer que $S_\infty(x) = 1$ presque sûrement.
    @remark : Non, j'ai trouvé que des résultats admettant celui ci justement, c'est pour cela que je cherche à le démontrer. Excepté une piste que j'ai trouvé dans un papier d'Hugo Duminil-Copin. J'en parle ci-dessous.

    Pour la suite, donc selon ce même papier, on pourrait montrer grâce à l'inégalité FKG que la probabilité que $S_\infty(x) = 1$ est strictement positive, puis montrer qu'elle suit une loi 0-1. Ce papier traite le cas unique $d=k=2$

    Mais je préférerais, n'étant pas encore très familier avec ces notions, trouver une méthode alternative, traitant aussi tout les cas $k\leqslant d$.

    Mais si je n'ai pas le choix, alors tant pis je devrais faire avec, ça m'aidera en plus à mieux comprendre.
  • @remark : désolé, j'étais parti avec $k = 1$. J'ai corrigé mon post en gardant seulement la partie pertinente.

    À vrai dire, le résultat que veut prouver MiKiDe ne me semble pas si évident pour $k \geq 2$. Remarque en passant : il suffit de considérer $k = d$, qui est le cas le plus difficile.
  • On m'a dit il y a environ 25ans (des percolateurs pro) que dans la quasi-totalité des cas de ce genre la proba est toujours 0 ou 1 et que le seul truc à chercher c'est qui des deux. Je poste ce souvenir à toutes fins utiles. C'était suite à une question de ma part qui demandait si des efforts avaient été fais pour construire des graphes tordus et périodiques en tout genre où la proba qu'un chemin existe soit solution d'une équation polynômiale n'ayant aucu ne solution dans [0,1] en vue d'exploiter les.pro bas pour avoir une contradiction dans ZF +INACCESSIBLE
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Je viens de trouver essentiellement la même chose. On peut d'ailleurs faire grossir le rectangle initial beaucoup plus vite.

    P.S. Il faut quand même dire un mot du produit $\displaystyle\prod_{n=2}^\infty (1-q^n)$ pour $q \in [0,1[$.
  • Pas besoin d'évoquer explicitement d'ergodicité, je pense : il lui suffit de voir qu'on peut repartir de plus loin (au nord ou à l'est) si la construction échoue, et ainsi de suite jusqu'à avoir un succès.
  • Merci pour vos réponses !
    Alors effectivement, l'ergodicité ça ne me dis rien, et après lecture, encore moins... Et il me semble que cette notion est trop avancée pour un élève de prépa. J'aimerai donc pouvoir l'éviter.

    Pour ce qui est de cette explication d'Hugo Dominil, je pense l'avoir compris.
    Mais comment donc le démontrer ? J'ai pensé à minorer en suivant le schéma d'Hugo Duminil-Copin. On pourrait montrer par récurrence que la probabilité qu'une boite de taille $n\times n$ soit recouverte est minorée par quelque chose de la forme $p^{\alpha n}, \alpha \in \mathbb{Z}$. Mais par passage à la limite, on perd l'inégalité stricte et je ne peux plus conclure sur le fait que la probabilité est strictement positive.

    @Siméon : d'où vient $\displaystyle\prod_{n=2}^\infty (1-q^n)$? Que représente $q$ dans notre problème ? Ou est-ce juste une remarque pour le calcul ?
  • MiKiDe a écrit:
    Mais comment donc le démontrer ? J'ai pensé à minorer en suivant le schéma d'Hugo Duminil-Copin. On pourrait montrer par récurrence que la probabilité qu'une boite de taille $n \times n$ soit recouverte est minorée par quelque chose de la forme $p^{\alpha n}$ , $\alpha \in \Z$. Mais par passage à la limite, on perd l'inégalité stricte et je ne peux plus conclure sur le fait que la probabilité est strictement positive.

    L'idée ici est plutôt de minorer, indépendamment de $n$, la probabilité pour qu'une boîte $n\times n$ (fixée) soit recouverte. La minoration à laquelle tu pensais est beaucoup trop faible pour cela : elle ne donne par mieux que $0$ (et d'ailleurs elle ne tient pas compte du processus d'activation).
  • @Remark :Oui tout à fait !
    Merci pour les explications je comprend maintenant.

    Je suppose que le calcul de ce produit est cependant très difficile.

    J'ai donc montré que ce produit était strictement positif ( par inégalité, en étudiant d'abord $\ln (1-t) + \frac{t}{1-t}$).
    Donc, si je suis bien le raisonnement, j'ai montré que la probabilité que $\mathbb{Z}^2$ soit recouvert est strictement positive. Il faut maintenant montrer qu'elle suit la loi 0-1 de Kolmogorov ?

    Cependant, j'ai vraiment du mal avec les formulations qui sont sur la page Wikipédia. J'ai trouvé une formulation plus simple et adaptée à la percolation (percolation de liens, modèle de base (pas bootstrap)) :
    Soit A un évènement invariant quand on change l'état d'un nombre fini d'arêtes. Alors $P_p(A) \in \{0;1\}$.

    Je pensais peut être alors reformuler cette formulation en changeant le mot "arrêtes" par "sites". Mais je ne sais pas si c'est vraiment adapté à mon problème d'automate cellulaire.
  • Pourquoi une étude de fonction pour montrer qu'un produit convergent de termes positifs est strictement positif ? Il y a des résultats bien connus (et accessible dès la sup) là-dessus. En particulier ça découle de la convergence de la série de terme général $q^n$, pour $|q| < 1$.
  • @Poirot :Pourquoi une étude de fonction ? Je voulais montrer ce résultats à partir des résultats de sup sur les séries numériques, en appliquant $\ln$ au produit. Comme le produit était un produit de termes inférieur à 1, j'ai eu peur qu'il puisse être égale à 0, le produit étant infini. Il m'a fallu une étude de fonction pour obtenir une inégalité satisfaisante. Comment auriez-vous fait ? Je suis sûrement passé à coté de quelquechose
  • Il suffit de remarquer que, comme la série de terme général $\log(1-q^n)$ converge, et comme les produits partiels sont égaux à $\exp(\sum_{k=2}^n \log(1-q^k))$, si jamais le produit tendait vers $0$, ça voudrait dire que la série diverge vers $-\infty$, contradiction.

    En fait on peut définir la convergence d'un produit infini comme la convergence des produits partiels vers une limite non nulle. Dans ce cas on a des caractérisations agréables que tu peux trouver dans ce document par exemple.
  • D'accord je vois, merci beaucoup, cette méthode est bien mieux que la mienne, je me suis compliqué la tâche pour rien.
  • Après recherche, il semblerait que dans le cas général $k\leq 2$, la probabilité que $S_\infty = \mathbb{Z}^2$ ne suive pas la loi 0-1. En effet, si l'on prend le cas $k=1$, et que l'on se place dans le cas où l'origine par exemple est le seul site actif, alors $S_\infty = \mathbb{Z}^2$, mais si l'on change ce site en inactif, alors $S_\infty = \emptyset$. Donc selon la formulation de la loi 0-1, l'événement associé varie par le changement d'un nombre fini d'état.

    Est-ce ma reformulation qui est fausse ? Ou peut être mon raisonnement ? Peut être que le cas $k=2$ fonctionne quand même ?
  • Oui il l'est je suis d'accord, mais je donnais un (probable) contre-exemple pour lequel la probabilité de l'événement $S_\infty = \mathbb{Z}^2$ ne suit pas la loi 0-1 de Kolmogorov, même si ce cas est évident et facile à montrer.
    Je me demande alors si il est vraiment possible de montrer que cette probabilité suit la loi 0-1.
  • C'était justement cette translation de l'état initial qui me faisait penser que cela ne suivait pas la loi 0-1 selon la formulation que j'ai faite 4 messages avant :
    Soit A un évènement invariant quand on change l'état d'un nombre fini de sites. Alors $P_p(A)\in\{0;1\}$.

    Ce probable contre-exemple mieux expliqué :
    Si on a une configuration initiale $C_0$ dans laquelle seule l'origine est active (ce qui arrive certes avec une probabilité nulle, mais cela ne veut pas pour autant dire que c'est impossible ?) . Dans ce cas, bien sûr, $S_\infty = \mathbb{Z}^2$. Maintenant, si l'on considère une configuration $C_1$ qui est la configuration $C_0$ dans laquelle l'origine a été rendue inactive. Dans notre cas, $S_\infty = \emptyset$. Ici mon événement n'est donc pas invariant quand on change l'état d'un nombre fini de sites.
  • D'accord, je vois.
    Est-ce cependant possible de montrer ce résultat sans invoquer l'ergodicité ?
  • @remark : Tu peux détailler ton usage du mot "ergodicité" ? Je ne connais que la définition dans les systèmes dynamiques. Tu veux dire que l'action de $\mathbb{Z}^2$ sur l'ensemble des configurations, muni de la mesure produit, est ergodique ? Si oui, comment est-ce que cela implique que la probabilité recherchée est $0$ ou $1$ ?
  • Oh, oui. Merci pour le détail !
  • J'ai tapé ergodicité mais j'ai rien compris (gros calculs avec sommes et intégrales) aux pages wiki. Mais @Georges, je ne sais pas si ça a à voir avec de l'ergodicité, mais je te donne un "argument maison": si tu as un graphe, des conditions aléatoires diverses pour que ses lampes (qui sont ses sommets) s'allument, qu'une fois allumées, elles restent allumées et que ce qui provoque l'allumage ne dépend que du tirage au sort + des voisines dans le graphe et si de plus ta situation est "symétrique", ie tu peux prouver d'une manière ou d'une autre que la proba pour chaque lampe qu'elle s'allume un jour est un même nombre $p$, et si, :-D encore de plus, quelle que soit l'exigence (un entier n) il existe des ensembles aussi grand que tu veux de lampes à distances (plus crout chemin qui les joint) 2 à 2 >n, alors la proba que tout le monde finisse par s'allumer est forcément 0 ou 1.

    En effet, deux lampes "à l'infini" (ANS ou ultrafiltres) ont des propensions de s'allumer à une date infiniment petite devant la distance qui les sépare qui sont indépendantes, autrement dit la proba qu'elles s'allument toutes deux "pas trop tard" est $\leq p^2$. (C'est une sorte "d'axiome, enfin plutôt de théorème de localité..".)

    Donc si $p<1$ alors la proba de "le monde entier s'éclaire" est $0$. Et si $p=1$ alors par sigma-additivité***, la proba que le monde entier s'éclaire est $1$ (si nombre de lampes dénombrable).

    Pour choisir entre les deux, faut être spécialiste de probas. La situation présente remplit évidemment toutes ces conditions.

    *** bête, gratuite et méchante :-D Elle est bien pratique, mais c'est de la triche.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Merci beaucoup remark, j'étais passé complètement à côté du fait que c'est DANS LA DEFINITION que se trouve {0;1}. Je croyais que ça se déduisait d'une éventuelle définition que je ne connaissais pas de manière élaborée.

    edit: pour être plus précis, je pensais que "ergodique" veut dire blabla et qu'un gros théorème célèbre dit "si ergodique alors ..$\in \{0;1\}$". C'est pourquoi je n'ai pas compris où voulait en venir wiki et ai abandonné la lecture. La réalité que tu me signales est que ergodique veut dire par définition "blabla et ..$\in \{0;1\}$" et que le travail consiste ou bien à prouver qu'un machin est ergodique ou qu'un truc ergodique a son tel machin qui vaut 1 (ie éliminer 0) par exemple.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.