離散確率空間上の確率集中不等式

本来, 確率変数は「ランダムな値をとる」ものであり, その挙動を予想することは困難です. しかし「n個の確率変数の和」といった幾つかのタイプの確率変数は「大体このくらいの値を高確率でとる（集中する）」ことが理論的に保証できます. この議論は確率集中不等式を用いてなされるものであり, 物理学, 機械学習, 計算機科学 (特に乱択アルゴリズムの解析), グラフ理論といった非常に広範囲な分野の理論的支柱の一つとなっています. 今回は離散確率空間上で成り立ついろんな確率集中不等式について紹介します.

この記事で紹介するのは Chernoff bound, Jansonの不等式, Kim-Vu polynomial concentration です. よくある確率集中不等式の本や連続の世界では Bernsteinの不等式, Azumaの不等式, Talagrandの不等式などが出てきますが, それらはここでは割愛します. Talagrandの不等式についてはめちゃくちゃ面白いので機会があれば紹介したいと思っています.

1. Chernoff bound

独立な確率変数の和の集中性を示す結果で, もっとも代表的なものです. $X_1,\ldots,X_n$を$[0,1]$の値をとる独立な確率変数で, $\mathrm{E}[X_i]=p_i$, $S=X_1+\cdots+X_n$, $\mu=E[S]$とします.

定理1 (Chernoff bound).
任意の $t>0$ に対して

$\Pr[S\geq \mu+t] \leq \exp\left(-\frac{t^2}{2(\mu+t/3)}\right)$.

任意の $t\leq \mu$ に対して

$\Pr[S\leq \mu-t] \leq \exp\left(-\frac{t^2}{2(\mu-t/3)}\right)$.

系2.
任意の$\epsilon>0$に対して,

$\Pr[S\geq (1+\epsilon)\mu] \leq \exp\left(-\frac{\min\{\epsilon,\epsilon^2\}\mu}{3}\right)$

及び

$\Pr[S\leq (1-\epsilon)\mu] \leq \exp\left(-\frac{\epsilon^2 \mu}{2}\right).$

Remark.
しばしば, $\Pr[S\geq (1+\epsilon)\mu] \leq \exp\left(-\Omega(\epsilon \mu)\right)$ などと勘違いされますが, これは $\epsilon\geq 1$ でないと成り立ちません. また, Chernoff boundには Hoeffidingなどいろんな亜種が知られていて, [1, 2]などが詳しいです. 特に

定理3.

独立なベルヌーイ試行 $X_1,\ldots,X_n$ に対して, $S=X_1+\cdots+X_n$, $\mu=\mathrm{E}[S]$とおく. 任意の $R\geq 2\mathrm{e}\mu$に対して

$\Pr[S\geq R]\leq 2^{-R}$

が成り立つ.

という結果も知られています[2, Corollary 10.4].

1.1. Chernoff bound の証明 (途中まで)

Chernoff boundの証明は初見だとビックリするようなアイデアに基づくものになっており, マルコフの不等式 ($\Pr[X>a]\leq \mathrm{E}[X]/a$) を使います. 概略だけ述べると

$\Pr[S\geq\mu+t] = \Pr[\exp(\lambda S)\geq \exp(\lambda(\mu+t))] \leq \exp(-\lambda(\mu+t))\mathrm{E}[\exp(\lambda S)]$

for any $\lambda\geq 0$ なので, 右辺の $\mathrm{E}[\exp(\lambda S)]$ を上から抑えることを考えます. ここで$S$は独立確率変数の和なので, 積に分解でき

$\mathrm{E}[\exp(\lambda S)]=\prod_{i=1}^n \mathrm{E}[\exp(\lambda X_i)] = \prod_{i=1}^n (1-p_i(1-\mathrm{e}^{-\lambda}))$

となります. (個人的には$\exp(\lambda S)$を考えるあたりがビックリポイントなのですが, モーメントなどをよくよく考えるとなんとなく自然に感じられるようになります). あとはこの右辺を気合いで上から抑えます. 具体的には

$\exp(\lambda x)\leq 1-x+x\exp(\lambda)$ for $x\in[0,1]$

