乱択アルゴリズム

「乱択アルゴリズム」が共立出版から出ているので読んでいます

乱択アルゴリズム(wikipedia)（ランダマイズドアルゴリズムの方が一般的かもしれない）はアルゴリズムの中に（擬似）乱数が含まれており、動作が決定的ではなく、乱数に依存して動きます。
有名な例では、クイックソートのアルゴリズム中にピボットを選択するところがあるのですが、そこを決定的に最初や真ん中の値ではなく、適当に乱数でランダムに選んだ場合がそれに当たります。

クイックソートは最悪計算量が要素数がnの時、O(n^2)かかってしまう問題点がありますが、ランダムにピボットを選んだ場合、かなり高い確率でO(nlogn)で動作することが言えます。もっとはっきりいうと、比較の回数がαnlogn（αは5よりちょっと大きいぐらい）より大きくなる確率は1/(n^2)以下だということが言えます。つまりnが大きい場合は殆ど間違いなくO(nlogn)で動き、最悪値を避けようと真面目に中央値を求める必要はありません（ただ、係数は減るので実際は真面目に求めてもいいが）

これは、学部の頃習った時に少し混乱しました。もし、入力列もランダムにくるのであれば、乱数を使わず、決定的に選んだ場合（たとえばクイックソートのピボットを常に先頭を選ぶ）と乱数を選んだ場合の平均計算量（ここでは入力で平均をとってる）は同じになるはずです。なぜ、乱数を使うのかと。

で、悩みましたが、今では次のように理解しています（本にもかいてありました。）

一つ目は、決定的なアルゴリズムの場合は非常に少数の入力に対し、必ず悪く動作し（もしくは誤った答えを出す）、それ以外の入力に対してはうまく動作する。確率的なアルゴリズムの場合は全ての入力に対し、非常に少ない確率で悪く動作し、殆どはうまく動作する。

しかし、入力の方は悪意があればいくらでも操作できますし、完全にランダムということは実際のところなかなかいえません。例えばクイックソートに対し昇順の入力を与えることは結構あるかもしれません（なんか他の操作の出力だったりして）。それに対し確率的アルゴリズムの場合は擬似乱数がよければ、かならず均すことができます。

二つ目は、一定確率しか当たらないものも、アルゴリズムを繰り返し適用することで成功確率を増幅することができます。例えば片側誤りアルゴリズム（真の答えがYESの時は必ずYESと答え、真の答えがNOの時は確率p>0でNOと答える）がある時、乱数を用いてk回適用し、一度でもNOという答えが出ればNO、全てがYESならばYESとすれば、成功確率は1-(1-p)^kに増幅されます。高速な素性判定法であるRabin-Mille法や、BloomFilterなどがこれにあたります。

参照を定数時間で行なうことができるハッシュアルゴリズムのCuckoo Hash(日本語だとRadium Softwareさんところに説明がある, ）も乱択アルゴリズムで構築します。これはキー kを登録する際に、二種類の違うハッシュ関数を用いてハッシュ値 h1(k), h2(k)を用意し、二部グラフ中のh1(k)、h2(k)のどちらかがあいていないかを調べ、もしあいているならそこに、あいていないなら、二部グラフに沿ってキーを一個ずつずらしてそこに登録します。でも、偶然、最悪閉路ができてずらせない場合、または閉路ができなくても、ずらす個数がlog n を超えちゃう場合があると困るのですが、この時は思い切って今のデータ構造を破棄して、ハッシュに使っていた乱数を変えて登録したキーを全部登録しなおします。このようなことが起きる確率も小さいことが示されています。（殆ど定数個数の避難場所を用意しておけば作り直さなくても大丈夫であることもしめされてます ）pdf)

これの動的なキー追加じゃなく、キー集合が与えられている静的な場合のバージョンが、最小完全ハッシュライブラリのbepで使われてます 説明資料（pdf)

更にうれしいことに、乱択にすることにより、面倒な実装を非常にシンプルにすることもできます。機械学習などで使われる最適化も、少数のサンプルをランダムにとってきて、それらだけから勾配を求めて降る確率的勾配降下法（Stochastic Gradient Descent）が理論的にも実用的にも非常に強力であることもわかってきました。実装も今までなんだったのかとがっかりするほど簡単です(sgd）。

もちろんマルコフ連鎖モンテカルロ法（MCMC）とかも乱拓の力を存分に発揮してるものの一つです。

私自身適当なので、乱択とかは好きです。