当摆脱模偏差时，min = -upper_bound％upper_bound如何；//工作？

Question

在回答另一个问题时，提供了以下解决方案，由OpenBSD提供，为了简洁起见，

uint32_t foo( uint32_t limit ) {
  uint32_t min = -limit % limit, r = 0;

    for(;;) {
      r = random_function();
      if ( r >= min ) break;
    }
    return r % limit;
 }

这条线是如何uint32_t min = -limit % limit工作的？我想知道的是，是否有数学证据证明它确实为随机数计算了一些下限并充分消除了模偏差？

Answer 1

在中-limit % limit，考虑由产生的-limit值为2 ^w？limit，其中w是所使用的无符号类型的宽度（以位为单位），因为定义了无符号算术以模2 ^w换行。（假设的类型limit不窄于int，这将导致将其提升为int使用正负号的算术，并且代码可能会中断。）然后认识到2 ^w？limit等于2 ^w模limit。因此-limit % limit当2 ^w除以时会产生余数limit。随便吧min。

在整数{0,1,2,3，…2 ^w？1} 的集合中，除以余数r（0？r < limit）的数字limit至少出现了下限（2 ^w / limit）次。我们可以识别每个：对于0？q <floor（2 ^w / limit），q • limit+ r具有r的余数，并且在集合中。如果为0？r < min，则集合中还有一个这样的数字，其中q = floor（2 ^w / limit）。那些占集合{0，1，2，3，…2 ^w？1}中的所有数字，因为floor（2 ^w/ limit）• limit+ min= 2 ^w，所以我们的计数是完整的。对于r个不同的余数，集合中有floor（2 ^w / limit）+1个数，该余数在其中；对于min?？在其他余数中，集合中存在floor（2 ^w / limit），且该余数。

现在假设我们从这个集合{0，1，2，3，…2 ^w？1}中随机抽取一个数字。显然数字为0？r < min可能会更频繁地出现，因为集合中有更多的它们。通过拒绝每个此类数字的一个实例，我们将其排除在分布之外。实际上，我们从集合{ min，min+1，min+ 2，…2 ^w？1} 中得出。结果是一个分布，该分布具有每个数字的精确下限（2 ^w / limit）出现次数以及一个特定的余数。

由于在有效分布中每个余数都表示相同的次数，因此，每个余数都有相同的机会通过均匀抽签选择。