という不等式を使います. この先は式変形を頑張って整理するだけです. 詳しく知りたい方は, 例えば [3, 21.4節] などをご覧ください.

2. Janson の不等式

Erdős–Rényiグラフ $G(n,p)$ を考えます. ここで$G(n,p)$ とは $n$ 頂点のグラフで各辺が独立に確率 $p$ で接続されて得られたグラフのことです. このグラフに含まれる三角形の個数を $Y$ とします. また, 辺$e$に対し, $X_e$を「$G(n,p)$が$e$を含んでいたら $1$, そうでなければ $0$」と定めます. すると

$Y=\sum_{u,v,w} X_{uv}X_{vw}X_{wu}$

と表せます. 一見すると確率変数の和なので Chernoff bound を使えば集中性が示せそうな気がしますが, 一般に $X_{uv}X_{uw}X_{wu}$と$X_{u'v'}X_{v'w'}X_{w'u'}$ は辺素でない限り独立じゃないのでChernoff boundは使えません. ただ, 辺素な三角形のペアは非常にたくさんあり, 従属関係がスパースなので集中性が示せるんじゃないかという気がします. このように独立な01確率変数上で従属関係がスパースな indicator の和に対し非常に強い下界を与えるのが Janson の不等式です. ちなみにLovász local lemmaも似たような設定を考えてます.

より一般に述べるために, 次の設定を考えます:
有限集合 $E$ で添字づけられた01確率変数の族 $(X_e)_{e\in E}$ を考えます. $\mathrm{E}[X_e]=p_e$ とし, 相異なる $e,f\in E$ に対して $X_e$ と $X_f$ は独立であるとし. $E$上の部分集合族 $\mathcal{E}\subseteq 2^E$ に対して確率変数 $Y_{\mathcal{E}}$ を

$Y_{\mathcal{E}}=\sum_{F\in\mathcal{E}} \prod_{e\in F} X_e$

と定めます. 三角形の例だと, $E$は$\binom{n}{2}$通りの辺の全体$\binom{V}{2}$であり, $X_e$ は $G(n,p)$ が辺$e$を含んでいるかどうかの indicator です. また, $\mathcal{E}$ は集合で書くと

$\mathcal{E}=\{\{a,b,c\}:a,b,c\in E$ are distinct. $\}$

です. すると $Y_{\mathcal{E}}$ は $G(n,p)$が含む三角形の個数になります.

定理4 (Jansonの不等式).

任意の $t>0$ に対し以下が成り立つ:

$\Pr[Y_{\mathcal{E}}\leq \mathrm{E}[Y_{\mathcal{E}}]-t] \leq \exp\left(-\frac{t^2}{\nabla}\right)$.

ここで $\nabla$は

$\nabla=\sum_{F_1,F_2\in\mathcal{E}:\,F_1\cap F_2\neq\emptyset} \mathrm{E}[\prod_{e\in F_1\cup F_2} X_e]$.

2.1. 三角形の個数の下界の導出

$\mathcal{E}$を, 冒頭で述べたように三角形の辺集合の全体と定めます. まず期待値 $\mathrm{E}[Y_\mathcal{E}]$を評価してみると,

$\mathrm{E}[Y_{\mathcal{E}}]=\binom{n}{3}p^3\approx \frac{(np)^3}{6}$

が得られます. 次に定理4に出てくる $\nabla$ を評価します. 式はややこしそうに見えますがやることは簡単で, 辺を共有する二つの三角形$F_1,F_2$に関して $p^{|F_1\cup F_2|}$ を足しあげるだけです. 実際, indicatorの期待値は確率と等しく, 総和の中の $\mathrm{E}[\prod_{e\in F_1\cup F_2} X_e]$ は今回の例でいうと $F_1$と$F_2$の辺が全て $G(n,p)$ に現れる確率と等しくなるので, $p^{|F_1\cup F_2|}$ となります.

