为什么使用 $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))

在此公式中,$RANDOM是 0-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的两倍。3的概率也略高于4、5。因此,您的结果是 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 仍然存在轻微偏差,因此 0 仍然是 100'000 次迭代测试中的获胜者。

要修复模偏差,您应该首先简化公式(如果您只想要 0-5,那么模就是 6,而不是 3600 甚至更疯狂的数字,没有意义)。仅这种简化就会大大减少您的偏差(32766 映射到 0,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 个可能值)。但无论如何,实现重新滚动逻辑并没有什么坏处(即使它可能永远不会实现)。

答案2

这是模偏差。如果RANDOM构造得当,0 到 32767 之间的每个值都会以相同的概率生成。当您使用模数时,您会更改概率:高于模数的所有值的概率都会添加到它们映射到的值中。

在您的示例中,6×3600 大约是值范围的三分之二。因此,顶部三分之一的概率会添加到底部三分之一的概率中,这意味着产生从 0 到 2 的值(大约)的可能性是产生从 3 到 5 的值的两倍。9×3600 接近 32767,因此模偏差要小得多,仅影响 32400 到 32767 之间的值。

为了回答你的主要问题,至少在 Bash 中,如果你知道种子,随机序列是完全可预测的。参见intrand32variables.c

相关内容