Cadre discret stabilité au bruit et influences.

Introduction générale dans le cadre discret

Parmi les domaines étudiés, on peut citer en premier lieu la “théorie du choix social”, une branche issue de l’économie, via l’étude de l’organisation d’un scrutin. L’issue d’une élection à deux candidats, disons 0 et 1 peut être modélisée par une fonction booléenne, dite fonction de choix, qui détermine le vainqueur. Au suffrage universel, la fonction de choix correspond à ce qu’on appelle la fonction Majorité. Lorsque l’issue ne dépend que de la volonté d’une seule personne, la fonction correspon- dante est celle qui associe une coordonnée. Ces fonctions sont appelées en conséquence fonctions dictateurs. D’autres systèmes de votes, qui respectent un principe moral de neutralité – ceux où aucun votant n’a trop d’influence sur le résultat – sont possibles. Citons l’exemple des majorités récursives qui régit l’élection présidentielle aux États-Unis, ou encore celle de majorités à poids.

Une élection peut également faire intervenir plus de deux candidats. Cette dernière situation aété étudiée dès le XVIIIe siècle par le marquis de Condorcet. Ce dernier énonce un célèbre paradoxe : il est toujours possible au suffrage universel d’obtenir un “issue irrationnelle”, c’est à dire une issue où le premier candidat est préféré au deuxième, qui est préféré au troisième lui-même étant préféré au premier. An milieu du XXe siècle, l’économiste Arrow a démontré que seuls le choix d’une seule personne évite la possibilité d’une issue irrationnelle – c’est le théorème d’impossibilité d’Arrow [Arr].En second lieu, on peut citer le domaine des graphes aléatoires. Sur de tels graphes, certaines pro- priétés sont modélisées par des fonctions booléennes. Par exemple, pour prendre un modèle simple, considérons un graphe à n sommets sur lequel chaque arête a une probabilité p 2 (0, 1) d’être pré-. Par exemple, y-a-t-il une composante connexe dans le graphe ? Est-ce que le graphe contient un k-cycle ? Ces propriétés citées sont monotones par rapport à p. Un fait récurrent est de considérer une suite graphes dont le nombre de sommets tend vers l’infini. Est associée à cette suite de graphes une suite de fonctions booléennes ( fMettons des arêtes sur le réseau avec probabilité 1=2. À l’événement qui correspond à une percola- tion, c’est-à-dire un chemin de gauche à droite (ou de bas en haut) est associé naturellement une fonction booléenne de f0, 1gvrage de Ryan O’Donnell “Analysis of Boolean functions” [OD]. En ce qui concerne l’utilisation des fonctions booléennes en percolation, nous renvoyons le lecteur aux notes de Garban et Steif [G-S]. Pour ce qui est de l’utilisation des influences, nous renvoyons le lecteur au survey de Kalai et Safra.

La grande majorité des travaux effectués sur l’analyse des fonctions booléennes s’appuie sur l’ana- lyse de Fourier sur le cube discret, devenue un outil indispensable. L’analyse de Fourier sur le cube commence au début du XXe siècle avec les travaux de Walsh et Paley qui construisent une base ortho- normée sur le cube discret, désormais appelée base de Walsh ou Fourier–Walsh. Le résultat fondateur et sous-jacent à tous les développements récents date cependant du début des années 70. Ce sont les travaux de Bonami [Bon] (publiés en francais et semble-t-il passé d’abord inaperçu sur le planappelé semi-groupe de Bonami–Beckner, un élément fondamental de l’analyse Booléenne. Notons que ce résultat est postérieur au premier théorème d’hypercontrativité du semi-groupe d’Ornstein Uhlenbeck de Nelson [Nel] (cependant incomplet) mais qu’il est plus fort au sens où, par théorèmedans le cadre continu, joue un rôle récurrent dans le domaine de l’analyse des fonctions booléennes et est un élément à la base d’une très grande partie des résultats que nous citerons, y compris les nôtres.

Analyse de Fourier discrète sur le cube

Cette section présente les élément basiques de l’analyse de Fourier discrète sur le cube. Le cube discret n dimensionnel est l’espace à deux points tensorisé n fois. Par commodité, il est parfois pré- férable de le définir comme f1, 1g, muni de la mesure uniforme. Sur le cube discret, par tensorisation, cette inégalité est vraie si et seulement si elle est vraie sur l’espace à deux points. En effet, avec des notations probabilistes, si x = ( ˜est la même que celle sur l’espace gaussien. Ceci n’est pas innocent. En effet par le même argument de Gross que pour les modèles continus, l’hypercontractivité avec ces constantes est équivalente à l’inégalité de Sobolev logarithmique suivante :Cette inégalité présente l’avantage de s’établir de manière un peu plus directe que l’inégalité d’hy- percontractivité de Bonami et Beckner citée plus haut. De manière plus globale, il est possible de déterminer des inégalités de Sobolev logarithmiques sur des modèles discrets plus généraux. Ceci nécessite de définir une forme de Dirichlet E , ce que nous verrons dans la prochaine section.