ここで $F_1,F_2$ は辺を共有するので, $|F_1\cup F_2|\leq 5$です. そこで三つの場合を考えます:
(i). $|F_1\cup F_2|=3$ の場合: このとき, $F_1=F_2$は同じ三角形を表すので, このような組$(F_1,F_2)$は全部で $O(n^3)$ 通りあります.

(ii). $|F_1\cup F_2|=4$ の場合: そもそも辺を共有する三角形で$|F_1\cup F_2|=4$となるものは存在しません.

(iii). $|F_1\cup F_2|=5$ の場合: $F_1$は三角形の全体$\mathcal{E}$から選ばれるので, $O(n^3)$通りの選び方があります. 一方で$F_2$は$F_1$と一本だけ辺を共有するため, 下図のような感じになります. すると $F_2$ の頂点の自由度は $1$ なので, $F_1$を固定したとき$F_2$は $O(n)$ 通りしかとれません. 従って組 $(F_1,F_2)$ は$O(n^4)$通りです.

Case (iii) における二つの三角形 $(F_1,F_2)$ に対して $F_1\cup F_2$ が表すグラフ.

以上より, $\nabla$は

$\nabla = O(n^3)p^3+O(n^4)p^5 = O(n^3p^3(1+np^2))$

となります. これを定理4 に代入すると,

$\Pr\left[Y_{\mathcal{E}} \leq \mathrm{E}[Y_{\mathcal{E}}]-t\right] \leq \exp\left(-\Omega\left(\frac{t^2}{(np)^3(1+np^2)}\right)\right)$

が得られます. 例えば $t=\mathrm{E}[Y_{\mathcal{E}}]\approx \frac{(np)^3}{6}$を代入すると,

$\Pr[G(n,p)$が三角形を含まない$]\leq \exp\left(-\Omega\left(\frac{(np)^3}{1+np^2}\right)\right) \leq \exp(-\Omega((np)^2))$

となるので, $p\geq \Omega(n^{-2/3})$ならば, $G(n,p)$ は指数的に高い確率で三角形を含む, ということが結論づけられます.

Remark.

実は Janson の不等式は多くの場合で指数部分が定数倍を除くとタイトなバウンドを与えていることが知られており[5], 非常に強力な不等式であることがわかります.

備忘録.

証明はChernoff boundと同様に $\mathrm{E}[\exp(-\lambda Y)]$ のバウンドをうまく与えるのですが, 独立性が成り立たないのが辛いポイントで, 「とりあえず$\lambda$で微分」「アイテム$e$を固定し, $X_e$と独立な部分和とそうでない部分和に分けて, 独立でない部分和に関してはFKG不等式を使ったり」などを工夫します.

3. The Kim-Vu polynomial concentration

文献[4]で示された定理を紹介します. 一般的な呼称がわからないのですが自分はとりあえず表題の通り呼んでいます. 2節で用いたセッティングをここでも流用します. すなわち, 台集合 $E$ 上の独立01確率変数 $(X_e)_{e\in E}$ と部分集合族 $\mathcal{E}\subseteq 2^E$ に対して, 新たな確率変数

$Y_{\mathcal{E}}=\sum_{F\in\mathcal{E}} w_F\prod_{e\in F} X_e$

の集中性を考えます. ここで $w_F>0$ は重みです. 2節では Janson の不等式を用いて下界だけ示しましたが, この節では集中性を述べる結果を紹介します. 上界も求められるためJansonより汎用性は高いように見えますが, 得られるバウンド自体は Janson よりも少し弱い結果になります.

ここでは, $Y_{\mathcal{E}}$ は $X_e$ を変数として見たとき多変数多項式になっていることに着目します. この節で紹介する定理は, この多項式の次数が小さいときに有効な結果になります.

準備として, 縮約について述べます. 部分集合 $A\subseteq E$ に対して, 確率変数 $Y_A$ を

$Y_A=\sum_{F\in\mathcal{E}:A\subseteq F} w_F \prod_{e\in F\setminus A} X_e$

と定めます. $A$を含むような$F$について, $A$以外の要素を掛けて足し上げているので, $Y_A$ は $Y_{\mathcal{E}}$ の $A$による縮約とみなすことができます.

