確率的解析と乱択アルゴリズム

確率論と計算機における問題解決の手法として
確率的解析と乱択アルゴリズムについて解説していく。
ここでは以下の問題を考える。

雇用問題

問題:
あなたは秘書を雇おうとしている。
その際にあなたは代理店を利用することにした。
その代理店は毎日１人、秘書を送ってくる。
あなたはその候補者と面談し、採用するかどうか選択する。
しかし、面談するのにあなたは費用を払う必要がある。
それに加え実際に候補者を雇うには更に費用がかかる。
そこであなたは現在の秘書よりも候補者が優れている場合すぐにでも雇う。
しかし、いくら費用がかかるか見積もりたい。
かかる費用を求めなさい。

この問題における重要点

この問題の解として、候補者を逐一比較していき数値的に高ければ雇う。
といったアルゴリズムが考えられる。
またこの問題では実行時間どうこうより
計算によって算出される費用に重点が置かれるため一般的な計算量の解析とは異なりコスト解析を行う必要がある。

このアルゴリズムにおける面談コスト( $C_i$ )は雇用コスト( $C_h$ )より小さい。
それを踏まえて $n$ 人の候補者から $m$ 人雇用した場合
このアルゴリズムのコストは $O(nC_i+mC_h)$ となる。
しかし $n$ 人の面談は必ず行わなければならないので、 $nC_i$ は変化しない。
よって、この問題では雇用コスト $C_h$ の解析に集中するべきである。

最悪の場合

この問題における最悪の場合は、面談した全ての候補者を雇用するときである。
つまり候補者の能力値が昇順になっているときである。
この時の雇用コストは $O(nC_h)$ となる。

確率的解析 ~Probabilistic Analysis~

上記の問題の様に確率を用いる問題の解析を「確率的解析」という。
確率的解析とは実行時間解析の手法ではない。
上記の問題における雇用コストを解析する手法である。
確率的解析を適用するには、入力分布に関する知識を用いるか
その分布自体を仮定してしまう必要がある。
それが完了すれば実行時間の平均を計算してアルゴリズムを解析する。
平均は入力可能な分布の上でとること、つまり全ての可能な入力に対する平均を算出する。

入力分布は慎重に決める必要がある。
というのも、問題において入力集合に対してある分布をとることで効率のよいアルゴリズムを設計するためである。
しかし妥当な入力分布が存在しない場合ある。
そのようなときには確率的解析を用いることができない。

今回の雇用問題の場合、候補者はランダムに出現し二人の候補者を比較できると仮定できる。
この仮定より、以下を満たす全順序が存在する仮定する。

${ \displaystyle 集合Xにおいて関係 \le が全順序付けられるなら、Xの任意の元a,b,cに対して \\ 1)a \le b かつ b \le a ならば a=b(反対称律) \\ 2)a \le b かつ b \le c ならば a \le c(推移律) \\ 3)a \le b または b \le aのいずれかが成立する(完全律) \\ }$

ここまで示した仮定により、候補者全員を1からnまでの数でただ一通りにランク付け出来る。
それを求める関数を $rank(i)$ とし候補者 $i$ のランクを表し、大きいほど能力値が高いとする。
よって候補者がランダムに出現することと、ランクから作られる $n!$ 通りの置換のうち
任意の一つに一致する事象はどれも等確率である。
またはランクリストは一様ランダム置換と言える。

確率的解析における乱択アルゴリズム

確率的解析を用いるには入力分布に関する知識が必須となる。(上記)
しかし、入力分布がわからない場合も多く、たとえ分布がはっきりとわかっていたとしても
必ずアルゴリズムとしてモデルに出来るとは限らない。
そこでアルゴリズムの振る舞いをランダムにして、アルゴリズム設計の道具としてランダム性を使うことが出来る。
ただこのままでは最初に挙げた問題の解決法としては使えないので
問題を以下のように変更する。

代理店が候補者リストを事前に送ってくる。
そのリストから私達が毎日面談するものを決める。

こうすることでランダムな順序で送られてくる候補者に
ランダムな順序を強制する。

乱択アルゴリズム

ここまで長々と書いてきたが乱択アルゴリズムとは何か？
多少変更した上記の問題に対して、解決方がランダム性を使うものとする。
こういった場合に、アルゴリズムの振る舞いは入力データと乱数生成器の２つで決まる。
そのように乱数を使用するアルゴリズムを乱択アルゴリズムという。
ただし計算機で用いる乱数生成器は、統計的にランダムに「見える」値を返す
決定アルゴリズムを用いた擬似乱数生成器によって実現されることが多い。

指標確率変数

雇用問題やその他乱択アルゴリズムを用いるであろう多数のアルゴリズム解析に指標確率変数を用いる。
これは確率と綿密な関係にある期待値をお互いに変換する便利な道具のようなものである。
標本空間 $S$ と事象 $A$ が与えられている時、 $A$ に関する指標確率変数を

