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

问题描述

昨天我有这个采访的问题，我不能完全回答：

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

给出一个函数 F（）= 0或1 用一个完美的1：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（）来生成的二进制数的位数<$ C的解决方案上来$ C> K = ln_2ñ。但是，这显然不会，比如说工作中，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.

有谁知道一个解决方案吗？

Does anyone know a solution?

推荐答案

您可以构建两个更大的最小功率RNG比 N 像你描述。然后，每当这个算法产生比 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

的概率，这个循环顶多停止与我的迭代是由界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。价格是需要4硬币翻转而不是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屋！