ブール関数の解析

数学と理論計算機科学において、ブール関数の解析とは、または上の実数値関数（このような関数は擬似ブール関数と呼ばれることもある）をスペクトルの観点から研究することです。^[1]研究対象となる関数は多くの場合ブール値を持ちますが、常にそうであるとは限らず、ブール関数になります。この分野は、組合せ論、社会的選択理論、ランダムグラフ、理論計算機科学、特に近似困難性、特性テスト、PAC学習において多くの応用がされています。 ${\displaystyle \{0,1\}^{n}}$${\displaystyle \{-1,1\}^{n}}$

ここでは主にドメイン で定義された関数について考えます。ドメイン で作業する方が便利な場合もあります。 がで定義されている場合、 で定義されている 対応する関数は${\displaystyle \{-1,1\}^{n}}$${\displaystyle \{0,1\}^{n}}$${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$${\displaystyle \{0,1\}^{n}}$

${\displaystyle f_{01}(x_{1},\ldots ,x_{n})=f((-1)^{x_{1}},\ldots ,(-1)^{x_{n}}).}$

同様に、私たちにとってブール関数は- 値関数ですが、代わりに - 値関数を検討する方が便利な場合がよくあります。 ${\displaystyle \{-1,1\}}$${\displaystyle \{0,1\}}$

すべての実数値関数は、多重線型多項式として一意に展開されます。 ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

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

(関数が 0-1 の値であっても、これは 2 を法とする合計ではなく、単なる実数の通常の合計であることに注意してください。)

これは関数 のアダマール変換であり、群のフーリエ変換です。係数はフーリエ係数と呼ばれ、全体の和はのフーリエ展開と呼ばれます。関数はフーリエ指標と呼ばれ、内積 に関して上のすべての関数の空間の正規直交基底を形成します。 ${\displaystyle f}$ ${\displaystyle \mathbb {Z} _{2}^{n}}$${\displaystyle {\hat {f}}(S)}$${\displaystyle f}$${\displaystyle \chi_{S}}$${\displaystyle \{-1,1\}^{n}}$${\displaystyle \langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)}$

フーリエ係数は内積を使って計算できます。

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

特に、これは であることを示している。ここで期待値は上の一様分布に関して取られる。パーセバルの恒等式は、 ${\displaystyle {\hat {f}}(\emptyset )=\operatorname {E} [f]}$${\displaystyle \{-1,1\}^{n}}$

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

をスキップすると、 の分散は次のようになります。 ${\displaystyle S=\emptyset }$${\displaystyle f}$

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

関数の次数は、サイズ の集合に対してとなる最大値です。言い換えると、 の次数は、その多線型多項式としての次数です。 ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$${\displaystyle d}$${\displaystyle {\hat {f}}(S)\neq 0}$${\displaystyle S}$${\displaystyle d}$${\displaystyle f}$

フーリエ展開をレベルに分解すると便利です。フーリエ係数はレベルにあります。 ${\displaystyle {\hat {f}}(S)}$${\displaystyle |S|}$

の度数は ​${\displaystyle d}$${\displaystyle f}$

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

これは、レベル 以外のすべてのフーリエ係数をゼロにすることによってから得られます。 ${\displaystyle f}$${\displaystyle d}$

同様に を定義します。 ${\displaystyle f^{>d},f^{<d},f^{\geq d},f^{\leq d}}$

関数の ' 番目の影響は、2つの同等の方法で定義できます。 ${\displaystyle i}$${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\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}}}$

がブール値の場合、 は' 番目の座標を反転すると関数の値が反転する 確率です。${\displaystyle f}$${\displaystyle \operatorname {Inf} _{i}[f]}$${\displaystyle i}$

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

は' 番目の座標に依存しません。 ${\displaystyle \operatorname {Inf} _{i}[f]=0}$${\displaystyle f}$${\displaystyle i}$

の総影響は、そのすべての影響の合計です。 ${\displaystyle f}$

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

ブール関数の総影響は、関数の平均感度でもあります。特定のポイントでのブール関数の感度は、' 番目の座標を反転すると関数の値が変化する座標の数です。この量の平均値が、まさに総影響です。 ${\displaystyle f}$${\displaystyle i}$${\displaystyle i}$

総影響は、適切に正規化された ハミンググラフの離散ラプラシアンを使用して定義することもできます。 ${\displaystyle \operatorname {Inf} [f]=\langle f,Lf\rangle }$

