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

Question

因为鸽子洞原理，不能随便用

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

生成无偏的、统一的结果。This answer to a similar question提供了一种解决方案，但就消耗的随机位而言，这是非常浪费的。

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

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

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

我想到的一种方法是

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 位更好。