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和添加硬币翻转以减少拒绝。

Answer 2

另一个有趣的解决方案可以通过马尔可夫链蒙特卡罗技术，Metropolis-Hastings 算法得出。如果需要大量样本，这将显着提高效率，但它只会接近极限内的均匀分布。

 initialize: x[0] arbitrarily    
 for i=1,2,...,N
  if (f() == 1) x[i] = (x[i-1]++) % n
  else x[i] = (x[i-1]-- + n) % n

对于较大的 N，向量 x 将包含 0 和 n 之间的均匀分布数。此外，通过添加接受/拒绝步骤，我们可以模拟任意分布，但您需要在 [0,1] 上模拟均匀随机数作为子过程。

Answer 3

def gen(a, b):
  min_possible = a
  max_possible = b

  while True:
    floor_min_possible = floor(min_possible)
    floor_max_possible = floor(max_possible)
    if max_possible.is_integer():
      floor_max_possible -= 1

    if floor_max_possible == floor_min_possible:
      return floor_max_possible

    mid = (min_possible + max_possible)/2
    if coin_flip():
      min_possible = mid
    else:
      max_possible = mid

Answer 4

My #RandomNumberGenerator #RNG

/w any f(x) that gives rand ints from 1 to x,  we can get rand ints from 1 to k, for any k:

get ints p & q, so p^q is smallest possible, while p is a factor of x, & p^q >= k;

Lbl A
i=0 & s=1; while i < q {
s+= ((f(x) mod p) - 1) * p^i;
i++;
}
if s > k,  goto A, else return s


//** about notation/terms:
rand = random
int = integer
mod is (from) modulo arithmetic 
Lbl is a “Label”, from the Basic language, & serves as a coordinates for executing code.  After the while loop, if s > k, then “goto A” means return to the point of code where it says “Lbl A”, & resume.  If you return to Lbl A & process the code again, it resets the values of i to 0 & s to 1.  
i is an iterator for powers of p, & s is a sum.  
"s+= foo" means "let s now equal what it used to be + foo".
"i++" means "let i now equal what it used to be + 1".
f(x) returns random integers from 1 to x. **//


I figured out/invented/solved it on my own, around 2008.  The method is discussed as common knowledge here.  Does anyone know since when the random number generator rejection method has been common knowledge?  RSVP.