从随机位生成随机数

Question

我有一个函数可以给我随机位 rand(0,1)，我想将其推广到 rand(a,b) ，使其在范围 a 到 b 中生成随机数。

我的想法是计算 b-a 的位数，然后将它们连接起来。我认为这会起作用，但它不会是均匀的。我觉得它会倾向于更大的数字，而不是更小的数字（接近 a 的数字）。并不是要直接回答问题，只是希望得到一些帮助。

编辑： 这是我目前的想法，只是不确定均匀性部分。

    pseudo code:
    function rand_range(a, b):
        n = b - a
        sum = a
        for i in range(n):
            sum += rand(0,1)

        return sum

- Igglyboo

---

你为什么认为结果数字不会均匀？ - arknave

我不是很确定，只是感觉如果范围偏向更高的值，我将不得不调用与范围相同数量的rand函数，因此范围越大，rand调用次数越多，我的随机数平均值就越高。这只是我的直觉，可能完全错误，我不知道。 - Igglyboo

rand(a,b) 返回介于整数 a 和 b 之间的整数吗？ - Nishanth

我认为真正的问题在于任意范围。如果a = 0且b = 2 ** n - 1，则没问题。但如何处理其他类型的范围似乎很棘手。 - FogleBird

是的，你获得的位数越多，平均值就会越高。实际上，如果随机位生成器是真正随机的，那么在大量样本中，平均值将非常接近于(b-a)/2。但是使用随机位生成器时，你生成00000和01101或任何其他5位序列的可能性是相同的。 - Jim Mischel

实际上，以这种方式生成的随机数将遵循二项分布，对于大的n，这将接近正态分布。 - Lutz Lehmann

Answer 1

对于均匀分布，您需要使用拒绝抽样：

假设您想生成4、5、6之间（包括4和6）的数字，则只需要2位。映射为：00 -> 4，01 -> 5，10 -> 6，11 -> reject。

pseudo code:
function rand_range(a, b):
    n = ceil(log2(b - a))
    m = b-a

    while(true)
        sum = a
        bits = []
        for i in range(n):
            bits.append(rand(0,1))
        sum += ToBase10(bits)
        if sum <= b:
            break

    return sum

- Nishanth

Answer 2

是的，它不会是统一的。

考虑三位的简单情况：

0+0+0  0
0+0+1  1
0+1+0  1
0+1+1  2
1+0+0  1
1+0+1  2
1+1+0  2
1+1+1  3

很明显，1和2的发生概率比0或3更高。

当位数增加时，分布会变得更加不均匀 - 0和最大值永远不可能出现超过一次，而中间的数字出现的次数最多。

对于随机分布，我能想到的最好方法是丢弃一些生成的数字。

将 b-a 四舍五入到最接近的2的幂减1，然后单独生成每个位，如果结果大于 b-a ，则重试。

因此，如果 b-a 为5，则向上取整为7，并生成涉及三个位的位以组成最大的数字7：

000  0
001  1
010  2
011  3
100  4
101  5
110  6
111  7

如果是6或7的情况，请将它们丢弃并重试。

可以通过使用字符串并连接0或1，最后转换为数字来完成此操作，或者在每个步骤中乘以2（以将所有位左移一位），然后加上0或1。

最后您仍需要将结果添加到a中。

- Bernhard Barker

---

为什么要丢弃而不是重新缩放？ - Alexandru Barbarosie

@AlexandruBarbarosie 是的，在最坏的情况下，你有大约50%的失败几率，但是失败两次是25%，三次是12.5%，等等。- 持续特别长时间的概率非常低，我肯定不希望我们一直处理最坏的情况。 - Bernhard Barker

@AlexandruBarbarosie，重新缩放只是重新分配误差，而不是消除它们。在这个简单的例子中尝试一下，你就会明白了。实际上，你从随机数生成器中获得的比特数要比你需要的多得多，因此必须丢弃的值的数量是微不足道的。 - Mark Ransom

@MarkRansom，你在重新缩放之前所说的错误是什么类型的？从我看到的情况来看，似乎没有任何错误，因此也就没有什么需要重新分配的。被丢弃的值高达50％，你可以在我的上面评论中看到。 - Alexandru Barbarosie

