乱択アルゴリズム
n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純な手法は、配列の各要素を順次見ていく方法だが、配列の先頭の方に「b」がかたまっている場合に長時間かかってしまう(n/2回の操作)。逆の順番で見て行っても、ひとつおきに見ていったとしても同じような問題が発生する。実際、要素を調べる順序が固定されている全ての戦略(決定性アルゴリズム)では、あらゆる組合せの入力に対して常に高速なアルゴリズムであるとは保証できない。一方、配列要素を「無作為な」順序で調べる場合、入力がどうであっても高い確率で「a」を素早く見つけ出すことができる。
上の例では、乱択アルゴリズムは常に正しい答えを返す。実行時間が長くなる可能性も確率は低いが存在する。しかし、エラーを返す可能性を認めてでも、常に素早く答えを得たいということもある。前者のような乱択アルゴリズムをラスベガス法と呼び、後者のような乱択アルゴリズムをモンテカルロ法と呼ぶ。ラスベガス法で所定の時間内に完了しない場合に間違った答えを返すようにすれば、モンテカルロ法に変換される。
また、確率解析学はありうべき全ての入力の集合に何らかの前提を設ける。この前提が効率的なアルゴリズムの設計に使われる。あるアルゴリズムへの入力の性質が不明な場合、確率解析的手法は使えない。乱択アルゴリズムでは、プログラム内の擬似乱数生成機能が使われることが多い。あるアルゴリズムが乱択であると言えるのは、その出力が入力だけでなく擬似乱数にも依存する場合である。
実用的なアルゴリズムとしては最も有名なクイックソートでも、ランダム性が有効である。このアルゴリズムの決定的なバージョンで n 個の数をソートするのに要する時間は最悪で O(n) となる(既にソートされている入力を使った場合)。しかし、事前にランダムに要素を入れ替えてからクイックソートを行うと、どんな入力であっても高い確率で O(n log n) の時間で完了する。ソート対象が大きければ大きいほど、この違いは重要となる。
より複雑な例として、グラフ理論での乱択アルゴリズムの利用として、以下のような最小カットを求める乱択アルゴリズムがある。
ここで、エッジ (u,v) を縮約するとは、新たなノード w を追加し、(u,xi) や (v,xi) といったエッジ(枝)を(w,xi)と置換し、グラフ G から u と v を削除することを意味する。
n = |V[G]| とすると、このアルゴリズムが最小カットを出力する確率は最低でも n であり、nlog(n) 回試行してその中で最小の出力を選べば、非常に高い確率で最小カットが得られる。