${\displaystyle \begin{eqnarray} I\{A\} = \left\{ \begin{array}{11} 1 & Aが発生する時 \\ 0 & Aが発生しない時 \end{array}\right. \end{eqnarray} }$

と定義する。

例1

一枚のコインをコイントスして表がでる回数の期待値を求めてみる。
標本空間は $S=\{H,T\}$ とし、コインには裏表しかないので確率 $Pr\{H\} = Pr\{T\}=1/2$ となる。
今回は表が出る回数の期待値なので、事象 $H$ (表が出るとき)に対して指標確率変数 $X_H$ を定義できる。
ここでは上記の指標確率変数にしたがって、表が出るなら1、裏がでるなら0とする。

${\displaystyle \begin{eqnarray} X_H=I\{H\} = \left\{ \begin{array}{11} 1 & Hが発生する時 \\ 0 & Hが発生しない時(Tが発生する時) \end{array}\right. \end{eqnarray} }$

この様にこの問題(コイントスで表が出る回数の期待値を求める)に対して指標確率変数を定義した。
この場合の期待値を $E$ として、指標確率変数 $X_H$ を用いて期待値を計算する。

${ \displaystyle \begin{equation} E \left[ X_H \right] \\ = E\left[ I\left\{ H \right\} \right] \\ = 1*Pr \left\{H \right\}+1*Pr \left\{T \right\} \\ = 1*(1/2)+0*(1/2) = 1/2 \end{equation} }$

よって１枚のコインをコイントスした時、表がでる回数の期待値は $1/2$ となる。
今回のコイントス問題の様に単純な問題だと指標確率変数を用いるのは面倒に感じるかも知れないが
これが一回のコイントスではなく一般の $n \in \mathbb{N}$ 回に対してだと圧倒的に便利になる。
その例を次に示す。

例2

例1で考察した問題に対して一回のコイントスではなく一般の $n \in \mathbb{N}$ に対して考察してみる。
ここで $i$ 番目の指標確率変数を $X_i$ とする。この時 $0 \le i \le n$ と $n,i \in \mathbb{N}$ とする。
例1で示した様に指標確率変数の和で表せるので、全体の確率変数 $X$ は次の様に表せる。

${\displaystyle \begin{equation} X = \sum_{i = 1}^{n} X_i \end{equation} }$

上の式に対して両辺で期待値を取ると

${\displaystyle \begin{equation} E \left[ X \right] \\ = E \left[ \sum_{i = 1}^{n} X_i \right] \\ = \sum_{i = 1}^{n} E \left[ X_i \right] \\ X_i = 1/2より \\ = \sum_{i = 1}^{n} 1/2 \\ = n/2 \end{equation} }$

となることがわかる。
これで一般の自然数 $n$ に対して期待値を指標確率変数を用いて表現することができた。
なぜ指標確率変数がすぐれた解析技術として使えるかというと、期待値が線形性を持つからである。
またこの例で指した様に、指標確率変数を用いる事で大幅に計算を単純化することができる。

雇用問題への応用

候補者は上記の例同様 $n$ 人いるので $X_i$ が $i$ 人目の指標確率変数となる。
それでは $i$ 人目の指標確率変数を以下のように定義する。

${ \displaystyle \begin{eqnarray} X_i = \left\{ \begin{array}{11} 1 & 候補者iが雇用される時 \\ 0 & 候補者iが雇用されない時 \\ \end{array} \right. \end{eqnarray} }$

また確率変数 $X$ は次の様に定義できる。

${\displaystyle X = X_1 + X_2 + X_3 + ... + X_n }$

更に $i$ 人目が最初の候補者から $i-1$ 人目までの候補者の中で最も優れている確率は $1/i$ なので
上記の例2よりこの問題の期待値は次の様に表せる。

${\displaystyle \begin{equation} E \left[ X \right] \\ = E \left[ \sum_{i = 1}^{n} X_i \right] \\ = \sum_{i = 1}^{n} E \left[ X_i \right] \\ X_i = 1/iより \\ = \sum_{i = 1}^{n} 1/i \\ = \log n +O(1) \end{equation} }$

乱択アルゴリズムの適用

雇用問題やコイントスの問題のような入力全ての置換が等しい確率で成立するという過程が成り立つような問題では
確率的解析が乱択アルゴリズムを用いた開発の指針となる。
具体的にはアルゴリズムが実行される前に候補者の順番をランダムに並び変え
強制的に全ての置換の出現確率を等しくするようにする。

確率的解析と乱択アルゴリズムの違い

上記の記述より、候補者がランダムに出現しようと期待値は変化しない
決定的なアルゴリズム、つまり解が一意に決まるものと比べて
乱択アルゴリズムは入力時ではなく、アルゴリズム内で入力分布のランダム化が発生する。
そのため、特定の入力に対して情報の更新が何回起こるかわからない。
しかし、以前の実行と今回の実行でランダム化が同じである確率はとても低い。
よって、特定の入力があったとき、その入力に対して常に最悪の処理を引き起こすことがない。
乱択アルゴリズムが最悪の処理を実行してしまうのは単に運が悪かったからというだけである。