algorithm - 如何使用最少的位生成任意范围内的无偏随机数

Question

因为鸽巢原理，不能随便用

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

生成无偏见、统一的结果。这answer一个类似的问题提供了一种解决方案，但就消耗的随机位而言，这是非常浪费的。

例如，如果源的随机范围很低，则必须从源生成第二个值的机会可能会很高。或者，使用更大的源范围本质上也是一种浪费。

虽然我确定可以得出最佳源范围大小，但这并没有解决可能有更好的算法而不是优化这个算法的问题。

[编辑] 我的想法已在答案中显示出来，以产生有偏见的结果。

我想到的一种方法是

1. 使用覆盖所需范围所需的最少位数。
2. 如果该值超出所需范围，则仅丢弃一位并再消耗一位。
3. 必要时重复。

Answer 1

消除偏差的常用方法是丢弃超出所需范围的数字。如前所述，这是浪费。可以通过从更多位开始并同时生成多个随机数来最大程度地减少浪费；您可以在输入和输出范围之间实现更好的匹配。

例如掷骰子。输出有 6 种可能性。天真的方法会为每个产生的随机数取 3 个随机位。第一个例子演示了鸽子洞问题。

def pigeon_die(total_bit_count):
    for i in xrange(total_bit_count // 3):
        bits = random.getrandbits(3)
        yield 1 + bits * 6 // 8

1 : 832855
2 : 417835
3 : 416012
4 : 833888
5 : 416189
6 : 416554
total 3333333
max/min 2.00448063998

第二个例子是常用的浪费方法。你可以看到它从相同数量的随机位生成更少的随机数，但偏差被消除了。

def wasteful_die(total_bit_count):
    for i in xrange(total_bit_count // 3):
        bits = random.getrandbits(3)
        if bits < 6:
            yield 1 + bits

1 : 417043
2 : 415812
3 : 417835
4 : 416012
5 : 416645
6 : 417243
total 2500590
max/min 1.00486517946

最后一个示例一次取 13 位，并从中生成 5 个随机数。这会产生比天真的方法更多的数字!

def optimized_die(total_bit_count):
    for i in xrange(total_bit_count // 13):
        bits = random.getrandbits(13)
        if bits < 6**5:
            for j in range(5):
                yield 1 + bits % 6
                bits //= 6

1 : 608776
2 : 608849
3 : 608387
4 : 608119
5 : 607855
6 : 608559
total 3650545
max/min 1.00163525841

13 位的选择是通过取 2 的幂的以 6 为底的对数并选择最接近整数的一位。

def waste_list(n):
    for bit in range(1, 31):
        potential = math.log(2**bit, n)
        count = int(potential)
        if count > 0:
            waste = potential - count
            yield waste, bit, count

for waste, bit, count in sorted(waste_list(6)):
    print bit, count, waste
    if bit == 3:
        break

13 5 0.029086494049
26 10 0.0581729880981
8 3 0.0948224578763
21 8 0.123908951925
3 1 0.160558421704

如您所见，有 4 个选择比简单的 3 位更好。