影響力の一般化された形式は、次のように定義される -安定影響力です。 ${\displaystyle \rho}$

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

対応する総影響は

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

関数には最大で「一定数」の「安定的に影響力のある」座標が存在することを証明できます。 ${\displaystyle f:\{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle |\{i\in [n]:\operatorname {Inf} _{i}^{\,(1-\delta )}[f]\geq \epsilon \}|\leq {\frac {1}{\delta \epsilon }}.}$

が与えられたとき、の周辺分布が一様で である場合、2 つのランダム ベクトルは-相関しているといいます。具体的には、最初に一様ランダムに選択し、次に各座標に独立して適用される次の 2 つの同等の規則のいずれかに従って選択することで、 -相関ランダム変数のペアを生成できます。 ${\displaystyle -1\leq \rho \leq 1}$${\displaystyle x,y\in \{-1,1\}^{n}}$${\displaystyle \rho }$${\displaystyle x,y}$${\displaystyle \operatorname {E} [x_{i}y_{i}]=\rho }$${\displaystyle \rho }$${\displaystyle x,z\in \{-1,1\}^{n}}$${\displaystyle y}$

${\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}}}$

この分布を と表記します。 ${\displaystyle y\sim N_{\rho }(x)}$

関数のノイズ安定性は、次の2 つの同等の方法で定義できます。 ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$${\displaystyle \rho }$

${\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}.}$

の場合、におけるのノイズ感度は ${\displaystyle 0\leq \delta \leq 1}$${\displaystyle f}$${\displaystyle \delta }$

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

がブール値の場合、これは各座標を の確率で独立して反転した場合にの値が変化する確率です。 ${\displaystyle f}$${\displaystyle f}$${\displaystyle \delta }$

ノイズ演算子は、 関数を受け取り、次の式で与えられる 別の関数を返す演算子です。${\displaystyle T_{\rho }}$${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$${\displaystyle T_{\rho }f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\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}.}$

のとき、ノイズ演算子は、各ビットがレート 1 で独立に反転する連続時間マルコフ連鎖を使用して定義することもできます。演算子は、このマルコフ連鎖をから始まるステップで実行し、最終状態で の平均値を取ることに対応します。このマルコフ連鎖はハミング グラフのラプラシアンによって生成され、これはノイズ演算子への総影響を関連付けます。 ${\displaystyle \rho >0}$${\displaystyle T_{\rho }}$${\displaystyle {\frac {1}{2}}\log {\frac {1}{\rho }}}$${\displaystyle x}$${\displaystyle f}$

ノイズ安定性は、ノイズ演算子によって定義できます。 ${\displaystyle \operatorname {Stab} _{\rho }[f]=\langle f,T_{\rho }f\rangle }$

