我在网上读到过有关 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 中,如果你知道种子,随机序列是完全可预测的。参见intrand32
variables.c
。