生成随机（a，b）调用Random（0,1）

已知Random(0,1)函数，它是一个统一的随机函数，意思是它将给出0或1，概率为50％。执行Random(a, b)，只打电话Random(0,1)生成随机（a，b）调用Random（0,1）

我到目前为止是，把范围a-b在0基于数组，然后我有索引0,1,2 ... b-a。

然后调用RANDOM(0,1) b-a次，将结果作为生成的idx求和。并返回元素。

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

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

2011-12-10 Kent

可能的重复：[如何使用错误的生成器获取随机数]（http://stackoverflow.com/questions/7694933/how-to-get-random-numbers-with-the-wrong-generator） – PengOne

如果您的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

来源

2011-12-10 17:34:31

该解决方案通过在0 ..（2^N-1）上产生均匀分布，然后在超出所需范围以在2的非幂次上构造均匀分布时丢弃结果，从而产生均匀分布。您的解决方案构造二项分布。 – 2011-12-10 22:00:36

我明白了，你的方式是正确的。但结果行是'result + = RANDOM（0,1）* 2 ** i'对吗？ – Kent

是的，你可以用任何方式构造它，甚至可以导致+ = RANDOM（0，1）<< i。 – 2011-12-10 22:15:16

当你对随机数求和时，结果不再是均匀分布的 - 它看起来像一个高斯函数。查阅“大数法则”或阅读任何概率书/文章。就像翻动硬币100次，极不可能给出100个头。它可能会提供接近50个头和50个尾巴。

来源

2011-12-10 17:28:58 user949300

谢谢对于这些信息，我会搜索一些相关的文章阅读。 – Kent

你的愿望把范围0到a-b首先是正确的。但是，你不能像你所说的那样去做。 This question问清楚如何做到这一点，而the answer利用独特的分解。在的基础上编写m=a-b，记录最大需要的指数，比如e。然后，找到m的最大倍数，它小于2^e，称之为k。最后，用RANDOM(0,1)生成e号码，把它们作为基地2扩大一些号码x，如果x < k*m，返回x，否则再试一次。该计划看起来是这样的（简单的情况下，当m < 2^2）：

int RANDOM(0,m) { 

    // find largest power of n needed to write m in base 2 
    int e=0; 
    while (m > 2^e) { 
     ++e; 
    } 

    // find largest multiple of m less than 2^e 
    int k=1; 
    while (k*m < 2^2) { 
     ++k 
    } 
    --k; // we went one too far 

    while (1) { 
     // generate a random number in base 2 
     int x = 0; 
     for (int i=0; i<e; ++i) { 
      x = x*2 + RANDOM(0,1); 
     } 
     // if x isn't too large, return it x modulo m 
     if (x < m*k) 
      return (x % m); 
    } 
}

现在，你可以简单地添加到a结果a和b之间得到均匀分布的数字。

来源

2011-12-10 22:08:05 PengOne

分而治之可以帮助我们在范围[a，b]中使用随机（0,1）生成一个随机数。我们的想法是

如果a等于b，则随机数在该范围[A，B]
生成随机（0,1）
如果是以上的
查找中间0，在范围[一，MID]返回一个随机数使用递归
在范围否则返回的随机数[中间+ 1，b]上使用递归

工作“C”的代码如下。

int random(int a, int b) 
{ 
    if(a == b) 
     return a; 

    int c = RANDOM(0,1); // Returns 0 or 1 with probability 0.5 
    int mid = a + (b-a)/2; 

    if(c == 0) 
     return random(a, mid); 
    else 
     return random(mid + 1, b); 
}

来源

2014-07-12 04:12:45 Bilal

如果所有子范围的大小相等，只会在范围是2的幂时才会发生均匀分布。它在数学上等同于生成位，并且只有在拒绝位于范围之外的位集不属于2的幂。 – pjs

感谢@pjs指出！ – Bilal

如果您有以相同的概率返回{0, 1}一个RNG，你可以很容易地创建一个返回数字{0, 2^n}具有相同概率的RNG。

要做到这一点，你只需使用你原来的RNG n次，并得到一个二进制数字，如0010110111。每个数字（从0到2^n）是相同的可能性。

现在很容易得到一个RNG从a到b，其中b - a = 2^n。您只需创建一个先前的RNG并将其添加a即可。

现在最后一个问题是如果b-a不是2^n？

好东西，你必须做几乎没有。依靠rejection sampling技术。它告诉你，如果你有一个很大的集合，并且有一个RNG超过这个集合，并且需要从这个集合的一个子集中选择一个元素，你可以继续从一个更大的集合中选择一个元素并丢弃它们直到它们存在于你的子集中。

所以你所做的就是找到b-a并找到第012个这样的b-a <= 2^n。然后使用拒绝采样，直到您选取一个更小的元素b-a。比你刚刚添加a。

来源

2016-04-25 01:56:05

生成随机（a，b）调用Random（0,1）

回答

相关问题