44

まず、この質問はこの質問から切り取られています。この部分は、長い質問のサブ部分よりも大きいと思うので、そうしました。気分を害する場合は、ご容赦ください。

ランダム性を生成するアルゴリズムがあるとします。では、どのようにテストしますか？または、より直接的に言えば、カードのデッキをシャッフルするアルゴリズムがあると仮定すると、それが完全にランダムなアルゴリズムであることをどのようにテストしますか?

問題にいくつかの理論を追加するには - カードのデッキは 52 でシャッフルできます! (52階乗) さまざまな方法。カードのデッキを取り、手でシャッフルし、すべてのカードの順番を書き留めます。あなたがまさにそのシャッフルを得る確率はどれくらいですか? 答え: 1 / 52!.

シャッフルした後、順番に各スートの A、K、Q、J ... が出る確率は? 答え 1 / 52!

したがって、一度シャッフルして結果を見るだけでは、シャッフル アルゴリズムのランダム性に関する情報はまったく得られません。2回で情報が増え、3回でさらに…

シャッフル アルゴリズムのランダム性をどのようにブラック ボックス テストしますか?

4

11 に答える 11

30

統計学。RNGをテストするための事実上の標準は、Diehardスイート（元々はhttp://stat.fsu.edu/pub/diehardで入手可能）です。あるいは、Entプログラムは、解釈は簡単ですが包括的ではないテストを提供します。

シャッフルアルゴリズムについては、 Fisher-Yates（別名「KnuthShuffle」）などのよく知られたアルゴリズムを使用してください。基になるRNGが均一にランダムである限り、シャッフルは均一にランダムになります。Javaを使用している場合、このアルゴリズムは標準ライブラリで使用できます（Collections.shuffleを参照）。

ほとんどのアプリケーションではおそらく問題ではありませんが、ほとんどのRNGは、52枚のカードデッキ（ここで説明）のすべての可能な順列を生成するのに十分な自由度を提供しないことに注意してください。

于 2008-09-11T12:45:04.717 に答える
7

ここでは、実行できる簡単なチェックを 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;
}
于 2008-09-11T13:50:23.937 に答える
6

まず、ご指摘のとおり、任意の出力が可能であるため、特定の有限出力が「真にランダム」であるかどうかを確実に知ることは不可能です。

実行できることは、出力のシーケンスを取得し、このシーケンスのさまざまな測定値をより可能性の高いものと照合することです。生成アルゴリズムが適切に機能しているという一種の信頼スコアを導き出すことができます。

たとえば、10種類のシャッフルの出力を確認できます。各カードに0から51の番号を割り当て、シャッフル全体で位置6のカードの平均を取ります。収束平均は25.5であるため、ここで1の値を見ると驚くでしょう。中心極限定理を使用して、特定の位置の各平均の可能性の推定値を取得できます。

しかし、ここで止まるべきではありません！このアルゴリズムは、各位置で正確な平均25.5を与えるように設計された2つのシャッフルを交互に繰り返すシステムによってだまされる可能性があるためです。どうすればもっとうまくできるでしょうか？

さまざまなシャッフルにわたって、各位置で均一な分布（任意のカードに対して等しい可能性）が期待されます。したがって、10個のシャッフルの中で、選択肢が「均一に見える」ことを確認することができます。これは基本的に、元の問題の単なる縮小版です。標準偏差が妥当に見えること、最小値が妥当であること、および最大値も確認できます。また、最も近い2枚のカード（割り当てられた番号による）などの他の値も意味があることを確認できます。

ただし、この広告のようなさまざまな測定値を無限に追加することもできません。十分な統計があれば、特定のシャッフルが何らかの理由で表示される可能性は非常に低いためです（たとえば、これはカードX、Y、Zが表示される数少ないシャッフルの1つです。注文）。したがって、大きな問題は、実行する適切な測定セットはどれかということです。ここで私は最善の答えがわからないことを認めなければなりません。ただし、特定のアプリケーションを念頭に置いている場合は、テストするプロパティ/測定値の適切なセットを選択して、それらを操作できます。これは、暗号学者が物事を処理する方法のようです。

