Russoの公式(Russo's formula)とは、有限個の独立な $0,1$ の変数がどれも確率 $p$ で $1$ になるとき、増加事象 $A$ の確率の $p$ についての導関数が、その値を変えると $A$ の成否が変わる元(ピボタルな元)の個数の期待値に等しいという公式で、Margulis–Russo の公式とも呼ばれる。任意の事象と変数ごとに異なる確率の場合にも、偏導関数の形で成り立つ。パーコレーションでは BK 不等式と組み合わせて、臨界確率の下での連結確率の指数減衰と、臨界確率の上での無限クラスタの確率の下界を導くのに使われ、鋭い閾値の定理の出発点にもなる。
Russoの公式(Russo's formula)は、有限個の独立な $0,1$ の変数がどれも確率 $p$ で $1$ になるとき、増加事象の確率の $p$ についての導関数が、その事象の ピボタルな元(その値を変えると事象が起きるかどうかが変わる元)の個数の期待値に等しい、という公式である。この公式(またはそれと同値な形)は何人もが独立に見つけており、L. Russo の 1981 年のパーコレーションの臨界確率の論文や、G. Margulis の 1974 年のグラフの連結度の論文がその例である(Gri18 p. 80)。そのため Margulis–Russo の公式とも呼ばれる。
公式そのものは、確率を各変数について 1 次式として書けば直ちに出る。重要なのは右辺の解釈で、「$p$ を少し上げたとき事象の確率がどれだけ増えるか」が「いまの配置で事象の成否を決めている元がいくつあるか」で測れる。パーコレーションでは、この等式と BK不等式 を組み合わせると、臨界確率の下での連結確率の指数的な減衰と、臨界確率の上での無限クラスタの確率の下からの評価が同時に得られる(Duminil-Copin–Tassion の定理)。この記事では公式とその変種を証明し、この定理の完全な証明を与える。
$E$ を有限集合、$N:=\lvert E\rvert$、$\Omega:=\{0,1\}^E$ とし、$\omega(e)=1$ の元を 開いた 元、$0$ の元を 閉じた 元という。$\mathbf p=(p_e)_{e\in E}\in[0,1]^E$ について、各 $e$ が独立に確率 $p_e$ で開く直積測度を $P_{\mathbf p}$ と書き、すべての $p_e$ が $p$ のときは $P_p$ と書く。$\omega\in\Omega$ と $e\in E$ について、$\omega$ の $e$ の値だけを $1$ に替えた配置を $\omega^e$、$0$ に替えた配置を $\omega_e$ とし、事象 $A$ について $A^e:=\{\omega\mid\omega^e\in A\}$、$A_e:=\{\omega\mid\omega_e\in A\}$ とおく。事象 $A$ が 増加 とは、$\omega\in A$、$\omega\le\omega'$(成分ごと)なら $\omega'\in A$ であることをいう。
事象 $A\subseteq\Omega$ と $\omega\in\Omega$ について、$1_A(\omega^e)\ne1_A(\omega_e)$ となる $e\in E$ を、$\omega$ における $A$ の ピボタルな元(pivotal element)という。その事象を $\mathrm{Piv}_e(A)$、$\omega$ におけるピボタルな元の個数を $N_A(\omega)$ と書く。
$\omega^e$ と $\omega_e$ は $\omega(e)$ によらないので、$A^e$、$A_e$、$\mathrm{Piv}_e(A)$ は $e$ 以外の元の値だけで決まる事象であり、直積測度のもとで $\omega(e)$ と独立である。$A$ が増加なら $A_e\subseteq A^e$ で、$\mathrm{Piv}_e(A)=A^e\setminus A_e$ である。パーコレーションでは、ピボタルな辺は「開くと事象が起き、閉じると起きない」辺、すなわち事象を実現するどの開いた道も通らざるをえない辺である。
$E$ を有限集合、$A\subseteq\Omega$ を事象とする。
1:$P_{\mathbf p}(A)=\sum_{\omega\in A}\prod_ep_e^{\omega(e)}(1-p_e)^{1-\omega(e)}$ は多項式である。$e$ を固定する。各 $\omega$ で
$$
1_A(\omega)=\omega(e)\,1_A(\omega^e)+(1-\omega(e))\,1_A(\omega_e)
$$
である($\omega(e)=1$ なら $\omega=\omega^e$、$0$ なら $\omega=\omega_e$)。$1_A(\omega^e)$ と $1_A(\omega_e)$ は $e$ 以外の元だけで決まり、$\omega(e)$ と独立なので、期待値をとると
$$
P_{\mathbf p}(A)=p_e\,P_{\mathbf p}(A^e)+(1-p_e)\,P_{\mathbf p}(A_e)
$$
である。$P_{\mathbf p}(A^e)$ と $P_{\mathbf p}(A_e)$ は $e$ 以外の元の分布だけで決まるので $p_e$ によらない。よって右辺は $p_e$ の 1 次式で、$p_e$ についての偏導関数は $P_{\mathbf p}(A^e)-P_{\mathbf p}(A_e)$ である。
2:$p\mapsto(p,\dots,p)$ に連鎖律を使う。
3:$A$ が増加なら $A_e\subseteq A^e$、$A^e\setminus A_e=\mathrm{Piv}_e(A)$ なので、2 の各項は $P_p(\mathrm{Piv}_e(A))$ で、和は $E_p[N_A]$ である。次に、$\omega\in\mathrm{Piv}_e(A)$ のとき、$\omega(e)=1$ なら $\omega=\omega^e\in A$、$\omega(e)=0$ なら $\omega=\omega_e\notin A$ である。よって $\mathrm{Piv}_e(A)\cap\{\omega(e)=1\}=\mathrm{Piv}_e(A)\cap A$ である。$\mathrm{Piv}_e(A)$ と $\omega(e)$ は独立なので
$$
P_p(\mathrm{Piv}_e(A)\cap A)=P_p(\mathrm{Piv}_e(A))\,P_p(\omega(e)=1)=p\,P_p(\mathrm{Piv}_e(A))
$$
であり、$e$ について足すと $E_p[N_A1_A]=p\,E_p[N_A]$ を得る。$\omega(e)=0$ の側も同様で、$E_p[N_A1_{\Omega\setminus A}]=(1-p)E_p[N_A]$ である。$\square$
1 の証明は事象の指示関数に限らない。$X\colon\Omega\to\mathbb R$ について、同じ計算で $\frac{d}{dp}E_p[X]=\sum_eE_p[X(\omega^e)-X(\omega_e)]$ を得る(Gri18 Exercise 4.9、p. 84)。
$A=\{$すべての元が開$\}$ なら $P_p(A)=p^N$ である。$e$ がピボタルなのは $e$ 以外がすべて開くときで、その確率は $p^{N-1}$ なので、$E_p[N_A]=Np^{N-1}=\frac{d}{dp}p^N$ である。
$1\le k\le N$ とし、$A_k=\{$開いた元が $k$ 個以上$\}$ とする。$e$ がピボタルなのは、$e$ 以外の $N-1$ 個のうちちょうど $k-1$ 個が開くときである。よって
$$
\frac{d}{dp}P_p(A_k)=N\binom{N-1}{k-1}p^{k-1}(1-p)^{N-k}
$$
である。左辺は 2 項分布 $\mathrm{Bin}(N,p)$ の上側の確率の導関数で、右辺は、$[0,1]$ の一様乱数 $N$ 個のうち $k$ 番目に小さいものの密度である。$N=3$、$k=2$ では $P_p(A_2)=3p^2-2p^3$ で、両辺は $6p(1-p)$ である。
公式を対数の導関数として読むと、ピボタルな元が多い事象ほど、$p$ を下げたときに確率が速く減ることが分かる。
$A\ne\emptyset$ を増加事象とし、$0< p< 1$ とする。
すべてが開いた配置は $A$ に属するので、$p>0$ で $P_p(A)>0$ である。1 は thm-rus-main の 3 の $E_p[N_A1_A]=pE_p[N_A]$ を $P_p(A)$ で割ったものである。2:仮定から $E_p[N_A\mid A]\ge m$ なので $\frac{d}{dp}\log P_p(A)\ge\frac mp$ で、$p_1$ から $p_2$ まで積分すると $\log\frac{P_{p_2}(A)}{P_{p_1}(A)}\ge m\log\frac{p_2}{p_1}$ である($p_2=1$ は連続性による)。$\square$
ex-rus-binomial の $A$ では、どの配置でもピボタルな元は $N$ 個で、2 は等号 $p_1^N=(p_1/p_2)^Np_2^N$ になる。
$d\ge1$ とし、$\mathbb Z^d$ の Bernoulli 結合パーコレーションの測度を $P_p$、原点が無限クラスタに属する確率を $\theta(p)$、臨界確率を $p_c=\sup\{p\mid\theta(p)=0\}$ とする(パーコレーション の定義)。$\Lambda(n):=\{-n,\dots,n\}^d$、$\partial\Lambda(n):=\Lambda(n)\setminus\Lambda(n-1)$、$E_n:=\{0\leftrightarrow\partial\Lambda(n)\}$、$g_p(n):=P_p(E_n)$ とおく。$E_n$ は両端が $\Lambda(n)$ にある辺だけで決まる増加事象で、$g_p(n)$ は $p$ の多項式である。有限集合 $S\ni0$ について、BK不等式 の節「パーコレーションへの応用」と同じく、$S$ の点と $S$ の外の点を結ぶ辺の集合を $\Delta S$($\langle x,y\rangle\in\Delta S$ では $x\in S$)、頂点がすべて $S$ にある開いた道で $0$ と $x$ が結ばれる事象を $0\overset{S}{\leftrightarrow}x$ とし、
$$
\varphi_p(S):=p\sum_{\langle x,y\rangle\in\Delta S}P_p\bigl(0\overset{S}{\leftrightarrow}x\bigr),\qquad \tilde p_c:=\sup\{p\in[0,1]\mid \varphi_p(S)< 1 \text{ となる有限集合 } S\ni0 \text{ がある}\}
$$
とおく($\varphi_0(\{0\})=0$ なので集合は空でない)。
証明は 2 つの部分からなる。$\tilde p_c$ より下では、$\varphi_p(S)< 1$ となる $S$ があり、BK不等式 の命題「有限の集合を出る辺による減衰の評価」から指数減衰が出る。$\tilde p_c$ より上では、どの $S$ でも $\varphi_p(S)\ge1$ で、Russo の公式から $g_p(n)$ についての微分不等式が出る。
段 1($p< \tilde p_c$ での指数減衰)。 $P_p(0\overset{S}{\leftrightarrow}x)$ は増加事象の確率なので $p$ について非減少で(パーコレーション の命題「単調性と 0-1 法則」の証明の結合)、$\varphi_p(S)$ も $p$ について非減少である。$p< \tilde p_c$ なら、$\tilde p_c$ の定義から $p< p'$ で $\varphi_{p'}(S)< 1$ となる $p'$ と $S$ があり、$\varphi_p(S)\le\varphi_{p'}(S)< 1$ である。$S\subseteq\Lambda(L-1)$ となる $L$ をとると、BK不等式 の命題「有限の集合を出る辺による減衰の評価」から $g_p(n)\le\varphi_p(S)^{\lfloor n/L\rfloor}$ で、2 の形の評価を得る。とくに $\theta(p)\le\lim_ng_p(n)=0$ である。
段 2($\tilde p_c< p< 1$ での微分不等式)。 $n\ge1$ を固定し、$\Lambda(n)$ の点のうち $\partial\Lambda(n)$ と開いた道で結ばれない点の集合を $\mathcal S$ とする(ランダムな集合)。$\partial\Lambda(n)$ の点は自分自身と結ばれるので $\mathcal S\subseteq\Lambda(n-1)$ であり、$0\in\mathcal S$ は $E_n$ が起きないことと同値である。$S\ni0$ を $\Lambda(n-1)$ の部分集合とする。
(a) $\{\mathcal S=S\}$ は、「$\Lambda(n)\setminus S$ のどの点も、$S$ を通らない開いた道で $\partial\Lambda(n)$ と結ばれる」と「$\Delta S$ の辺がすべて閉じている」の共通部分に等しい。実際 $\mathcal S=S$ なら、$S$ の外の点から $\partial\Lambda(n)$ への開いた道の頂点はどれも $\partial\Lambda(n)$ と結ばれるので $S$ に入らず、$\langle x,y\rangle\in\Delta S$ が開いていれば $y\notin S$ を通って $x$ が $\partial\Lambda(n)$ と結ばれてしまう。逆に右辺の 2 条件のもとでは、$S$ の外の点は $\mathcal S$ に入らず、$S$ の点から出る開いた道は $\Delta S$ の辺を通れないので $S$ から出られず、$S\cap\partial\Lambda(n)=\emptyset$ から $\partial\Lambda(n)$ に着かない。右辺は両端が $S$ にある辺を使わずに書けているので、$\{\mathcal S=S\}$ は両端が $S$ にない辺だけで決まる。一方 $0\overset{S}{\leftrightarrow}x$ は両端が $S$ にある辺だけで決まる。よって両者は独立である。
(b) 辺 $e$ について、「$e$ が閉じていて $E_n$ のピボタルな辺である」ことは、「$0\in\mathcal S$、$e=\langle x,y\rangle\in\Delta\mathcal S$($x\in\mathcal S$)、$0\overset{\mathcal S}{\leftrightarrow}x$」と同値である。$\Rightarrow$:$E_n$ は起きていないので $0\in\mathcal S$ である。$e$ を開くと $0$ から $\partial\Lambda(n)$ への開いた自己回避の道ができ、それは $e$ を通る。$e$ の手前の端点を $x$、先の端点を $y$ とすると、$0$ から $x$ までの部分の頂点は $0$ と結ばれるので $\mathcal S$ に属し、$y$ は $\partial\Lambda(n)$ と結ばれるので $\mathcal S$ に属さない。$\Leftarrow$:$x\in\mathcal S$ なので $e$ は閉じている(開いていれば $y$ を通って $x$ が $\partial\Lambda(n)$ と結ばれる)。$e$ を開くと $0$ から $x$、$e$、$y$ から $\partial\Lambda(n)$ がつながり、閉じると $0\in\mathcal S$ なので $E_n$ は起きない。
thm-rus-main の 3 と (b)、(a) から
$$
\begin{aligned}
(1-p)\frac{d}{dp}g_p(n)&=\sum_eP_p(e \text{ が閉でピボタル})=\sum_{S\ni0}\ \sum_{\langle x,y\rangle\in\Delta S}P_p\bigl(\mathcal S=S,\ 0\overset{S}{\leftrightarrow}x\bigr)\\
&=\sum_{S\ni0}P_p(\mathcal S=S)\sum_{\langle x,y\rangle\in\Delta S}P_p\bigl(0\overset{S}{\leftrightarrow}x\bigr)=\frac1p\sum_{S\ni0}\varphi_p(S)\,P_p(\mathcal S=S)
\end{aligned}
$$
である(和は $\Lambda(n-1)$ の部分集合 $S\ni0$ について)。$p>\tilde p_c$ ではどの $S$ でも $\varphi_p(S)\ge1$ なので、右辺は $\frac1pP_p(0\in\mathcal S)=\frac1p(1-g_p(n))$ 以上である。すなわち
$$
\frac{d}{dp}g_p(n)\ge\frac{1-g_p(n)}{p(1-p)}\qquad(\tilde p_c< p< 1)
$$
である。
段 3(積分)。 $p< 1$ ではすべての辺が閉じる確率が正なので $g_p(n)< 1$ である。$\tilde p_c< p_0< p< 1$ とすると、段 2 は $\frac{d}{dp}\bigl(-\log(1-g_p(n))\bigr)\ge\frac{d}{dp}\log\frac p{1-p}$ と書けるので、$p_0$ から $p$ まで積分して $-\log(1-g_{p_0}(n))\ge0$ を使うと
$$
\frac1{1-g_p(n)}\ge\frac{p(1-p_0)}{p_0(1-p)},\qquad\text{すなわち}\qquad g_p(n)\ge\frac{p-p_0}{p(1-p_0)}
$$
である。$\lvert C\rvert=\infty$ はすべての $n$ で $E_n$ が起きることと同値で、$E_n$ は $n$ について減少するので $g_p(n)\to\theta(p)$ である。$n\to\infty$、次に $p_0\downarrow\tilde p_c$ として、$\theta(p)\ge\frac{p-\tilde p_c}{p(1-\tilde p_c)}$($\tilde p_c< p< 1$)を得る。$p=1$ では $\theta(1)=1$ である。
段 4($\tilde p_c=p_c$)。 段 1 から $p< \tilde p_c$ なら $\theta(p)=0$ なので $\tilde p_c\le p_c$ である。段 3 から $p>\tilde p_c$ なら $\theta(p)>0$ で、$\theta$ は非減少なので $p\ge p_c$ である。よって $p_c\le\tilde p_c$ で、1 が示された。2、3 は段 1、段 3 で $\tilde p_c$ を $p_c$ に替えたものである。$\square$
2 は Menshikov と Aizenman–Barsky が 1986 年ごろに別の方法で示した、臨界点の下での指数減衰である(Gri18 pp. 86–87)。上の証明は H. Duminil-Copin と V. Tassion の 2016 年の論文によるもので、Gri18 Theorem 5.1 の証明(pp. 87–90)の筋に従っている。3 は臨界点のすぐ上で $\theta(p)$ が少なくとも 1 次で立ち上がることを述べ、「平均場の下界」と呼ばれる。$\theta(p_c)=0$(臨界点で無限クラスタがないこと)は 3 からは出ない。Gri18 Conjecture 5.8(p. 90)はこれを $d\ge2$ のすべてで予想し、2018 年の時点で知られていたのは $d=2$ と $d\ge11$ である。
増加事象 $A$ について $f(p):=P_p(A)$ は $0$ から $1$ へ増える。Russo の公式でピボタルな元の期待値(すべての元の 影響 の和)を下から抑えられれば、$f$ が狭い区間で $0$ に近い値から $1$ に近い値へ移ることが分かる。下からの評価は、Kahn–Kalai–Linial の型の影響の不等式(Gri18 §4.5)で与えられる。
定数 $c>0$ があって、次が成り立つ。$N=\lvert E\rvert\ge1$ とし、$A\ne\emptyset,\Omega$ を増加事象とする。$E$ の置換の部分群で $E$ に推移的に作用するものがあり、$A$ がその作用で不変なら、$0< p< 1$ で
$$
\frac{d}{dp}P_p(A)\ge c\,P_p(A)\bigl(1-P_p(A)\bigr)\log N
$$
である。
Gri18 Theorem 4.69(p. 81)。E. Friedgut と G. Kalai の 1996 年の定理で、Gri18 は影響の不等式(同 Theorem 4.38)と thm-rus-main から導いている。この記事では証明しない。帰結として、$h(p):=\log\frac{f(p)}{1-f(p)}$ は $h'(p)=\frac{f'(p)}{f(p)(1-f(p))}\ge c\log N$ を満たすので、$0< \varepsilon< \frac12$ について $f$ が $\varepsilon$ から $1-\varepsilon$ まで増える $p$ の区間の長さは $\frac{2}{c\log N}\log\frac{1-\varepsilon}\varepsilon$ 以下である。対称性がない場合の Talagrand による形は Gri18 Theorem 4.68(p. 81)にある。この方向の最初の結果は Russo の 1982 年の近似的な 0-1 法則で、$\log N$ の量的な形は含んでいなかった(Gri18 p. 82)。$\mathbb Z^2$ の臨界確率が $\frac12$ であること(パーコレーション の定理「Kesten の定理」)にも、この種の議論による証明がある。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 直積測度(thm-rus-main) | 2 元 $e,f$ が同じ値をとり、その値が確率 $p$ で $1$、$A=\{e,f \text{ がともに開}\}$ | $\frac{d}{dp}P(A)=1$ だが $E[N_A]=2p$($p\ne\frac12$ で不一致) |
| $A$ が増加(thm-rus-main の 3) | $A=\{e \text{ が閉}\}$ | $\frac{d}{dp}P_p(A)=-1$ だが $E_p[N_A]=1$ |
| $E$ が有限(thm-rus-main) | $E=\{1,2,\dots\}$、$A=\{\liminf_nS_n/n\ge\frac12\}$($S_n$ は $1,\dots,n$ のうち開いた元の数) | $P_p(A)$ が微分できて導関数が $E_p[N_A]$ に等しいこと($N_A\equiv0$ だが $P_p(A)$ は $p=\frac12$ で不連続) |
| ピボタルな元が $m$ 個以上(cor-rus-log の 2) | $N=2$、$A=\{$開いた元が $1$ 個以上$\}$、$m=1$ | $P_{p_1}(A)>(p_1/p_2)P_{p_2}(A)$($p_1< p_2$) |
要点:1 行目は 2 元の連動、3 行目は大数の強法則、4 行目は両方が開いた配置にピボタルな元がないことによる。
1 行目:$P(A)=p$ なので導関数は $1$ である。$e$ がピボタルなのは $f$ が開くときで、その確率は $p$、$f$ も同じなので $E[N_A]=2p$ である。
2 行目:$P_p(A)=1-p$ で、$e$ はどの配置でもピボタルである($\omega^e\notin A$、$\omega_e\in A$)。一般の形 2 では $P_p(A^e)-P_p(A_e)=0-1=-1$ で、2 は成り立つ。
3 行目:1 つの元の値を変えると $S_n$ は高々 $1$ 変わり、$S_n/n$ の下極限は変わらないので、どの元もピボタルでない。大数の強法則 から $P_p$ のもとでほとんど確実に $S_n/n\to p$ なので、$P_p(A)$ は $p\ge\frac12$ で $1$、$p< \frac12$ で $0$ である。よって $p=\frac12$ で不連続で微分できず、$P_{0.6}(A)-P_{0.4}(A)=1\ne0=\int_{0.4}^{0.6}E_p[N_A]\,dp$ である。
4 行目:$P_p(A)=2p-p^2$ で、$P_p(A)/p=2-p$ は $p$ について減少するので、$p_1< p_2$ で $P_{p_1}(A)/p_1>P_{p_2}(A)/p_2$ である。両方が開いた配置では、どちらの元を閉じても $A$ は起きるので、ピボタルな元はない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する