为什么在使用 $RANDOM 时会得到分布不均的结果？

Question

我在维基百科$RANDOM上阅读了 RNG并在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

为什么大约 2 倍以上的值更倾向于 0、1、2，而不是 3、4、5，但是当我更改最大模数时，它们几乎平均分布在所有 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

Answer 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 个可能值大的数量级）。但是无论如何实现重新滚动逻辑并没有什么坏处（即使它可能永远不会通过）。

Answer 2

这是模偏差。如果RANDOM构造良好，则 0 到 32767 之间的每个值都会以相等的概率产生。当您使用模数时，您会更改概率：模数以上的所有值的概率都会添加到它们映射到的值中。

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

为了回答您的主要问题，至少在 Bash 中，如果您知道种子，则随机序列是完全可预测的。见intrand32在variables.c。