在一个范围内生成无偏随机整数的最佳算法是什么？

Question

在这个StackOverflow问题中:

从范围生成随机整数

接受的答案表明以下公式用于生成给定min和之间的随机整数max,min并且max包含在范围内:

output = min + (rand() % (int)(max - min + 1))

但它也说

这仍然略微偏向较低的数字......也可以扩展它以消除偏差.

但这并没有解释为什么它偏向于较低的数字或如何消除偏见.因此,问题是:这是在(签名)范围内生成随机整数的最佳方法,而不依赖于任何花哨的东西,只是rand()功能,如果它是最优的,如何消除偏差？

编辑:

我刚刚测试了while@Joey建议的-loop算法对浮点外推:

static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0);
return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);

看看有多少均匀的"球""落入"并分布在许多"桶"中,一个用于浮点外推,另一个用于while-loop算法.但结果根据"球"(和"桶")的数量而变化,所以我不能轻易选择胜利者.可以在此Ideone页面找到工作代码.例如,对于10个桶和100个球,对于浮点外推,桶中理想概率的最大偏差小于while-loop算法(分别为0.04和0.05),但是有1000个球,while-loop 的最大偏差算法较小(0.024和0.011),对于10000个球,浮点外推再次做得更好(0.0034和0.0053),依此类推,没有太多的一致性.考虑到没有一种算法能够比其他算法更好地一致地产生均匀分布的可能性,使得我倾向于浮点外推,因为它似乎比while-loop算法执行得更快.那么选择浮点外推算法还是我的测试/结论不完全正确呢？

Answer 1

问题是你正在进行模运算.如果RAND_MAX你的模数可以被整除,那就不会有问题,但通常情况并非如此.作为一个非常人为的例子,假设RAND_MAX为11,你的模数为3.你将获得以下可能的随机数和以下结果:

0 1 2 3 4 5 6 7 8 9 10
0 1 2 0 1 2 0 1 2 0 1

如您所见,0和1比2更可能.

解决此问题的一个选择是拒绝采样:通过禁用上面的数字9和10,可以使得到的分布再次均匀.棘手的部分是弄清楚如何有效地做到这一点.一个非常好的例子(一说我花了两天的时间理解为什么它的工作原理),可以在Java的发现java.util.Random.nextInt(int)方法.

Java算法有点棘手的原因是它们避免了诸如乘法和除法之类的慢速操作.如果你不太在意,你也可以用天真的方式做到这一点:

int n = (int)(max - min + 1);
int remainder = RAND_MAX % n;
int x, output;
do {
  x = rand();
  output = x % n;
} while (x >= RAND_MAX - remainder);
return min + output;

编辑:纠正上面代码中的fencepost错误,现在它可以正常工作.我还创建了一个小样本程序(C#;为0到15之间的数字采用统一的PRNG,并通过各种方式从中为0到6之间的数字构建PRNG):

using System;

class Rand {
    static Random r = new Random();

    static int Rand16() {
        return r.Next(16);
    }

    static int Rand7Naive() {
        return Rand16() % 7;
    }

    static int Rand7Float() {
        return (int)(Rand16() / 16.0 * 7);
    }

    // corrected
    static int Rand7RejectionNaive() {
        int n = 7, remainder = 16 % n, x, output;
        do {
            x = Rand16();
            output = x % n;
        } while (x >= 16 - remainder);
        return output;
    }

    // adapted to fit the constraints of this example
    static int Rand7RejectionJava() {
        int n = 7, x, output;
        do {
            x = Rand16();
            output = x % n;
        } while (x - output + 6 > 15);
        return output;
    }

    static void Test(Func<int> rand, string name) {
        var buckets = new int[7];
        for (int i = 0; i < 10000000; i++) buckets[rand()]++;
        Console.WriteLine(name);
        for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]);
    }

    static void Main() {
        Test(Rand7Naive, "Rand7Naive");
        Test(Rand7Float, "Rand7Float");
        Test(Rand7RejectionNaive, "Rand7RejectionNaive");
    }
}

结果如下(粘贴到Excel中并添加单元格的条件着色,以便差异更明显):

现在我在上面的拒绝采样中修正了我的错误,它应该正常工作(在它偏向0之前).正如您所看到的,float方法根本不是完美的,它只是以不同方式分配偏差数字.

Answer 2

当随机数发生器(RAND_MAX + 1)的输出数量不能被所需范围(max-min + 1)整除时,会出现问题.由于从随机数到输出将存在一致的映射,因此某些输出将映射到比其他输出更多的随机数.这与映射的完成方式无关 - 你可以使用模数,除法,转换到浮点,无论你能想出什么伏都,基本问题仍然存在.

问题的严重程度非常小,而且要求不高的应用程序通常可以忽略它.范围越小,RAND_MAX越大,效果越不明显.

我拿了你的示例程序并稍微调整了一下.首先,我创建了一个特殊版本rand,只有0-255的范围,以更好地展示效果.我做了一些调整rangeRandomAlg2.最后,我将"球"的数量更改为1000000,以提高一致性.您可以在此处查看结果:http://ideone.com/4P4HY

请注意,浮点版本产生两个紧密分组的概率,接近0.101或0.097,两者之间没有任何内容.这是行动中的偏见.

我认为称这种"Java算法"有点误导 - 我敢肯定它比Java要老.

int rangeRandomAlg2 (int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while (x >= RAND_MAX - remainder);
    return min + x % n;
}

Answer 3

很容易理解为什么这个算法产生有偏差的样本.假设您的rand()函数从集合中返回统一的整数{0, 1, 2, 3, 4}.如果我想用它来生成随机位,0或者1我会说rand() % 2.套装{0, 2, 4}给了我0,而套装{1, 3}给了我1- 很明显我的样本0有60%,1有40%的可能性,根本不统一!

要解决此问题,您必须确保所需范围除以随机数生成器的范围,或者在随机数生成器返回的数字大于目标范围的最大可能倍数时丢弃结果.

在上面的示例中,目标范围是2,适合随机生成范围的最大倍数是4,因此我们丢弃不在集合中的任何样本{0, 1, 2, 3}并再次滚动.