于 2008-09-11T12:49:16.313 に答える
4

ランダム性のテストには多くの理論があります。カードシャッフルアルゴリズムの非常に単純なテストでは、多くのシャッフルを実行してから、各カードが任意の位置で表に出る確率が均一であるというカイ2乗検定を実行できます。しかし、それは連続するカードが相関していないことをテストしないので、あなたはそれについてもテストしたいと思うでしょう。

KnuthのArtofComputer Programmingの第2巻では、セクション3.3.2（経験的テスト）と3.3.4（スペクトルテスト）で使用できるいくつかのテストと、それらの背後にある理論について説明しています。

于 2008-09-11T12:51:45.217 に答える
3

ランダム性をテストする唯一の方法は、テスト対象のデータの予測モデルを構築しようとするプログラムを作成し、そのモデルを使用して将来のデータを予測し、その予測の不確実性またはエントロピーを示すことです。時間の経過とともに最大（つまり、均一な分布）に向かう傾向があります。もちろん、モデルが必要なコンテキストをすべてキャプチャしたかどうかは常にわかりません。モデルが与えられると、最初のモデルにランダムに見える非ランダムデータを生成する2番目のモデルを構築することが常に可能になります。しかし、冥王星の軌道がシャッフルアルゴリズムの結果にわずかな影響しか及ぼさないことを認める限り、その結果が許容できるほどランダムであることに満足できるはずです。

もちろん、これを行う場合は、モデルを生成的に使用して、実際に必要なデータを作成することもできます。そして、あなたがそれをするなら、あなたは正方形の1に戻っています。

于 2008-09-11T12:32:52.827 に答える
2

たくさんシャッフルして、結果を記録します（これを正しく読んでいる場合）。「乱数ジェネレーター」の比較を見たのを覚えています。彼らはそれを何度もテストし、結果をグラフ化します。

本当にランダムな場合、グラフはほとんど偶数になります。

于 2008-09-11T12:29:58.717 に答える
0

私はあなたの質問に完全には従っていません。あなたは言う

ランダム性を生成するアルゴリズムがあると仮定します。では、どのようにテストしますか？

どう言う意味ですか？ランダム性を生成できると想定している場合は、それをテストする必要はありません。

優れた乱数ジェネレーターがあれば、ランダム順列を作成するのは簡単です（たとえば、カードを1〜52と呼びます。52個の乱数を生成して、それぞれを順番にカードに割り当て、52個の乱数に従って並べ替えます）。順列を生成することによって、優れたRNGのランダム性を破壊することはありません。

難しい問題は、RNGを信頼できるかどうかです。 これは、特定のコンテキストでその問題について話し合っている人々へのサンプルリンクです。

于 2008-09-11T12:47:01.450 に答える
0

テスト52！可能性はもちろん不可能です。代わりに、3、5、10 などの少数のカードでシャッフルを試してみてください。その後、数十億回のシャッフルをテストし、ヒストグラムとカイ 2 乗統計テストを使用して、各順列が「偶数」になることを証明できます。の回。

于 2008-09-11T12:57:31.160 に答える
0

簡単なテストのために、いつでも圧縮を試すことができます。圧縮されなくなったら、他のテストに進むことができます。

私は一生懸命試しましたが、シャッフルでは機能しません。すべてのテストが失敗します。また、非常にずさんで、必要な値の範囲などを指定することはできません。

于 2016-10-05T20:10:03.817 に答える
0

これまでのところコードがないため、元の質問への回答からテスト部分をコピーして貼り付けます。

  // ...
  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 のランダム性のテストは、科学の一分野です。

于 2008-09-11T13:18:55.900 に答える
-1

自分で考えてみると、私は次のようなことをします：

セットアップ (疑似コード)

// 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.

それで、私たちがその数からどれだけ離れているかを計算します。

于 2008-09-11T14:43:50.733 に答える