の場合、関数の-ノルムは次のように定義されます。 ${\displaystyle 1\leq q<\infty }$${\displaystyle L_{q}}$${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

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

また、次のように定義します${\displaystyle \|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.}$

超収縮定理は、任意のおよびに対して、 ${\displaystyle q>2}$${\displaystyle q'=1/(1-1/q)}$

${\displaystyle \|T_{\rho }f\|_{q}\leq \|f\|_{2}\quad {\text{and}}\quad \|T_{\rho }f\|_{2}\leq \|f\|_{q'}.}$

超収縮性は関数解析の対数ソボレフ不等式と密接に関係している。^[2]

同様の結果は逆性過収縮として知られています。^[3]${\displaystyle q<2}$

多くの場合、関数への入力は 上で一様に分布しているわけではなく、またはに偏っています。このような状況では、ドメイン 上の関数を考えるのが一般的です。 の場合、pバイアス測度は次のように与えられます。 ${\displaystyle \{-1,1\}^{n}}$${\displaystyle -1}$${\displaystyle 1}$${\displaystyle \{0,1\}^{n}}$${\displaystyle 0<p<1}$${\displaystyle \mu _{p}}$

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

この尺度は、各座標を独立して確率 で 1 、確率 で 0になるように選択することによって生成できます。 ${\displaystyle p}$${\displaystyle 1-p}$

古典的なフーリエ特性は、この尺度に関してもはや直交しません。代わりに、次の特性を使用します。

${\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\}|}.}$

のpバイアス フーリエ展開は、pバイアスキャラクタ の線形結合としてのの展開です。${\displaystyle f}$${\displaystyle f}$

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

影響とノイズ演算子の定義は、スペクトル定義を使用して pバイアス設定に拡張できます。

の影響は次のように表される 。${\displaystyle i}$

${\displaystyle \operatorname {Inf} _{i}[f]=\sum _{S\ni i}{\hat {f}}(S)^{2}=p(1-p)\operatorname {E} [(f-f^{\oplus i})^{2}].}$

総影響は個々の影響の合計です。

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

相関する確率変数のペアは、独立に と を選択することで得られます。ここで は次のように与えられます。 ${\displaystyle \rho }$${\displaystyle x,z\sim \mu _{p}}$${\displaystyle y\sim N_{\rho }(x)}$${\displaystyle N_{\rho }}$

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

ノイズ演算子は次のように表される。

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

これを使用して、以前と同様にノイズ安定性とノイズ感度を定義できます。

ルッソ・マルグリスの公式（マルグリス・ルッソの公式^[1]とも呼ばれる）は、単調なブール関数に対して、 ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$

${\displaystyle {\frac {d}{dp}}\operatorname {E} _{x\sim \mu _{p}}[f(x)]={\frac {\operatorname {Inf} [f]}{p(1-p)}}=\sum _{i=1}^{n}\Pr[f\neq f^{\oplus i}].}$

影響と確率は両方とも に関して取られ、右側の項には の平均感度があります。を特性と考えると、式は が変化するにつれて、で発生する確率の導関数が での平均感度に等しくなることを示しています。 ${\displaystyle \mu _{p}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle p}$${\displaystyle f}$${\displaystyle p}$${\displaystyle p}$

ルッソ・マルギュリスの公式は、フリードガットの定理のような鋭い閾値定理を証明するための鍵となります。

この分野における最も深い成果の 1 つである不変性原理は、ブール立方体上の関数の分布をガウス空間上の関数の分布に結び付けます。ガウス空間は、標準的な次元ガウス測度を備えた空間です。 ${\displaystyle \{-1,1\}^{n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n}$

ブールキューブ上のフーリエ解析の基本概念の多くは、ガウス空間にも同等のものがあります。

• ガウス空間におけるフーリエ展開に対応するものはエルミート展開であり、これは多変数エルミート多項式の無限和（ に収束する）への展開である。${\displaystyle L^{2}}$
• セットの指標関数の総影響または平均感度に対応するのはガウス表面積であり、これはセットの境界のミンコフスキー内容です。
• ノイズ演算子に対応するのはオルンシュタイン・ウーレンベック演算子（メーラー変換に関連）で、 または （は-相関標準ガウス分布のペア）で与えられます。${\displaystyle (U_{\rho }f)(x)=\operatorname {E} _{z\sim N(0,1)}[f(\rho x+{\sqrt {1-\rho ^{2}}}z)]}$${\displaystyle (U_{\rho }f)(x)=\operatorname {E} [f(y)]}$${\displaystyle x,y}$${\displaystyle \rho }$
• 超収縮性は（適切なパラメータを使用すれば）ガウス空間でも成立します。

ガウス空間はブール キューブよりも対称性が高く (たとえば、回転不変)、ブール キューブの離散設定では実現が難しい可能性のある連続引数をサポートします。不変性原理は 2 つの設定をリンクし、ガウス空間の結果からブール キューブの結果を推測できるようにします。

の次数が最大 1 の場合、 は定数、座標に等しい、または座標の否定に等しい。特に、は独裁制、つまり最大 1 つの座標に依存する関数 です。${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle f}$${\displaystyle f}$

フリードグート・カライ・ナオール定理^[4]は、 FKN定理としても知られ、がほぼ次数1である場合に独裁制に近いことを述べています。定量的に、およびの場合、は独裁制に-近く、つまり、何らかのブール独裁制に対して、または同等に、何らかのブール独裁制に対して となります。 ${\displaystyle f}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle \|f^{>1}\|^{2}<\varepsilon }$${\displaystyle f}$${\displaystyle O(\varepsilon )}$${\displaystyle \|f-g\|^{2}=O(\varepsilon )}$${\displaystyle g}$${\displaystyle \Pr[f\neq g]=O(\varepsilon )}$${\displaystyle g}$

同様に、最大次数のブール関数は最大 個の座標に依存するため、定数個の座標に依存する関数（junta ）になります。ここで、 は、Wellens によって示されているように、少なくとも 1.5​​、最大 4.41 に等しい絶対定数です。^[5] Kindler–Safra の定理^{[6] は、} Friedgut–Kalai–Naor の定理をこの設定に一般化します。これは、が を満たす場合、 は最大次数のブール関数に -近いことを述べています。 ${\displaystyle d}$${\displaystyle C_{W}2^{d}}$${\displaystyle C_{W}}$${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle \|f^{>d}\|^{2}<\varepsilon }$${\displaystyle f}$${\displaystyle O(\varepsilon )}$${\displaystyle d}$

ブール立方体のポアンカレ不等式（上記の式から導かれる）は、関数に対して、 ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

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

これは次のことを意味します。 ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\geq {\frac {\operatorname {Var} [f]}{n}}}$

カーン・カライ・リニアル定理^[7]はKKL定理としても知られ、がブール値である場合にとなることを述べています。 ${\displaystyle f}$${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]=\Omega \left({\frac {\log n}{n}}\right)}$

