主页 / unix / 问题 / 528343
Accepted
cprn
Asked: 2019-07-05 01:10:13 +0800 CST

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

  • 772

我在Wikipedia上阅读了有关 RNG和TLDP$RANDOM上的功能，但它并没有真正解释这个结果：

$ 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 倍以上的值比 3、4、5 更倾向于 0、1、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
random

2 个回答

  1. Best Answer

    为了扩展模偏差的主题，您的公式是：

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

    • 37

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

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

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

    • 23

相关问题