例えば $\mathcal{E}$ を 前節で考えた三角形をなす辺集合の族とし, $A=\{\{1,2\}\}$ を辺$12$のみからなる集合としましょう (今は大集合$E$は$\binom{n}{2}$個の辺集合であることに注意). すると, $Y_A$ は辺$\{1,2\}$を含む三角形 $F$ に対して 辺$\{1,2\}$を除去して足し上げたものになっているため,

$Y_A = \sum_{u\in V\setminus\{1,2\}} X_{1,u}X_{2,u}$

となります. イメージとしては $G(n,p)$ が 辺集合$A$ を含むという事象を条件つけたときの $Y_{\mathcal{E}}$ を表しています.


定理5 (The Kim-Vu polynomial concentration).

$Y_{\mathcal{E}}$ を $k$ 次多項式とする. すなわち, 任意の $F\in\mathcal{E}$ に対して $|F|\leq k$ が成り立つとする. $a_k=8^k\sqrt{k!}$とし,

$\Xi(\mathcal{E})=\max_{A\subseteq E}\mathrm{E}[Y_A]$,

$\Xi'(\mathcal{E})=\max_{\emptyset\neq A\subseteq E}\mathrm{E}[Y_{A}].$

と定める. 任意の$\lambda>1$に対して

$\Pr\left[|Y_\mathcal{E}-\mathrm{E}[Y_{\mathcal{E}}]|\geq a_k \sqrt{\Xi(\mathcal{E})\Xi'(\mathcal{E})}\lambda^k\right]\leq O(\exp(-\lambda+(k-1)\log n))$

が成り立つ.

3.1. $G(n,p)$ が含む三角形の個数の集中性

三角形の個数は $Y_{\mathcal{E}}$ として表せるため, 定理5により集中性が示せます. $A\subseteq E$に対して $\mathrm{E}[Y_A]$ を評価する必要がありますが, $A$を一辺 $\{1,2\}$ のみからなる集合のとき, 冒頭の例で述べた事実を使うと

$\mathrm{E}[Y_A]= \sum_{u\in V\setminus \{1,2\}} p^2 = O(np^2)$

となります. $A=\{\{1,2\},\{1,3\}\}$ ならば, $A$を含む $F$ としては三角形123しかありえないので, $\mathrm{E}[Y_A]=p$ です. つまり, $A$は増えれば増えるほど $Y_A$ は減っていく一方なので, 

$\Xi(\mathcal{E})=\max_{A\subseteq E}\mathrm{E}[Y_A]=O(n^3p^3)$,

$\Xi'(\mathcal{E})=\max_{\emptyset\neq A\subseteq E}\mathrm{E}[Y_{A}]=O(np^2)$

が成り立ちます. これを定理5に突っ込むと

$\Pr\left[|Y_{\mathcal{E}}-\mathrm{E}[Y_{\mathcal{E}}]|\geq  \Theta(n^2p^{2.5})\lambda^3\right] \leq O(\exp(-\lambda+2\log n))$

となります. 例えば $\lambda=3\log n$ を代入すると, 確率 $1-O(n^{-1})$ で

$\frac{(np)^3}{6}-O(n^2p^{2.5}(\log n)^3) \leq $三角形の個数 $\leq \frac{(np)^3}{6}+O(n^2p^{2.5}(\log n)^3)$

が成り立つことが簡単に示せます.

[1]. Concentration Inequalities and Martingale Inequalities: A Survey, F. Chung, and L. Lu, Internet Mathematics Vol. 3, No. 1: pp. 79-127 (2006).

[2]. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics, B. Doerr, arXiv:1801.06733, (2018).

[3]. Introduction to Random Graphs, A. Frieze, and M. Karoński, Cambridge University Press, (2016).

[4]. Concentration of multivariate polynomials and its applications, J. H. Kim, and V. H. Vu, Combinatorica, Vol. 20, No. 3, pp. 417-434 (2000).

[5]. The lower tail: Poisson approximation revisited, S. Janson, and L. Warnke, Random Structures and Algorithms, Vol. 48, No. 2, pp. 219-246 (2014).