ランダム化アルゴリズム

ランダム化アルゴリズムとは、その論理または手順の一部としてある程度のランダム性を用いるアルゴリズムのことです。このアルゴリズムは通常、一様乱数ビットを補助入力として使用し、その動作を制御します。これは、乱数ビットによって決定されるあらゆるランダムな選択肢の中で、「平均的な場合」において良好なパフォーマンスを達成することを目的としています。したがって、実行時間、出力（またはその両方）はランダム変数となります。

ランダムな入力を使用して常に正しい答えで終了するが、期待実行時間が有限であるアルゴリズム（例えばクイックソート^{[ 1 ]}のようなラスベガスアルゴリズム）と、誤った結果を生成する可能性がある（例えばMFAS問題に対するモンテカルロアルゴリズム^{[ 2 ]}のようなモンテカルロアルゴリズム）または失敗を通知したり終了できなかったりして結果を生成できないアルゴリズムとの間には区別がある。場合によっては、確率的アルゴリズムが問題を解決する唯一の実用的な手段となる。^{[ 3 ]}

一般的に、ランダム化アルゴリズムは、真の乱数発生器の代わりに擬似乱数発生器を用いて近似的に実装されます。このような実装では、理想的な真の乱数発生器の存在を前提とした理論的な挙動や数学的な保証から逸脱する可能性があります。

具体例として、n個の要素を持つ配列の中から「 a 」を見つける問題を考えてみましょう。

入力： n ≥ 2 個の要素からなる配列。要素の半分は「a」、残りの半分は「b」である。

出力:配列の中から「a 」を探します。

本稿では、ラスベガスアルゴリズムとモンテカルロアルゴリズムの2種類のアルゴリズムを示す。

ラスベガスのアルゴリズム：

findingA_LV (配列A 、n ) begin repeat n個の要素からランダムに1 つの要素を選択します。'a 'が見つかるまで繰り返しますend

このアルゴリズムは確率1で成功します。反復回数は変化し、任意に大きくすることができますが、期待される反復回数は

