Análisis de funciones booleanas

Cada función de valor real${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$tiene una expansión única como polinomio multilineal :

${\displaystyle f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x),\quad \chi _{S}(x)=\prod _{i\in S}x_{i}.}$

(Tenga en cuenta que, incluso si la función toma valores entre 0 y 1, esto no es una suma módulo 2, sino simplemente una suma ordinaria de números reales).

Esta es la transformada de Hadamard de la función${\displaystyle f}$, que es la transformada de Fourier en el grupo${\displaystyle \mathbb {Z} _ {2}^{n}}$. Los coeficientes${\displaystyle {\hat {f}}(S)}$se conocen como coeficientes de Fourier , y la suma total se conoce como la expansión de Fourier de${\displaystyle f}$. Las funciones${\displaystyle \chi _{S}}$se conocen como caracteres de Fourier y forman una base ortonormal para el espacio de todas las funciones sobre${\displaystyle \{-1,1\}^{n}}$, con respecto al producto interno${\displaystyle \langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)}$.

Los coeficientes de Fourier se pueden calcular utilizando un producto interno:

${\displaystyle {\hat {f}}(S)=\langle f,\chi _{S}\rangle .}$

En particular, esto demuestra que${\displaystyle {\hat {f}}(\emptyset )=\operatorname {E} [f]}$, donde el valor esperado se toma con respecto a la distribución uniforme sobre${\displaystyle \{-1,1\}^{n}}$La identidad de Parseval establece que

${\displaystyle \|f\|^{2}=\operatorname {E} [f^{2}]=\sum _{S}{\hat {f}}(S)^{2}.}$

Si nos saltamos${\displaystyle S=\emptyset }$, entonces obtenemos la varianza de${\displaystyle f}$:

${\displaystyle \operatorname {Var} [f]=\sum _{S\neq \emptyset }{\hat {f}}(S)^{2}.}$

