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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

给定一个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我们不想要的。

有人知道解决方案吗？

回答：

您可以使用比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。价格需要四次掷硬币而不是三分硬币和一个除法运算。您可以根据需要继续增加p并添加硬币翻转，以减少拒绝。

以上是 从掷硬币创建随机数生成器 的全部内容， 来源链接： utcz.com/qa/435265.html

回到顶部