カーン・カライ・リニアル定理によって与えられた境界は厳密であり、ベン・オールとリニアルの部族関数によって達成される： ^[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}).}$

カーン・カライ・線形定理はこの分野における最初の結果の 1 つであり、ブール関数のコンテキストに超収縮性を導入したものです。

が -junta (最大で 座標に依存する関数)である場合、ポアンカレ不等式に従います。 ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle M}$${\displaystyle M}$${\displaystyle \operatorname {Inf} [f]\leq M}$

フリードグートの定理^[9]はこの結果の逆である。これは、任意のに対して、関数は座標に応じてブール関数に-近いことを述べている。 ${\displaystyle \varepsilon >0}$${\displaystyle f}$${\displaystyle \varepsilon }$${\displaystyle \exp(\operatorname {Inf} [f]/\varepsilon )}$

ルッソ・マルギュリスの補題と組み合わせると、フリードグートの軍事政権定理は、任意の に対して、任意の単調関数は、ある に対してに関して軍事政権に近いことを意味します。 ${\displaystyle p}$${\displaystyle \mu _{q}}$${\displaystyle q\approx p}$

不変性原理^[10]はベリー・エッセン定理を非線形関数に 一般化したものである。

ベリー・エッシーンの定理は、（他にもありますが） およびがその他に比べて大きすぎる場合、を超えるの分布は同じ平均と分散を持つ正規分布に近くなることを述べています。 ${\displaystyle f=\sum _{i=1}^{n}c_{i}x_{i}}$${\displaystyle c_{i}}$${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$

不変性原理（特殊な場合）は、 が上の有界次数の多重線型多項式であり、 のすべての影響が小さい場合、上の均一測度の下での の分布は、ガウス空間での分布に近いことを非公式に述べています。 ${\displaystyle f}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle \{-1,1\}^{n}}$

より正式には、 を一変数リプシッツ関数、、 、とし ます。 と仮定します。すると、 ${\displaystyle \psi }$${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}}$${\displaystyle k=\deg f}$${\displaystyle \varepsilon =\max _{i}\sum _{S\ni i}{\hat {f}}(S)^{2}}$${\displaystyle \sum _{S\neq \emptyset }{\hat {f}}(S)^{2}\leq 1}$

${\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 ).}$

適切な を選択すると、両方の尺度における の分布がCDF 距離で近くなり、 CDF 距離は で与えられることを意味します。 ${\displaystyle \psi }$${\displaystyle f}$${\displaystyle \sup _{t}|\Pr[f(x)<t]-\Pr[f(g)<t]|}$

不変性原理は、多数決安定定理の最初の証明における重要な要素でした。

ブール関数は、 （ただし ）を満たす場合、線形です。ブール線形関数がまさに という特性であることを示すのは難しくありません。 ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle f(xy)=f(x)f(y)}$${\displaystyle xy=(x_{1}y_{1},\ldots ,x_{n}y_{n})}$${\displaystyle \chi _{S}}$

特性テストでは、与えられた関数が線形かどうかをテストします。次のようなテストをするのは自然なことです。一様にランダムに選択し、 であることを確認します。 が線形であれば、常にテストに合格します。Blum、Luby、および Rubinfeld ^[11]は、テストが確率で合格する場合、 はフーリエ キャラクターに -近いことを示しまし た。彼らの証明は組み合わせ論的でした。 ${\displaystyle x,y\in \{-1,1\}^{n}}$${\displaystyle f(xy)=f(x)f(y)}$${\displaystyle f}$${\displaystyle 1-\varepsilon }$${\displaystyle f}$${\displaystyle O(\varepsilon )}$

