(講義ノート)乱択アルゴリズム第1回

入力の仮定はなく、アルゴリズムと保証は最悪時で成り立つ。

表記

$X$ 　確率変数(実数をとる)
$\mathbb{E}[X]$ 　確率変数 $X$ の期待値
- 独立変数でなくても、期待値の線形性がある。期待値の和は和の期待値。
$\mathbb{E}[X_1 + X_2] = \mathbb{E}[X_1] + \mathbb{E}[X_2]$

クイックソート(乱択アルゴリズムの解析の例)

実数の配列 $A$ を与えられて、ソートをする。

アルゴリズムは以下の通り

$|A|=1$ ならば、そのまま出力して終わり。それ以外の時は $A$ からpivotという値を1つ一様に選び $a$ とする。
$|A|$ の元の中で $a$ より小さいものを配列 $L$ 、大きいものを $R$ に振り分けておく( $L,R$ の中でまだソートできてない)。
$L, R$ を再帰的にソートする。

pivotの選び方は乱択なので、最悪だと $O(|A|^2)$ の計算量となる。では期待値はどうなのか？

平均的にはpivotは真ん中を選びそうなので、長さは $|L|=|R|=|A|/2$ となる。これで漸化式は以下のようになる。

T(n)=2T(n/2) + O(n)

マスター定理によって $O(n \log n)$ とわかる。普通に樹形図を書いていっても各段階でかかるのが $O(n)$ だとわかり深さが $O(\log n)$ なので実際正しい。

これをしっかりやるには、以下のようになる。

$1 \leq i < j \leq |A|$ に対して、 $X_{ij}$ は

$1$ 　 $A_i, A_j$ が比較された
$0$ 　 $A_i, A_j$ が比較されない

(ちなみにこれは指示関数という名前)

\mathbb{E}[\sum_{1 \leq i < j \leq |A|} X_{ij}] = \sum_{1 \leq i < j \leq |A|} \mathbb{E} [X_{ij}]

総比較回数の期待値を計算すると、確率変数本体の期待値となり結局 $A_i, A_j$ が比較される確率を調べればよい。

お互いが比較されるには、pivotに $A_i, A_j$ の一方が選ばれるときである。これの確率は、pivotが $A_i, A_j$ よりいずれも大きい、小さい場合は再帰的にやればよい。結局間に入ってるものだけ考えればよい。あいだにはいるのは $j-i+1$ 個あるので、 $\mathbb{E}[X_{ij}] = 2/(j-i+1)$ となる。

これをもって計算すると、

\sum_{1 \leq i < j \leq |A|} \mathbb{E} [X_{ij}] = \sum_{i=1}^{|A|} \sum_{j=i+1}^{|A|} \frac{2}{j-i+1}

$k=j-i$ とすると以下のようにできる。

2 \sum_{i=1}^{|A|} \sum_{k=1}^{|A|-i} \frac{1}{k+1} = 2 \sum_{i=1}^{|A|} \log (|A|-2+i) = O(|A| \log |A|)

Kargerの最小カットアルゴリズム

$G=(V,E)$ が与えられ、それの最小カットを計算する。

Tips: 縮約=2つの頂点を1つにまとめるかんじ。

アルゴリズムは以下の通り

$G$ が3頂点以上持つとき、辺を1本一様に選びそれを縮約する。
これを続けて、最後に残った2頂点の間の枝数を出力する。
この流れをある程度繰り返して得られた数を最小カットだとする。

最小カット $C \subseteq E$ を固定する(つまり、 $C$ 以外の枝を縮約しても $C$ は残る)

$\epsilon_i$ を、 $i$ 頂点残っているときに $C$ を縮約しない事象とする。

最後の最後まで $C$ を残すというのは、以下の確率で計算される。

Pr[\bigcap_{j=3}^N \epsilon_j] = Pr[\epsilon_N] Pr[\bigcap_{j=3}^{N-1} \epsilon_j | \epsilon_N] \\ = Pr[\epsilon_N] Pr[\epsilon_{N-1} | \epsilon_i] Pr[\epsilon_{N-2} | \epsilon_N \cap \epsilon_{N-1}] \cdots

ここで、 $Pr[\epsilon_j | \bigcap_{k=j+1}^N \epsilon_k]$ は、今まで選ばれなかったという条件の下での頂点 $j$ 個存在するときでも選ばれなかったという事象の確率。なので、 $1 - |C|/e$ 、 $e$ はその時の枝数と簡単に得ることができる。

枝数は $j \times |C| / 2$ で抑えることができる(残っている頂点の数で考えると自明)ので、以下の不等式が成り立つ。

1 - \frac{|C|}{e} \leq 1 - \frac{2}{j}

これを用いることで、先ほどの乗算の長い列に代入することで、

Pr[\epsilon_N] Pr[\epsilon_{N-1} | \epsilon_i] Pr[\epsilon_{N-2} | \epsilon_N \cap \epsilon_{N-1}] \cdots \\ \geq \prod _{j=3}^N (1 - \frac{2}{j}) = \prod _{j=3}^N \frac{j-2}{j} = \frac{1}{3} \cdot \frac{2}{4} \cdot \frac{3}{5} \cdots \frac{N-4}{N-2} \cdot \frac{N-3}{N-1} \cdot \frac{N-2}{N} \\ = \frac{1 \cdot 2 }{(N-1)N} = \frac{2}{N(N-1)}

このことから、少なくとも $2/N(N-1)$ の確率で、最小カットが見つかるということ。Kargerのアルゴリズムはこれを $C N^2$ 回繰り返すというもの。

(1-\frac{2}{N(N-1)})^{CN^2} \leq (1 - \frac{1}{N^2})^{CN^2} = e^{-2C}

ここで、 $C=5$ とすれば、 $0.00005$ 以下の確率となり割と現実的であると言える。