时间戳

首页 > 解决方案 > 偏差如何在有界随机数生成中表现出来

random - 偏差如何在有界随机数生成中表现出来

问题描述

我正在尝试消化以下 关于无偏见、高效随机数生成的帖子https://www.pcg-random.org/posts/bounded-rands.html 。

这是描述经典模数方法的摘录。

uint32_t bounded_rand(rng_t& rng, uint32_t range) {
    return rng() % range;
}

但除了慢之外，还有偏颇。要理解为什么 rand() % 52 会产生有偏差的数字，如果我们假设 rand() 会产生 [0..2^32) 范围内的数字，请注意 52 并不能完美地整除 2^32，而是将其整除 82,595,524 次余数 48。这意味着如果我们使用 rand() % 52，将有 82,595,525 种方法从我们的 52 张牌中选择前 48 张牌，而只有 82,595,524 种方法可以选择最后 4 张牌。换句话说，对这最后四张牌有 0.00000121% 的偏差……

这篇文章继续展示了另一种技术，该技术使用浮点算法基本上生成所需范围的随机分数并将其截断为整数。

static uint32_t bounded_rand(rng_t& rng, uint32_t range) {
    double zeroone = 0x1.0p-32 * rng();
    return range * zeroone;
}

这种方法与经典的模数方法一样有偏见，但偏见的表现方式不同。例如，如果我们选择 [0..52) 范围内的数字，则数字 0、13、26 和 39 出现的频率会比其他数字少。

最后一段让我感到困惑。我不精通浮点算术，所以我努力在取模方法中的偏差和浮点方法中的偏差之间建立联系。我所看到的是，在这两种技术中，有 4 个数字是有偏见的。

标签： random

解决方案

让我们从小事做起。假设我们有一个方法rng()可以在 [0, 128) 中生成任何随机整数。如果我们将其所有 128 个结果映射如下（其中 X 是这些结果之一）：

 floor((X / 128.0) * 52)

然后我们得到下表：

 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 11, 11, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 21, 21, 21, 22, 22, 23, 23, 23, 24, 24, 25, 25, 26, 26, 26, 27, 27, 28, 28, 28, 29, 29, 30, 30, 30, 31, 31, 32, 32, 32, 33, 33, 34, 34, 34, 35, 35, 36, 36, 36, 37, 37, 38, 38, 39, 39, 39, 40, 40, 41, 41, 41, 42, 42, 43, 43, 43, 44, 44, 45, 45, 45, 46, 46, 47, 47, 47, 48, 48, 49, 49, 49, 50, 50, 51, 51

请注意，有些数字在此表中出现了两次，而另一些则出现了 3 次。这是因为我们将一个大范围映射到一个小范围，而 128 不能被 52 整除，而且还因为舍入误差。在这个例子中，52 除以 128 大约是 0.4，所以表中的下一个条目是前一个条目加上大约 0.4，然后表中的所有条目都向下舍入，从而产生一些比其他更频繁出现的数字。另一方面，如果我们使用 64 而不是 52，那么 128 项表中的所有 64 个条目将恰好出现两次。

另请参见Daniel Lemire的“模减少的快速替代方案”。

以下是上表的详细形成方式。如果我们将这些结果映射如下：

X / 128.0

然后表格的开头将如下所示：

0.000, 0.008, 0.016, 0.023, 0.031, 0.039, 0.047, 0.055, 0.062, 0.070, 0.078, 0.086, 0.094, 0.102, 0.109, 0.117, 0.125, 0.133, ...

如果我们将此表乘以 52，它现在看起来像：

0.000, 0.406, 0.812, 1.219, 1.625, 2.031, 2.438, 2.844, 3.250, 3.656, 4.062, 4.469, 4.875, 5.281, 5.688, 6.094, 6.500, 6.906, 7.312, ...

最后我们四舍五入得到：

0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, ...

推荐阅读