Jansonの不等式

同義語:Janson's inequality

概要

Jansonの不等式(Janson's inequality)とは、有限集合の元を独立に選んで作る無作為な部分集合 $R$ と部分集合 $D_1,\dots,D_m$ について、どの $D_i$ も $R$ に含まれない確率が $\exp(-\mu+\Delta/2)$ 以下である、という不等式である。$\mu$ は $R$ に含まれる $D_i$ の個数の期待値、$\Delta$ は共通の元をもつ $D_i,D_j$ の順序対について両方が含まれる確率の和である。Harris の不等式から証明でき、ランダムグラフが部分グラフを含まない確率を指数関数的に評価する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 確率論的方法, Erdős–Rényiのランダムグラフ, Markovの不等式

Jansonの不等式(Janson's inequality)とは、有限集合の各元を独立に選んで作る無作為な部分集合 $R$ と、部分集合 $D_1,\dots,D_m$ について、「$D_i\subset R$」という事象がどれも起こらない確率を
$$ P(\text{どの }D_i\text{ も }R\text{ に含まれない})\le\exp\Bigl(-\mu+\frac\Delta2\Bigr) $$
と上から抑える不等式である。ここで $\mu$ は起こる事象の個数の期待値、$\Delta$ は共通の元をもつ $D_i,D_j$ の組について両方が起こる確率を足したもので、事象どうしの依存の強さを測る。
事象がすべて独立なら、どれも起こらない確率は $\prod_i(1-P(D_i\subset R))\le e^{-\mu}$ である。Janson の不等式は、依存が弱い($\Delta$ が小さい)ときにも、ほぼ同じ指数関数の評価が成り立つことを述べる。確率論的方法 の第 2 モーメント法(Chebyshevの不等式)は「どれも起こらない確率は $\mathrm{Var}(X)/\mu^2$ 以下」という多項式の程度の評価しか与えないので、Janson の不等式はこれを指数関数の評価に強める道具である。ランダムグラフで、ある部分グラフを 1 つも含まない確率を見積もるのが典型的な使い方である。
この記事では、Harris の不等式を準備して Janson の不等式を証明し、依存が強い場合の拡張版、下側の裾の評価を示す。応用として、$G(n,p)$ が三角形を含まない確率の極限 $e^{-c^3/6}$($p=c/n$)と、$p$ が大きいときの指数関数の評価を導く。

設定

$\Gamma$ を有限集合とし、各 $s\in\Gamma$ に $0\le q_s< 1$ を与える。各 $s$ を確率 $q_s$ で独立に選んで無作為な部分集合 $R\subset\Gamma$ を作る。$\Gamma$ の空でない部分集合 $D_1,\dots,D_m$ について
$$ B_i:=\{D_i\subset R\},\qquad I_i:=\mathbf 1_{B_i},\qquad X:=\sum_{i=1}^mI_i,\qquad p_i:=P(B_i)=\prod_{s\in D_i}q_s $$
とおく。$X$ は $R$ に含まれる $D_i$ の個数である。

期待値と依存の量

$i\ne j$ で $D_i\cap D_j\ne\emptyset$ のとき $i\sim j$ と書き、
$$ \mu:=E[X]=\sum_ip_i,\qquad\Delta:=\sum_{(i,j):\,i\sim j}P(B_i\cap B_j) $$
とおく。$\Delta$ の和は順序対 $(i,j)$ についてとる($(i,j)$ と $(j,i)$ を別に数える)。

$i\not\sim j$($i\ne j$)なら $B_i$ と $B_j$ は互いに素な座標の集合で決まるので独立である。$\Delta$ は独立でないかもしれない組だけを数える。文献によっては、順序を区別しない組で和をとった $\Delta/2$ を $\Delta$ と書くので注意する。

Harris の不等式

$R$ を $\{0,1\}^\Gamma$ の元($s\in R$ なら $1$)と同一視し、成分ごとの大小で順序を入れる。関数 $f\colon\{0,1\}^\Gamma\to\mathbb{R}$ が 増加 であるとは、$\omega\le\omega'$ なら $f(\omega)\le f(\omega')$ であることをいい、$-f$ が増加のとき 減少 という。事象は指示関数が増加(減少)のとき増加(減少)という。$B_i$ は増加事象で、補事象 $\overline{B_i}$ は減少事象である。

Harris の不等式

$f,g$ がともに増加、またはともに減少なら $E[fg]\ge E[f]E[g]$ である。$f$ が増加で $g$ が減少なら $E[fg]\le E[f]E[g]$ である。

要点:座標の個数についての帰納法で、パーコレーション の定理「Harris の不等式」の証明と同じである(確率 $q_s$ が座標ごとに違っても同じ議論が通る)。

証明を開く

ともに増加の場合を示せば、ともに減少の場合は $-f,-g$ に、増加と減少の場合は $f,-g$ に使えばよい。座標が 1 個のとき、$\omega,\omega'$ を独立で同じ分布の変数とすると $(f(\omega)-f(\omega'))(g(\omega)-g(\omega'))\ge0$ で、期待値をとって $2(E[fg]-E[f]E[g])\ge0$ である。座標が $k\ge2$ 個のとき、1 つの座標 $s$ を除いた座標を固定した条件付き期待値を考える。固定した値ごとに $f,g$ は $\omega_s$ の増加関数なので、1 個の場合から $E[fg\mid\omega_{\ne s}]\ge f_1g_1$、ただし $f_1:=E[f\mid\omega_{\ne s}]$、$g_1:=E[g\mid\omega_{\ne s}]$ である。座標が独立なので $f_1,g_1$ は残りの $k-1$ 個の座標の増加関数であり、帰納法の仮定から $E[f_1g_1]\ge E[f_1]E[g_1]=E[f]E[g]$ である。$\square$

独立な場合との比較

$P(X=0)\ge\prod_{i=1}^m(1-p_i)$ である。

減少事象の共通部分は減少事象なので、lem-jan-harris を $\overline{B_m}$ と $\overline{B_1}\cap\cdots\cap\overline{B_{m-1}}$ に使い、$m$ についての帰納法で $P(\overline{B_1}\cap\cdots\cap\overline{B_m})\ge\prod_i P(\overline{B_i})$ を得る。$\square$

$\log(1-p)\ge-p/(1-p)$ なので、$\pi:=\max_ip_i< 1$ なら $P(X=0)\ge\exp(-\mu/(1-\pi))$ でもある。

主定理

Janson の不等式

上の設定で
$$ P(X=0)\le\exp\Bigl(-\mu+\frac\Delta2\Bigr) $$
である。

条件付き確率の積に分ける

$Q_i:=P\bigl(B_i\mid\overline{B_1}\cap\cdots\cap\overline{B_{i-1}}\bigr)$ とおく($q_s< 1$ と $D_j\ne\emptyset$ から $p_j< 1$ なので、cor-jan-lower により条件の事象の確率は正である)。
$$ P(X=0)=\prod_{i=1}^m(1-Q_i)\le\exp\Bigl(-\sum_iQ_i\Bigr) $$
なので、$Q_i\ge p_i-\sum_{j< i,\,j\sim i}P(B_i\cap B_j)$ を示せばよい。これを $i$ について足すと、右辺の第 2 項の和は順序を区別しない組ごとに 1 回ずつ数えるので $\Delta/2$ になる。
$i$ を固定し、$j< i$ を $j\sim i$ のものと $j\not\sim i$ のものに分けて、$E:=\bigcap_{j< i,\,j\sim i}\overline{B_j}$、$F:=\bigcap_{j< i,\,j\not\sim i}\overline{B_j}$ とおく。$P(E\cap F)\le P(F)$ なので
$$ Q_i=\frac{P(B_i\cap E\cap F)}{P(E\cap F)}\ge\frac{P(B_i\cap E\cap F)}{P(F)}=P(B_i\cap E\mid F) $$
である。さらに
$$ P(B_i\cap E\mid F)\ge P(B_i\mid F)-\sum_{j< i,\,j\sim i}P(B_i\cap B_j\mid F) $$
である。$F$ は $D_i$ の外の座標だけで決まるので $B_i$ と独立で、$P(B_i\mid F)=p_i$ である。$B_i\cap B_j$ は増加事象、$F$ は減少事象なので、lem-jan-harris により $P(B_i\cap B_j\cap F)\le P(B_i\cap B_j)P(F)$、すなわち $P(B_i\cap B_j\mid F)\le P(B_i\cap B_j)$ である。以上で示すべき不等式を得る。$\square$

cor-jan-lower と合わせると、$\Delta\to0$、$\pi\to0$ となる状況では $P(X=0)$ は $e^{-\mu}$ にほぼ等しい。すなわち $X=0$ の確率は、平均 $\mu$ の Poisson分布 で $0$ をとる確率と同じ程度である。
$\Delta$ が $\mu$ より大きいと右辺は $1$ を超え、thm-jan-main は何も言わない。そのときは事象の一部だけを使う。

Janson の不等式の拡張版

$\Delta\ge\mu>0$ なら
$$ P(X=0)\le\exp\Bigl(-\frac{\mu^2}{2\Delta}\Bigr) $$
である。

事象を無作為に間引く

$S\subset\{1,\dots,m\}$ について、$\mu_S:=\sum_{i\in S}p_i$、$\Delta_S$ を $i,j\in S$ の順序対だけの和とする。$X=0$ なら $S$ のどの $B_i$ も起こらないので、thm-jan-main を $S$ の事象に使って $P(X=0)\le\exp(-\mu_S+\Delta_S/2)$ である。
$0< r\le1$ とし、$S$ を各 $i$ を独立に確率 $r$ で含めて無作為に選ぶ($R$ とは別の乱数)。$S$ についての期待値は $E_S[\mu_S]=r\mu$、$E_S[\Delta_S]=r^2\Delta$ なので、$\mu_S-\Delta_S/2\ge r\mu-r^2\Delta/2$ となる $S$ が存在する。$r:=\mu/\Delta$ とすると右辺は $\mu^2/(2\Delta)$ である。$\square$

期待値より小さい側への偏りの確率も、同じ量で抑えられる。$\Lambda:=\mu+\Delta$ とおく。

下側の裾の評価

$0\le t\le\mu$ について
$$ P(X\le\mu-t)\le\exp\Bigl(-\frac{t^2}{2\Lambda}\Bigr) $$
である。さらに $P(X=0)\le e^{-\mu^2/\Lambda}$ である。

要点:Laplace 変換 $\psi(\lambda):=E[e^{-\lambda X}]$ について、Harris の不等式と Jensen の不等式で $-(\log\psi)'(\lambda)\ge\mu e^{-\lambda\Lambda/\mu}$ を示し、Markovの不等式 に使う。

証明を開く

$\mu=0$ なら $t=0$ で自明なので $\mu>0$ とする。$\lambda\ge0$ について $-\psi'(\lambda)=\sum_iE[I_ie^{-\lambda X}]$ である。$p_i>0$ の $i$ を固定し、$Y_i:=\sum_{j:\,D_j\cap D_i\ne\emptyset}I_j$($j=i$ を含む)、$Z_i:=X-Y_i$ とおく。$B_i$ を条件とする $R$ の分布は、$D_i$ の座標を $1$ に固定し残りを独立に選ぶ積の分布なので、lem-jan-harris がそのまま使える。$e^{-\lambda Y_i}$、$e^{-\lambda Z_i}$ はともに減少関数なので

$E[I_ie^{-\lambda X}]=p_iE[e^{-\lambda Y_i}e^{-\lambda Z_i}\mid B_i]\ge p_iE[e^{-\lambda Y_i}\mid B_i]\,E[e^{-\lambda Z_i}\mid B_i]$

である。$Z_i$ は $D_i$ の外の座標だけで決まるので $E[e^{-\lambda Z_i}\mid B_i]=E[e^{-\lambda Z_i}]\ge\psi(\lambda)$($Z_i\le X$)であり、Jensen の不等式から $E[e^{-\lambda Y_i}\mid B_i]\ge\exp(-\lambda E[Y_i\mid B_i])$ である。重み $p_i/\mu$ についてもう一度 Jensen の不等式を使うと

$-\dfrac{\psi'(\lambda)}{\psi(\lambda)}\ge\sum_ip_ie^{-\lambda E[Y_i\mid B_i]}\ge\mu\exp\Bigl(-\dfrac\lambda\mu\sum_ip_iE[Y_i\mid B_i]\Bigr)=\mu e^{-\lambda\Lambda/\mu}$

である。最後の等号は $\sum_ip_iE[Y_i\mid B_i]=\sum_iE[I_iY_i]=\sum_ip_i+\sum_{i\sim j}E[I_iI_j]=\Lambda$ による。$0$ から $\lambda$ まで積分し、$1-e^{-u}\ge u-u^2/2$($u\ge0$)を使うと

$-\log\psi(\lambda)\ge\dfrac{\mu^2}\Lambda\bigl(1-e^{-\lambda\Lambda/\mu}\bigr)\ge\lambda\mu-\dfrac{\lambda^2\Lambda}2$

である。Markov の不等式から $P(X\le\mu-t)=P(e^{-\lambda X}\ge e^{-\lambda(\mu-t)})\le e^{\lambda(\mu-t)}\psi(\lambda)\le\exp(-\lambda t+\lambda^2\Lambda/2)$ であり、$\lambda:=t/\Lambda$ とおけばよい。また $P(X=0)\le\psi(\lambda)\le\exp\bigl(-\frac{\mu^2}\Lambda(1-e^{-\lambda\Lambda/\mu})\bigr)$ で $\lambda\to\infty$ とすると最後の主張を得る。$\square$

$P(X=0)$ についての 3 つの評価の指数 $\mu-\Delta/2$、$\mu^2/(2\Delta)$、$\mu^2/\Lambda$ を比べると、$\Delta$ が $\mu$ より十分小さいときは thm-jan-main が良い評価を与える。$\Delta\ge\mu$ では $\Lambda\le2\Delta$ なので $\mu^2/\Lambda\ge\mu^2/(2\Delta)$ で thm-jan-lower-tail の方が良いが、thm-jan-extended の指数はその半分以上あり、thm-jan-main だけから出る。

4 頂点のランダムグラフ

$G(4,\frac12)$ で、$\Gamma$ を 6 個の頂点の対、$q_s=\frac12$、$D_1,\dots,D_4$ を 4 つの三角形の辺の集合とする。$X=0$ は三角形を含まないことである。$\mu=4\cdot\frac18=\frac12$ である。2 つの三角形は必ず 1 辺を共有するので、順序対は $12$ 組あり、どれも辺 $5$ 本を使うので $\Delta=12\cdot\frac1{32}=\frac38$ である。三角形を含まないラベル付きのグラフは $64$ 個中 $41$ 個で、
$$ 0.586\approx\Bigl(\frac78\Bigr)^4\le P(X=0)=\frac{41}{64}\approx0.641\le e^{-1/2+3/16}\approx0.732 $$
である(左は cor-jan-lower、右は thm-jan-main。$41$ は全数を数えて確かめた)。

応用:三角形を含まない確率

$G(n,p)$ は $n$ 頂点の各対を独立に確率 $p$ で辺にしたランダムグラフである(Erdős–Rényiのランダムグラフ)。$\Gamma$ を頂点の対の全体、$q_s=p$、$D_T$ を 3 頂点の集合 $T$ の 3 辺とすると、$X$ は三角形の個数である。

三角形を含まない確率

$n\ge4$、$0< p< 1$、$G_n\sim G(n,p)$ とし、$\mu=\binom n3p^3$ とする。

  1. $c>0$ を定数とし $p=c/n$ とすると、$n\to\infty$ で $P(G_n\text{ が三角形を含まない})\to e^{-c^3/6}$ である。
  2. $P(G_n\text{ が三角形を含まない})\le\exp\bigl(-\min\{\mu/2,\ n^2p/36\}\bigr)$ である。

異なる $T,T'$ について $T\sim T'$ は 2 頂点を共有すること、すなわち 1 辺を共有することであり、このとき辺は合わせて $5$ 本である。順序対 $(T,T')$ は、$T$、共有する辺、$T'$ の残りの頂点を選んで $\binom n3\cdot3(n-3)$ 組あるので
$$ \Delta=3(n-3)\binom n3p^5 $$
である。
1:$\mu=\binom n3c^3/n^3\to c^3/6$、$\Delta\le\frac{n^3}6\cdot3n\cdot\frac{c^5}{n^5}=\frac{c^5}{2n}\to0$ なので、thm-jan-main から上極限は $e^{-c^3/6}$ 以下である。cor-jan-lower と $\log(1-x)\ge-x/(1-x)$ から、確率は $\exp\bigl(-\binom n3p^3/(1-p^3)\bigr)$ 以上で、これは $e^{-c^3/6}$ に近づく。
2:$\Delta< \mu$ なら thm-jan-main から確率は $e^{-\mu/2}$ 以下である。$\Delta\ge\mu$ なら thm-jan-extended から確率は $\exp(-\mu^2/(2\Delta))$ 以下で、
$$ \frac{\mu^2}{2\Delta}=\frac{n(n-1)(n-2)p}{36(n-3)}\ge\frac{n^2p}{36} $$
である($(n-1)(n-2)\ge n(n-3)$)。$\square$

確率論的方法 の命題「ランダムグラフの三角形」は第 2 モーメント法で、$np\to\infty$ なら三角形を含まない確率が $0$ に近づくことを示す。その証明の評価は $12/(np)^3+72/(n\cdot np)$ で、多項式の程度でしか小さくならない。prop-jan-triangle の 2 は、$np\to\infty$ のとき確率が $\exp(-\min\{\mu/2,n^2p/36\})$ と指数関数的に小さいことを示す。$\Delta\ge\mu$ の場合は確率が $\exp(-n^2p/36)$ 以下で、この指数は定数倍を除いて最良である。辺が 1 本もないグラフは三角形を含まないので、確率は $(1-p)^{\binom n2}$ 以上であり、$p\le\frac12$ なら $1-p\ge e^{-2p}$ から $e^{-n^2p}$ 以上である。
1 は、三角形が $0$ 個である確率が、平均 $c^3/6$ の Poisson分布 で $0$ をとる確率に近づくことを述べ、Erdős–Rényiのランダムグラフ の反例の表で使われている極限 $1-e^{-c^3/6}$ を与える。$n=1000$、$c=2$ では、cor-jan-lower の下界は約 $0.2647$、thm-jan-main の上界は約 $0.2668$ で、極限 $e^{-4/3}\approx0.2636$ に近い。

反例:仮定を外すと成り立たないこと

外す仮定反例成り立たなくなること
$R$ の座標の独立性$\Gamma=\{1,\dots,m\}$、確率 $\frac12$ で $R=\Gamma$、残りの確率 $\frac12$ で $R=\emptyset$。$D_i=\{i\}$、$m\ge2$$\Delta=0$、$\mu=\frac m2$ だが $P(X=0)=\frac12>e^{-m/2}$
lem-jan-harris の単調性$\Gamma=\{1\}$、$q_1=\frac12$、$f=\mathbf 1_{\{1\in R\}}$、$g=\mathbf 1_{\{1\notin R\}}$$f$ は増加だが $g$ は増加でなく、$E[fg]=0< \frac14=E[f]E[g]$
thm-jan-extended の $\Delta\ge\mu$$\Gamma=\{1,2,3\}$、$q_s=\frac12$、$D_1=\{1,2\}$、$D_2=\{2,3\}$$\mu=\frac12$、$\Delta=\frac14$ で、$P(X=0)=\frac58>e^{-1/2}\approx0.607$
表の確かめ

1 行目:$D_i$ は互いに交わらないので $\Delta=0$ で、各 $B_i$ の確率は $\frac12$ である。$X=0$ は $R=\emptyset$ のことなので確率は $\frac12$ であり、$m\ge2$ では $e^{-m/2}\le e^{-1}< \frac12$ である。座標の独立性がないので、互いに素な $D_i$ の事象も独立でない。2 行目:$fg=0$ である。3 行目:$p_1=p_2=\frac14$、$P(B_1\cap B_2)=\frac18$ なので $\mu=\frac12$、$\Delta=2\cdot\frac18=\frac14$ で、$P(X=0)=1-(\frac14+\frac14-\frac18)=\frac58$ である。$\mu^2/(2\Delta)=\frac12$ である。$\square$

補足

名前と文献

JW14 は、Janson が下側の裾の評価 $P(X\le(1-\varepsilon)E[X])\le\exp(-\varphi(-\varepsilon)\mu^2/\Lambda)$($\varphi(x)=(1+x)\log(1+x)-x$、$0\le\varepsilon\le1$)を証明したと述べ、これを Janson の不等式と呼んでいる(p. 1 の式 (2)。同論文の $\Lambda$ はこの記事の $\Lambda$ と同じく順序対で和をとる)。$\varphi(-\varepsilon)\ge\varepsilon^2/2$ なので、$t=\varepsilon\mu$ とした thm-jan-lower-tail はその帰結である。同論文は、Harris の不等式から cor-jan-lower の形の下界が出ることにも触れている(p. 2 の式 (3))。thm-jan-main の形の評価を、FK26 は Janson、Łuczak、Ruciński の不等式と呼び、§34.6 の下側の裾の評価の系として述べている(Corollary 34.14、p. 714。同書の $\Delta$ は順序を区別しない組の和で、この記事の $\Delta/2$ に当たる)。この記事の prf-thm-jan-main の条件付き確率による証明、prf-thm-jan-extended の間引きの議論、prop-jan-triangle は書き下ろしたものである。

一般の増加事象

prf-thm-jan-main で使ったのは、$B_i$ が増加事象であること、$D_i$ の外の座標と独立であること、Harris の不等式だけである。したがって $B_i$ を「$D_i$ の座標だけで決まり、確率が $1$ より小さい増加事象」に置き換えても、同じ証明で thm-jan-main が成り立つ。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する