El grado de una función${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$es el máximo${\displaystyle d}$de tal manera que${\displaystyle {\hat {f}}(S)\neq 0}$para algún conjunto${\displaystyle S}$de tamaño${\displaystyle d}$. En otras palabras, el grado de${\displaystyle f}$es su grado como polinomio multilineal.

Es conveniente descomponer la expansión de Fourier en niveles : el coeficiente de Fourier${\displaystyle {\hat {f}}(S)}$está en el nivel${\displaystyle |S|}$.

El título${\displaystyle d}$parte de${\displaystyle f}$es

${\displaystyle f^{=d}=\sum _{|S|=d}{\hat {f}}(S)\chi _{S}.}$

Se obtiene de${\displaystyle f}$al poner a cero todos los coeficientes de Fourier que no estén en el nivel${\displaystyle d}$.

De manera similar definimos${\displaystyle f^{>d},f^{<d},f^{\geq d},f^{\leq d}}$.

El${\displaystyle i}$la influencia de una función${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$puede definirse de dos maneras equivalentes:

${\displaystyle {\begin{aligned}&\operatorname {Inf} _{i}[f]=\operatorname {E} \left[\left({\frac {ff^{\oplus i}}{2}}\right)^{2}\right]=\sum _{S\ni i}{\hat {f}}(S)^{2},\\[5pt]&f^{\oplus i}(x_{1},\ldots ,x_{n})=f(x_{1},\ldots ,x_{i-1},-x_{i},x_{i+1},\ldots ,x_{n}).\end{aligned}}}$

Si${\displaystyle f}$es booleano entonces${\displaystyle \operatorname {Inf} _{i}[f]}$es la probabilidad de que voltear el${\displaystyle i}$La coordenada 'th invierte el valor de la función:

${\displaystyle \operatorname {Inf} _{i}[f]=\Pr[f(x)\neq f^{\oplus i}(x)].}$

Si${\displaystyle \operatorname {Inf} _{i}[f]=0}$entonces${\displaystyle f}$no depende de la${\displaystyle i}$coordenada.

La influencia total de${\displaystyle f}$es la suma de todas sus influencias:

${\displaystyle \operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.}$

La influencia total de una función booleana es también la sensibilidad promedio de la función. La sensibilidad de una función booleana${\displaystyle f}$en un punto dado es el número de coordenadas${\displaystyle i}$de tal manera que si volteamos el${\displaystyle i}$En la coordenada ', el valor de la función cambia. El valor promedio de esta cantidad es exactamente la influencia total.

La influencia total también puede definirse utilizando el laplaciano discreto del gráfico de Hamming , debidamente normalizado: ${\displaystyle \operatorname {Inf} [f]=\langle f,Lf\rangle }$.

Una forma generalizada de influencia es la${\displaystyle \rho }$-influencia estable, definida por:

${\displaystyle \operatorname {Inf} _{i}^{\,(\rho )}[f]=\operatorname {Stab} _{\rho }[\operatorname {D} _{i}f]=\sum _{S\ni i}\rho ^{|S|-1}{\hat {f}}(S)^{2}.}$

Las influencias totales correspondientes son

${\displaystyle \operatorname {I} ^{(\rho )}[f]={\frac {d}{d\rho }}\operatorname {Stab} _{\rho }[f]=\sum _{S}|S|\rho ^{|S|-1}{\hat {f}}(S)^{2}.}$

Se puede demostrar que una función${\displaystyle f:\{-1,1\}^{n}\to \{-1,1\}}$tiene como máximo “constantemente” muchas coordenadas “de influencia estable”: ${\displaystyle |\{i\in [n]:\operatorname {Inf} _{i}^{\,(1-\delta )}[f]\geq \epsilon \}|\leq {\frac {1}{\delta \epsilon }}.}$

Dado${\displaystyle -1\leq \rho \leq 1}$, decimos que dos vectores aleatorios${\displaystyle x,y\in \{-1,1\}^{n}}$son${\displaystyle \rho }$-correlacionado si las distribuciones marginales de${\displaystyle x,y}$son uniformes y${\displaystyle \operatorname {E} [x_{i}y_{i}]=\rho }$. Concretamente, podemos generar un par de${\displaystyle \rho }$-variables aleatorias correlacionadas eligiendo primero${\displaystyle x,z\in \{-1,1\}^{n}}$uniformemente al azar y luego elegir${\displaystyle y}$Según una de las dos reglas equivalentes siguientes, aplicadas independientemente a cada coordenada:

${\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}\quad {\text{or}}\quad y_{i}={\begin{cases}x_{i}&{\text{w.p. }}{\frac {1+\rho }{2}},\\-x_{i}&{\text{w.p. }}{\frac {1-\rho }{2}}.\end{cases}}}$

Denotamos esta distribución por${\displaystyle y\sim N_{\rho }(x)}$.

La estabilidad del ruido de una función${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$en${\displaystyle \rho }$puede definirse de dos maneras equivalentes:

${\displaystyle \operatorname {Stab} _{\rho }[f]=\operatorname {E} _{x;y\sim N_{\rho }(x)}[f(x)f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)^{2}.}$

Para${\displaystyle 0\leq \delta \leq 1}$, la sensibilidad al ruido de${\displaystyle f}$en${\displaystyle \delta }$es

${\displaystyle \operatorname {NS} _{\delta }[f]={\frac {1}{2}}-{\frac {1}{2}}\operatorname {Stab} _{1-2\delta }[f].}$

Si${\displaystyle f}$es booleano, entonces esta es la probabilidad de que el valor de${\displaystyle f}$cambia si invertimos cada coordenada con probabilidad${\displaystyle \delta }$, de forma independiente.

El operador de ruido${\displaystyle T_{\rho }}$es un operador que toma una función${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$y devolviendo otra función${\displaystyle T_{\rho }f\colon \{-1,1\}^{n}\to \mathbb {R} }$dado por

${\displaystyle (T_{\rho }f)(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\chi _{S}.}$

Cuando${\displaystyle \rho >0}$El operador de ruido también se puede definir utilizando una cadena de Markov de tiempo continuo en la que cada bit se invierte independientemente con una tasa de 1. El operador${\displaystyle T_{\rho }}$corresponde a ejecutar esta cadena de Markov para${\displaystyle {\frac {1}{2}}\log {\frac {1}{\rho }}}$pasos comenzando en${\displaystyle x}$y tomando el valor promedio de${\displaystyle f}$en el estado final. Esta cadena de Markov se genera mediante el laplaciano del grafo de Hamming, y esto relaciona la influencia total con el operador de ruido.

La estabilidad del ruido se puede definir en términos del operador de ruido:${\displaystyle \operatorname {Stab} _{\rho }[f]=\langle f,T_{\rho }f\rangle }$.

Para${\displaystyle 1\leq q<\infty }$, el${\displaystyle L_{q}}$-norma de una función${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$se define por

${\displaystyle \|f\|_{q}={\sqrt[{q}]{\operatorname {E} [|f|^{q}]}}.}$

También definimos${\displaystyle \|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.}$

El teorema de la hipercontractilidad establece que para todo${\displaystyle p>q>1}$, si${\displaystyle |\rho |\leq {\sqrt {\frac {q-1}{p-1}}}}$entonces

${\displaystyle \|T_{\rho }f\|_{p}\leq \|f\|_{q}.}$

La hipercontractilidad está estrechamente relacionada con las desigualdades logarítmicas de Sobolev del análisis funcional . ^{[ 2 ]}

Un resultado similar para${\displaystyle 1>p>q}$se conoce como hipercontractilidad inversa . ^{[ 3 ]} Afirma que si${\displaystyle |\rho |\leq {\sqrt {\frac {1-p}{1-q}}}}$entonces

${\displaystyle \|T_{\rho }f\|_{q}\geq \|f\|_{p}.}$

En muchas situaciones, la entrada a la función no está distribuida uniformemente sobre${\displaystyle \{-1,1\}^{n}}$, pero en cambio tiene un sesgo hacia${\displaystyle -1}$o${\displaystyle 1}$En estas situaciones es habitual considerar funciones sobre el dominio${\displaystyle \{0,1\}^{n}}$. Para${\displaystyle 0<p<1}$, la medida sesgada p${\displaystyle \mu _{p}}$es dado por

${\displaystyle \mu _{p}(x)=p^{\sum _{i}x_{i}}(1-p)^{\sum _{i}(1-x_{i})}.}$

Esta medida se puede generar eligiendo cada coordenada independientemente como 1 con probabilidad${\displaystyle p}$y 0 con probabilidad${\displaystyle 1-p}$.

Los caracteres de Fourier clásicos ya no son ortogonales con respecto a esta medida. En su lugar, utilizamos los siguientes caracteres:

${\displaystyle \omega _{S}(x)=\left({\sqrt {\frac {p}{1-p}}}\right)^{|\{i\in S:x_{i}=0\}|}\left(-{\sqrt {\frac {1-p}{p}}}\right)^{|\{i\in S:x_{i}=1\}|}.}$

La expansión de Fourier con sesgo p de${\displaystyle f}$es la expansión de${\displaystyle f}$como una combinación lineal de caracteres con sesgo p :

${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\omega _{S}.}$

Podemos extender las definiciones de influencia y del operador de ruido al contexto con sesgo p utilizando sus definiciones espectrales.

Uno de los resultados más profundos en este campo, el principio de invariancia , conecta la distribución de funciones en el cubo booleano.${\displaystyle \{-1,1\}^{n}}$a su distribución en el espacio gaussiano , que es el espacio${\displaystyle \mathbb {R} ^{n}}$dotado del estándar${\displaystyle n}$medida gaussiana de -dimensiones .

Muchos de los conceptos básicos del análisis de Fourier en el cubo booleano tienen contrapartes en el espacio gaussiano:

• La contraparte de la expansión de Fourier en el espacio gaussiano es la expansión de Hermite, que es una expansión a una suma infinita (convergiendo en${\displaystyle L^{2}}$) de polinomios de Hermite multivariados .
• La contraparte de la influencia total o sensibilidad promedio para la función indicadora de un conjunto es el área de superficie gaussiana, que es el contenido de Minkowski del límite del conjunto.
• La contraparte del operador de ruido es el operador de Ornstein-Uhlenbeck (relacionado con la transformada de Mehler ), dado por${\displaystyle (U_{\rho }f)(x)=\operatorname {E} _{z\sim N(0,1)}[f(\rho x+{\sqrt {1-\rho ^{2}}}z)]}$, o alternativamente por${\displaystyle (U_{\rho }f)(x)=\operatorname {E} [f(y)]}$, dónde${\displaystyle x,y}$es un par de${\displaystyle \rho }$-Gaussianas estándar correlacionadas.
• La hipercontractilidad se cumple (con los parámetros adecuados) también en el espacio gaussiano.

El espacio gaussiano es más simétrico que el cubo booleano (por ejemplo, es invariante a la rotación) y admite argumentos continuos que pueden ser más difíciles de abordar en el entorno discreto del cubo booleano. El principio de invariancia vincula ambos entornos y permite deducir resultados del cubo booleano a partir de resultados del espacio gaussiano.

Si${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$tiene grado como máximo 1, entonces${\displaystyle f}$es constante, igual a una coordenada o igual a la negación de una coordenada. En particular,${\displaystyle f}$es una dictadura : una función que depende como máximo de una coordenada.

El teorema de Friedgut-Kalai-Naor, ^{[ 4 ]} también conocido como teorema FKN , establece que si${\displaystyle f}$Casi tiene grado 1, entonces está cerca de una dictadura. Cuantitativamente, si${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$y${\displaystyle \|f^{>1}\|^{2}<\varepsilon }$, entonces${\displaystyle f}$es${\displaystyle O(\varepsilon )}$-cercano a una dictadura, es decir,${\displaystyle \|f-g\|^{2}=O(\varepsilon )}$para alguna dictadura booleana${\displaystyle g}$, o equivalentemente,${\displaystyle \Pr[f\neq g]=O(\varepsilon )}$para alguna dictadura booleana${\displaystyle g}$.

De manera similar, una función booleana de grado como máximo${\displaystyle d}$depende como máximo de${\displaystyle C_{W}2^{d}}$coordenadas, convirtiéndola en una junta (una función que depende de un número constante de coordenadas), donde${\displaystyle C_{W}}$es una constante absoluta igual a al menos 1,5 y como máximo 4,41, como lo demostró Wellens. ^{[ 5 ]} El teorema de Kindler-Safra ^{[ 6 ]} generaliza el teorema de Friedgut-Kalai-Naor a este contexto. Establece que si${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$Satisface${\displaystyle \|f^{>d}\|^{2}<\varepsilon }$entonces${\displaystyle f}$es${\displaystyle O(\varepsilon )}$-cerca de una función booleana de grado como máximo${\displaystyle d}$.

La desigualdad de Poincaré para el cubo booleano (que se deduce de las fórmulas que aparecen arriba) establece que para una función${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$,

${\displaystyle \operatorname {Var} [f]\leq \operatorname {Inf} [f]\leq \deg f\cdot \operatorname {Var} [f].}$

Esto implica que${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\geq {\frac {\operatorname {Var} [f]}{n}}}$.

El teorema de Kahn-Kalai-Linial, ^{[ 7 ]} también conocido como teorema KKL , establece que si${\displaystyle f}$es booleano entonces${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]=\Omega \left({\frac {\log n}{n}}\right)}$.

La cota dada por el teorema de Kahn-Kalai-Linial es ajustada y se logra mediante la función de tribus de Ben-Or y Linial: ^{[ 8 ]}

${\displaystyle (x_{1,1}\land \cdots \land x_{1,w})\lor \cdots \lor (x_{2^{w},1}\land \cdots \land x_{2^{w},w}).}$

El teorema de Kahn-Kalai-Linial fue uno de los primeros resultados en este campo, y fue el que introdujo la hipercontractilidad en el contexto de las funciones booleanas.

Si${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$es un${\displaystyle M}$-junta (una función que depende de como máximo)${\displaystyle M}$coordenadas) entonces${\displaystyle \operatorname {Inf} [f]\leq M}$Según la desigualdad de Poincaré.

El teorema de Friedgut ^{[ 9 ]} es un recíproco de este resultado. Afirma que para cualquier${\displaystyle \varepsilon >0}$, la función${\displaystyle f}$es${\displaystyle \varepsilon }$-cerca de una junta booleana dependiendo de${\displaystyle \exp(\operatorname {Inf} [f]/\varepsilon )}$coordenadas.

Combinado con el lema de Russo-Margulis, el teorema de la junta de Friedgut implica que para cada${\displaystyle p}$, toda función monótona está cerca de una junta con respecto a${\displaystyle \mu _{q}}$para algunos${\displaystyle q\approx p}$.

El principio de invariancia ^{[ 10 ]} generaliza el teorema de Berry-Esseen a funciones no lineales.

El teorema de Berry-Esseen establece (entre otras cosas) que si${\displaystyle f=\sum _{i=1}^{n}c_{i}x_{i}}$y no${\displaystyle c_{i}}$es demasiado grande en comparación con el resto, entonces la distribución de${\displaystyle f}$encima${\displaystyle \{-1,1\}^{n}}$se aproxima a una distribución normal con la misma media y varianza.

El principio de invariancia (en un caso especial) establece informalmente que si${\displaystyle f}$es un polinomio multilineal de grado acotado sobre${\displaystyle x_{1},\ldots ,x_{n}}$y todas las influencias de${\displaystyle f}$son pequeños, entonces la distribución de${\displaystyle f}$bajo la medida uniforme sobre${\displaystyle \{-1,1\}^{n}}$es cercana a su distribución en el espacio gaussiano.

Más formalmente, dejemos${\displaystyle \psi }$Sea una función de Lipschitz univariada , sea${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}}$, dejar${\displaystyle k=\deg f}$y dejar ${\displaystyle \varepsilon =\max _{i}\sum _{S\ni i}{\hat {f}}(S)^{2}}$. Supongamos que${\displaystyle \sum _{S\neq \emptyset }{\hat {f}}(S)^{2}\leq 1}$. Entonces

${\displaystyle \left|\operatorname {E} _{x\sim \{-1,1\}^{n}}[\psi (f(x))]-\operatorname {E} _{g\sim N(0,I)}[\psi (f(g))]\right|=O(k9^{k}\varepsilon ).}$

Al elegir lo apropiado${\displaystyle \psi }$, esto implica que las distribuciones de${\displaystyle f}$bajo ambas medidas están cerca en distancia CDF , que viene dada por${\displaystyle \sup _{t}|\Pr[f(x)<t]-\Pr[f(g)<t]|}$.

El principio de invariancia fue el ingrediente clave en la demostración original del teorema de que la mayoría es la más estable .

Una función booleana${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$es lineal si satisface${\displaystyle f(xy)=f(x)f(y)}$, dónde${\displaystyle xy=(x_{1}y_{1},\ldots ,x_{n}y_{n})}$No es difícil demostrar que las funciones lineales booleanas son exactamente los caracteres${\displaystyle \chi _{S}}$.

En las pruebas de propiedades queremos comprobar si una función dada es lineal. Es natural intentar la siguiente prueba: elegir${\displaystyle x,y\in \{-1,1\}^{n}}$uniformemente al azar y comprobar que${\displaystyle f(xy)=f(x)f(y)}$. Si${\displaystyle f}$Si es lineal, entonces siempre pasa la prueba. Blum, Luby y Rubinfeld ^{[ 11 ]} demostraron que si la prueba pasa con probabilidad${\displaystyle 1-\varepsilon }$entonces${\displaystyle f}$es${\displaystyle O(\varepsilon )}$-cercano a un carácter de Fourier. Su demostración fue combinatoria.

Bellare et al. ^{[ 12 ]} dieron una demostración analítica de Fourier extremadamente simple, que también muestra que si la prueba tiene éxito con probabilidad${\displaystyle 1/2+\varepsilon }$, entonces${\displaystyle f}$está correlacionado con un carácter de Fourier. Su prueba se basa en la siguiente fórmula para la probabilidad de éxito de la prueba:

${\displaystyle {\frac {1}{2}}+{\frac {1}{2}}\sum _{S\subseteq [n]}{\hat {f}}(S)^{3}.}$

El teorema de imposibilidad de Arrow establece que, para tres o más candidatos, la única regla de votación unánime que siempre tiene un ganador de Condorcet es una dictadura.

La demostración habitual del teorema de Arrow es combinatoria. Kalai ^{[ 13 ]} dio una demostración alternativa de este resultado en el caso de tres candidatos utilizando el análisis de Fourier. Si${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$es la regla que asigna un ganador entre dos candidatos dados sus órdenes relativos en los votos, entonces la probabilidad de que haya un ganador de Condorcet dado un voto uniformemente aleatorio es${\displaystyle {\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}[f]}$, de donde se deduce fácilmente el teorema.

El teorema FKN implica que si${\displaystyle f}$es una regla para la cual casi siempre hay un ganador de Condorcet, entonces${\displaystyle f}$Está cerca de ser una dictadura.

Un resultado clásico en la teoría de grafos aleatorios establece que la probabilidad de que un${\displaystyle G(n,p)}$El grafo aleatorio está conectado y tiende a${\displaystyle e^{-e^{-c}}}$si${\displaystyle p\sim {\frac {\log n+c}{n}}}$. Este es un ejemplo de un umbral pronunciado : el ancho de la "ventana de umbral", que es${\displaystyle O(1/n)}$, es asintóticamente menor que el umbral mismo, que es aproximadamente${\displaystyle {\frac {\log n}{n}}}$. Por el contrario, la probabilidad de que un${\displaystyle G(n,p)}$El gráfico contiene un triángulo que tiende a${\displaystyle e^{-c^{3}/6}}$cuando${\displaystyle p\sim {\frac {c}{n}}}$Aquí tanto la ventana de umbral como el umbral mismo son${\displaystyle \Theta (1/n)}$y, por lo tanto, este es un umbral aproximado .

El teorema del umbral agudo de Friedgut ^{[ 14 ]} establece, en términos generales, que una propiedad de grafo monótona (una propiedad de grafo es una propiedad que no depende de los nombres de los vértices) tiene un umbral agudo a menos que esté correlacionada con la aparición de subgrafos pequeños. Este teorema se ha aplicado ampliamente para analizar grafos aleatorios y percolación .

En relación con esto, el teorema KKL implica que el ancho de la ventana umbral siempre es como máximo${\displaystyle O(1/\log n)}$. ^{[ 15 ]}

Dejar${\displaystyle \operatorname {Maj} _{n}\colon \{-1,1\}^{n}\to \{-1,1\}}$denotemos la función de mayoría en${\displaystyle n}$coordenadas. La fórmula de Sheppard proporciona la estabilidad asintótica al ruido de la mayoría:

${\displaystyle \operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]\longrightarrow 1-{\frac {2}{\pi }}\arccos \rho .}$

Esto está relacionado con la probabilidad de que si elegimos${\displaystyle x\in \{-1,1\}^{n}}$uniformemente al azar y forma${\displaystyle y\in \{-1,1\}^{n}}$volteando cada parte de${\displaystyle x}$con probabilidad${\displaystyle {\frac {1-\rho }{2}}}$, entonces la mayoría permanece igual:

${\displaystyle \operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]=2\Pr[\operatorname {Maj} _{n}(x)=\operatorname {Maj} _{n}(y)]-1}$.

Hay funciones booleanas con mayor estabilidad al ruido. Por ejemplo, una dictadura${\displaystyle x_{i}}$tiene estabilidad de ruido${\displaystyle \rho }$.

El teorema de la mayoría es el más estable establece, informalmente, que las únicas funciones que tienen una estabilidad de ruido mayor que la mayoría tienen coordenadas influyentes. Formalmente, para cada${\displaystyle \varepsilon >0}$existe${\displaystyle \tau >0}$de tal manera que si${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$tiene expectativa cero y${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\leq \tau }$, entonces${\displaystyle \operatorname {Stab} _{\rho }[f]\leq 1-{\frac {2}{\pi }}\arccos \rho +\varepsilon }$.

La primera demostración de este teorema utilizó el principio de invariancia junto con un teorema isoperimétrico de Borell en el espacio gaussiano; desde entonces se han ideado demostraciones más directas. ^{[ 16 ] [ 17 ]}

La afirmación «La mayoría es la más estable» implica que el algoritmo de aproximación de Goemans-Williamson para MAX-CUT es óptimo, asumiendo la conjetura de juegos únicos . Esta implicación, debida a Khot et al., ^{[ 18 ]} fue el impulso para demostrar el teorema.