消除模偏差：arc4random_uniform() 函数中是如何实现的？
Eliminating modulo bias: how is it achieved in the arc4random_uniform() function?
模偏差是天真地使用模运算来获得小于给定 "upper bound" 的伪随机数时出现的问题。
因此，作为一名 C 程序员，我正在使用 arc4random_uniform() 函数的修改版本来生成均匀分布的伪随机数。
问题是我不明白这个函数在数学上是如何工作的。
这是函数的解释性注释，后面是完整源代码的link：
/*
* Calculate a uniformly distributed random number less than upper_bound
* avoiding "modulo bias".
*
* Uniformity is achieved by generating new random numbers until the one
* returned is outside the range [0, 2**32 % upper_bound). This
* guarantees the selected random number will be inside
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
* after reduction modulo upper_bound.
*/
从上面的注释我们可以定义：
[2^32 % upper_bound, 2^32) - 区间 A[0, upper_bound) - 区间 B
为了工作，该函数依赖于区间 A 映射到区间 B 的事实。
我的问题是：从数学上讲，区间 A 中的数字如何均匀映射到区间 B 中的数字？这有证据吗？
有时从一个易于理解的示例开始，然后从那里进行概括会有所帮助。为了简单起见，让我们假设 arc4random returns 一个 uint8_t 而不是 uint32_t，所以 arc4random 的输出是区间 [0,256)。让我们选择一个 upper_bound 的 7。
注意7并不能整除256
256 = 7 * 36 + 4
这意味着天真地使用模运算得到小于 7 的伪随机数将导致以下概率分布
37/256 for outcomes 0,1,2,3
36/256 for outcomes 4,5,6
这就是所谓的模偏差，结果 0、1、2、3 比结果 4、5、6 更有可能。
为避免模偏差，我们可以简单地拒绝值 252,253,254,255，并生成一个新数字，直到结果位于 [0,252) 区间内。区间 [0,252) 中的所有数字具有相等的概率（拒绝较高的数字不会影响较低的数字的分配）。而且由于7整除252，所以得到的概率分布是均匀的
36/252 for outcomes 0,1,2,3,4,5,6,7
这基本上就是 arc4random_uniform 所做的，除了 arc4random_uniform 拒绝范围底部的数字。具体来说，间隔 A 为
[2^8 % 7, 2^8) which is [4, 256)
在区间[4,256)中生成一个数字（称其为N）后，最终计算结果为
outcome = N % 7
区间[4,256)内有252个数，由于252是7的倍数，所以区间[0,7)内每一个结果的概率均等
这就是 arc4random_uniform 的工作原理，它 rejects/retries 用于小范围的数字，其余范围内的数字计数是 upper_bound 的倍数。 （由于 upper_bound 与 2^32 相比通常是一个较小的数字，因此对单个结果进行多次重试的几率非常小。）
但你真的关心模偏差吗？在大多数情况下，答案是 "No"。考虑我们的上限为 7 的示例。朴素模实现的概率分布是
613566757 / 4294967296 for outcomes 0,1,2,3
613566756 / 4294967296 for outcomes 4,5,6
这是小于 0.0000002% 的模偏差。
所以你可以选择：要么在重试上花费极少的时间以获得完美的分布，要么接受概率分布中的极小误差以避免重试。
模偏差是天真地使用模运算来获得小于给定 "upper bound" 的伪随机数时出现的问题。
因此，作为一名 C 程序员，我正在使用 arc4random_uniform() 函数的修改版本来生成均匀分布的伪随机数。
问题是我不明白这个函数在数学上是如何工作的。
这是函数的解释性注释，后面是完整源代码的link：
/*
* Calculate a uniformly distributed random number less than upper_bound
* avoiding "modulo bias".
*
* Uniformity is achieved by generating new random numbers until the one
* returned is outside the range [0, 2**32 % upper_bound). This
* guarantees the selected random number will be inside
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
* after reduction modulo upper_bound.
*/
从上面的注释我们可以定义：
[2^32 % upper_bound, 2^32)- 区间 A[0, upper_bound)- 区间 B
为了工作，该函数依赖于区间 A 映射到区间 B 的事实。
我的问题是：从数学上讲，区间 A 中的数字如何均匀映射到区间 B 中的数字？这有证据吗？
有时从一个易于理解的示例开始，然后从那里进行概括会有所帮助。为了简单起见，让我们假设 arc4random returns 一个 uint8_t 而不是 uint32_t，所以 arc4random 的输出是区间 [0,256)。让我们选择一个 upper_bound 的 7。
注意7并不能整除256
256 = 7 * 36 + 4
这意味着天真地使用模运算得到小于 7 的伪随机数将导致以下概率分布
37/256 for outcomes 0,1,2,3
36/256 for outcomes 4,5,6
这就是所谓的模偏差，结果 0、1、2、3 比结果 4、5、6 更有可能。
为避免模偏差，我们可以简单地拒绝值 252,253,254,255，并生成一个新数字，直到结果位于 [0,252) 区间内。区间 [0,252) 中的所有数字具有相等的概率（拒绝较高的数字不会影响较低的数字的分配）。而且由于7整除252，所以得到的概率分布是均匀的
36/252 for outcomes 0,1,2,3,4,5,6,7
这基本上就是 arc4random_uniform 所做的，除了 arc4random_uniform 拒绝范围底部的数字。具体来说，间隔 A 为
[2^8 % 7, 2^8) which is [4, 256)
在区间[4,256)中生成一个数字（称其为N）后，最终计算结果为
outcome = N % 7
区间[4,256)内有252个数，由于252是7的倍数，所以区间[0,7)内每一个结果的概率均等
这就是 arc4random_uniform 的工作原理，它 rejects/retries 用于小范围的数字，其余范围内的数字计数是 upper_bound 的倍数。 （由于 upper_bound 与 2^32 相比通常是一个较小的数字，因此对单个结果进行多次重试的几率非常小。）
但你真的关心模偏差吗？在大多数情况下，答案是 "No"。考虑我们的上限为 7 的示例。朴素模实现的概率分布是
613566757 / 4294967296 for outcomes 0,1,2,3
613566756 / 4294967296 for outcomes 4,5,6
这是小于 0.0000002% 的模偏差。
所以你可以选择：要么在重试上花费极少的时间以获得完美的分布，要么接受概率分布中的极小误差以避免重试。