@AlexandruBarbarosie，错误在于分布的不均匀性；请参见我上面的链接以获取示例。这是一个众所周知的问题。至于被丢弃的值的数量，最坏情况下确实可以接近50％，但我的观点是你不太可能接近最坏情况。尽管在问题中给出的人为示例中，最坏情况更有可能发生。再次请参见我上面的链接。 - Mark Ransom

Answer 3

不仅结果不是随机的，而且你可能无法生成介于 (a,b) 之间的值，因为可能会发生 rand(0,1) 总是生成 0 的情况，从而产生一个超出你范围的数字（如果 a>0）。

这个问题存在的原因是，假设对于一个范围 (0,5)，0 只有一种表示方式，即 00000，而 1 则有五种表示方式： 10000、01000、00100、00010、00001。意识到这一点后，直接的解决方案应该是一个双射映射，因此最简单的解决方案是将你的 0 和 1 视为一个数字的位，因为任何数字在二进制中都有唯一的表示方法。

因此，伪代码如下：

const MAX_BITS = 9;
const MAX_VAL = 1023; 
fun rand_range(a,b){
    sum = 0;
    for i<MAX_BITS
        sum += pow(2,i)*rand(1,0)
    // rescale
    return (b-a) * sum/MAX_VAL + a

}

对于您的数据类型的 MAX_BITS 和 MAX_VAL 限制，可以选择将其作为 rand_range() 的输入范围，以确保每个输入都可以被正确地重新缩放。

- Alexandru Barbarosie

---

如果您重新缩放这些值，这是否真正均匀？ - Igglyboo

@lgglyboo 可能存在一点偏差，这完全取决于 MAX_VAL ，它应该是 >=(b-a)，但同时尽可能小，换句话说，应为第一个大于 b-a 的2的幂。在这种情况下，偏差可以忽略不计。 - Alexandru Barbarosie

Answer 4

我认为以下是更好的方法：

1. find log2(b-a) (number of bits to represent b-a)
2. generate log2(b-a) bits at random and construct decimal number from it.
3. if number is greater than (b-a) reject it and repeat 2.
4. else evaluate a + rand(b-a).

时间复杂度 :- 如果随机数生成器是真正的随机数，则需要两次迭代才能在范围b-a内获取随机数，因此 T(a,b) = log(b-a)

以下是Java实现代码 :-

public class RNG {

    public static int rand(int a,int b) {
        int bits = 0;
        int diff = b-a;
        Random r = new Random();
        while(diff>0) {
            bits++;
            diff = diff/2;
        }
        while(true) {
            int acc = 0;
            for(int i=0;i<bits;i++) {
                acc = 2*acc +  r.nextInt(2);
            }
            if(acc<=b-a) {
                return(a+acc);
            }

        }

    }


    public static void main(String[] args) {

        int a = 150;
        int b = 300;
        int freq[] = new int[b+1];
        for(int i=0;i<1000;i++) {
          int k = rand(a,b);
          freq[k]++;

        }
        System.out.println("freq:");
        for(int j=a;j<=b;j++) {
            System.out.println(j+" : "+freq[j]);
        }
    }

}

- Vikram Bhat

---

我唯一看到的问题是它不能保证真正完成。 - Igglyboo

它完成的概率非常低，但平均而言，它将在2次迭代中完成。 - Vikram Bhat

@Igglyboo 在 k 次迭代中不完成的概率是 (0.5)^k，即使进行 10 次迭代，该概率也小于 0.001。 - Vikram Bhat

Answer 5

在Python中，你可以通过继承random.Random类来获得完整的接口，包括randint(a, b)。

import random

class Random(random.Random):
    def random(self):
        """Get the next random number in the range [0.0, 1.0)."""
        return self.getrandbits(53) * 2**-53
    def getrandbits(self, k):
        """getrandbits(k) -> x.  Generates an int with k random bits."""
        return sum(rand(0, 1) << r for r in range(k))

    def seed(self, *args, **kwargs): # unused methods
        return None
    def getstate(self, *args, **kwargs):
        raise NotImplementedError
    def setstate(self, *args, **kwargs):
        raise NotImplementedError

x = rand(a,b) 可以表示为 r = Random(); x = r.randint(a, b)

优点是，如果正确定义了random()、getrandbits()方法，那么其余的代码已经经过测试，只需要正常工作。_randbelow()方法展示了如何使用这些基本操作来返回范围在[0,n)内的随机整数，这可以轻松扩展以定义randint(a, b)。

- jfs