ランダムクラスターモデル(random-cluster model)とは、有限グラフの辺の部分集合 $\omega$ に $p^{\lvert\omega\rvert}(1-p)^{\lvert E\setminus\omega\rvert}q^{k(\omega)}$($k(\omega)$ は連結成分の個数)に比例する確率を与える模型で、FK パーコレーションとも呼ばれる。$q=1$ は独立なパーコレーションで、整数 $q\ge2$ では Edwards–Sokal の結合により Potts 模型と結ばれ、色の相関が連結の確率で書ける。$q\ge1$ では正の相関と $p,q$ についての比較不等式が成り立ち、分配関数は Tutte 多項式の特殊値で、平面グラフでは双対グラフの同じ模型と対応する。正方格子の臨界確率は自己双対点 $\sqrt q/(1+\sqrt q)$ である。
ランダムクラスターモデル(random-cluster model)は、有限グラフの辺の部分集合 $\omega$ に、独立な辺のパーコレーションの重み $p^{\lvert\omega\rvert}(1-p)^{\lvert E\setminus\omega\rvert}$ と、連結成分の個数 $k(\omega)$ についての因子 $q^{k(\omega)}$ の積に比例する確率を与える模型である。Fortuin と Kasteleyn が 1970 年ごろに導入し、FK パーコレーションとも呼ばれる(Gri18 p. 156)。$q=1$ は独立な パーコレーション で、整数 $q\ge2$ では Potts模型 と同じ確率空間に結合でき、色の相関が連結の確率で書ける。
この記事では次を証明する。
この記事のグラフ $G=(V,E)$ は有限で、平行辺とループを許す(Tutte多項式 の記事と同じ設定)。$\omega\subset E$ を開いた辺の集合と見て、全域部分グラフ $(V,\omega)$ の連結成分の個数(孤立点も数える)を $k(\omega)$ と書く。$x,y\in V$ が $(V,\omega)$ の同じ成分にあることを $x\leftrightarrow y$ と書く。
$p\in[0,1]$、$q>0$ とする。$\{0,1\}^E$($E$ の部分集合の全体)の上の確率測度
$$
\varphi_{G,p,q}(\omega):=\frac1{Z^{\mathrm{RC}}_G(p,q)}\,p^{\lvert\omega\rvert}(1-p)^{\lvert E\setminus\omega\rvert}q^{k(\omega)}
$$
を ランダムクラスターモデル といい、$Z^{\mathrm{RC}}_G(p,q)$ を分配関数という。$G$ が明らかなときは $\varphi_{p,q}$ と書く。
定義は Gri18 (8.1)(p. 156)による。$q>1$ では成分の多い(開いた辺の少ない、または閉路を多く含む)配置が、$q< 1$ では成分の少ない配置が重くなる。$q=1$ では各辺が独立に確率 $p$ で開く。
$0< p< 1$ なら、$\alpha:=p/(1-p)$ として $\varphi_{p,q}(\omega)\propto\alpha^{\lvert\omega\rvert}q^{k(\omega)}$ と書ける。
$0< p< 1$、$e\in E$ とし、$e$ の両端を $x,y$ とする。$e$ 以外の辺の状態を $\omega\subset E\setminus\{e\}$ に固定した条件のもとで、$e$ が開く確率は
$$
\begin{cases}p&(x\leftrightarrow y\text{ が }\omega\text{ で成り立つとき})\\[2pt]\dfrac{p}{p+q(1-p)}&(\text{そうでないとき})\end{cases}
$$
である。
$e$ を開いた配置と閉じた配置の重みの比は $\frac{p\,q^{k(\omega\cup\{e\})}}{(1-p)\,q^{k(\omega)}}$ である。$x,y$ が $\omega$ でつながっていれば(ループもこの場合)$e$ を足しても成分は変わらず、比は $\alpha$ で、確率は $\frac{\alpha}{1+\alpha}=p$ である。つながっていなければ成分が 1 つ減り、比は $\alpha/q$ で、確率は $\frac{\alpha/q}{1+\alpha/q}=\frac p{p+q(1-p)}$ である。$\square$
$q=1$ なら 2 つの値は一致し、辺の独立性に戻る。$q\ne1$ では辺の状態は独立でない。$q>1$ では、すでにつながっている 2 点を結ぶ辺の方が開きやすい。条件付けを $e$ の状態にすると、$e$ を閉じた条件では $G$ から $e$ を除いたグラフの、$e$ を開いた条件では $e$ を縮約したグラフのランダムクラスターモデルが得られる(Gri18 Theorem 8.11、p. 159)。
$q\to0$ の極限. $p,q\to0$ を $q/p\to0$ となるようにとると、連結な $G$ では $\varphi_{p,q}$ は全域木の上の一様分布に近づく(Gri18 p. 156、§8.4)。重みが $\alpha^{\lvert\omega\rvert}q^{k(\omega)}$ なので、まず $k(\omega)=1$ が強く選ばれ、その中で $\alpha\to0$ により辺の最も少ない全域木が選ばれる。たとえば $K_4$ で $p=10^{-3}$、$q=10^{-6}$ とすると、16 本の全域木の確率の和は $0.998$ で、どの全域木も同じ確率 $0.0624$ をもつ。
$q\ge2$ を整数、$G$ をループのないグラフ、$\beta\ge0$、$p:=1-e^{-\beta}$ とする。色の配置 $\sigma\in[q]^V$ と辺の配置 $\omega\subset E$ の組に
$$
\mu(\sigma,\omega)\propto\prod_{e\in E}\Bigl((1-p)\mathbf{1}_{e\notin\omega}+p\,\mathbf{1}_{e\in\omega}\,\delta_e(\sigma)\Bigr)
$$
で確率を与える。$\delta_e(\sigma)$ は辺 $e$ の両端の色が等しいとき $1$、そうでないとき $0$ である(Potts模型 の定義の記号)。$\mu(\sigma,\omega)>0$ となるのは、開いた辺の両端の色がすべて等しいとき、すなわち $\sigma$ が $(V,\omega)$ の各成分の上で一定のときである。
この結合は Gri18 §8.1(pp. 157–158)にある。3 は、ランダムクラスターモデルの標本の各成分に一様な色を塗ると Potts 模型の標本が得られることを、4 は逆に Potts 模型の標本からランダムクラスターモデルの標本を作れることを言っている。
$x,y\in V$ について
$$
\pi_{G,\beta,q}(\sigma_x=\sigma_y)-\frac1q=\Bigl(1-\frac1q\Bigr)\varphi_{G,p,q}(x\leftrightarrow y)
$$
である。
thm-rc-es の 3 から、$\omega$ を与えた条件付き確率 $\mu(\sigma_x=\sigma_y\mid\omega)$ は、$x\leftrightarrow y$ なら $1$、そうでなければ $\frac1q$ である。2 と 1 を使って $\omega$ について平均すると、左辺の確率は $\varphi(x\leftrightarrow y)+\frac1q\bigl(1-\varphi(x\leftrightarrow y)\bigr)$ である。$\square$
これは Gri18 Theorem 8.6(p. 158)である。Potts 模型の「長距離の秩序」が、ランダムクラスターモデルで遠い 2 点がつながることに置き換わる。
$\{0,1\}^E$ に包含の順序を入れる。$q\ge1$ なら $\varphi_{p,q}$ は格子条件を満たし、増加関数どうしは正に相関する(FKG不等式 の命題「ランダムクラスターモデルの格子条件」。その証明の中で、成分の個数の不等式
$$
k(\omega\cup\tau)+k(\omega\cap\tau)\ge k(\omega)+k(\tau)\qquad(\omega,\tau\subset E)
$$
が示されている)。$q< 1$ では正の相関が成り立たない例がある(同じ記事の反例の表)。この成分の個数の不等式から、パラメータを変えたときの単調性が出る。測度 $\nu,\nu'$ について、すべての増加関数 $f$ で $E_\nu[f]\le E_{\nu'}[f]$ となることを $\nu\le_{\mathrm{st}}\nu'$ と書く。
$0< p,p'< 1$、$q,q'>0$ とする。
FKG不等式 の定理「Holley の不等式」により、$\{0,1\}^E$ の上の確率測度 $\mu^+,\mu^-$ が、すべての $a,b\subset E$ で
$$
\mu^+(a\cup b)\,\mu^-(a\cap b)\ge\mu^+(a)\,\mu^-(b)\qquad(\ast)
$$
を満たせば $\mu^-\le_{\mathrm{st}}\mu^+$ である。$s:=\lvert a\cup b\rvert-\lvert a\rvert=\lvert b\rvert-\lvert a\cap b\rvert\ge0$ とおく。$\alpha:=\frac p{1-p}$、$\alpha':=\frac{p'}{1-p'}$ とする。
これは Gri18 Theorem 8.8(p. 159)で、同書は Holley の不等式で示すとだけ述べている。1 は「$p$ を増やすか $q$ を減らすと開いた辺が増える」、2 は「$q$ を増やしても $p/(q(1-p))$ を保てば開いた辺は減らない」ことを言っている。
$q\ge1$、$0< p< 1$ とし、$\pi:=\frac p{p+q(1-p)}$ とおく。$\varphi_{\pi,1}\le_{\mathrm{st}}\varphi_{p,q}\le_{\mathrm{st}}\varphi_{p,1}$ である。
右の不等式は thm-rc-comp の 1 で $(p',q')=(p,q)$、$(p,q)$ を $(p,1)$ としたものである。左の不等式は 2 で $(p',q')=(p,q)$、$(p,q)$ を $(\pi,1)$ としたもので、$\frac\pi{1-\pi}=\frac p{q(1-p)}$ から条件は等号で成り立つ。$\square$
$\pi$ は lem-rc-cond の小さい方の値である。ランダムクラスターモデルの開いた辺は、確率 $\pi$ と $p$ の独立なパーコレーションの間にはさまれる。
$A\subset E$ の階数を $r(A):=\lvert V\rvert-k(A)$ とし、Tutte多項式 を $T(G;x,y)=\sum_{A\subset E}(x-1)^{r(E)-r(A)}(y-1)^{\lvert A\rvert-r(A)}$ で表す(同記事の定義「ランク生成関数」と、それが Tutte 多項式に等しいこと)。
$0< p< 1$、$q>0$ について
$$
Z^{\mathrm{RC}}_G(p,q)=q^{k(E)}p^{r(E)}(1-p)^{\lvert E\rvert-r(E)}\;T\Bigl(G;\,1+\frac{q(1-p)}p,\,\frac1{1-p}\Bigr)
$$
である。2 つの変数は $(x-1)(y-1)=q$ を満たす。
$x-1=q/\alpha$、$y-1=\alpha$($\alpha=\frac p{1-p}$)とおくと、$A$ の項は
$$
\Bigl(\frac q\alpha\Bigr)^{k(A)-k(E)}\alpha^{\lvert A\rvert-\lvert V\rvert+k(A)}=q^{-k(E)}\alpha^{k(E)-\lvert V\rvert}\cdot\alpha^{\lvert A\rvert}q^{k(A)}
$$
である。$A$ について足すと $T=q^{-k(E)}\alpha^{-r(E)}\sum_A\alpha^{\lvert A\rvert}q^{k(A)}$ で、$Z^{\mathrm{RC}}_G=(1-p)^{\lvert E\rvert}\sum_A\alpha^{\lvert A\rvert}q^{k(A)}$ と合わせると主張を得る。$\square$
$q=1$ では $x=\frac1p$ となり、Tutte多項式 の定理「信頼性多項式との関係」と同じ形の計算になる。分配関数は双曲線 $(x-1)(y-1)=q$ の上の Tutte 多項式の値である。
$G$ を連結な平面グラフ図とし、$G^*$ をその双対グラフとする(双対グラフ)。$G$ の辺 $e$ に対応する $G^*$ の辺を $e^*$ とし、$\omega\subset E$ について、閉じた辺の双対を開いたものを $\omega_d:=\{e^*\mid e\in E\setminus\omega\}$ とする。
$0< p< 1$、$q>0$ とし、$p_d\in(0,1)$ を
$$
\frac{p_d}{1-p_d}=\frac{q(1-p)}{p}
$$
で定める。すべての $\omega\subset E$ について $\varphi_{G,p,q}(\omega)=\varphi_{G^*,p_d,q}(\omega_d)$ である。
$H:=(V,\omega)$ の面の個数を $f(\omega)$ とする。双対グラフ の補題「部分グラフの面と双対の成分」により、$f(\omega)$ は $G^*$ から $\omega$ の辺の双対を除いたグラフ、すなわち $(V^*,\omega_d)$ の成分の個数 $k^*(\omega_d)$ に等しい。平面グラフ の命題「連結成分の個数を入れたEulerの公式」を $H$ に使うと $\lvert V\rvert-\lvert\omega\rvert+f(\omega)=1+k(\omega)$ なので、
$$
k(\omega)=k^*(\omega_d)+\lvert V\rvert-1-\lvert\omega\rvert
$$
である。$\lvert\omega\rvert=\lvert E\rvert-\lvert\omega_d\rvert$ を使うと
$$
\alpha^{\lvert\omega\rvert}q^{k(\omega)}=C\cdot\Bigl(\frac q\alpha\Bigr)^{\lvert\omega_d\rvert}q^{k^*(\omega_d)},\qquad C:=\Bigl(\frac\alpha q\Bigr)^{\lvert E\rvert}q^{\lvert V\rvert-1}
$$
で、$q/\alpha=\frac{p_d}{1-p_d}$ である。$\omega\mapsto\omega_d$ は全単射なので、正規化すると主張を得る。$\square$
双対性は Gri18 (8.27)–(8.30)(pp. 168–169)にある。$p_d=p$ となるのは $\bigl(\frac p{1-p}\bigr)^2=q$ のとき、すなわち
$$
p=p_{\mathrm{sd}}(q):=\frac{\sqrt q}{1+\sqrt q}
$$
のときで、これを 自己双対点 という。正方格子は双対がまた正方格子なので、$p_{\mathrm{sd}}(q)$ は臨界点の候補になる。
$q\ge1$ とし、$\mathbb{Z}^d$($d\ge2$)の最近接の辺を考える。有限の箱 $\Lambda$ の外の辺をすべて閉じた(自由境界)または開いた(固定境界)条件のもとで箱の中の測度を作り、$\Lambda\uparrow\mathbb{Z}^d$ とすると、弱極限 $\varphi^0_{p,q}$、$\varphi^1_{p,q}$ が存在し、平行移動で不変になる(Gri18 Theorem 8.13、p. 160。正の相関から、箱を広げたときの単調性が出ることによる)。原点が無限の成分に属する確率を $\theta^b(p,q):=\varphi^b_{p,q}(0\leftrightarrow\infty)$ とし、
$$
p_c(q):=\sup\{p\mid\theta^1(p,q)=0\}
$$
とおく。$\theta^1(p,q)=0$ なら $\varphi^0_{p,q}=\varphi^1_{p,q}$ で、2 つの測度が異なる $p$ は高々可算個である(Gri18 Theorem 8.18、p. 162)。$\theta^0$ で定めた臨界点も同じ値になる。
cor-rc-sandwich を無限体積に移すと、独立なパーコレーションの臨界確率 $p_c(1)$ を使って
$$
p_c(1)\le p_c(q)\le\frac{q\,p_c(1)}{1+(q-1)p_c(1)}\qquad(q\ge1)
$$
を得る(Gri18 Theorem 8.21 と (8.22)、pp. 163–164)。右辺は $\pi=p_c(1)$ を $p$ について解いた値で、とくに $0< p_c(q)< 1$ である。
$d=2$ では、Beffara と Duminil-Copin により、$q\ge1$ で $p_c(q)=p_{\mathrm{sd}}(q)=\frac{\sqrt q}{1+\sqrt q}$ である(Gri18 Theorem 8.25、p. 168)。$q=1$ は独立なパーコレーションの $p_c=\frac12$(Harris–Kesten の定理)、$q=2$ は Ising モデルの臨界温度の計算に当たる(同 p. 168)。cor-rc-corr を通して、整数 $q\ge2$ の Potts 模型の臨界の逆温度 $\log(1+\sqrt q)$ が得られる(Potts模型 の定理「正方格子の臨界点(Beffara–Duminil-Copin)」)。
臨界点で $\theta^1(p_c,q)=0$ となるか(連続な転移)、正のままか(不連続な転移)は $q$ による。$\mathbb{Z}^2$ では $1\le q\le4$ で連続、$q>4$ で不連続であることが、2017 年 12 月の時点の概説 DC18 の §5.2(pp. 17–18)と Figure 6(p. 17)にまとめられている(連続と不連続の定義と二分法は同 Theorem 5.1、p. 16)。高い次元での境目は、Gri18(2018 年)の時点で予想の段階にある(Conjecture 8.23、p. 164)。
$G$ が木なら、どの $\omega$ でも $k(\omega)=\lvert V\rvert-\lvert\omega\rvert$ なので、$\varphi_{p,q}(\omega)\propto(\alpha/q)^{\lvert\omega\rvert}$ で、各辺は独立に確率 $\pi=\frac p{p+q(1-p)}$ で開く。これは lem-rc-cond で両端がつながっていない場合の値である。
$G=C_n$($n$ 頂点の閉路)では、すべての辺が開くと $k=1$、そうでなければ $(V,\omega)$ は森で $k=n-\lvert\omega\rvert$ である。よって
$$
Z^{\mathrm{RC}}_{C_n}(p,q)=(1-p)^n\bigl((q+\alpha)^n-\alpha^n+q\alpha^n\bigr)
$$
で、すべての辺が開く確率は $q\,p^n/Z^{\mathrm{RC}}_{C_n}$ である。$n=3$、$p=0.6$、$q=3$ では $Z=6.264$、すべて開く確率は $0.1034$ である。
$p_{\mathrm{sd}}(1)=\frac12$、$p_{\mathrm{sd}}(2)=\frac{\sqrt2}{1+\sqrt2}=2-\sqrt2\approx0.586$、$p_{\mathrm{sd}}(3)\approx0.634$、$p_{\mathrm{sd}}(4)=\frac23$ である。$p=1-e^{-\beta}$ で逆温度に直すと $\beta=\log(1+\sqrt q)$ で、$q=2,3,4$ では約 $0.881$、$1.005$、$1.099$ である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 辺の独立性のための $q=1$ | 三角形、$p=\frac12$、$q=2$ | 2 辺の開く事象の共分散が $\frac3{196}>0$ |
| 正の相関のための $q\ge1$ | 三角形、$p=\frac12$、$q=\frac12$ | 2 辺の開く事象の共分散が負 |
| thm-rc-comp 2 の $\frac{p'}{q'(1-p')}\ge\frac p{q(1-p)}$ | 1 本の辺、$p'=p$、$q'=2$、$q=1$ | 辺が開く確率が $\frac p{2-p}< p$ に下がる |
| thm-rc-es の $\beta\ge0$ | 1 本の辺で $\beta< 0$ | 色の一致の確率が $\frac1q$ より小さく、cor-rc-corr の右辺($0$ 以上)と合わない |
三角形で $p=\frac12$ のとき、重みは $\omega$ の辺数 $0,1,2,3$ について $q^3,q^2,q,q$ に比例する($\frac12$ の冪は共通)。$Z'=q^3+3q^2+4q$、1 つの辺が開く重みは $q^2+3q$、決まった 2 辺が開く重みは $2q$ なので、共分散は $Z'^{-2}\bigl(2qZ'-(q^2+3q)^2\bigr)=Z'^{-2}q^2(q^2-1)$ である。$q=2$ では $Z'=28$ で $\frac{12}{784}=\frac3{196}$、$q=\frac12$ では負になる(FKG不等式 の反例の表と同じ計算)。
1 本の辺(両端が異なる)では、lem-rc-cond の小さい方の値から、辺が開く確率は $\frac p{p+q(1-p)}$ で、$q=2$ なら $\frac p{2-p}$ である。$q=1$、$p$ の測度より確率が小さいので、2 の結論 $\varphi_{p,2}\ge_{\mathrm{st}}\varphi_{p,1}$ は成り立たない。
1 本の辺の Potts 模型では、色が一致する確率は $\frac{e^\beta}{e^\beta+q-1}$ で、$\beta< 0$ なら $\frac1q$ より小さい。このとき $p=1-e^{-\beta}< 0$ で、$\varphi$ は確率測度にならない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する