Scaling limits for the threshold window: When does a monotone Boolean function flip its outcome?

Abstract

Soit $f:\{0,1\}^{n}\to\{0,1\}$ une fonction booléenne monotone, et $\{\eta_{p}:p\in[0,1]\}$ le couplage monotone canonique d'éléments de $\{0,1\}^{n}$ choisis selon la mesure produit d'intensité $p\in[0,1]$. Le point aléatoire $p\in[0,1]$ en lequel $f(\eta_{p})$ bascule de $0$ à $1$ est souvent concentré près d'une valeur particulière, présentant ainsi un effet de seuil. Pour une suite de telles fonctions booléennes, nous étudions de plus près la fenêtre de seuil correspondante en considérant la loi limite lorsque $n$ tend vers l'infini (proprement normalisée pour être non-dégénérée) de ce point aléatoire critique où la fonction booléenne bascule. Nous déterminons cette loi pour de nombreuses fonctions booléennes classiques, en portant une attention particulière aux cas de la majorité itérée et des croisements de percolation. Il se trouve que ces lois limites ont des comportements d'une grande variété : en fait, nous montrons que toute mesure de probabilité non-dégénérée sur $\mathbb{R}$ peut être obtenue de cette façon à partir d'une suite bien choisie de fonctions booléennes.

Locations

• Annales de l Institut Henri Poincaré Probabilités et Statistiques - View - PDF
• Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) - View - PDF
• arXiv (Cornell University) - View - PDF