生成随机(a,b)调用Random(0,1)

Question

有已知的Random(0,1)功能,它是一个统一的随机函数,这意味着,它将给出0或1,概率为50%.实现Random(a, b)只调用Random(0,1)

我到目前为止,将范围ab放在一个基于0的数组中,然后我有索引0,1,2 ... ba.

然后调用RANDOM(0,1)ba次,将结果总和为生成的idx.并返回元素.

但是由于书中没有答案,我不知道这种方式是正确的还是最好的.如何证明返回每个元素的概率完全相同1/(b-a+1)？

什么是正确/更好的方法来做到这一点？

Answer 1

如果您的RANDOM(0,1)返回0或1,每个概率为0.5,那么您可以生成位,直到您有足够的数字表示二进制数(b-a + 1).这为您提供了一个稍微过大的随机数:如果失败,您可以测试并重复.像这样的东西(在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