ランダム性をテストする方法 (適切な例 - シャッフル)
https://stackoverflow.com/questions/56411
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
まず、この質問は以下から抜粋したものです これ 質問。この部分は、長い質問の下位部分よりも重要であると考えたので、このようにしました。気分を害される場合は、ご容赦ください。
ランダム性を生成するアルゴリズムがあると仮定します。さて、どうやってテストするのでしょうか？もっと直接的に言うと、トランプをシャッフルするアルゴリズムがあると仮定します。それが完全にランダムなアルゴリズムであることをどのようにテストしますか?
問題にいくつかの理論を追加するために - カードのデッキは52でシャッフルできます！(52 階乗) のさまざまな方法。カードのデッキを用意し、手でシャッフルし、すべてのカードの順序を書き留めます。まさにそのシャッフルが得られる確率はどれくらいですか?答え：1/52！
シャッフルした後に A、K、Q、J が得られる確率はどれくらいですか...シーケンス内の各スーツの?答えは1/52！
したがって、一度シャッフルして結果を見るだけでは、シャッフル アルゴリズムのランダム性に関する情報はまったく得られません。2 回行うとさらに多くの情報が得られ、3 回行うとさらに多くの情報が得られます...
シャッフル アルゴリズムのランダム性をブラック ボックス テストするにはどうすればよいでしょうか?
解決
統計。RNG をテストするための事実上の標準は、 ダイハード スイート (当初は次の場所で入手可能でした) http://stat.fsu.edu/pub/diehard）。あるいは、 耳鼻咽喉科プログラム 解釈は簡単ですが、包括的ではないテストを提供します。
シャッフルアルゴリズムについては、以下のようなよく知られたアルゴリズムを使用します。 フィッシャー・イェーツ （別名「クヌース・シャッフル」）。基礎となる RNG が一様にランダムである限り、シャッフルは一様にランダムになります。Java を使用している場合、このアルゴリズムは標準ライブラリで利用できます (「 コレクション.シャッフル).
おそらくほとんどのアプリケーションでは問題ありませんが、ほとんどの RNG は 52 枚のカード デッキのあらゆる可能な組み合わせを生成するのに十分な自由度を提供していないことに注意してください (説明済み) ここ).
他のヒント
ここでは、実行できる簡単なチェックを 1 つ紹介します。生成された乱数を使用して Pi を推定します。これはランダム性の証拠ではありませんが、貧弱な RNG は通常、この問題ではうまく機能しません (~3.14 ではなく 2.5 や 3.8 などを返します)。
理想的には、これはランダム性をチェックするために実行する多くのテストのうちの 1 つにすぎません。
他に確認できることは、 標準偏差 出力の。0..n の範囲内に一様に分布した値の母集団の予想標準偏差は、n/sqrt(12) に近づきます。
/**
* This is a rudimentary check to ensure that the output of a given RNG
* is approximately uniformly distributed. If the RNG output is not
* uniformly distributed, this method will return a poor estimate for the
* value of pi.
* @param rng The RNG to test.
* @param iterations The number of random points to generate for use in the
* calculation. This value needs to be sufficiently large in order to
* produce a reasonably accurate result (assuming the RNG is uniform).
* Less than 10,000 is not particularly useful. 100,000 should be sufficient.
* @return An approximation of pi generated using the provided RNG.
*/
public static double calculateMonteCarloValueForPi(Random rng,
int iterations)
{
// Assumes a quadrant of a circle of radius 1, bounded by a box with
// sides of length 1. The area of the square is therefore 1 square unit
// and the area of the quadrant is (pi * r^2) / 4.
int totalInsideQuadrant = 0;
// Generate the specified number of random points and count how many fall
// within the quadrant and how many do not. We expect the number of points
// in the quadrant (expressed as a fraction of the total number of points)
// to be pi/4. Therefore pi = 4 * ratio.
for (int i = 0; i < iterations; i++)
{
double x = rng.nextDouble();
double y = rng.nextDouble();
if (isInQuadrant(x, y))
{
++totalInsideQuadrant;
}
}
// From these figures we can deduce an approximate value for Pi.
return 4 * ((double) totalInsideQuadrant / iterations);
}
/**
* Uses Pythagoras' theorem to determine whether the specified coordinates
* fall within the area of the quadrant of a circle of radius 1 that is
* centered on the origin.
* @param x The x-coordinate of the point (must be between 0 and 1).
* @param y The y-coordinate of the point (must be between 0 and 1).
* @return True if the point is within the quadrant, false otherwise.
*/
private static boolean isInQuadrant(double x, double y)
{
double distance = Math.sqrt((x * x) + (y * y));
return distance <= 1;
}
まず、あなたが指摘したように、特定の有限出力が「本当にランダム」であるかどうかを確実に知ることは不可能です。 任意の出力が可能です.
できることは、一連の出力を取得し、このシーケンスのさまざまな測定値をより可能性の高いものと比較することです。生成アルゴリズムが適切に機能しているという一種の信頼スコアを導き出すことができます。
たとえば、10 個の異なるシャッフルの出力を確認できます。各カードに 0 ～ 51 の数字を割り当て、シャッフル全体で 6 番目のカードの平均を求めます。収束平均は 25.5 なので、ここで値 1 が表示されると驚くでしょう。中心極限定理を使用して、特定の位置に対する各平均の可能性を推定することができます。
しかし、ここで立ち止まるべきではありません！なぜなら、このアルゴリズムは、各ポジションで正確な平均値 25.5 が得られるように設計された 2 つのシャッフルを交互に行うだけのシステムによって騙される可能性があるからです。どうすればもっと良くなるでしょうか?
さまざまなシャッフルにわたって、各位置で均一な分布 (特定のカードの確率が等しい) が期待されます。そのため、10のシャッフルの中で、選択が「均一に見える」ことを確認することができます。これは基本的に、元の問題の縮小バージョンにすぎません。標準偏差が妥当であること、最小値が妥当であること、最大値も妥当であることを確認できます。また、(割り当てられた番号によって) 最も近い 2 枚のカードなど、他の値も意味があることを確認することもできます。
しかし、十分な統計があれば、何らかの理由で特定のシャッフルが発生する可能性は非常に低いと思われるため、このようにさまざまな測定値を無限に追加することもできません。これは、カード X、Y、Z が順番に現れる数少ないシャッフルの 1 つです)。そこで大きな疑問は次のとおりです。どの測定値を取得するのが適切ですか?ここで、最善の答えがわからないことを認めなければなりません。ただし、特定のアプリケーションを念頭に置いている場合は、テストする適切なプロパティ/測定値のセットを選択し、それらを使用して作業することができます。これが暗号学者の処理方法のようです。
ランダム性のテストには多くの理論があります。カード シャッフル アルゴリズムの非常に単純なテストでは、多数のシャッフルを実行してから、各カードがどの位置に現れる確率が均一であるかをカイ二乗検定を実行できます。ただし、これでは連続するカードが相関していないことをテストすることはできないため、それについてもテストを行う必要があります。
Knuth の Art of Computer Programming の第 2 巻には、セクション 3.3.2 (経験的テスト) と 3.3.4 (スペクトル テスト) で使用できる多数のテストとその背後にある理論が記載されています。
たくさんシャッフルして、結果を記録します（これを正しく読んでいれば）。「乱数発生器」の比較を見たのを覚えています。彼らはそれを何度もテストし、結果をグラフ化するだけです。
本当にランダムであれば、グラフはほぼ均等になります。
ランダム性をテストする唯一の方法は、テスト対象のデータの予測モデルを構築するプログラムを作成し、そのモデルを使用して将来のデータを予測し、その予測の不確実性またはエントロピーを示すことです。最大値に向かう傾向があります（すなわち、一様分布) の経時変化。もちろん、モデルが必要なコンテキストをすべて捉えているかどうかは常にわかりません。モデルが与えられれば、最初のモデルではランダムに見える非ランダムなデータを生成する 2 番目のモデルを構築することが常に可能になります。しかし、冥王星の軌道がシャッフル アルゴリズムの結果に与える影響はわずかであることを受け入れる限り、その結果が許容範囲内でランダムであることに満足できるはずです。
もちろん、これを行う場合は、モデルを使用することもできます。 生成的に, 実際に必要なデータを作成します。そうすれば、また振り出しに戻ります。
あなたの質問に完全に従っていません。あなたは言う
ランダム性を生成するアルゴリズムがあると仮定します。さて、どうやってテストするのでしょうか？
どういう意味ですか？ランダム性を生成できると想定している場合は、テストする必要はありません。
優れた乱数ジェネレーターを手に入れれば、ランダムな順列を作成するのは簡単です (例:カードを 1 から 52 まで呼び出します。52 個の乱数を生成し、それぞれを順番にカードに割り当て、52 個の乱数に従って並べ替えます。順列を生成しても、優れた RNG のランダム性を破壊することはありません。
難しい問題は、RNG を信頼できるかどうかです。 こちらです 特定のコンテキストでその問題について議論している人々へのサンプル リンク。
テスト52！可能性はもちろん不可能です。代わりに、3 枚、5 枚、10 枚など、より少ない枚数のカードでシャッフルを試してください。次に、数十億回のシャッフルをテストし、ヒストグラムとカイ二乗統計検定を使用して、各順列が「偶数」回出現することを証明できます。
これまでのところコードがないため、テスト部分をコピーアンドペーストします。 私の答え 元の質問に。
// ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout << "pos=" << j->first.first << " card=" << j->first.second
<< " freq=" << j->second << std::endl;
}
このコードは、基礎となる擬似乱数ジェネレータのランダム性をテストしません。PRNG のランダム性のテストは科学の一分野です。
簡単なテストのために、いつでも圧縮してみることができます。圧縮できなくなったら、他のテストに進むことができます。
もっと頑張ってみましたが、シャッフルでは機能しませんでした。すべてのテストが失敗します。また、これは非常に厄介で、必要な値の範囲などを指定することはできません。
自分なりに考えてみると、私だったら次のようなことをします。
セットアップ（疑似コード）
// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
StatMatrix[Card.Position][Card.Number]++;
}
これにより、カードが特定の位置に何回配置されたかを示す行列 52x52 が得られます。これを何度も繰り返します (私なら 1000 から始めますが、私より統計に詳しい人はもっと良い数値を与えるかもしれません)。
マトリックスを分析する
完全なランダム性があり、シャッフルを無限回実行する場合、各カードおよび各位置について、カードがその位置に配置された回数は、他のカードの場合と同じになります。同じことを別の言い方で言うと、次のようになります。
statMatrix[position][card] / numberOfShuffle = 1/52.
そこで、その数字からどれだけ離れているかを計算してみます。
