☰

$RANDOMを使用すると結果が不均一に分布するのはなぜですか？

tag-icon • tag-icon random
$RANDOMを使用すると結果が不均一に分布するのはなぜですか？

オンラインでRNGについて読んだ。ウィキペディアそして$RANDOM役割を果たすTLDPただし、この結果は実際には説明されていません。

$ max=$((6*3600))
$ for f in {1..100000}; do echo $(($RANDOM%max/3600)); done | sort | uniq -c
  21787 0
  22114 1
  21933 2
  12157 3
  10938 4
  11071 5

上記の値は3、4、5よりも確率が約2倍高い傾向がありますが、最大モジュラスを変更すると10値全体にほぼ均等に分布するのはなぜですか。

$ max=$((9*3600))
$ for f in {1..100000}; do echo $(($RANDOM%max/3600)); done | sort | uniq -c
  11940 0
  11199 1
  10898 2
  10945 3
  11239 4
  10928 5
  10875 6
  10759 7
  11217 8

ベストアンサー1

モジュラー偏差のトピックを拡張するには、式は次のとおりです。

max=$((6*3600))
$(($RANDOM%max/3600))

この式では、$RANDOM0から32767の範囲の任意の値です。

   RANDOM Each time this parameter is referenced, a random integer between
          0 and 32767 is generated.

可能な値にマッピングする方法を視覚化するのに役立ちます。

0 = 0-3599
1 = 3600-7199
2 = 7200-10799
3 = 10800-14399
4 = 14400-17999
5 = 18000-21599
0 = 21600-25199
1 = 25200-28799
2 = 28800-32399
3 = 32400-32767

したがって、式では、0、1、2は4、5よりも2倍高くなります。 ３が出る確率も４、５よりやや高い。したがって、結果は勝者0、1、2、敗者4、5です。

に変更すると、9*3600結果は次のようになります。

0 = 0-3599
1 = 3600-7199
2 = 7200-10799
3 = 10800-14399
4 = 14400-17999
5 = 18000-21599
6 = 21600-25199
7 = 25200-28799
8 = 28800-32399
0 = 32400-32767

1〜8は同じ確率を持っていますが、0はまだわずかに偏っているため、100,000回のテスト繰り返しでは、0はまだ勝者です。

モジュールでバイアスを修正するには、まず公式を単純化する必要があります（0〜5だけを望む場合は、モジュールは3600または理解できないよりクレイジーな数字ではなく6になります）。この単純化だけでバイアスが大幅に減少します（32766はゼロにマッピングされ、32767は1にマップされ、両方の数字はわずかなバイアスを提供します）。

$RANDOMたわみを完全に除去するには、たとえば、下から転がす必要があります32768 % 6（使用可能な任意の範囲に完全にマップされていない状態を削除します）。

max=6
for f in {1..100000}
do
    r=$RANDOM
    while [ $r -lt $((32768 % $max)) ]; do r=$RANDOM; done
    echo $(($r%max))
done | sort | uniq -c | sort -n

テスト結果：

  16425 5
  16515 1
  16720 0
  16769 2
  16776 4
  16795 3

別のアプローチは、大きな偏りのない（32768の可能な値より大きいサイズ次数）さまざまなランダムソースを使用することです。しかし、とにかくリローリングロジックを実装するのは悪いことではありません（実装されていなくても）。

おすすめ記事