乱択アルゴリズム : Freivald のアルゴリズム

乱択アルゴリズムは，確率的に解を返すアルゴリズムである．このようなアルゴリズムの例である Freival のアルゴリズムとその解説を行う．

まず，乱択アルゴリズムは二つの種類に大別できる．

• ラスベガスアルゴリズム : 解は常に正しいが，どれくらい時間がかかるかはランダム
• モンテカルロアルゴリズム : 時間は一定だが，解はランダム(1/2以上の確率で正しい)

モンテカルロアルゴリズムが与えられたら，ラスベガスアルゴリズムを自明に生成できる．（実際には，任意の確率で正しい解を生成できるアルゴリズムを生成できる.）

一方でラスベガスアルゴリズムが与えられた時，モンテカルロアルゴリズムを求める方法は自明ではない．

Quick Sort

• 種類 : ラスベガスアルゴリズム
• 平均計算量 : $O(nlog⁡n)\mathcal{O}(n\log n)$
• 最悪計算量 $O(n2)\mathcal{O}(n^2)$

クイックソートはよく知られたアルゴリズムであるが，同時に確率的アルゴリズムでもある．

クイックソートの詳細については省略する．

この手法は，リストのどの元でリストを二分するかという選択の時点で確率性が用いられている．しかしながらこの確率性は（理論的には）本質的なものではなく，中央値を用いれば常に最適な計算量（定数部分は重くなるので非実用的だが）を実現できる．

この証明は省略する．

Freival のアルゴリズム

• 種類 : モンテカルロアルゴリズム
• 計算量 : $O(n2)\mathcal{O}(n^2)$

古典的な確率アルゴリズムである Freival のアルゴリズムは以下のようなアルゴリズムである．

---

Freival のアルゴリズム:

• 入力 : $n×nn\times n$ 次元行列 $A,B,CA,B,C$．
• 出力 : 以下の式を満たす時 YES, 満たさない時 NO.
  
  $$AB=C.AB=C.$$
• 手順 :
  1. ランダムな $nn$ 次元ベクトル $r∈{0,1}nr\in \{0,1\}^n$ を生成する.
  2. 次の値 $pp$ を計算する．
     
     $$p=A(Br)−Crp=A(Br)-Cr$$
  3. $p=0p = 0$ なら Yes, $p≠0p\neq 0$　ならば No.

---

証明

正しさを示しておこう．この証明はWikipediaにもとづいている．

---

定理 : Freival のアルゴリズムは

• $AB=CAB=C$ ならば確率1 で YES を返す．
• $AB≠CAB\neq C$ ならば確率1/2 以上で NO を返す．

---

証明 : $AB=CAB=C$ であるときは自明．

$AB≠CAB\neq C$ であるとき，以下のように $DD$ を置く．

$$D=AB−CD = AB -C$$

このとき次が成立する．($Ds,tD_{s,t}$ は行列 $DD$ の $(s,t)(s,t)$ 番目の要素)

$$∃Ds,t∈D,Ds,t≠0.(Freival-1)\exists D_{s,t}\in D, D_{s,t}\neq 0.\tag{Freival-1}$$

一方で Freival のアルゴリズムでランダムに選ぶ $rr$ について

$$ABr−Cr=Dr.ABr-Cr = Dr.$$

である．アルゴリズムの定義から，$Dr=0Dr=0$ である確率が， $AB≠CAB\neq C$ であるときに YES を返す確率になる．そこで $Dr=0Dr = 0$ である確率を求めることにする．

まず注意として $r∈{0,1}nr\in\{0,1\}^n$ はランダムに選択された元なので以下が成立する．

$$∀ri∈r,P(ri=0)=1/2.\forall r_i\in r,P(r_i = 0)= 1/2.$$

次に $D,rD,r$ について，以下を満たす $(Dr)i,y(Dr)_i,y$ を考える．このとき $Di,jD_{i,j}$ は (Freival-1) を満たすような $i,ji,j$.

$$(Dr)i=∑k=0Di,krk=Di,jrj+y.(Dr)_i = \sum_{k=0} D_{i,k}r_k=D_{i,j}r_j+y.$$

またこれについて，確率はベイズの定理より

$$P((Dr)i=0)=P((Dr)i=0∣y=0)⋅P(y=0)+P((Dr)i=0∣y≠0)⋅P(y≠0).P((Dr)_i=0)\\=P((Dr)_i=0\mid y=0)\cdot P(y=0)\\+ P((Dr)_i=0\mid y\neq 0)\cdot P(y\neq 0).$$

と分割できる．このとき ($Di,j≠0D_{i,j}\neq 0$ より)

$$P((Dr)i=0∣y=0)=P(Di,jri=0)=P(ri=0)=1/2.\begin{aligned} P((Dr)_i=0\mid y=0) &= P(D_{i,j}r_i=0)\\ &= P(r_i=0) \\&= 1/2. \end{aligned}$$

$$P((Dr)i=0∣y≠0)=P(ri=1∧Di,j=−y)≤P(ri=1)=1/2.\begin{aligned} P((Dr)_i=0\mid y\neq 0)&=P(r_i=1\land D_{i,j}=-y)\\ &\leq P(r_i=1)=1/2. \end{aligned}$$

であるので，$P(y=0),P(y≠0)P(y=0),P(y\neq 0)$ の確率がどのように分布していても，

$$P((Dr)i=0)≤1/2.P((Dr)_i=0)\leq 1/2.$$

が成立する．ゆえに

$$P((Dr)=0)=P((Dr)1=0∧(Dr)2=0∧⋯∧(Dr)n=0)≤P((Dr)i=0)≤1/2.\begin{aligned} P((Dr)=0) &=P((Dr)_1=0\land (Dr)_2=0\land\cdots\land (Dr)_n=0)\\ &\leq P((Dr)_i=0)\leq 1/2. \end{aligned}$$

ゆえに $AB≠CAB\neq C$ であるとき YES を返す確率が 1/2 以下であることがわかった．ゆえに NO を返す確率が 1/2 以上である．□

次に計算量について考える．

---

定理 : Freival のアルゴリズムの計算量は $O(n2)\mathcal{O}(n^2)$.

---

証明 : $A(Br)A(Br)$ の計算量は $O(n2)\mathcal{O}(n^2)$, $CrCr$ の計算量は $O(n2)\mathcal{O}(n^2)$. $A(Br)−CrA(Br)-Cr$ の計算量は $O(n)\mathcal{O}(n)$, ゆえに全体として計算量は $O(n2).\mathcal{O}(n^2).$ □