生成对Random（0，1）进行调用的Random（a，b） [英] Generate Random(a, b) making calls to Random(0, 1)

问题描述

有一个已知的 Random（0,1）函数，它是一个统一的随机函数，这意味着它将给出0或1，概率为50％。实现 Random（a，b）仅调用 Random（0,1）

There is known Random(0,1) function, it is a uniformed random function, which means, it will give 0 or 1, with probability 50%. Implement Random(a, b) that only makes calls to Random(0,1)

到目前为止，我仍然将范围ab放入基于0的数组中，然后得到索引0、1、2 ... ba。

What I though so far is, put the range a-b in a 0 based array, then I have index 0, 1, 2...b-a.

然后调用 RANDOM（0,1） ba次，将结果求和为生成的idx。并返回该元素。

then call the RANDOM(0,1) b-a times, sum the results as generated idx. and return the element.

但是，由于书中没有答案，因此我不知道这种方法是正确的还是最好的。如何证明返回每个元素的概率完全相同并且为 1 /（b-a + 1）吗？

However since there is no answer in the book, I don't know if this way is correct or the best. How to prove that the probability of returning each element is exactly same and is 1/(b-a+1) ?

什么是正确/更好的方法？

And what is the right/better way to do this?

推荐答案

如果您的RANDOM（0，1）返回0或1，每个概率为0.5，那么您可以生成位，直到您有足够的二进制数来表示数字（b-a + 1）。这会给您一个随机数，但范围会稍大一些：如果失败，您可以测试并重复。这样的东西（在Python中）。

If your RANDOM(0, 1) returns either 0 or 1, each with probability 0.5 then you can generate bits until you have enough to represent the number (b-a+1) in binary. This gives you a random number in a slightly too large range: you can test and repeat if it fails. Something like this (in Python).

def rand_pow2(bit_count):
    """Return a random number with the given number of bits."""
    result = 0
    for i in xrange(bit_count):
        result = 2 * result + RANDOM(0, 1)
    return result

def random_range(a, b):
    """Return a random integer in the closed interval [a, b]."""
    bit_count = math.ceil(math.log2(b - a + 1))
    while True:
        r = rand_pow2(bit_count)
        if a + r <= b:
            return a + r

这篇关于生成对Random（0，1）进行调用的Random（a，b）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！