乱択アルゴリズム(randomized algorithm)とは、入力のほかに一様な乱数を読み、その値によって動きを変えるアルゴリズムで、確率は乱数についてとり、どの入力でも高い確率で正しいことを保証する。必ず正しく計算時間が乱数で変わる Las Vegas 型と、時間が決まっていて誤りを許す Monte Carlo 型がある。誤りは独立な繰り返しで指数的に減らせ、片側誤りなら $\varepsilon^k$、両側誤りでも正答の確率が $1/2+\gamma$ 以上なら多数決で $e^{-2\gamma^2k}$ 以下になる。行列の積の検査、乱択クイックソート、グラフの最小カットを辺の縮約で求める方法(成功の確率は $2/(n(n-1))$ 以上)が代表例である。
前提知識: 期待値の線形性, Markovの不等式, 計算量理論
乱択アルゴリズム(randomized algorithm)は、入力のほかに一様な乱数を読み、乱数の値によって動きを変えるアルゴリズムである。出力や計算時間は乱数で決まる確率変数になる。確率は乱数についてだけとり、入力は固定する。したがって「どの入力でも、高い確率で正しい」という保証は、入力の分布を仮定しない最悪の場合の保証である。
乱数を使う利点は 2 つある。1 つは、決定的な方法より簡単で速い方法が作れることである。行列の積 $AB=C$ の検査は、積を計算し直すと $n^3$ 程度の演算が要るが、乱数のベクトル $r$ をとって $A(Br)$ と $Cr$ を比べれば $n^2$ 程度の演算で、誤りを確率 $1/2$ 以上で見つける。もう 1 つは、誤りの確率を繰り返しで指数的に小さくできることである。誤りの確率が $1/2$ の検査も、独立に $20$ 回繰り返せば誤りは $2^{-20}<10^{-6}$ になる。
この記事では、Las Vegas 型と Monte Carlo 型の区別、計算量のクラス RP・coRP・BPP・ZPP を定義し、繰り返しで誤りを減らす評価、$\mathrm{ZPP}=\mathrm{RP}\cap\mathrm{coRP}$、行列の積の検査、乱択クイックソートの比較回数を証明する。主定理として、グラフの最小カットを辺の縮約で求める方法(Karger)の成功確率の評価を証明する。
乱択アルゴリズム $\mathcal A$ は、入力 $x$ と、互いに独立で一様に $0,1$ をとる乱数の列 $r=(r_1,r_2,\dots)$ を読み、出力 $\mathcal A(x,r)$ を返す(または停止しない)手続きである。入力 $x$ を固定したとき、出力と計算の歩数 $T_{\mathcal A}(x,r)$ は $r$ の関数として確率変数であり、確率 $P$ と期待値 $E$ は $r$ についてとる。
問題の正しい答えを $f(x)$ とする。
判定問題(言語)$L\subset\{0,1\}^\ast$ について、$x\in L$ なら $L(x)=1$、そうでなければ $L(x)=0$ とおく。「多項式時間」は入力の長さ $\lvert x\rvert$ の多項式で抑えられる歩数をいう(計算量理論)。
$\mathbf{RP}$ の $2/3$ を $1/2$ にしても、$\mathbf{BPP}$ の $2/3$ を $1/2$ より大きい別の定数にしても、クラスは変わらない(prop-ra-onesided、thm-ra-majority)。定義は AB07 の Definitions 7.1・7.6・7.7 に合わせた(そこでは確率的 Turing 機械で述べている)。
この記事の結論を使える条件をまとめる。
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| 片側誤り $\varepsilon$ を $k$ 回:誤り $\varepsilon^k$ | 独立な乱数で繰り返す | prop-ra-onesided |
| 多数決 $k$ 回:誤り $\le e^{-2\gamma^2k}$ | 正答の確率 $\ge\frac12+\gamma$、独立 | thm-ra-majority |
| 期待時間 $T$ の Las Vegas 型を $T/\delta$ 歩で打ち切る:未完了の確率 $\le\delta$ | 期待時間が有限 | Markovの不等式 |
| $\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}$ | — | thm-ra-zpp |
| $AB\ne C$ を見逃す確率 $\le\frac12$、手間は $O(n^2)$ | $r$ が $\{0,1\}^n$ で一様 | thm-ra-freivalds |
| 特定の最小カットを出す確率 $\ge\binom n2^{-1}$ | 連結な多重グラフ、$n\ge2$ 頂点 | thm-ra-karger |
| 最小カットは $\binom n2$ 個以下 | 同上 | cor-ra-count |
| 縮約を $\lceil\binom n2\ln(1/\delta)\rceil$ 回:失敗 $\le\delta$ | 独立に繰り返し、最小を採る | cor-ra-count |
| 乱択クイックソートの比較の回数の期待値 $2(n+1)H_n-4n$ | 相異なる $n$ 個 | prop-ra-quicksort |
| $0$ でない多項式が一様な点で $0$ になる確率 $\le d/\lvert S\rvert$ | 全次数 $\le d$、点を $S^n$ から | Schwartz–Zippelの補題 の定理「Schwartz–Zippelの補題」 |
| 合成数を「おそらく素数」とする確率 $\le4^{-k}$ | 奇数 $n\ge3$、$k$ 回 | Miller–Rabin素数判定法 の系「合成数を見逃す確率」 |
ここで $H_n=1+\frac12+\cdots+\frac1n$ は 調和数 である。
判定問題の乱択アルゴリズム $\mathcal A$ が、$x\notin L$ なら必ず $0$ を出力し、$x\in L$ なら確率 $1-\varepsilon$ 以上で $1$ を出力するとする。独立な乱数で $k$ 回実行し、$1$ が 1 回でも出れば $1$、そうでなければ $0$ を出力する手続きは、$x\notin L$ なら必ず $0$ を出力し、$x\in L$ で $0$ を出力する確率は $\varepsilon^k$ 以下である。
$x\notin L$ なら各回の出力が $0$ なので、出力は $0$ である。$x\in L$ のとき、出力が $0$ になるのは $k$ 回すべてで $0$ が出たときで、各回の確率は $\varepsilon$ 以下、乱数は独立なので、その確率は $\varepsilon^k$ 以下である。
とくに $\mathbf{RP}$ の定義の $2/3$ は、正の定数 $q$ に替えてもよい。成功の確率 $q$ でも $k$ 回で $1-(1-q)^k$ になり、$k$ を十分大きくとれば $2/3$ 以上になるからである。
$\gamma>0$ とし、乱択アルゴリズム $\mathcal A$ がすべての $x$ で $P(\mathcal A(x,r)=L(x))\ge\frac12+\gamma$ を満たすとする。独立な乱数で奇数 $k$ 回実行し、多いほうの答えを出力する手続きの誤りの確率は $e^{-2\gamma^2k}$ 以下である。
$i$ 回目の答えが正しければ $X_i=1$、誤りなら $X_i=0$ とおく。$X_1,\dots,X_k$ は独立で $[0,1]$ に値をとり、$S_k=\sum_iX_i$ について $E[S_k]\ge(\frac12+\gamma)k$ である。多数決が誤るのは正しい答えが半数未満のとき、つまり $S_k\le k/2$ のときで、このとき
$$
S_k-E[S_k]\le\frac k2-\Bigl(\frac12+\gamma\Bigr)k=-\gamma k
$$
となる。Hoeffdingの不等式 の定理「Hoeffding の不等式」を $D=\sum_i(1-0)^2=k$、$t=\gamma k$ で使うと
$$
P(S_k\le k/2)\le P(S_k-E[S_k]\le-\gamma k)\le e^{-2\gamma^2k^2/k}=e^{-2\gamma^2k}
$$
である。
$\gamma=\frac16$(正答の確率 $\frac23$)なら $e^{-k/18}$ で、誤りを $\delta$ 以下にするには $k\ge18\ln(1/\delta)$ とすればよい。したがって $\mathbf{BPP}$ の $2/3$ は $1/2$ より大きいどの定数に替えてもよい。$\gamma$ が $\lvert x\rvert^{-c}$ のように入力とともに小さくなっても、$k$ を多項式で増やせば同じ議論が通る(AB07 Theorem 7.10)。
期待時間が $T$ の Las Vegas 型を $T/\delta$ 歩で打ち切ると、Markovの不等式 の定理「Markov の不等式」により、打ち切られる確率は $T/(T/\delta)=\delta$ 以下である。打ち切ったときの答えの決め方で、誤りの向きを選べる。
$\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}$ である(AB07 Theorem 7.8)。
要点:$\subset$ は打ち切りで、$\supset$ は 2 つの片側誤りのアルゴリズムを交互に動かして示す。
$\subset$:$L\in\mathbf{ZPP}$ を判定する Las Vegas 型の $\mathcal A$ の期待時間が多項式 $T(\lvert x\rvert)$ 以下であるとする。$\mathcal A$ を $3T(\lvert x\rvert)$ 歩まで動かし、停止すればその出力を、停止しなければ $0$ を出力する手続き $\mathcal B$ を作る。$\mathcal B$ はどの乱数でも多項式時間で止まる。$\mathcal A$ の出力は必ず正しいので、$x\notin L$ なら $\mathcal B$ の出力は必ず $0$ である。$x\in L$ のとき、Markov の不等式により $P(T_{\mathcal A}\ge3T)\le\frac13$ なので、$\mathcal B$ は確率 $\frac23$ 以上で $1$ を出力する。よって $L\in\mathbf{RP}$ である。打ち切ったときに $1$ を出力すれば、同じ議論で補集合が $\mathbf{RP}$ に属し、$L\in\mathbf{coRP}$ である。
$\supset$:$\mathcal A_1$ を $L$ の $\mathbf{RP}$ のアルゴリズム、$\mathcal A_2$ を補集合の $\mathbf{RP}$ のアルゴリズムとし、どちらも多項式 $p(\lvert x\rvert)$ 歩以内で止まるとする。新しい乱数で $\mathcal A_1$ を動かして $1$ が出れば $1$ を出力し、新しい乱数で $\mathcal A_2$ を動かして $1$ が出れば $0$ を出力し、どちらでもなければ最初に戻る手続きを $\mathcal C$ とする。$\mathcal A_1$ が $1$ を出すのは $x\in L$ のときだけで、$\mathcal A_2$ が $1$ を出すのは $x\notin L$ のときだけなので、$\mathcal C$ の出力は必ず正しい。$x\in L$ なら $\mathcal A_1$ が、$x\notin L$ なら $\mathcal A_2$ が確率 $\frac23$ 以上で $1$ を出すので、各回の終わりに止まる確率は $\frac23$ 以上で、回数の期待値は $\sum_{j\ge1}(\frac13)^{j-1}=\frac32$ 以下である。よって $\mathcal C$ は確率 $1$ で止まり、期待時間は $\frac32\cdot2p(\lvert x\rvert)$ に定数を足したもの以下で、$L\in\mathbf{ZPP}$ である。
$K$ を体とし、$A,B,C$ を $K$ の成分の $n\times n$ 行列とする。$r\in\{0,1\}^n$ を一様に選び、$A(Br)=Cr$ なら「$AB=C$」、そうでなければ「$AB\ne C$」と答える。$AB=C$ なら答えは必ず正しく、$AB\ne C$ なら誤って「$AB=C$」と答える確率は $\frac12$ 以下である。演算の回数は $3n^2$ 程度である。
$D=AB-C$ とおくと、$A(Br)-Cr=Dr$ である。$D=0$ なら $Dr=0$ で、答えは正しい。$D\ne0$ なら $D_{ij}\ne0$ となる $(i,j)$ をとる。$r_j$ 以外の座標を固定すると、$(Dr)_i=D_{ij}r_j+s$($s$ は $r_j$ によらない)である。$r_j=0$ と $r_j=1$ でともに $(Dr)_i=0$ なら、差をとって $D_{ij}=0$ となり矛盾するので、$(Dr)_i=0$ となる $r_j$ は高々 1 つである。$r_j$ はほかの座標と独立に確率 $\frac12$ ずつで $0,1$ をとるので
$$
P(Dr=0)\le P\bigl((Dr)_i=0\bigr)\le\frac12
$$
である。$Br$、$A(Br)$、$Cr$ はどれも行列とベクトルの積で、乗算は $n^2$ 回ずつである。
これは Schwartz–Zippelの補題 の、全次数 $1$ の多項式 $(Dr)_i$ を $S=\{0,1\}$ で調べる場合にあたる($d/\lvert S\rvert=1/2$)。誤りは片側なので、独立に $k$ 回繰り返せば誤りは $2^{-k}$ 以下になる(prop-ra-onesided)。
この節のグラフは、自己ループをもたず、多重辺を許す連結な無向グラフ $G=(V,E)$ で、$n=\lvert V\rvert\ge2$ とする。
$G/e$ の頂点は元の頂点の集合にあたり、$G/e$ のカットは同じ大きさの $G$ のカットにあたる。したがって $c(G/e)\ge c(G)$ である。また $G/e$ は連結なので、頂点が 2 つ以上ある間は辺が 1 本以上あり、アルゴリズムは $n-2$ 回の縮約で止まる。
カット $(A,B)$ が出力されることと、$A$ と $B$ を結ぶ辺が 1 本も縮約されないことは同値である(KS96 Lemma 2.1)。
$A$ と $B$ を結ぶ辺が縮約されると、その両端は同じ頂点にまとめられるので、$(A,B)$ は出力されない。逆に、そのような辺が 1 本も縮約されないとする。$a\in A$ と $b\in B$ が同じ頂点にまとめられたなら、縮約した辺だけで $a$ から $b$ への道があり、その道は $A$ と $B$ を結ぶ辺を通るので矛盾する。よって $A$ の頂点と $B$ の頂点は別の頂点に残り、最後の 2 頂点は $A$ と $B$ にあたる。
$(A,B)$ を $G$ の最小カットの 1 つとする。縮約アルゴリズムが $(A,B)$ を出力する確率は
$$
\binom n2^{-1}=\frac2{n(n-1)}
$$
以上である(KS96 Theorem 2.2)。
$c=c(G)$ とおく。$G$ は連結なので $c\ge1$ である。$A$ と $B$ を結ぶ $c$ 本の辺を 横切る辺 と呼ぶ。lem-ra-survive により、$n-2$ 回の縮約のどこでも横切る辺を選ばない確率を下から評価すればよい。
頂点が $r$ 個($3\le r\le n$)の段で、それまで横切る辺を 1 本も選んでいないとする。このとき $A$ の頂点と $B$ の頂点は別の頂点に残っているので、横切る $c$ 本の辺は自己ループにならず、そのまま残っている。一方、その時点のグラフ $H$ では $c(H)\ge c$ なので、1 つの頂点 $v$ だけを片側にするカットの大きさ、つまり $v$ の次数は $c$ 以上である。次数の和は辺の本数の 2 倍なので、$H$ の辺は $rc/2$ 本以上ある。よって、この段で横切る辺を選ぶ確率は
$$
\frac c{\lvert E(H)\rvert}\le\frac c{rc/2}=\frac2r
$$
以下である。$r$ 個の段で横切る辺を選ばない事象を $F_r$ とすると、条件付き確率の積により
$$
P(F_n\cap F_{n-1}\cap\cdots\cap F_3)=\prod_{r=3}^nP(F_r\mid F_n\cap\cdots\cap F_{r+1})\ge\prod_{r=3}^n\Bigl(1-\frac2r\Bigr)=\prod_{r=3}^n\frac{r-2}r
$$
である。右辺の積は分子が $1\cdot2\cdots(n-2)$、分母が $3\cdot4\cdots n$ なので、$\dfrac{1\cdot2}{(n-1)n}=\dfrac2{n(n-1)}$ に等しい。
縮約アルゴリズムの 1 回の実行は $O(n^2)$ の時間で実装できるので(KS96 Corollary 3.2)、$N=O(n^2\log(1/\delta))$ 回で多項式時間になる。最小カットは 最大流最小カット定理 による決定的な方法でも求まるが、縮約アルゴリズムは辺の重みも流れも使わない簡単な方法である。
図: 左は 2 つの三角形を 1 本の辺(橋)で結んだ 6 頂点のグラフで、最小カットは橋 1 本を切るカットである。右は、完全グラフ K_m を 2 つ橋で結んだ 2m 頂点のグラフで、m を 3 から 8 まで動かしたときの、橋のカットが出力される確率を対数目盛りで比べたもの。辺を一様に選ぶ縮約(実測、約 0.37 から 0.62)は下界 2/(n(n-1))(約 0.067 から 0.0083)より上にあり、頂点の対を一様に選んでまとめる方法は下界よりはるかに小さい(m=8 で約 1.0×10^-5)。
相異なる $n$ 個の数を並べ替える。乱択クイックソート は、列から基準の要素 $p$(ピボット)を一様に選び、$p$ と残りの要素を $1$ 回ずつ比べて $p$ より小さい列と大きい列に分け、それぞれを同じ方法で並べ替える。出力は必ず正しく、比較の回数が乱数で変わる Las Vegas 型である。
相異なる $n$ 個の数の乱択クイックソートの比較の回数の期待値は $2(n+1)H_n-4n$ である。とくに $2n\ln n+O(n)$ である。
要点:小さい順に $z_1< \dots< z_n$ とすると、$z_i$ と $z_j$($i< j$)が比べられる確率は $2/(j-i+1)$ で、期待値の線形性 で足し合わせる。
比較はピボットと他の要素の間でだけ行い、同じ組を 2 回比べることはない(ピボットは以後の列に入らない)。$I_{ij}=\{z_i,\dots,z_j\}$ とする。$I_{ij}$ からピボットが選ばれるまでは、$I_{ij}$ の要素は同じ列に入っている($I_{ij}$ の外のピボットは $I_{ij}$ を分けない)。$I_{ij}$ から最初に選ばれるピボットは、その時点の列に $I_{ij}$ が丸ごと入っているので、$I_{ij}$ の $j-i+1$ 個から一様に選ばれる。それが $z_i$ か $z_j$ なら $z_i$ と $z_j$ は比べられ、間の要素なら 2 つは別の列に分かれて以後比べられない。よって比べられる確率は $2/(j-i+1)$ である。$k=j-i+1$ とおくと、差が $k-1$ の組は $n-k+1$ 個あるので、比較の回数の期待値は
$\displaystyle\sum_{i< j}\frac2{j-i+1}=\sum_{k=2}^n\frac{2(n-k+1)}k=2(n+1)\sum_{k=2}^n\frac1k-2(n-1)=2(n+1)(H_n-1)-2(n-1)=2(n+1)H_n-4n$
である。$H_n=\ln n+O(1)$ から後半が従う。
期待値は入力の並び方によらない。決定的に先頭の要素をピボットにする方法では、整列済みの入力で比較が $\binom n2$ 回になる。乱択にしても最悪の乱数では $\binom n2$ 回になりうるが、その確率は小さい。
$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$、$B=\begin{pmatrix}5&6\\7&8\end{pmatrix}$、$C=\begin{pmatrix}19&22\\43&51\end{pmatrix}$ とする。$AB=\begin{pmatrix}19&22\\43&50\end{pmatrix}$ なので $AB\ne C$ で、$D=AB-C$ は $(2,2)$ 成分だけが $-1$ である。$r=(0,0),(1,0)$ では $A(Br)=Cr$(たとえば $r=(1,0)$ で両辺とも $(19,43)$)、$r=(0,1),(1,1)$ では第 2 成分が $50\ne51$、$93\ne94$ と食い違う。見つける確率はちょうど $\frac12$ で、thm-ra-freivalds の評価が等号になる。$10$ 回繰り返すと見逃す確率は $2^{-10}\approx9.8\times10^{-4}$ である。
片側誤り $\varepsilon=\frac12$ なら $2^{-k}\le10^{-6}$ から $k=20$($2^{-20}\approx9.54\times10^{-7}$)。両側誤りで正答の確率が $\frac23$($\gamma=\frac16$)なら、thm-ra-majority から $k\ge18\ln10^6\approx248.7$ で、奇数の $k=249$ をとると上界は $e^{-249/18}\approx9.82\times10^{-7}$ である。二項分布で正確に計算すると、$k=249$ の多数決の誤りは約 $2.96\times10^{-8}$ で、上界は 30 倍ほど余裕がある。
$K_4$(頂点 $a,b,c,d$、辺 $6$ 本)の最小カットは 1 頂点だけを片側にする $4$ 個で、大きさは $3$ である。1 回目の縮約で、どの辺を選んでも同じ形になる。$a,b$ をまとめたとすると、まとめた頂点と $c$、$d$ はそれぞれ $2$ 本の辺で結ばれ、$c$ と $d$ は $1$ 本で結ばれる(計 $5$ 本)。2 回目に $c$–$d$ の辺(確率 $\frac15$)を選ぶと出力は $\{a,b\}\mid\{c,d\}$ で大きさ $4$、ほかの $4$ 本(確率 $\frac45$)を選ぶと $c$ か $d$ の一方だけが残り、大きさ $3$ の最小カットが出る。対称性から各最小カットの確率は $\frac15$ で、thm-ra-karger の下界 $\frac16$ を超える。$n=50$、$\delta=10^{-6}$ なら $N=\lceil1225\ln10^6\rceil=16925$ 回で足りる。
$n=3$ のとき、prop-ra-quicksort の値は $2\cdot4\cdot\frac{11}6-12=\frac83$ である。直接数えると、最初のピボットが真ん中の数(確率 $\frac13$)なら比較は $2$ 回、端の数(確率 $\frac23$)なら $2$ 回のあと残り $2$ 個で $1$ 回の計 $3$ 回なので、期待値は $\frac13\cdot2+\frac23\cdot3=\frac83$ で一致する。$n=10$ では $22H_{10}-40\approx24.437$ 回で、整列済みの入力に先頭をピボットとする決定的な方法の $\binom{10}2=45$ 回より少ない。
各行は条件を 1 つだけ外し、ほかの条件は保つ。
| 外す条件 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $r$ を乱数で選ぶ | $r=(1,1)$ に固定(ex-ra-fixed) | $AB\ne C$ を確率 $1$ で見逃す |
| 繰り返しの乱数が独立 | 最初の $r$ を使い回す(ex-ra-fixed) | $k$ 回でも見逃す確率は $\frac12$ のまま |
| 片側誤りの向き | 両側誤りに「1 回でも yes なら yes」を使う | no の入力で誤る確率 $1-(\frac23)^k\to1$($k=5$ で約 $0.868$) |
| 正答の確率 $\ge\frac12+\gamma$、$\gamma>0$ | 正答の確率がちょうど $\frac12$(ex-ra-half) | 多数決の誤りはどの奇数 $k$ でも $\frac12$ |
| 辺を一様に選ぶ | 頂点の対を一様に選んでまとめる(ex-ra-pairs) | 成功の確率が $\binom n2^{-1}$ を大きく下回る |
| グラフが連結 | 辺のない 3 頂点のグラフ | 縮約する辺がなく、1 回目で止まる |
$A=I$、$B=0$、$C=\begin{pmatrix}-1&1\\0&0\end{pmatrix}$ とすると $AB=0\ne C$ で、$D=AB-C=\begin{pmatrix}1&-1\\0&0\end{pmatrix}$ である。$r=(1,1)$ では $Dr=0$ なので、$r$ を固定した検査は必ず見逃す。どの固定した $r\ne0$ にも $Dr=0$ となる $D\ne0$ があるので($r$ に直交する行を並べる)、乱数で選ぶことが要る。また ex-ra-freivalds で最初に引いた $r$ を $k$ 回使い回すと、$k$ 回とも同じ答えになり、見逃す確率は $\frac12$ のまま減らない。
入力によらず確率 $\frac12$ ずつで $0,1$ を出力するアルゴリズムは、正答の確率がちょうど $\frac12$ である。奇数 $k$ 回の多数決では、正しい答えの回数 $S_k$ が二項分布 $\mathrm{B}(k,\frac12)$ に従い、$S_k$ と $k-S_k$ は同じ分布なので $P(S_k\le\frac{k-1}2)=P(S_k\ge\frac{k+1}2)=\frac12$ である。誤りの確率は $k$ によらず $\frac12$ で、thm-ra-majority の結論は $\gamma=0$ では成り立たない。
完全グラフ $K_m$ を 2 つ用意し、1 本の辺(橋)で結んだ $n=2m$ 頂点のグラフの最小カットは、橋だけを切るカットで大きさ $1$ である。各段で辺でなく、その時点の頂点の対を一様に選んでまとめるとする。橋のカットが出力されるのは、毎回同じ側の 2 頂点を選ぶときに限る。両側に $a$ 個と $b$ 個の頂点が残っているとき、その確率は $\bigl(\binom a2+\binom b2\bigr)/\binom{a+b}2$ で、出力の確率 $f(a,b)$ は
$$
f(a,b)=\frac{\binom a2f(a-1,b)+\binom b2f(a,b-1)}{\binom{a+b}2},\qquad f(1,1)=1,\ f(a,0)=f(0,b)=0
$$
で決まる。$m=10$($n=20$)では $f(10,10)\approx5.7\times10^{-7}$ で、下界 $\binom{20}2^{-1}\approx5.3\times10^{-3}$ より 4 桁小さい。辺を一様に選ぶと、各段で選ばれやすいのは辺の多い $K_m$ の中の辺で、橋は選ばれにくい。thm-ra-karger の証明の「次数が $c$ 以上なので辺が多い」という議論は、辺を選ぶことに依存している。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 乱択の確率を入力の分布の確率と混同する | 保証はどの入力でも乱数について成り立つ。入力が無作為に来るときだけ速い方法(平均的な場合の解析)とは別物 | def-ra-main |
| 片側誤りで、不確実なほうの答えを確実と思う | $\mathbf{RP}$ のアルゴリズムが $1$ を出せば $x\in L$ は確実だが、$0$ は誤りうる | def-ra-classes |
| 繰り返しで乱数を使い回す | 誤りの確率が掛け算で減るのは、独立な乱数を引き直すときだけ | ex-ra-fixed |
| 縮約で多重辺を 1 本にまとめる | 多重辺は残す。まとめると次数と辺の本数が元のグラフのカットの大きさを表さない | thm-ra-karger の証明 |
| 期待時間を最悪の時間と思う | 乱択クイックソートの期待値は $2n\ln n+O(n)$ だが、最悪の乱数では $\binom n2$ 回。時間の上限が要るなら Markov の不等式で打ち切る | prop-ra-quicksort |
| 上界を誤りの値と思う | Hoeffding の不等式の上界は実際の誤りより大きいことが多い | ex-ra-amplify |
$\mathbf P\subset\mathbf{ZPP}\subset\mathbf{RP}\subset\mathbf{BPP}$ である。$\mathbf{RP}\subset\mathbf{NP}$ も成り立つ。$x\in L$ のとき $1$ を出す乱数の値が 1 つはあり、それを証拠として決定的に検証できるからである。$\mathbf{BPP}=\mathbf P$ かどうかは AB07 の時点(2007 年)では知られておらず、もっともらしい計算量の仮定のもとでは成り立つと述べられている(p. 117)。
縮約アルゴリズムは、頂点が約 $n/\sqrt2$ 個になるまで縮約したグラフで 2 回ずつ再帰的に繰り返すと、全体の時間を $O(n^2\log^3n)$ 程度に下げられる(KS96)。乱数を使わずに同じ保証を得る方法(脱乱択化)の例として、条件付き期待値の方法がある(近似アルゴリズム)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する