9

バイアスを最小限に抑えて、高速ランダム シャッフルを繰り返し生成したいと考えています。

基本的な乱数発生器 (RNG) がバイアスされていない限り、 Fisher-Yates シャッフルがバイアスされていないことが知られています。

To shuffle an array a of n elements:
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

しかし、RNG が偏っている (しかし高速である) 場合はどうなるでしょうか?

25 要素の配列のランダム順列を多数生成したいとします。偏った RNG で Fisher-Yates アルゴリズムを使用すると、順列に偏りが生じますが、これは、シャッフル アルゴリズムを適用する前に、25 要素の配列が同じ状態から始まることを前提としていると思います。たとえば、1 つの問題は、RNG の周期が 2^32 ~ 10^9 しかない場合、これは 25 であるため、25 要素のすべての可能な順列を生成できないことです! ~ 10^25 順列。

私の一般的な質問は、Fisher-Yates シャッフルの新しいアプリケーションを開始する前に、シャッフルされた要素をシャッフルしたままにしておくと、バイアスが減少し、アルゴリズムがすべての順列を生成できるようになるかということです。

私の推測では、一般的にはより良い結果が得られると思いますが、繰り返しシャッフルされる配列に、基礎となる RNG に関連する多数の要素が含まれている場合、順列が実際には予想よりも頻繁に繰り返される可能性があるようです。

これに対処する研究を知っている人はいますか？

サブ質問として、配列内の 25 個の要素のうち 5 個の順列を繰り返したい場合はどうすればよいので、Fisher-Yates アルゴリズムを使用して 5 個の要素を選択し、完全なシャッフルを行う前に停止しますか? (スワップされた配列の最後にある 5 つの要素を使用します。) 次に、以前の部分的にシャッフルされた 25 要素の配列を使用して、5 の別の順列を選択します。基になる RNG にバイアスがある場合は、元の 25 要素の配列。これについて何か考えはありますか？

25 要素のうち 5 要素の可能な順列は 6,375,600 しかないため、部分シャッフルのケースをテストする方が簡単だと思います。バイアスをチェックするために使用する簡単なテストはありますか?

4

5 に答える 5

3

RNG の周期が 2^32 ~ 10^9 しかない場合、これは 25 であるため、25 要素のすべての可能な順列を生成することはできません! ~ 10^25 順列

これは、シードが連続するすべての選択を決定する場合にのみ当てはまります。RNG が次の選択ごとに指定された範囲で正確に均等な分布を提供することが期待できる限り、すべての順列を生成できます。RNG がそれを実行できない場合、シード ベースを大きくしても役に立ちません。

副次的な質問ですが、抽選ごとに再シードすることもできます。ただし、ジェネレーターの再シードは、再シードに十分なエントロピーが含まれている場合にのみ役立ちます。タイムスタンプにはあまりエントロピーが含まれておらず、アルゴリズムの計算にも含まれていません。

リストされていないため、このソリューションが何の一部であるかはわかりませんが、ランダムな入力を使用してより大きなドメインから何かを計算しようとしている場合は、おそらくより良い方法があります。

于 2010-09-29T23:23:40.487 に答える
2

偏った RNG を使用すると、Knuth シャッフルを繰り返し実行するとすべての順列が生成されると思いますが、それを証明することはできません (RNG の期間と偏りの程度によって異なります)。

では、質問を逆にしてみましょう: ランダムな入力とバイアスされた RNG を必要とするアルゴリズムが与えられた場合、アルゴリズムの出力をデスキューするのと RNG の出力をデスキューするのはどちらが簡単ですか?

当然のことながら、後者の方がはるかに簡単に実行できます (そして、より幅広い関心があります)。それを実行するための標準的な手法がいくつかあります。Von Neumann による単純な手法は次のとおりです: バイアスされた RNG からのビットストリームが与えられた場合、ビットをペアで取得し、(0,0) と (1,1) のペアごとに破棄し、(1,0) ごとに 1 を返します。ペアとすべての (0,1) ペアの 0。この手法は、各ビットがストリーム内の他のビットと同じ確率で 0 または 1 になるストリームからのビットであり、ビットが相関していないことを前提としています。Elias は von Neumann の手法をより効率的なスキーム(より少ないビットが破棄されるスキーム) に一般化しました。

ただし、強く偏ったビットや相関のあるビットであっても、高速フーリエ変換に基づく手法などを使用して、有用な量のランダム性が含まれている場合があります。

