乱択アルゴリズム乱択アルゴリズムの概要

乱択アルゴリズムが使われる背景

n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純な手法は、配列の各要素を順次見ていく方法だが、配列の先頭の方に「b」がかたまっている場合に長時間かかってしまう（n/2回の操作）。逆の順番で見て行っても、ひとつおきに見ていったとしても同じような問題が発生する。実際、要素を調べる順序が固定されている全ての戦略（決定性アルゴリズム）では、あらゆる組合せの入力に対して常に高速なアルゴリズムであるとは保証できない。一方、配列要素を「無作為な」順序で調べる場合、入力がどうであっても高い確率で「a」を素早く見つけ出すことができる。

上の例では、乱択アルゴリズムは常に正しい答えを返す。実行時間が長くなる可能性も確率は低いが存在する。しかし、エラーを返す可能性を認めてでも、常に素早く答えを得たいということもある。前者のような乱択アルゴリズムをラスベガス法と呼び、後者のような乱択アルゴリズムをモンテカルロ法と呼ぶ。ラスベガス法で所定の時間内に完了しない場合に間違った答えを返すようにすれば、モンテカルロ法に変換される。

また、確率解析学はありうべき全ての入力の集合に何らかの前提を設ける。この前提が効率的なアルゴリズムの設計に使われる。あるアルゴリズムへの入力の性質が不明な場合、確率解析的手法は使えない。乱択アルゴリズムでは、プログラム内の擬似乱数生成機能が使われることが多い。あるアルゴリズムが乱択であると言えるのは、その出力が入力だけでなく擬似乱数にも依存する場合である。

複雑性

計算複雑性理論では、乱択アルゴリズムは確率的チューリングマシンとしてモデル化される。ラスベガス法とモンテカルロ法を含むいくつかの「複雑性クラス」が研究されている。

RP: 最も基本的な確率的複雑性クラス。決定問題LがRPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に $x\in {}L$ である確率は1/2以上で、「いいえ」を出力した場合に $x\notin {}L$ である確率は1であるときに言う。(なお上述の「1/2」を0と1の間にある任意の定数に置き換えても定義は変わらない)。
Co-RP: RPの補問題のクラス。すなわち、L^cがRPに属するとき、決定問題LはCo-RPに属するという。
BPP: 決定問題LがBPPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に $x\in {}L$ である確率も、「いいえ」を出力した場合に $x\notin {}L$ である確率も2/3以上であるときに言う。(なお上述の「2/3」を1/2と1の間にある任意の定数に置き換えても定義は変わらない)。
ZPP: 決定問題LがZPPに属するとは、(最悪時間は多項式とは限らないが)平均は多項式時間のある乱択アルゴリズムAが存在し、A(x)が「はい」を出力した場合に $x\in {}L$ である確率も、「いいえ」を出力した場合に $x\notin {}L$ である確率も1であるときに言う。

NP困難問題などのようにこれらのクラスよりも難しい問題では、乱択アルゴリズムでさえも十分ではなく、近似アルゴリズムが必要となる。

歴史的に見れば、1976年にミラー-ラビン素数判定法によって素数判定が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。当時、素数判定の実用的な決定的アルゴリズムは知られていなかった。

ミラー-ラビン素数判定法は、2つの正の整数 k と n について「k は n が合成数であることの証拠である」というような二項関係に基づいている。これをもう少し具体化すると、

n が合成数である証拠があるなら、n は合成数（素数でない）である
n が合成数なら、n 未満の自然数の少なくとも4分の3は n の合成性の証拠である
n と k が与えられたとき、k が n の合成性の証拠かどうかを素早く判定するアルゴリズムがある

以上から、素数判定問題が Co-RP クラスであることを暗示していることがわかる。ある合成数 n より小さい100個のランダムに選ばれた数があるとき、合成数である証拠となる数を見つけられない確率は (1/4)¹⁰⁰ であり、多くの実用的な目的にはこれが十分によい素数判定となる。n が大きい場合、これ以外の実用的な素数判定法は存在しないだろう。間違う確率は、乱数を使った判定を行う回数を増やせば増やすほど減っていく。

従って、実際には間違う確率を非常に小さくできるため、間違った場合のことは無視できる。実際、素数判定の多項式時間の決定的アルゴリズムが発見されたが（AKS素数判定法）、暗号ソフトウェアでは未だに乱択アルゴリズムが使われていることも多く、将来的にも全て決定的アルゴリズムに置換されることにはならないだろう。

乱数列の選択

乱数列の生成には、擬似乱数を使用することもあれば、真の乱数を利用することもある。「良い」乱数列である必要性に関しては、他の多くの乱数の応用の場合と同様だろう。再現性のためには、真の乱数であればどのような乱数列が使用されたかを全て保存しなければならない（擬似乱数であれば、シードだけ保存しておけば再現できる）。真の乱数には、それの生成に要する時間的コストといった問題もある（情報理論と物理法則にもとづく、絶対的な限界がある）。

脚注

^ 英: expected runtime

[前の解説]

[続きの解説]

「乱択アルゴリズム」の続きの解説一覧

[1] 英: expected runtime

乱択アルゴリズム 乱択アルゴリズムの概要