『確率と計算』 第6章

6 The Probabilistic Method

6.1 Basic Counting

例題: 辺の色塗り問題

$K_n$ を $n$ 頂点のグラフとする。$K_n$の $k$-クリークは完全なサブグラフ $K_k$ とおく。

定理 6.1

\[ {n \choose k} 2^{-{k \choose 2} + 1} < 1 \]

であるとき、1色だけの $K_k$ がないように、 $K_n$ の辺を2色で塗りわけることができる。

6.2 The Expectation Arguments

平均を利用する方法もある。背景としては、離散確率空間では、 確率変数について、平均より大きくない値が少なくとも1つあり、 また平均より小さくない値が少なくとも1つあると、ある正の確率で仮定できる。

Lemma 6.2

確率空間 $\mathcal{S}$ があり、その上での確率変数 $X$ について $\mathbf{E}[X]=\mu$ である。このとき $\mathrm{Pr}(X\ge\mu)\gt0$ であり、 $\mathrm{Pr}(X\le\mu)\gt0$ である

応用はグラフのラージカットをもとめる問題(NP-hard)。

定理 6.3 $m$個の辺をもつ無向グラフ$G(V,E)$で、 少なくとも $m/2$ 個の$A$の点から$B$の点を結ぶ辺をもつように $V$ を2つの互いに素な集合 $A$, $B$にわける方法がある。

ラスベガスアルゴリズムは、頂点を$A$, $B$にわけて、$A$ から $B$ にむかう辺の集合を得る。 これを ${m \over 2} + 1$ 回くりかえして、最大のものをえらぶ。

6.3 Derandomization Using Conditonal Expectation

決定的なアルゴリズムの考えかた

$k$個の点を$A$,$B$にふりわけた状態で、のこりの点をランダムに$A$,$B$にふりわけたとき、 のカットの値の期待値 $\mathbf{E}[C(A,B)|x_1,x_2,x_3,…,x_k]$ をかんがえる。 $x_i$ は頂点 $v_i$ が $A$, $B$ のどちらにふりわけられたかをあらわす。

6.4 Sample and Modify

ランダムにつくったあと、期待する性質をもつように改変する。

定理 6.5 $G=(V,E)$ を $n$ 個の頂点、 $m\ge n/2$ 本の辺をもつとする。 $G$ は少なくとも $n^2/4m$ 個の頂点をもつ independent set – 辺をもたない頂点の集合 を含む。

定理 6.6 任意の $k \ge 3$ について、十分に大きい $n$ について、 内周(girth)が少なくとも $k$, 辺が ${1 \over 4}n^{1+1/k}$ 本の辺をもつ $n$ 頂点のグラフが存在する。

6.5 The Second Moment Method

定理 6.7 $X$ が整数値をとる確率変数としたとき、以下が成立する。

\[ \mathrm{Pr}(X=0) \le {\mathbf{Var}[X] \over (\mathbf{E}[X])^2} \]

定理 6.8 $G_{n,p}$ で $p=f(n)$, $f(n)=o(n^{-2/3})$ とする。そのとき 任意の $\epsilon > 0$ かつ、十分に大きい $n$ について、 $G_{n,p}$ から生成される あるグラフが4個以上の頂点をもつクリークを含んでいる確率が $\epsilon$ より小さい。 同様に、$f(n)=\omega(n^{-2/3})$のとき、十分に大きい $n$ について、 $G_{n,p}$ から生成される あるグラフが4個以上の頂点をもつクリークを 含まない 確率が $\epsilon$ より小さい。

6.6 The Conditional Expectation Inqeuality

定理 6.10 $X=\Sigma_{i=1}^{n}X_i$ で, $X_i$ は0-1の確率変数とする。このとき

\[ \mathrm{Pr}(X>0) \ge \sum_{i=1}^n{\mathrm{Pr}(X_i=1) \over \mathbf{E}[X|X_i=1]} \]

6.7-10 Lovász Local Lemma