从抛硬币创建随机数生成器 [英] Creating a random number generator from a coin toss

问题描述

昨天我遇到了这个面试问题，我无法完全回答:

Yesterday i had this interview question, which I couldn't fully answer:

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

Given a function f() = 0 or 1 with a perfect 1:1 distribution, create a function f(n) = 0, 1, 2, ..., n-1 each with probability 1/n

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

I could come up with a solution for if n is a natural power of 2, ie use f() to generate the bits of a binary number of k=ln_2 n. But this obviously wouldn't work for, say, n=5 as this would generate f(5) = 5,6,7 which we do not want.

有人知道解决办法吗?

推荐答案

您可以按照您的描述为大于 n 的 2 的最小幂构建 rng.然后每当这个算法生成一个大于 n-1 的数字时，把这个数字扔掉再试一次.这就是所谓的拒绝方法.

You can build a rng for the smallest power of two greater than n as you described. Then whenever this algorithm generates a number larger than n-1, throw that number away and try again. This is called the method of rejection.

添加

算法是

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 次迭代后仍在运行，概率小于十亿分之一.

The probability that this loop stops with at most i iterations is bounded by 1 - (1/2)^i. This goes to 1 very rapidly: The loop is still running after 30 iterations with probability less than one-billionth.

您可以使用稍微修改的算法减少预期的迭代次数:

You can decrease the expected number of iterations with a slightly modified algorithm:

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 并添加硬币翻转以尽可能减少拒绝.

For example if we are trying to generate 0 .. 4 (n = 5) with the simpler algorithm, we would reject 5, 6 and 7, which is 3/8 of the results. With p = 3 (for example), pn = 15, we'd have m = 16 and would reject only 15, or 1/16 of the results. The price is needing four coin flips rather than 3 and a division op. You can continue to increase p and add coin flips to decrease rejections as far as you wish.

这篇关于从抛硬币创建随机数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！