从投掷硬币创建随机数生成器

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和添加硬币翻转,以减少拒绝,只要您愿意.