乱択アルゴリズム

同義語:確率的アルゴリズムランダム化アルゴリズムrandomized algorithmprobabilistic algorithm

概要

乱択アルゴリズム(randomized algorithm)とは、入力のほかに一様な乱数を読み、その値によって動きを変えるアルゴリズムで、確率は乱数についてとり、どの入力でも高い確率で正しいことを保証する。必ず正しく計算時間が乱数で変わる Las Vegas 型と、時間が決まっていて誤りを許す Monte Carlo 型がある。誤りは独立な繰り返しで指数的に減らせ、片側誤りなら $\varepsilon^k$、両側誤りでも正答の確率が $1/2+\gamma$ 以上なら多数決で $e^{-2\gamma^2k}$ 以下になる。行列の積の検査、乱択クイックソート、グラフの最小カットを辺の縮約で求める方法(成功の確率は $2/(n(n-1))$ 以上)が代表例である。

$$\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}} $$

前提知識: 期待値の線形性, 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$ についてとる。

Las Vegas 型と Monte Carlo 型

問題の正しい答えを $f(x)$ とする。

  1. 乱択アルゴリズムが Las Vegas 型 であるとは、すべての $x$ で確率 $1$ で停止し、停止したときの出力が必ず $f(x)$ であることをいう。計算時間は確率変数で、その期待値 $E[T_{\mathcal A}(x,r)]$ で評価する。
  2. Monte Carlo 型 であるとは、すべての $x$ と $r$ で決まった歩数以内に停止し、出力が $f(x)$ と異なることを許すことをいう。$P(\mathcal A(x,r)\ne f(x))$ を 誤りの確率 という。
  3. 答えが yes か no の問題(判定問題)の Monte Carlo 型で、no の入力では必ず no と答えるものを 片側誤り、どちらの入力でも誤りうるものを 両側誤り という。

判定問題(言語)$L\subset\{0,1\}^\ast$ について、$x\in L$ なら $L(x)=1$、そうでなければ $L(x)=0$ とおく。「多項式時間」は入力の長さ $\lvert x\rvert$ の多項式で抑えられる歩数をいう(計算量理論)。

乱択の計算量のクラス
  1. $L\in\mathbf{BPP}$ とは、どの乱数でも多項式時間で停止する乱択アルゴリズム $\mathcal A$ があり、すべての $x$ で $P(\mathcal A(x,r)=L(x))\ge2/3$ となることをいう。
  2. $L\in\mathbf{RP}$ とは、どの乱数でも多項式時間で停止する $\mathcal A$ があり、$x\in L$ なら $P(\mathcal A(x,r)=1)\ge2/3$、$x\notin L$ なら $P(\mathcal A(x,r)=1)=0$ となることをいう。$L$ の補集合が $\mathbf{RP}$ に属するとき $L\in\mathbf{coRP}$ という。
  3. $L\in\mathbf{ZPP}$ とは、Las Vegas 型の $\mathcal A$ で、出力が必ず $L(x)$ に等しく、期待値 $E[T_{\mathcal A}(x,r)]$ が $\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 機械で述べている)。
この記事の結論を使える条件をまとめる。

  1. 確率は乱数についてだけとる:入力は固定し、どの入力でも成り立つ評価を述べる。入力の分布を仮定した「平均的な場合」とは別の概念である。
  2. 繰り返しの乱数は独立:同じ乱数を使い回すと、何回繰り返しても誤りの確率は減らない。
  3. 片側誤りは向きを使う:「1 回でも yes なら yes」の規則は、no の入力で yes と答えないときだけ正しい。
  4. 両側誤りは正答の確率が $1/2$ より一定以上大きいこと:$1/2+\gamma$($\gamma>0$)なら多数決が効く。
  5. 縮約の評価は連結な多重グラフで、辺を一様に選ぶ(thm-ra-karger)。

公式の表

公式使える条件根拠
片側誤り $\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}$ 以下である。

Hoeffding の不等式を当てる

$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)。

Las Vegas 型と片側誤り

期待時間が $T$ の Las Vegas 型を $T/\delta$ 歩で打ち切ると、Markovの不等式 の定理「Markov の不等式」により、打ち切られる確率は $T/(T/\delta)=\delta$ 以下である。打ち切ったときの答えの決め方で、誤りの向きを選べる。

ZPP と RP・coRP

$\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$ 程度である。

0 でない成分の 1 つの座標を動かす

$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$ とする。

カットと辺の縮約
  1. 空でない真部分集合 $A\subsetneq V$ と $B=V\setminus A$ の組 $(A,B)$ を カット といい、$A$ と $B$ を結ぶ辺の本数をその 大きさ という。大きさが最小のカットを 最小カット、その大きさを $c(G)$ と書く。$(A,B)$ と $(B,A)$ は同じカットとみなす。
  2. 辺 $e$ の両端 $u,v$ を 1 つの頂点にまとめ、$u$ と $v$ を結んでいた辺(自己ループになる辺)をすべて除き、ほかの辺は多重辺のまま残したグラフを $G/e$ と書き、$e$ の 縮約 という。
  3. 縮約アルゴリズム:頂点が 2 つになるまで、その時点のグラフの辺を一様に 1 本選んで縮約する。残った 2 つの頂点にまとめられた元の頂点の集合を $A$、$B$ とし、カット $(A,B)$ を出力する。

