拒絶反応は、乱数の真に均一な分布を取得する唯一の方法ですか？

Question

均一な分布で範囲$ [0..r-1] $に数値を出力するランダムジェネレーターがあるとします。

$ n <r $ and $ n $が$ r $を均等に分割しないと仮定します。を取得するために 本当に均一な分布 を使用できます拒否サンプリング 方法：

• $ k $が最大の整数である場合、$ k n <r $
• ランダム数を選択$ r $ in $ [0..r-1] $
• $ r <k n $の場合、出力$ r mod n $、それ以外の場合は、条件が満たされるまで他の乱数r '、r "、...

拒絶反応は、真に均一な個別の分布を取得する唯一の方法ですか？

答えが「はい」の場合、なぜですか？

注：$ n> r $の場合、アイデアは同じです：乱数を生成します$ r '$ in $ [0..r^m-1]、r^m> = n $、たとえば$ r' = r （... r（r r_1 + r_2）...） + r_m $ここで、$ r_i $は範囲の乱数です$ [0..r-1] $

Answer 1

はいといいえ、「唯一の方法」とはどういう意味かによって異なります。はい、終了することが保証されている方法はないという点で、あなたができる最善の方法（$ n $ n $と$ r $のジェネリック値の場合）は、確率1で終了するアルゴリズムです。あなたが好きなだけ小さい。

なぜ保証された終了が不可能である理由

決定論的計算エンジン（チューリングマシンまたはボートを浮かぶもの）に加えて、$ r $ -elementセット$ [0..r-1] $のランダムな要素を生成するOracleがあるとします。あなたの目標は、$ n $ -elementセット$ [0、n-1] $の要素を生成することです。エンジンの出力は、Oracleによって返される値のシーケンスにのみ依存します。これは、潜在的に無限のシーケンス$（r_0、r_1、r_2、 ldots）$の関数$ f $です。

エンジンが最大$ m $のオラクルを呼び出すと仮定します。 Oracleが$ M $時間未満と呼ばれる痕跡があるかもしれません。もしそうなら、常に$ m $時間と呼ばれるようにオラクルを余分に呼び出すことは、出力を変えません。したがって、一般性を失うことなく、Oracleは正確に$ M $時間と呼ばれると仮定します。結果$ x $の確率は、シーケンス$（r_0、 ldots、r_ {m-1}）$の数です。 Oracleは均一なランダムジェネレーターであるため、各シーケンスは登録可能で、確率が1/r^m $です。したがって、各結果の確率はフォーム$ a/r^m $です。ここで、$ a $は$ 0 $と$ r^m $の整数です。

$ n $が$ r^m $を約$ m $で除算する場合、ランダムジェネレーター$ m $ timesを呼び出すことにより、$ n $要素を超える均一な分布を生成できます（これは読者に運動として残されます）。そうでなければ、これは不可能です。確率$ 1/n $で結果を得る方法はありません。条件は、すべての$ n $の主要な要因が$ r $の要因であると言うことと同等であることに注意してください（これはあなたがあなたの質問で書いたものよりも寛容です。たとえば、あなたは4の間でランダムな要素を選択できます。 6は6を分割しませんが6）。

廃棄物を減らす

戦略では、$ r ge k 、n $の場合、すぐに再描画する必要はありません。直感的には、ミックスに保持できる$ [k 、n .. r-1] $に少しエントロピーが残っています。

実際、あなたが実際にランダム数を$ n $を永久に生成し続けると仮定し、$ d $ drawsを作成して一度に$ U $を生成します。このグループ化された世代で簡単な拒否サンプリングを行うと、$ d $ drawsを超える廃棄物は$ dfrac {r^d -k 、n^u} {d} $、つまり$ r^d mathbin { mathrm {mod}} n^u $を引き分けの数で割った。これは、$ gcd（r、n）$というわずかです。 $ r $と$ n $が共同である場合、$ d $の十分に大きな値を選択することで、廃棄物を任意に小さくすることができます。 $ r $と$ n $の一般値の場合、$ gcd（r、n）$と$ n/ gcd（r、n）$の生成を考慮する必要があるため、計算はより複雑です。しかし、繰り返しますが、十分な大きさのグループで廃棄物を任意に小さくすることができます。

実際には、比較的非効率的な乱数（暗号化の場合）であっても、$ n $が小さい場合を除き、単純な拒絶サンプリング以外のことをする価値はほとんどありません。たとえば、$ r $が通常2および$ n $の電力が通常数百または数千のビットである暗号化では、通常、均一な乱数の生成は、目的の範囲でのまっすぐな拒絶サンプリングによって進行します。

Answer 2

Shannonのソースコーディング定理は、ある意味で、$ log n/ log r $サンプル（平均して）$ [0、 ldots、r-1] $の$ log n/ log r $サンプルが必要であることを示しています。タイプ$ [0、 ldots、n-1] $。より正確には、Shannonは、最初のタイプの$ m $サンプルを与えられた（非効率的な）アルゴリズムを提供し、2番目のタイプの$ m（ log n/ log r - epsilon）$サンプルを出力し、高い確率で出力します。彼はまた、$ m（ log n/ log r + epsilon）$の出力を高い確率で出力することは不可能であることを示しています。

Shannonの定理は、歪んだ入力分布のより一般的なケース（おそらく歪んだ出力分布）でも機能します。その場合、対数をエントロピーに置き換える必要があります。定理によって与えられたアルゴリズムはランダムに定義されていますが、場合によっては、それを除去することが可能です（やや悪いパフォーマンスの犠牲を払って）。

Answer 3

実際、いや、拒絶サンプリングは唯一の進行方法とはほど遠いものです。残念ながら、コンピューターがすべての情報をビットとして保存し、したがってランダムな情報を操作できることを考慮すると、$ n $のバイナリベース開発が無限である場合、範囲n $の均一なランダム変数を描画するアルゴリズムは無限になります。

この定理は、Knuth and Yao（1976）による古典的な結果であり、DDG-Treeのフレームワークを開発しました（離散分布生成ツリー）。

ジルによって暴露される方法は、拒絶によって発生する廃棄物を緩和するために行われた典型的な種類のものですが、もちろん、次のKnuthとYaoの木を生成できる場合、それははるかに効率的です - 平均してランダムビットの平均96％保存されます。

これについては、以下で詳細を説明しました CSTHEORY POST.