Hugo Vanneuville

VERSION COURTE

Regardons une fonction f : {0,1}^n →{0,1}, que l’on voit comme une règle de décision. On peut par exemple penser au processus de décision par majorité. Dans cet exposé, j’essaierai d’expliquer pourquoi le processus par majorité est dans un certain sens stable alors qu’un processus par majorité itérée est sensible au bruit, selon un sens précis qui a été introduit par Benjamini, Kalai et Schramm. Les motivations viennent plutôt de la physique statistique (il s’agit d’introduire des techniques non spectrales pour étudier des phénomènes d’instabilité en percolation), mais dans l’exposé je vais seulement considérer les modèles de décision ci-dessus. En particulier, j’aimerais expliquer comment une structure fractale (ce qui ici veut juste dire « itérative ») peut jouer un rôle dans le phénomène de sensibilité au bruit.

VERSION LONGUE

A) Regardons les deux processus de choix suivants, traduits ici dans les termes d’une élection : *il y a exactement deux candidat.e.s, qu’on note 0 et 1, *il y a n personnes qui votent, *on dispose donc d’un n-uplet x \in {0,1}^n (tout le monde vote, et il n’y a pas de vote blanc…), *en France on choisirait qui gagne avec la fonction Maj(x)=indicatrice de l’événement qu’il y a plus de 1 que de 0, *on va aussi dans cet exposé regarder la façon de choisir itérative suivante. Supposons que n=3^k pour un certain k. On regroupe les n personnes en 3^{k-1} groupes de 3, chacun de ces groupes de 3 prend une décision à la majorité, on se retrouve ainsi avec un élément de {0,1}^{3^{k-1}}, et on itère le processus jusqu’à ce que k=0. On a alors décidé qui avait gagné. On note IMaj=indicatrice que 1 gagne dans ce processus.

B) Supposons que x est tiré aléatoirement et uniformément dans {0,1}^n : chaque personne vote pour 1 ou 0 avec proba 1/2, indépendamment des autres. Alors, on peut montrer que lorsque n tend vers l’infini, Maj et IMaj deviennent indépendants l’un de l’autre. C’est une conséquence d’un phénomène plus général : on peut montrer que dans un certain sens Maj est un processus de décision stable tandis que IMaj est très sensible au bruit : si y est une version bruitée de x, alors lorsque n tend vers l’infini, IMaj(x) et IMaj(y) deviennent indépendants l’un de l’autre.

C) La notion de sensibilité au bruit est apparue dans l’étude de la percolation dans un article de Benjamini, Kalai et Schramm en 1999, où ils montrent que la percolation planaire est sensible au bruit. Des théorèmes quantitatifs puis optimaux ont ensuite été obtenus par Schramm—Steif et Garban—Pete—Schramm. Tous ces travaux reposent sur des méthodes spectrales. De telles méthodes sont très riches mais ont aussi des limitations (notamment, on ne sait pas comment les étendre à d’autres modèles de physique statistique). Avec Vincent Tassion, on a développé des méthodes non spectrales, qui reposent sur des inégalités différentielles. Je vais essayer des les expliquer non pas dans le cas de la percolation mais dans le cas du modèle plus simple de IMaj défini ci-dessus. En particulier, j’aimerais expliquer comment la structure fractale (ce qui ici veut juste dire « itérative ») de IMaj joue un rôle dans ce phénomène de sensibilité au bruit.