math - 来自 2 个随机数任务的 3 个随机数

Question

假设，你有一些均匀分布的rnd(x)函数，它会返回 0 或 1。你如何使用这个函数来创建任何rnd(x,n)函数，它会返回从 0 到 n 的均匀分布数？

我的意思是每个人都在使用它，但对我来说它并不那么聪明。例如，我可以创建右边界为 2^n-1（[0-1]、[0-3]、[0-7] 等）的分布，但找不到如何为范围执行此操作的方法像 [0-2] 或 [0-5] 不使用非常大的数字以获得合理的精度。

Answer 1

假设您需要rnd(n)使用另一个rnd1()返回 0 或 1 的函数来创建返回范围 [0, n] 内均匀分布的随机数的函数。

1. 找到最小k的2^k >= n+1
2. 创建由k位组成的数字并使用 填充其所有位rnd1()。结果是 [0, 2^k-1] 范围内的均匀分布数
3. 将生成的数字与 进行比较n。如果它小于或等于 n，则返回它。否则转到步骤 2。

一般来说，这是如何通过使用生成大范围数字的库函数在小范围内生成统一数字的一种变体：

unsigned int rnd(n) {
  while (true) {
    unsigned int x = rnd_full_unsigned_int();
    if (x < MAX_UNSIGNED_INT / (n+1) * (n+1)) {
      return x % (n+1);
    }
  }
}

上面代码的解释。如果您只是返回rnd_full_unsigned_int() % (n+1)，那么这将产生对小值数字的偏见。黑色螺旋代表从 0 到 MAX_UNSIGNED_INT 的所有可能值，从内部计数。单转路径的长度为 (n+1)。红线显示了为什么会出现偏差。因此，为了消除这种偏差，我们首先在 [0, MAX_UNSIGNED_INT] 范围内创建随机数 x（这很容易使用位填充）。然后，如果 x 落入偏差生成区域，我们重新创建它。我们不断地重新创建它，直到它不落入产生偏差的区域。此时 x 的形式为a*(n+1)-1，因此x % (n+1)是一个均匀分布的数 [0, n]。