エイリアス方式

コンピューティングにおいて、エイリアス法は、離散確率分布からサンプリングするための効率的なアルゴリズムのファミリーであり、1974年にアラスター・J・ウォーカーによって発表されました。^{[1] [2]}つまり、任意の離散確率分布p _iに従って整数値1 ≤ i ≤ nを返します。アルゴリズムは通常、O ( n log n )またはO ( n )の前処理時間を使用し、その後、 O (1)時間で分布からランダムな値を抽出できます。^[3]

内部的には、アルゴリズムは確率 表 U _iと別名表 K _i ( 1 ≤ i ≤ n ) の 2 つの表を参照します。ランダムな結果を生成するために、公平なサイコロを振って2 つの表のインデックスiを決定します。次に、偏ったコインを投げて、確率U _iでiの結果を選択し、そうでない場合はK _i (確率1 − U _i ) を選択します。^[4]

より具体的には、アルゴリズムは次のように動作します。

1. 均一なランダム変量0 ≤ x < 1を生成します。
2. i = ⌊ nx ⌋ + 1、y = nx + 1 − iとします。(これにより、i は{1, 2, ..., n }に一様分布し、y は[0, 1)に一様分布します。)
3. y < U _iの場合は、iを返します。これはバイアスのあるコイン投げです。
4. それ以外の場合は、K _iを返します。

Marsagliaら^{[5]が提案した確率表の代替定式化である}二乗ヒストグラム法では、 3番目のステップで条件x <  V _i = ( U _i  +  i  − 1)/ nをチェックすることでyの計算を回避します。

分布には、n を2 の累乗などの都合の良い値に増やすために、追加の確率p _i = 0が埋め込まれることがあります。

2 つのテーブルを生成するには、まずU _i = np _iを初期化します。このとき、テーブル エントリを次の 3 つのカテゴリに分けます。

• U _i > 1 の「オーバーフル」グループでは、
• U _i < 1かつK _iが初期化されていない「underfull」グループ、および
• U _i = 1またはK _i が初期化されている「完全に完全な」グループ。

U _i = 1の場合、対応する値K _{i は}参照されることはなく、重要ではありませんが、K _i = iの値は意味があります。これにより、確率がU _i = 1を正確に表すことができない固定小数点数として表される場合の問題も回避されます。

すべてのテーブル エントリが完全にいっぱいにならない限り、次の手順を繰り返します。

1. 過剰エントリU _i > 1と不足エントリU _j < 1を任意に選択します。(これらのうちの 1 つが存在する場合は、もう一方も存在する必要があります。)
2. K _j ← iを設定して、エントリjの未使用のスペースを結果iに割り当てます。
3. U _i ← U _i − (1 − U _j ) = U _i + U _j − 1に変更して、エントリiから割り当てられたスペースを削除します。
4. エントリj はちょうどいっぱいになりました。
5. U _iの新しい値に基づいて、エントリi を適切なカテゴリに割り当てます。

各反復では、少なくとも 1 つのエントリが「完全にいっぱい」のカテゴリに移動します (最後の反復では 2 つが移動します)。そのため、この手順は最大でn  −1回の反復後に終了することが保証されます。各反復はO (1)時間で実行できるため、テーブルはO ( n )時間 でセットアップできます。

Vose ^{[3] : 974は、}浮動小数点の丸め誤差により、ステップ1で言及されている保証が破られる可能性があることを指摘しています。1つのカテゴリが他のカテゴリより先に空になった場合、残りのエントリのU _iは1に設定され、誤差は無視できます。浮動小数点を考慮したソリューションは、Walker-Vose法またはVoseエイリアス法と呼ばれることもあります。

ステップ 1 での任意の選択のため、エイリアス構造は一意ではありません。

y < U _iの場合、検索手順が若干速くなるため( K _iを参照する必要がないため)、テーブル生成中の目標の 1 つはU _iの合計を最大化することです。これを最適に行うことはNP 困難であることが判明しています^{[5] : 6}が、貪欲アルゴリズムはそれなりに近づきます。つまり、最も裕福な人から奪い、最も貧しい人に与えます。つまり、各ステップで最大のU _iと最小のU _{j を}選択します。これにはU _iをソートする必要があるため、 O ( n log n )時間 かかります。

エイリアス法は、均一偏差の生成自体が高速である場合には非常に効率的ですが、ランダム ビットの使用という点では最適とは程遠い場合があります。これは、必要なランダム ビットがわずかである場合でも、毎回 完全精度のランダム変量xが使用されるためです。

確率が特によくバランスが取れている場合、U _i = 1が多くなります。 iのこれらの値では、K _{i は}必要なく、y を生成するのは時間の無駄です。たとえば、p ₁ = p ₂ = 1 ⁄ 2の場合、32 ビットのランダム変数x を使用して 32 個の出力を生成できますが、エイリアス方式では 1 つしか生成されません。

確率が著しく不均衡な場合、つまりU _i ≈ 0 となる場合が多々あります。たとえば、p ₁ = 0.999か​​つp ₂ = 0.001の場合、ほとんどの場合、ケース 1 が当てはまると判断するために必要なランダム ビットはわずかです。このような場合、Marsaglia ら^{[5] : 1–4}が説明したテーブル メソッドの方が効率的です。同じ確率で多くの選択を行う場合、平均して 1 ビット未満の偏りのないランダム ビットしか必要としません。算術符号化技法を使用すると、バイナリ エントロピー関数によって指定された限界に近づくことができます。

• Donald Knuth著『The Art of Computer Programming』、第 2 巻: Seminumerical Algorithms、セクション 3.4.1。

• http://www.keithschwarz.com/darts-dice-coins/ Keith Schwarz: Vose のアルゴリズムの詳細な説明、数値的に安定したバージョン、および Java 実装へのリンク
• https://jugit.fz-juelich.de/mlz/ransampl Joachim Wuttke: 小さな C ライブラリとしての実装。
• https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 Liam Huang による C++ での実装
• https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs Vose アルゴリズムの C# 実装。
• https://github.com/cdanek/KaimiraWeightedList 浮動小数点の不安定性のない Vose アルゴリズムの C# 実装。