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

乱数を引くと最悪ケースが消える理由

通常のアルゴリズムの計算量は入力だけで決まり、最悪計算量（Big-O）はその入力空間の中で一番不利なケースを指します。問題は、攻撃者やデータ生成側がその最悪入力を狙って作れることです。乱択アルゴリズム（randomized algorithm）は、実行中に内部で乱数（コイン投げ）を引き、その乱数に応じて挙動を変えます。これにより計算量や正しさが、固定の最悪入力ではなく自分が引いた乱数の上で平均された量になります。

決定的な平均ケース解析との違いが核心です。平均ケース解析は「入力がこの確率分布から来る」と仮定して期待値を取りますが、その仮定が崩れれば保証は消えます。乱択アルゴリズムは入力を一切仮定しません。乱数は自分が引くので、どんな敵対的な入力に対しても、期待計算量や成功確率が成り立ちます。乱数の引き方が入力から独立しているため、攻撃者は「いつも遅くなる入力」を構成できないのです。

Las Vegas と Monte Carlo

乱数が「正しさ」と「実行時間」のどちらに不確実性を持ち込むかで、乱択アルゴリズムは2種類に分かれます。

Las Vegas 型は出力が必ず正しく、揺れるのは実行時間だけです。たまたま悪い乱数を引けば遅くなりますが、間違った答えは返しません。Monte Carlo 型は実行時間を固定する代わりに、低い確率で誤った答えを返すことを許します。この2つは無関係ではなく、Las Vegas のアルゴリズムに「時間切れで打ち切ったら適当に答える」打ち切りを入れれば Monte Carlo に変換でき、逆に Monte Carlo を「正しい答えが出るまで結果を検証して繰り返す」ことで Las Vegas にできます（検証が安く可能な場合）。

乱択クイックソート（Las Vegas の典型）

通常のクイックソートはピボットを「先頭要素」など固定位置から選びます。すると既ソート列のような特定の入力でピボットが毎回最小（または最大）になり、分割が偏って O(n^2) に劣化します。これは決定的なので、攻撃者は最悪入力を構成できます。

乱択クイックソートはピボットを毎回一様ランダムに選びます。出力（ソート結果）は常に正しいので Las Vegas 型です。揺れるのは比較回数だけ。鍵となる事実は、ランダムなピボットが「上位 1/4 から下位 1/4 を除いた中央寄りの半分」に入る確率が 1/2 あり、そのとき両側の部分問題サイズがどちらも全体の 3/4 以下になることです。良いピボットが定数確率で出るので、分割の深さは期待で O(log n) に収まります。

期待比較回数の見方（指標変数法）:
- 値の組 (i番目に小さい要素, j番目に小さい要素) が比較されるのは
  両者の間の値の中で「先にピボットに選ばれたのが i か j」のときだけ
- その確率は 2 / (j - i + 1)
- 全ペアで総和すると Σ 2/(j-i+1) ≒ 2n·ln n
=> 期待比較回数 = O(n log n)

重要なのは、この O(n log n) がどの入力に対しても成り立つことです。既ソートだろうが逆順だろうが、ピボットは入力と無関係にランダムなので、最悪入力という概念が消えます。最悪計算量自体は依然 O(n^2)（運悪く毎回偏った場合）ですが、その確率は天文学的に小さく、期待値が O(n log n) に張り付きます。分割統治の漸化式としての見方は分割統治法とマスター定理に接続します。

ミラーラビン素数判定（Monte Carlo の典型）

巨大な整数 n が素数かを判定する問題です。試し割りは n の桁数に対して指数時間で実用になりません。ミラーラビン法はフェルマーの小定理の強化版を使い、多項式時間で判定します。

土台はフェルマーの小定理「n が素数なら、1 <= a < n のすべての a で a^(n-1) ≡ 1 (mod n)」です。ただしこの逆は偽で、カーマイケル数のように合成数でも全ての a で成立してしまう例外があり、単純なフェルマー判定は破れます。ミラーラビンはこれを強めます。n - 1 を 2^s * d（d は奇数）と分解し、各 a について次の強い条件を課します。

n-1 = 2^s · d  （d は奇数）
証人 a が「素数らしい」と認める条件は、次のどちらか:
  (1) a^d ≡ 1            (mod n)
  (2) ある r (0 <= r < s) で a^(2^r · d) ≡ -1  (mod n)
どちらも満たさない a が見つかれば、n は確実に合成数（a はその「証人」）

この強い条件のおかげで、n が合成数なら、1 < a < n-1 の範囲のうち少なくとも 3/4 が「合成数であることの証人」になることが証明できます。つまりランダムに a を1個選んで判定すると、合成数を誤って素数と認める確率は高々 1/4 です。素数を合成数と誤ることは決してない（素数なら全 a で条件成立）ので、これは片側誤りの Monte Carlo です。

確率増幅と誤り確率の設計

Monte Carlo の誤り確率を反復で下げられるのは、各試行が独立だからです。1回の誤り確率が p なら、独立な k 回がすべて誤る確率は p^k。p < 1 である限り、k を線形に増やすだけで誤り確率は指数的に減ります。これが乱択の実務的な威力の中心です。

ただし「片側誤り」か「両側誤り」かで増幅の手順が変わります。

片側誤りは単純で、ミラーラビンのように「証人が1つでも見つかれば確定」できます。両側誤りは多数決を取り、チェルノフ限界により「過半数が誤る確率」が試行回数に対して指数的に小さくなることを使います。いずれにせよ、必要な信頼度から逆算して試行回数 k を決められるのが乱択設計の利点です。誤り確率という連続量を、計算コストと引き換えに好きなだけ小さくできるわけです。

まとめ: 乱数が与える2つの保証

乱択アルゴリズムは、入力ではなく自分の引く乱数の上で平均を取ることで、敵対的入力に対しても性能や正しさを保証します。Las Vegas は答えを常に正しく保ちつつ実行時間を確率変数にし（乱択クイックソートは期待 O(n log n)、最悪入力が消える）、Monte Carlo は実行時間を固定して低確率の誤りを許します（ミラーラビンは片側誤りで誤り (1/4)^k）。Monte Carlo の誤り確率は独立試行の反復で指数的に削れるため、コストと信頼度を自由に調整できます。決定的アルゴリズムが「最悪入力に縛られる」一方、乱択は「予測不能性そのものを設計資源にする」――この発想は、難問の近似や計算量クラス P・NPをめぐる議論にも通じる、アルゴリズム設計の強力な一手です。