${\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

定数であるため、多数の呼び出しにおける期待実行時間は$\displaystyle \Theta (1)$（ビッグシータ表記を参照）

モンテカルロアルゴリズム：

findingA_MC (配列A 、n 、k ) begin i := 0 repeat n個の要素からランダムに1 つの要素を選択します。i := i + 1 until i = kまたは'a'が見つかるまでend

「a」が見つかればアルゴリズムは成功し、そうでなければアルゴリズムは失敗します。k回の反復後、 「 a 」が見つかる確率は次のとおりです。

このアルゴリズムは成功を保証するものではありませんが、実行時間は制限されています。反復回数は常にk以下です。kを定数とすると、実行時間（期待値と絶対値）は次のようになります。$\displaystyle \Theta (1)$。

ランダム化アルゴリズムは、囚人のジレンマのように、悪意のある「敵対者」や攻撃者が意図的にアルゴリズムに不正な入力を与えようとする場合に特に役立ちます（最悪ケースの複雑性と競合分析（オンラインアルゴリズム）を参照） 。このため、ランダム性は暗号学において遍在しています。暗号アプリケーションでは、擬似乱数は使用できません。なぜなら、敵対者が擬似乱数を予測でき、アルゴリズムが事実上決定論的になってしまうからです。したがって、真の乱数の発生源、または暗号学的に安全な擬似乱数生成器のいずれかが必要です。ランダム性が本質的に存在するもう1つの分野は量子コンピューティングです。

上記の例では、ラスベガスアルゴリズムは常に正しい答えを出力しますが、その実行時間はランダム変数です。モンテカルロアルゴリズム（シミュレーションのモンテカルロ法に関連）は、入力サイズとそのパラメータkの関数によって制限される時間内に完了することが保証されていますが、わずかなエラーの確率を許容します。任意のラスベガスアルゴリズムは、指定された時間内に完了しない場合に任意の、場合によっては誤った答えを出力するようにすることで、（マルコフの不等式を介して）モンテカルロアルゴリズムに変換できることに注意してください。逆に、答えが正しいかどうかを確認する効率的な検証手順が存在する場合、モンテカルロアルゴリズムを正しい答えが得られるまで繰り返し実行することで、モンテカルロアルゴリズムをラスベガスアルゴリズムに変換できます。

計算複雑性理論では、ランダム化アルゴリズムを確率的チューリングマシンとしてモデル化します。 ラスベガスアルゴリズムとモンテカルロアルゴリズムの両方が考慮され、いくつかの複雑性クラスが研究されています。最も基本的なランダム化複雑性クラスは RP であり、これは NO インスタンスを絶対的な確実性で認識し、YES インスタンスを少なくとも 1/2 の確率で認識する効率的な (多項式時間) ランダム化アルゴリズム (または確率的チューリングマシン) が存在する決定問題のクラスです。RP の補集合は co-RP です。平均実行時間が多項式時間で、出力が常に正しい (終了しない可能性のある) アルゴリズムを持つ問題クラスはZPPに属すると言われます。

YESとNOの両方のインスタンスを多少の誤差を伴って識別することが許容される問題のクラスはBPPと呼ばれます。このクラスはPのランダム化版として機能し、つまりBPPは効率的なランダム化アルゴリズムのクラスを表します。

ランダム性は、空間や時間のようなリソースと見なすことができます。デランダム化とは、ランダム性を取り除く（または可能な限り少なく使用する）プロセスです。^{[ 21 ] [ 22 ]}すべてのアルゴリズムの実行時間を大幅に増加させることなくデランダム化できるかどうかは、現時点ではわかっていません。 ^{[ 23 ]}例えば、計算複雑性では、P = BPPかどうかはわかっていません。^{[ 23 ]}つまり、小さなエラー確率で多項式時間で実行される任意のランダム化アルゴリズムを、ランダム性を使用せずに多項式時間で実行するようにデランダム化できるかどうかはわかりません。

特定のランダム化アルゴリズムを非ランダム化するために使用できる具体的な方法がいくつかあります。

• 条件付き確率法とその一般化、悲観的推定量
• 不一致理論（幾何アルゴリズムのランダム性を排除するために使用される）
• アルゴリズムで使用されるランダム変数の限定的な独立性の利用、例えばユニバーサルハッシュで使用されるペアワイズ独立性^{[ 24 ]}
• エキスパンダーグラフ（または一般的にはディスパーサー）を使用して、限られた量の初期ランダム性を増幅する（この最後のアプローチは、ランダムソースから擬似ランダムビットを生成するとも呼ばれ、擬似ランダム性という関連トピックにつながる）。
• ランダム化アルゴリズムを、アルゴリズムのタスクにおけるランダム性の源としてハッシュ関数を使用するように変更し、その後、ハッシュ関数の考えられるすべてのパラメータ（シード）を総当たりで試行することでアルゴリズムを非ランダム化する。この手法は通常、サンプル空間を網羅的に探索し、アルゴリズムを決定論的にするために使用される（例：ランダム化グラフアルゴリズム）。

計算モデルをチューリングマシンに限定した場合、ランダムな選択を行う能力によって、その能力がなければ多項式時間で解けない問題が多項式時間で解けるようになるかどうかは、現在未解決の問題である。これは、P = BPP であるかどうかの問題である。しかし、他の文脈では、ランダム化によって厳密な改善が得られる問題の具体的な例が存在する。

• 最初の動機付けとなる例に基づくと、2k^文字からなる指数関数的に長い文字列（半分がa、半分がb）が与えられた場合、ランダムアクセスマシンは最悪の場合、aのインデックスを見つけるために^{2k -1回}のルックアップを必要とします。ランダムな選択が許される場合、この問題は期待値多項式回数のルックアップで解決できます。
• 組み込みシステムやサイバーフィジカルシステムで数値計算を実行する自然な方法は、高い確率で正しい結果に近似する結果（またはおそらく近似的に正しい計算（PACC））を提供することです。近似計算と正しい計算の間の不一致損失の評価に関連する難しい問題は、ランダム化を利用することで効果的に対処できます^{[ 25 ]。}
• 通信複雑性において、2 つの文字列の等価性は、以下の方法である程度の信頼性をもって検証できます。${\displaystyle \log n}$ランダム化プロトコルによる通信のビット。決定論的プロトコルには${\displaystyle \Theta (n)}$強い相手から身を守る場合。^{[ 26 ]}
• 凸体の体積は、ランダム化アルゴリズムによって多項式時間で任意の精度で推定できます。^{[ 27 ]} BárányとFüredi は、決定論的アルゴリズムでは同じことができないことを示しました。^{[ 28 ]}これは無条件に真であり、つまり、凸体がブラックボックスとしてのみ照会できると仮定すれば、複雑性理論の仮定に頼る必要はありません。
• ランダム性が役立つと思われる場所のより複雑性理論的な例として、クラスIPがあります。IP は、全能の証明者と BPP アルゴリズムを実装する検証者との間の多項式時間長の相互作用によって (高い確率で) 受け入れられるすべての言語で構成されます。IP = PSPACE。^{[ 29 ]}ただし、検証者が決定論的である必要がある場合は、IP = NP になります。
• 化学反応ネットワーク（有限個の分子に対して作用する A+B → 2C + D のような有限個の反応の集合）では、初期状態から特定の目標状態に到達できるかどうかは決定可能ですが、特定の目標状態に到達する確率を近似すること（次にどの反応が起こるかの標準的な濃度に基づく確率を使用）は決定不可能です。より具体的には、ランダムな化学反応ネットワークを使用した場合に限り、制限付きチューリングマシンを任意の高い確率で常に正しく動作するようにシミュレートできます。単純な非決定論的化学反応ネットワーク（次に起こりうる反応はどれでも起こり得る）では、計算能力は原始的な再帰関数に制限されます。^{[ 30 ]}

• 近似計数アルゴリズム
• アトランティックシティのアルゴリズム
• ボゴソート
• カウントミニスケッチ
• HyperLogLog
• カーガーのアルゴリズム
• ラスベガスのアルゴリズム
• モンテカルロアルゴリズム
• 決定延期の原則
• アルゴリズムの確率解析
• 確率的ロードマップ
• ゼロサムゲームとしてのランダム化アルゴリズム

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、1990年。ISBN 0-262-03293-7第5章：確率解析とランダム化アルゴリズム、91～122ページ 。
• Dirk Draheim著「確率的型付きラムダ計算のセマンティクス（マルコフ連鎖セマンティクス、停止挙動、および表示的セマンティクス）」 Springer、2017年。
• ジョン・クラインバーグとエヴァ・タルドス著『アルゴリズム設計』第13章「ランダム化アルゴリズム」
• Fallis, D. (2000). 「ランダム化アルゴリズムの信頼性」. The British Journal for the Philosophy of Science . 51 (2): 255–271 . doi : 10.1093/bjps/51.2.255 .
• M. ミッツェンマッハー、E. ウプファル著『確率と計算：ランダム化アルゴリズムと確率解析』ケンブリッジ大学出版局、ニューヨーク（NY）、2005年。
• Rajeev Motwaniおよび P. Raghavan。『ランダム化アルゴリズム』ケンブリッジ大学出版局、ニューヨーク（NY）、1995 年。
• Rajeev Motwani および P. Raghavan。「ランダム化アルゴリズム」。ランダム化アルゴリズムに関する調査。
• クリストス・パパディミトリウ（1993）、『計算複雑性』（第1 版）、アディソン・ウェスリー、ISBN 978-0-201-53082-7第11章：ランダム化計算、241～278ページ 。
• Rabin, Michael O. (1980). 「素数判定のための確率的アルゴリズム」 . Journal of Number Theory . 12 : 128–138 . doi : 10.1016/0022-314X(80)90084-0 .
• AA Tsay、WS Lovejoy、David R. Karger、「カット、フロー、ネットワーク設計問題におけるランダムサンプリング」、オペレーションズリサーチの数学、24(2):383–413、1999年。
• 「科学計算のためのランダム化アルゴリズム」（RASC）、OSTI.GOV（2021年7月10日）。