algorithm - 从抛硬币创建随机数生成器

Question

昨天我有一个面试问题，我无法完全回答:

给定一个函数 f() = 0 or 1完美的 1:1 分布，创建函数 f(n) = 0, 1, 2, ..., n-1每个概率为 1/n

如果 n 是 2 的自然次方，我可以想出一个解决方案，即使用 f()生成二进制数的位 k=ln_2 n .但这显然不适用于 n=5，因为这会生成 f(5) = 5,6,7。这是我们不想要的。

有人知道解决办法吗？

Answer 1

如您所述，您可以为大于 n 的最小的 2 次幂构建一个 rng。然后，每当此算法生成大于 n-1 的数字时，丢弃该数字并重试。这称为拒绝方法。

添加

算法是

Let m = 2^k >= n where k is is as small as possible.
do
   Let r = random number in 0 .. m-1 generated by k coin flips
while r >= n
return r

此循环在最多 i 次迭代后停止的概率受 1 - (1/2)^i 限制。这很快变为 1:循环在 30 次迭代后仍在运行，概率小于十亿分之一。

您可以通过稍微修改算法来减少预期的迭代次数:

Choose p >= 1
Let m = 2^k >= p n where k is is as small as possible.
do
   Let r = random number in 0 .. m-1 generated by k coin flips
while r >= p n
return floor(r / p)

例如，如果我们尝试使用更简单的算法生成 0 .. 4 (n = 5)，我们将拒绝 5、6 和 7，这是结果的 3/8。对于 p = 3(例如，pn = 15)，我们会得到 m = 16，并且只会拒绝 15，即 1/16 的结果。价格需要抛四次硬币而不是抛 3 次和一次除法运算。您可以继续增加 p 并添加掷硬币以尽可能减少拒绝。