$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)。

各段で横切る辺を選ぶ確率は 2/r 以下

$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. $G$ の最小カットは $\binom n2$ 個以下である。$n$ 頂点の閉路 $C_n$($n\ge3$)は $\binom n2$ 個の最小カットをもち、縮約アルゴリズムはその各々をちょうど確率 $\binom n2^{-1}$ で出力する。
  2. 縮約アルゴリズムを独立に $N$ 回実行し、出力のうち最小の大きさのカットを採ると、最小カットが得られない確率は $(1-\binom n2^{-1})^N\le e^{-N/\binom n2}$ 以下である。$N\ge\binom n2\ln(1/\delta)$ ならこれは $\delta$ 以下である。
  1. 異なるカットを出力する事象は互いに排反で、各最小カットの確率は thm-ra-karger により $\binom n2^{-1}$ 以上なので、個数を $M$ とすると $M\binom n2^{-1}\le1$ である。$C_n$ の最小カットの大きさは $2$ で($1$ 本の辺を除いても連結)、$n$ 本の辺から $2$ 本を選んで除くと 2 つの弧に分かれ、そのカットの大きさは $2$ である。異なる 2 本の組は異なるカットを与えるので、最小カットは $\binom n2$ 個あり、上の評価と合わせて $M=\binom n2$ である。確率の和は $1$ 以下で各項が $\binom n2^{-1}$ 以上、項の数が $\binom n2$ なので、各確率はちょうど $\binom n2^{-1}$ である。
  2. 固定した最小カットを 1 回で出さない確率は $1-\binom n2^{-1}$ 以下で、実行は独立なので、$N$ 回とも最小カットを出さない確率はその $N$ 乗以下である。$1-t\le e^{-t}$ から後半が従う。

縮約アルゴリズムの 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)。 図: 左は 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)$ である。

2 つの要素が比べられる確率

要点:小さい順に $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$ 回になりうるが、その確率は小さい。

計算の手順

  1. 何を保証するかを決める。答えが必ず正しいことが要るなら Las Vegas 型、計算時間の上限が要るなら Monte Carlo 型を選ぶ。
  2. 1 回の誤りの確率を評価する。どの入力でも成り立つ上界 $\varepsilon$(または正答の確率の下界 $\frac12+\gamma$)を、乱数についての確率として示す。
  3. 誤りの向きを確かめる。片側誤りなら、確実なほうの答えが 1 回でも出たらそれを採る。両側誤りなら多数決にする。
  4. 回数を決める。目標の誤り $\delta$ に対し、片側なら $k=\lceil\ln(1/\delta)/\ln(1/\varepsilon)\rceil$、両側なら $k\ge\ln(1/\delta)/(2\gamma^2)$ の奇数、縮約なら $N=\lceil\binom n2\ln(1/\delta)\rceil$。
  5. 乱数を毎回新しく、独立に引く。
  6. Las Vegas 型を時間の上限つきで使うときは、期待時間 $T$ の $1/\delta$ 倍で打ち切り、打ち切ったときの答えを誤りの向きに合わせて決める。

例題

2 × 2 の積の検査

$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}$ である。

誤りを $10^{-6}$ にする回数

片側誤り $\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 倍ほど余裕がある。

完全グラフ K4 の縮約

$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$ 回で足りる。

3 個の数のクイックソート

$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$ のまま減らない。

正答の確率がちょうど 1/2

入力によらず確率 $\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)。乱数を使わずに同じ保証を得る方法(脱乱択化)の例として、条件付き期待値の方法がある(近似アルゴリズム)。

関連項目

参考文献

[1]
David R. Karger, Clifford Stein, A New Approach to the Minimum Cut Problem, Journal of the ACM, 1996, 番号と頁は著者版(1996-08-06)のもの:§2、Lemma 2.1・Theorem 2.2(pp. 8–9)、Corollary 3.2(p. 12)、§4 と Theorem 4.4(pp. 12–15)。doi:10.1145/234533.234534
[2]
Sanjeev Arora; Boaz Barak, Computational Complexity: A Modern Approach, Web draft(2007-01-08)。刊行版は 2009 年, Cambridge University Press, 2009, 頁は Web draft 2007-01-08 の通し頁:Definition 7.1(p. 116)、Definition 7.4 と BPP=P についての注意(p. 117)、Definition 7.6(p. 120)、Definition 7.7 と Theorem 7.8(p. 121)、Theorems 7.10・7.12(p. 122)、§7.4.2(p. 124)

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