20

特定の試行回数の後にN個の一意の数値のセットから特定の数値が選択される確率をテストするアルゴリズムを検討します（たとえば、N = 2の場合、ルーレット（0なし）でX回の試行にかかる確率はどれくらいですか？勝つために黒？）。

このための正しい分布は、pow（1-1 / N、X-1）*（1 / N）です。

ただし、次のコードを使用してこれをテストすると、Nとは関係なく、シードとは関係なく、X=31に常に深い溝があります。

これは、使用中のPRNGの実装の詳細のために防ぐことができない本質的な欠陥ですか、これは本当のバグですか、それとも明らかな何かを見落としていますか？

// C

#include <sys/times.h>
#include <math.h>
#include <stdio.h>

int array[101];
void main(){

    int nsamples=10000000;
    double breakVal,diffVal;
    int i,cnt;

    // seed, but doesn't change anything
    struct tms time;
    srandom(times(&time));

    // sample
    for(i=0;i<nsamples;i++){
        cnt=1;
        do{
            if((random()%36)==0) // break if 0 is chosen
                break;
            cnt++;
        }while(cnt<100);
        array[cnt]++;
    }

    // show distribution
    for(i=1;i<100;i++){
        breakVal=array[i]/(double)nsamples; // normalize
        diffVal=breakVal-pow(1-1/36.,i-1)*1/36.; // difference to expected value
        printf("%d %.12g %.12g\n",i,breakVal,diffVal);
    }
}

libc6パッケージ2.15-0ubuntu20とIntelCorei5-2500SandyBridgeを搭載した最新のXubuntu12.10でテストしましたが、これは数年前に古いUbuntuマシンですでに発見されています。

また、Unity3D /Monoを使用してWindows7でこれをテストしました（ただし、どのMonoバージョンかはわかりません）。ここでは、System.Randomを使用するとX = 55で溝が発生しますが、Unityの組み込みのUnity.Randomには目に見える溝がありません（少なくともX <100の場合）。

配布：ここに画像の説明を入力してください

違い：ここに画像の説明を入力してください

4

3 に答える 3

11

これは、glibc のrandom()関数が十分にランダムでないことが原因です。このページによると、 によって返される乱数についてはrandom()、次のようになります。

oi = (oi-3 + oi-31) % 2^31

また：

oi = (oi-3 + oi-31 + 1) % 2^31.

ここで を取り、上記の最初の方程式が使用されたものであるとします (これは、各数値に対して 50% の確率で発生します)。との場合、確率は 1/36 未満です。これは、50% の確率で 2^31 未満になるためです。xi = oi % 36xi-31=0xi-3!=0xi=0oi-31 + oi-3

xi = oi % 36 = (oi-3 + oi-31) % 36 = oi-3 % 36 = xi-3、

これは非ゼロです。これにより、0 サンプルの後に 31 サンプルが表示される溝が発生します。

于 2013-02-04T01:10:24.457 に答える
7

この実験で測定されているのは、ベルヌーイ実験の成功した試行間の間隔です。ここで、成功はrandom() mod k == 0一部k(OP の 36) として定義されます。random()残念ながら、 の実装がベルヌーイ試行が統計的に独立していないという事実によって損なわれています。

`random()'の出力を書きますが、次のことに注意してください。rndiith

rndi = rndi-31 + rndi-3    確率0.75で

rndi = rndi-31 + rndi-3 + 1確率0.25で

(証明の概要については、以下を参照してください。)

としましょう。現在、 を見ています。そうでなければ、サイクルを長さとして数えていたからです。rndi-31 mod k == 0rndirndi-3 mod k ≠ 0k-3

しかし (ほとんどの場合) .(mod k): rndi = rndi-31 + rndi-3 = rndi-3 ≠ 0

そのため、現在の試行は以前の試行から統計的に独立しておらず、成功した後の 31回目の試行は、偏りのない一連のベルヌーイ試行よりも成功する可能性がはるかに低くなります。

線形合同ジェネレーターを使用する際の通常のアドバイスは、実際にはアルゴリズムには適用されませんが、random()上位ビットは「よりランダム」であるため、下位ビットの代わりに上位ビットを使用することです (つまり、連続する値との相関が低い)。high log k bitsしかし、それはこの場合も機能しません。なぜなら、上記の恒等式は functionについても function についても同様に成り立つからmod k == low log k bitsです。

実際、特に出力の上位ビットを使用する場合は、線形合同ジェネレーターがより適切に機能すると予想される場合があります。random().

randomアルゴリズム、デフォルトの場合:

state符号なし long のベクトルとします。シード、いくつかの固定値、および混合アルゴリズムを使用して初期化します。簡単にするために、状態ベクトルは無限であると見なすことができますが、最後の 31 個の値のみが使用されるため、実際にはリング バッファーとして実装されます。state0...state30

引き起こすrndi: (Note: ⊕ is addition mod 232.)

statei = statei-31 ⊕ statei-3

rndi = (statei - (statei mod 2)) / 2

Now, note that:

(i + j) mod 2 = i mod 2 + j mod 2    if i mod 2 == 0 or j mod 2 == 0

(i + j) mod 2 = i mod 2 + j mod 2 - 2 if i mod 2 == 1 and j mod 2 == 1

If i and j are uniformly distributed, the first case will occur 75% of the time, and the second case 25%.

So, by substitution in the generation formula:

rndi = (statei-31 ⊕ statei-3 - ((statei-31 + statei-3) mod 2)) / 2

     = ((statei-31 - (statei-31 mod 2)) ⊕ (statei-3 - (statei-3 mod 2))) / 2 or

     = ((statei-31 - (statei-31 mod 2)) ⊕ (statei-3 - (statei-3 mod 2)) + 2) / 2

The two cases can be further reduced to:

rndi = rndi-31 ⊕ rndi-3

rndi = rndi-31 ⊕ rndi-3 + 1

上記のように、rnd i-31と rnd i-3が一様分布から独立して引き出されたと仮定すると、最初のケースは 75% の確率で発生します (そうではありませんが、妥当な最初の近似値です)。

于 2013-02-04T02:31:03.613 に答える
1

他の人が指摘したように、random()十分にランダムではありません。

この場合、下位ビットの代わりに上位ビットを使用しても役に立ちません。man 3 randマニュアル ( ) によると、 の古い実装でrand()は下位ビットに問題がありました。そのため、random()代わりに が推奨されます。ただし、 の現在の実装でrand()は と同じジェネレータを使用していrandom()ます。

古いの推奨される正しい使用法rand()を試しました：

if ((int)(rand()/(RAND_MAX+1.0)*36)==0)

...そして X=31 で同じ深い溝を得ました

rand()興味深いことに、の数を別の数列と混ぜると、溝がなくなります。

unsigned x=0;
//...

        x = (179*x + 79) % 997;
        if(((rand()+x)%36)==0)

古いLinear Congruential Generatorを使用しています。素数表からランダムに 79、179、997 を選びました。これにより、長さ 997 の繰り返しシーケンスが生成されます。

とはいえ、このトリックはおそらく非ランダム性やフットプリントを導入した可能性があります...結果として得られる混合シーケンスは、他の統計テストに確実に失敗します。x連続する反復で同じ値を取ることはありません。実際、すべての値を繰り返すには正確に 997 回の反復が必要です。

''[..] 乱数は、ランダムに選択された方法で生成されるべきではありません。いくつかの理論を使用する必要があります。" (DEKnuth、「The Art of Computer Programming」、vol.2)

シミュレーションの場合、確実に知りたい場合は、Mersenne Twisterを使用してください。

于 2013-02-04T11:52:31.407 に答える