Bellareら^{​​[12]は、}非常に単純なフーリエ解析的証明を与え、テストが確率 で成功すると、 はフーリエ特性と相関していることも示した。彼らの証明は、テストの成功確率に関する次の式に依存している。 ${\displaystyle 1/2+\varepsilon }$${\displaystyle f}$

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

アローの不可能性定理によれば、候補者が 3 人以上の場合、必ずコンドルセの勝者が出る唯一の全会一致の投票ルールは独裁制である。

アローの定理の通常の証明は組み合わせ論的である。カライ^[13]は、フーリエ解析を用いて3人の候補者の場合のこの結果の別の証明を示した。が、2人の候補者の相対的な投票順位に基づいて勝者を割り当てる規則である場合、一様ランダム投票が与えられた場合にコンドルセの勝者が存在する確率はであり、そこから定理は簡単に導かれる。 ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle {\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}[f]}$

FKN 定理は、コンドルセ勝者がほぼ常に存在するルールである場合、独裁制に近いことを意味します。 ${\displaystyle f}$${\displaystyle f}$

ランダム グラフの理論における古典的な結果によれば、ランダム グラフが連結されている確率はの場合に に近づく傾向があります。これは、鋭いしきい値の例です。つまり、「しきい値ウィンドウ」の幅は で、しきい値自体の幅（およそ ）よりも漸近的に小さくなります。対照的に、グラフに三角形が含まれる確率は の場合に に近づく傾向があります。ここでは、しきい値ウィンドウとしきい値自体はどちらも であるため、これは粗いしきい値です。 ${\displaystyle G(n,p)}$${\displaystyle e^{-e^{-c}}}$${\displaystyle p\sim {\frac {\log n+c}{n}}}$${\displaystyle O(1/n)}$${\displaystyle {\frac {\log n}{n}}}$${\displaystyle G(n,p)}$${\displaystyle e^{-c^{3}/6}}$${\displaystyle p\sim {\frac {c}{n}}}$${\displaystyle \Theta (1/n)}$

フリードガットの鋭い閾値定理^[14]は、大まかに言えば、単調なグラフ特性（グラフ特性とは頂点の名前に依存しない特性）は、小さなサブグラフの出現と相関がない限り、鋭い閾値を持つと述べています。この定理は、ランダムグラフやパーコレーションの解析に広く適用されています。

関連する注意点として、KKL定理は閾値ウィンドウの幅が常に最大であることを意味している。^[15]${\displaystyle O(1/\log n)}$

座標上の多数決関数を表すとします。シェパードの公式は多数決の漸近的ノイズ安定性を与えます。 ${\displaystyle \operatorname {Maj} _{n}\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle n}$

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

これは、一様にランダムに選択し、の各ビットを確率 で反転して を形成すると、大多数が同じままになる 確率に関係しています。${\displaystyle x\in \{-1,1\}^{n}}$${\displaystyle y\in \{-1,1\}^{n}}$${\displaystyle x}$${\displaystyle {\frac {1-\rho }{2}}}$

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

より大きなノイズ安定性を持つブール関数が存在します。たとえば、独裁政権はノイズ安定性を持ちます。 ${\displaystyle x_{i}}$${\displaystyle \rho }$

多数決は最も安定であるという定理は、非公式には、多数決よりも大きいノイズ安定性を持つ関数だけが影響力のある座標を持つと述べています。正式には、任意の に対して、の期待値が 0 で の場合、となる が存在します。 ${\displaystyle \varepsilon >0}$${\displaystyle \tau >0}$${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\leq \tau }$${\displaystyle \operatorname {Stab} _{\rho }[f]\leq 1-{\frac {2}{\pi }}\arccos \rho +\varepsilon }$

この定理の最初の証明は、ガウス空間におけるボレルの等周定理と組み合わせて不変性原理を使用したものでした。それ以来、より直接的な証明が考案されました。^{[16] [17]}

多数決が最も安定であることは、ユニークゲーム予想を仮定すると、 MAX-CUTのGoemans-Williamson近似アルゴリズムが最適であることを意味します。この示唆は、Khotら^[18]によるもので、定理を証明するきっかけとなりました。