もう 1 つのオプションは、バイアスをかけた RNG 出力を暗号的に強力な関数 (メッセージ ダイジェスト アルゴリズムなど) にフィードし、その出力を使用することです。

乱数ジェネレーターの歪みを補正する方法の詳細については、Randomness Recommendations for Security RFCを読むことをお勧めします。

私のポイントは、ランダムベースのアルゴリズムの出力が RNG によって提供されるエントロピーによって上限がある場合の品質です。極端に偏っている場合、何をしても出力は極端に偏ります。アルゴリズムは、バイアスされたランダム ビットストリームに含まれるエントロピーよりも多くのエントロピーを絞り込むことはできません。さらに悪いことに、おそらくいくつかのランダムなビットが失われます。アルゴリズムが偏った RNG で機能すると仮定しても、良い結果を得るには、少なくとも RNG の歪みを補正するのにかかる労力と同じくらいの計算労力を費やす必要があります (ただし、おそらくより多くの労力が必要になるでしょう。アルゴリズムを実行し、同時にバイアスを「打ち負かす」必要があるためです)。

質問が単なる理論上のものである場合は、この回答を無視してください。実用的である場合は、アルゴリズムの出力について仮定するのではなく、RNG の歪みを補正することを真剣に検討してください。

于 2010-09-30T00:30:20.697 に答える
2

いくつかのポイント：

1) Fisher Yates shuffle を使用している人は誰でもこれを読んで、その実装が正しいことを二重に確認する必要があります。
2) シャッフルを繰り返すと、より高速な乱数ジェネレーターを使用する目的が損なわれませんか? 確かに、必要なエントロピーを得るためにすべてのシャッフルを 5 回繰り返す必要がある場合は、低バイアス ジェネレーターを使用することをお勧めします。
3) これをテストできる環境はありますか? もしそうなら、試してみてください - ジェフのグラフは、小さなデックを使用して結果を視覚的に描写することで、非常に多くのエラーを簡単に検出できることを明確にしています.

于 2010-09-29T22:44:52.017 に答える
1

あなたの質問に完全に答えることはできませんが、この意見はコメントするには長すぎるようです。

Fisher-Yates の反復ごとに RNG から引き出された乱数の数が、RNG 期間との最小公倍数が高いことを確認するとどうなりますか? これは、アルゴリズムの最後でランダムな整数を「無駄にする」ことを意味する場合があります。25 個の要素をシャッフルする場合、24 個の乱数が必要です。最後に乱数をもう 1 つ引いて 25 の乱数を作成すると、RNG 期間よりもはるかに長い繰り返しがあるとは限りません。もちろん、ピリオドに達する前に、同じ 25 個の数字が連続して発生する可能性があります。しかし、25 には 2^32 の 1 以外に公約数がないため、25*(2^32) になるまで反復は保証されません。これは大きな改善ではありませんが、この RNG は高速だとおっしゃいました。「無駄」だったら？値ははるかに大きかったですか？すべての順列を取得することはまだ現実的ではないかもしれませんが、少なくとも到達できる数を増やすことはできます。

于 2010-09-29T22:47:54.480 に答える
1

それは完全にバイアスに依存します。一般的に、私は「それを当てにしないでください」と言います。

非バイアスに収束するバイアス アルゴリズム:

半分は何もせず、残りの半分は正しくシャッフルします。指数関数的に偏りのない方向に収束します。n 回のシャッフルの後、1-1/2^n の確率でシャッフルに偏りがなく、1/2^n の確率で入力シーケンスが選択されます。

偏ったままの偏ったアルゴリズム:

最後の要素を除くすべての要素をシャッフルします。最後の要素を移動しない方向に永続的に偏っています。

より一般的な例:

シャッフル アルゴリズムを順列の重み付き有向グラフと考えてください。ノードからの重みは、シャッフルされたときにある順列から別の順列に遷移する確率に対応します。偏ったシャッフル アルゴリズムの重みは均一ではありません。

ここで、そのグラフの 1 つのノードを水で満たし、重みに基づいて水が 1 つのノードから次のノードに流れたとします。水の分布が開始ノードに関係なく均一に収束する場合、アルゴリズムは偏りのないものに収束します。

では、どのような場合に水が均一に広がらないのでしょうか? 平均以上の体重のサイクルがある場合、サイクル内のノードは互いに供給し合い、水の平均量を上回ったままになる傾向があります。より多くの水を得るにつれて、入ってくる量が減少し、出ていく量が増えるため、すべてを摂取するわけではありませんが、平均以上になります.

于 2010-09-30T04:39:32.600 に答える