FKG不等式(FKG inequality)とは、有限の分配束の上の確率測度 $\mu$ が格子条件 $\mu(x\vee y)\mu(x\wedge y)\ge\mu(x)\mu(y)$ を満たすとき、増加関数 $f,g$ について $E_\mu[fg]\ge E_\mu[f]E_\mu[g]$ が成り立つという定理である。Ahlswede–Daykin の四関数定理から導け、同じ定理から Holley の不等式と集合族の不等式 $|A||B|\le|A\vee B||A\wedge B|$ も得られる。直積測度の場合が Harris の不等式で、Isingモデルやランダムクラスターモデル($q\ge1$)にも適用できる。
FKG不等式(FKG inequality)は、有限の分配束の上の確率測度 $\mu$ が条件 $\mu(x\vee y)\mu(x\wedge y)\ge\mu(x)\mu(y)$ を満たすとき、増加関数どうしが正に相関する、すなわち $E_\mu[fg]\ge E_\mu[f]E_\mu[g]$ が成り立つという定理である。名前は Fortuin、Kasteleyn、Ginibre に由来する(FKG71)。
「ある辺が開いている」と「別の辺が開いている」のように、大きい配置を好む 2 つの事象は、互いに相手を起こりやすくする。この直観を、独立でない測度にまで正確に述べたものが FKG 不等式である。独立な場合は Harris の不等式(パーコレーション)になり、1 つの全順序の上では Chebyshevの和の不等式 になる。Isingモデル の箱についての単調性も、Jansonの不等式 の出発点も、この形の不等式である。
この記事では、Ahlswede–Daykin の四関数定理(thm-fkg-four)を証明し、そこから FKG 不等式、Holley の不等式、集合族の不等式をまとめて導く。条件と結論の関係は次のとおりである。
| 主張 | 測度の条件 | 結論 |
|---|---|---|
| thm-fkg-four | 4 個の関数の不等式 | 和の不等式 |
| thm-fkg-main | 格子条件 | 増加関数の正の相関 |
| thm-fkg-holley | 2 個の測度の間の条件 | 確率的な大小 |
| cor-fkg-harris | 全順序の直積の上の直積測度 | 増加関数の正の相関 |
| cor-fkg-daykin | 測度なし | $\lvert A\rvert\lvert B\rvert\le\lvert A\vee B\rvert\lvert A\wedge B\rvert$ |
$L$ を空でない有限の分配束とする。すなわち $L$ は半順序集合で、2 元の最小上界 $x\vee y$ と最大下界 $x\wedge y$ をもち、$x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)$ を満たす。典型例は、有限集合 $S$ の部分集合の全体 $2^S$($\vee=\cup$、$\wedge=\cap$)と、$\{0,1\}^S$ や $\{-1,+1\}^S$ に成分ごとの順序を入れたものである。
$f\colon L\to\mathbb{R}$ が 増加 であるとは、$x\le y$ なら $f(x)\le f(y)$ であることをいう。$-f$ が増加のとき 減少 という。確率測度 $\mu$ について $E_\mu[f]:=\sum_{x\in L}f(x)\mu(x)$ と書く。
$\mu\colon L\to[0,\infty)$ が 格子条件(FKG lattice condition)を満たすとは、すべての $x,y\in L$ について
$$
\mu(x\vee y)\,\mu(x\wedge y)\ge\mu(x)\,\mu(y)
$$
であることをいう。文献では対数優モジュラ(log-supermodular)ともいう。$\mu$ がいたるところ正なら、$\log\mu$ についての不等式 $\log\mu(x\vee y)+\log\mu(x\wedge y)\ge\log\mu(x)+\log\mu(y)$ と同じである。
$L$ を有限の分配束、$\mu$ を $L$ の上の確率測度で格子条件を満たすものとする。$f,g\colon L\to\mathbb{R}$ がともに増加なら
$$
E_\mu[fg]\ge E_\mu[f]\,E_\mu[g]
$$
である。ともに減少でも同じで、一方が増加で他方が減少なら不等号は逆向きになる。
証明は四関数定理のあとの prf-fkg-main に置く。文献では $\mu$ がいたるところ正であると仮定することが多い(Gri18 Theorem 4.11、p. 62)が、この記事の証明はこの仮定を使わない。
$L$ の部分集合 $A,B$ について $A\vee B:=\{a\vee b\mid a\in A,\ b\in B\}$、$A\wedge B:=\{a\wedge b\mid a\in A,\ b\in B\}$ とおき、関数 $\phi\colon L\to[0,\infty)$ について $\phi(A):=\sum_{a\in A}\phi(a)$ と書く。
$L$ を有限の分配束、$\alpha,\beta,\gamma,\delta\colon L\to[0,\infty)$ とする。すべての $a,b\in L$ について
$$
\alpha(a)\beta(b)\le\gamma(a\vee b)\,\delta(a\wedge b)
$$
なら、すべての $A,B\subset L$ について
$$
\alpha(A)\,\beta(B)\le\gamma(A\vee B)\,\delta(A\wedge B)
$$
である。
段 1:$A=B=L=2^{\{1\}}$ の場合. 元を $0,1$ と書き、$\alpha_0=\alpha(0)$ などとする。仮定は
$$
\alpha_0\beta_0\le\gamma_0\delta_0,\quad\alpha_0\beta_1\le\gamma_1\delta_0,\quad\alpha_1\beta_0\le\gamma_1\delta_0,\quad\alpha_1\beta_1\le\gamma_1\delta_1
$$
である。$s:=\alpha_0\beta_1$、$t:=\alpha_1\beta_0$、$c:=\gamma_1\delta_0$、$e:=\gamma_0\delta_1$ とおく。第 1 式と第 4 式の和から $\alpha_0\beta_0+\alpha_1\beta_1\le\gamma_0\delta_0+\gamma_1\delta_1$ なので、$s+t\le c+e$ を示せばよい。$c=0$ なら $s=t=0$ である。$c>0$ とする。第 1 式と第 4 式の積から
$$
st=(\alpha_0\beta_0)(\alpha_1\beta_1)\le\gamma_0\delta_0\gamma_1\delta_1=ce
$$
である。$s,t\le c$ なので $(c-s)(c-t)\ge0$、すなわち $c^2+st\ge c(s+t)$ である。$c$ で割って $s+t\le c+st/c\le c+e$ を得る。
段 2:$A=B=L=2^{\{1,\dots,n\}}$ の場合. $n$ についての帰納法による。$n=1$ は段 1 である。$n\ge2$ とし、$a\subset\{1,\dots,n-1\}$ について $\alpha'(a):=\alpha(a)+\alpha(a\cup\{n\})$ とおき、$\beta',\gamma',\delta'$ も同様に定める。$a,b\subset\{1,\dots,n-1\}$ を固定する。段 1 を
$$
\alpha_0=\alpha(a),\ \alpha_1=\alpha(a\cup\{n\}),\ \beta_0=\beta(b),\ \beta_1=\beta(b\cup\{n\}),
$$
$$
\gamma_0=\gamma(a\cup b),\ \gamma_1=\gamma(a\cup b\cup\{n\}),\ \delta_0=\delta(a\cap b),\ \delta_1=\delta((a\cap b)\cup\{n\})
$$
に当てはめる。段 1 の 4 個の仮定は、もとの仮定の $a$ と $b$ に $n$ を入れるかどうかの 4 通りである。よって $\alpha'(a)\beta'(b)\le\gamma'(a\cup b)\delta'(a\cap b)$ が得られ、$\alpha',\beta',\gamma',\delta'$ は $n-1$ の場合の仮定を満たす。$\alpha'$ の総和は $\alpha$ の総和に等しいので(ほかも同じ)、帰納法の仮定から結論を得る。
段 3:一般の $A,B$ と $L=2^S$ の場合. $\alpha$ を $A$ の外で $0$ にした関数を $\alpha'$、$\beta$ を $B$ の外で $0$ にした関数を $\beta'$、$\gamma$ を $A\vee B$ の外で $0$ にした関数を $\gamma'$、$\delta$ を $A\wedge B$ の外で $0$ にした関数を $\delta'$ とする。$a\in A$、$b\in B$ なら $a\vee b\in A\vee B$、$a\wedge b\in A\wedge B$ なのでもとの不等式がそのまま残り、それ以外では左辺が $0$ である。段 2 を $\alpha',\beta',\gamma',\delta'$ に当てはめれば結論を得る。
段 4:一般の $L$. 分配束 の定理「有限分配束の表現定理(Birkhoff)」により、$L$ は結合既約元の集合 $S$ の下方集合の全体と束同型で、そこでは $\vee=\cup$、$\wedge=\cap$ である。$L$ を $2^S$ の部分集合で $\cup,\cap$ について閉じたものとみなし、4 個の関数を $2^S$ の残りの元で $0$ と定める。$a,b\in L$ なら $a\cup b,a\cap b\in L$ で不等式はもとのままで、それ以外では左辺が $0$ である。段 3 を当てはめれば結論を得る。$\square$
定理は AD78 による。FV17 Theorem 3.50(p. 129)は直積測度を重みにした形で同じ証明を述べ、FKG 不等式を導いている。
$f,g$ に定数を足しても $E_\mu[fg]-E_\mu[f]E_\mu[g]$ は変わらないので、$f,g\ge0$ としてよい。$\alpha:=f\mu$、$\beta:=g\mu$、$\gamma:=fg\mu$、$\delta:=\mu$ とおく。$f(a)\le f(a\vee b)$、$g(b)\le g(a\vee b)$ と格子条件から
$$
\alpha(a)\beta(b)=f(a)g(b)\mu(a)\mu(b)\le f(a\vee b)g(a\vee b)\,\mu(a\vee b)\mu(a\wedge b)=\gamma(a\vee b)\delta(a\wedge b)
$$
である。thm-fkg-four を $A=B=L$ で使うと $E_\mu[f]E_\mu[g]\le E_\mu[fg]\cdot1$ である($L\vee L=L\wedge L=L$)。ともに減少なら $-f,-g$ に、増加と減少の組なら $f,-g$ に当てはめる。$\square$
$\mu^+,\mu^-$ を $L$ の上の確率測度とし、すべての $a,b\in L$ について $\mu^+(a\vee b)\,\mu^-(a\wedge b)\ge\mu^+(a)\,\mu^-(b)$ とする。このとき増加関数 $f$ について $E_{\mu^+}[f]\ge E_{\mu^-}[f]$ である。
定数を足して $f\ge0$ としてよい。$\alpha:=f\mu^-$、$\beta:=\mu^+$、$\gamma:=f\mu^+$、$\delta:=\mu^-$ とおくと、$f(a)\le f(a\vee b)$ と仮定($a,b$ を入れ替えたもの)から
$$
\alpha(a)\beta(b)=f(a)\mu^-(a)\mu^+(b)\le f(a\vee b)\mu^+(a\vee b)\mu^-(a\wedge b)=\gamma(a\vee b)\delta(a\wedge b)
$$
である。thm-fkg-four から $E_{\mu^-}[f]\cdot1\le E_{\mu^+}[f]\cdot1$ である。$\square$
定理は Hol74 による。Gri18 Theorem 4.4(p. 60)は $L=\{0,1\}^E$ で、測度がいたるところ正のとき、Markov 連鎖による結合で示し、そこから FKG 不等式を導いている。結合の証明からは、$\mu^-$ の標本が $\mu^+$ の標本の下にくるように 2 つを同じ確率空間に実現できるという、より強い情報が得られる。
$L=L_1\times\dots\times L_n$(各 $L_i$ は有限の全順序集合)に成分ごとの順序を入れ、$\mu=\mu_1\otimes\dots\otimes\mu_n$ を直積測度とする。増加関数 $f,g$ について $E_\mu[fg]\ge E_\mu[f]E_\mu[g]$ である。とくに $n=1$ では、全順序集合の上のどんな確率測度についてもこの不等式が成り立つ。
全順序では $\{x_i\vee y_i,x_i\wedge y_i\}=\{x_i,y_i\}$ なので、$\mu_i(x_i\vee y_i)\mu_i(x_i\wedge y_i)=\mu_i(x_i)\mu_i(y_i)$ である。積をとると格子条件が等号で成り立つ。thm-fkg-main から従う。$\square$
$\{0,1\}^E$ の場合が Harris の不等式で、パーコレーション には無限個の辺への拡張とともに座標の個数の帰納法による証明がある。Harris の結果は Har60 による(Gri18 §4.2)。
有限の分配束 $L$ の部分集合 $A,B$ について $\lvert A\rvert\,\lvert B\rvert\le\lvert A\vee B\rvert\,\lvert A\wedge B\rvert$ である。とくに有限集合 $S$ の部分集合の族 $\mathcal{A}$ について、差の族 $\mathcal{A}\setminus\mathcal{A}:=\{a\setminus b\mid a,b\in\mathcal{A}\}$ は $\lvert\mathcal{A}\setminus\mathcal{A}\rvert\ge\lvert\mathcal{A}\rvert$ を満たす。
前半は thm-fkg-four で 4 個の関数をすべて $1$ とする。後半は $L=2^S$、$A=\mathcal{A}$、$B=\{S\setminus b\mid b\in\mathcal{A}\}$ とする。$a\cap(S\setminus b)=a\setminus b$ なので $A\wedge B=\mathcal{A}\setminus\mathcal{A}$ である。$a\cup(S\setminus b)=S\setminus(b\setminus a)$ なので $\lvert A\vee B\rvert=\lvert\mathcal{A}\setminus\mathcal{A}\rvert$ である。$\lvert B\rvert=\lvert\mathcal{A}\rvert$ なので $\lvert\mathcal{A}\rvert^2\le\lvert\mathcal{A}\setminus\mathcal{A}\rvert^2$ である。$\square$
頂点 $u,v,w$ の三角形の各辺を独立に確率 $1/2$ で開く。$A$ を $u$ と $v$ が開いた辺でつながる事象、$B$ を $v$ と $w$ がつながる事象とする。どちらも増加事象である。$P(A)=P(B)=\frac12+\frac12\cdot\frac14=\frac58$ で、$A\cap B$ は 3 頂点がつながる事象なので $P(A\cap B)=\frac12$ である。確かに $\frac12\ge\frac{25}{64}$ である。
$G=(V,E)$ を有限グラフ、$\beta\ge0$、$h\in\mathbb{R}^V$ とし、$\{-1,+1\}^V$ の上の確率測度を
$$
\mu_h(\sigma)=\frac1{Z_h}\exp\Bigl(\beta\sum_{xy\in E}\sigma_x\sigma_y+\sum_{x\in V}h_x\sigma_x\Bigr)
$$
とする。Isingモデル の命題「Ising モデルは格子条件を満たす」は一様な磁場の場合を述べているが、その証明で頂点の項に使う等式 $(\sigma\vee\tau)_x+(\sigma\wedge\tau)_x=\sigma_x+\tau_x$ は頂点ごとの磁場でも同じなので、$\mu_h$ も格子条件を満たし、増加関数は正に相関する。
さらに $h\ge h'$(成分ごと)なら $\mu^+=\mu_h$、$\mu^-=\mu_{h'}$ は thm-fkg-holley の条件を満たす。実際、$\beta$ の項は同じ命題の辺ごとの不等式で処理できる。磁場の項については、$(\sigma\vee\tau)_x-\sigma_x=\tau_x-(\sigma\wedge\tau)_x\ge0$ なので
$$
\sum_xh_x\bigl((\sigma\vee\tau)_x-\sigma_x\bigr)-\sum_xh'_x\bigl(\tau_x-(\sigma\wedge\tau)_x\bigr)=\sum_x(h_x-h'_x)\bigl((\sigma\vee\tau)_x-\sigma_x\bigr)\ge0
$$
である($\log\mu^+(\sigma\vee\tau)+\log\mu^-(\sigma\wedge\tau)-\log\mu^+(\sigma)-\log\mu^-(\tau)$ で $Z_h,Z_{h'}$ は打ち消し合う)。よって増加関数の期待値は磁場について増加である。同じ形の議論は境界条件についても使え、Isingモデル の箱についての単調性を与える。
$G=(V,E)$ を有限グラフ、$\omega\subset E$ について $k(\omega)$ を $(V,\omega)$ の連結成分の個数とする。$0< p< 1$、$q>0$ について $\{0,1\}^E$ の上の確率測度を
$$
\mu_{p,q}(\omega)=\frac1Zp^{\lvert\omega\rvert}(1-p)^{\lvert E\setminus\omega\rvert}q^{k(\omega)}
$$
で定める。$q\ge1$ なら $\mu_{p,q}$ は格子条件を満たす。
$p,1-p$ の因子は格子条件を等号で満たすので、$k(\omega\cup\tau)+k(\omega\cap\tau)\ge k(\omega)+k(\tau)$ を示せばよい($q\ge1$ で $q^k$ が $k$ について広義増加)。$e\notin\omega$ について、$k(\omega\cup\{e\})-k(\omega)$ は、$e$ の両端が $\omega$ でつながっていれば $0$、そうでなければ $-1$ である。$\omega\subset\omega'$、$e\notin\omega'$ なら、$\omega'$ でつながっていない 2 点は $\omega$ でもつながっていないので
$$
k(\omega\cup\{e\})-k(\omega)\le k(\omega'\cup\{e\})-k(\omega')
$$
である。$\tau\setminus\omega=\{e_1,\dots,e_r\}$ とし、$\omega\cap\tau$ に $e_1,\dots,e_r$ を順に足す列と $\omega$ に順に足す列を比べ、この不等式を各段で使って足すと $k(\tau)-k(\omega\cap\tau)\le k(\omega\cup\tau)-k(\omega)$ を得る。$\square$
正の相関の主張は Gri18 Theorem 8.7(p. 159)にある。$q=1$ は独立なパーコレーションで、$q=2$ は Isingモデル と対応する。
| 外す条件 | 反例 | 成り立たなくなるもの |
|---|---|---|
| $L$ が分配束 | $N_5=\{0,a,b,c,1\}$($0< a< b< 1$、$0< c< 1$、$c$ は $a,b$ と比較不能)の一様分布。格子条件は等号で成り立つ。$f=\mathbf{1}_{\{a,b,1\}}$、$g=\mathbf{1}_{\{c,1\}}$ | $E[fg]=\frac15$、$E[f]E[g]=\frac35\cdot\frac25=\frac6{25}$ で、thm-fkg-main が偽 |
| 格子条件 | $\{0,1\}^2$ で $\mu(0,1)=\mu(1,0)=\frac12$。$\mu(1,1)\mu(0,0)=0< \frac14$。$f=x_1$、$g=x_2$ | $E[fg]=0$、$E[f]E[g]=\frac14$ |
| $f,g$ の向きがそろう | $\{0,1\}$ の上の一様分布で $f=x$、$g=1-x$ | $E[fg]=0< \frac14$(不等号は逆向き) |
| $q\ge1$(prop-fkg-rc) | 三角形で $p=\frac12$、$0< q< 1$。下の計算 | 2 辺の指示関数の共分散が負 |
最後の行を確かめる。部分集合の重みの和は $Z'=q^3+3q^2+4q$ である(辺 $0$ 本で $q^3$、$1$ 本が 3 通りで $q^2$、$2$ 本が 3 通りで $q$、$3$ 本で $q$)。辺 $e$ が開く重みは $q^2+3q$、辺 $e,e'$ がともに開く重みは $2q$ なので、
$$
Z'^2\bigl(P(e,e')-P(e)P(e')\bigr)=2qZ'-(q^2+3q)^2=q^2(q^2-1)
$$
である。この符号は $q-1$ の符号に等しい。$q=1$ で $0$ になるのは、独立な場合に当たるからである。
$N_5$ と分配律. 反例の第 1 行で分配律が成り立たないことを示すのは $b\wedge(a\vee c)=b$ と $(b\wedge a)\vee(b\wedge c)=a$ である。同じ $f,g$ の形は $M_3$($0$ と $1$ の間に比較不能な 3 元)の一様分布でも $\frac15< \frac6{25}$ を与える。分配束 の定理「菱形と五角形による分配束の特徴づけ」により、分配束でない束は $N_5$ か $M_3$ を部分束にもつ。
無限の場合. 有限個の座標に依存する関数で近似すれば、無限個の座標の上の極限の測度にも不等式が移る。パーコレーション の Harris の不等式の証明はマルチンゲールの収束定理でこれを行う。
$\mu$ の正値性. Holley の結合の証明は単一の座標を動かす Markov 連鎖を使うので、測度の正値性が効く。四関数定理の証明は和の不等式だけで進むので、値が $0$ の点があっても通る。FKG71 の段階でも、正値性を外す方法が述べられている(Gri18 p. 62)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する