在水库采样中重新使用随机数

Question

最近有人询问了另一个问题:给定一个未知长度列表,通过扫描它只返回一次随机项目

我知道你不应该,我只是不能把我的手指放在一个规范的解释为什么不.

看一下示例代码:

import random, sys

def rnd(): # a function that returns a random number each call
    return int(random.getrandbits(32))

class fixed: # a functor that returns the same random number each call
    def __init__(self):
        self._ret = rnd()
    def __call__(self):
        return self._ret

def sample(rnd,seq_size):
    choice = 0
    for item in xrange(1,seq_size):
        if (rnd() % (item+1)) == 0:
            choice = item
    return choice

dist = [0 for i in xrange(500)]
for i in xrange(1000):
    dist[sample(rnd,len(dist))] += 1
print "real",dist
print

dist = [0 for i in xrange(500)]
for i in xrange(1000):
    dist[sample(fixed(),len(dist))] += 1
print "reuse",dist

为每个项目生成一个新的随机数的适当油藏采样的选择很好地均匀分布,因为它应该是:

real [1, 3, 0, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 0, 0, 1, 3, 3, 4, 0, 2, 1, 2, 1, 1, 4, 0, 3, 1, 1, 2, 0, 0, 0, 1, 4, 6, 2, 3, 1, 1, 3, 2, 1, 3, 3, 1, 4, 1, 1, 2, 2, 5, 1, 2, 1, 0, 3, 1, 0, 2, 6, 1, 2, 2, 1, 1, 1, 1, 3, 2, 1, 5, 4, 0, 3, 3, 4, 0, 0, 2, 1, 3, 2, 3, 0, 2, 4, 6, 3, 0, 1, 3, 0, 2, 2, 4, 3, 2, 1, 2, 1, 2, 2, 1, 4, 2, 0, 0, 1, 1, 0, 1, 4, 2, 2, 2, 1, 0, 3, 1, 2, 1, 0, 2, 2, 1, 5, 1, 5, 3, 3, 1, 0, 2, 2, 0, 3, 2, 3, 0, 1, 1, 3, 0, 1, 2, 2, 0, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 3, 3, 1, 0, 1, 1, 0, 1, 3, 2, 1, 4, 3, 4, 1, 1, 1, 2, 1, 2, 0, 0, 0, 1, 1, 2, 6, 0, 1, 1, 0, 1, 0, 1, 2, 2, 3, 0, 1, 2, 2, 1, 0, 4, 2, 1, 2, 2, 0, 4, 4, 0, 3, 2, 2, 1, 2, 4, 1, 2, 1, 0, 2, 1, 1, 5, 1, 2, 2, 3, 2, 3, 0, 1, 2, 3, 2, 5, 2, 3, 0, 1, 1, 1, 1, 3, 4, 2, 4, 1, 2, 3, 2, 5, 2, 1, 0, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 2, 0, 4, 1, 1, 2, 3, 4, 3, 1, 2, 3, 3, 3, 2, 1, 2, 0, 0, 4, 3, 2, 2, 5, 5, 3, 3, 3, 1, 0, 1, 3, 1, 1, 2, 4, 3, 1, 4, 4, 2, 5, 0, 5, 4, 2, 1, 0, 4, 1, 3, 3, 2, 4, 2, 3, 3, 1, 3, 3, 4, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 2, 4, 0, 1, 3, 2, 2, 4, 2, 2, 3, 4, 5, 3, 2, 1, 2, 3, 2, 2, 2, 4, 4, 0, 1, 3, 3, 3, 4, 1, 2, 4, 0, 4, 0, 3, 2, 1, 1, 4, 2, 1, 0, 0, 0, 4, 2, 2, 1, 4, 3, 1, 1, 3, 2, 4, 3, 4, 2, 1, 1, 2, 2, 3, 3, 1, 2, 2, 1, 1, 2, 3, 1, 9, 1, 3, 4, 2, 4, 4, 0, 1, 0, 1, 0, 2, 1, 0, 1, 2, 3, 3, 6, 2, 2, 1, 2, 4, 3, 3, 3, 2, 1, 2, 1, 2, 8, 2, 3, 1, 5, 3, 0, 2, 1, 1, 4, 2, 2, 1, 2, 3, 2, 1, 0, 4, 3, 4, 3, 1, 3, 2, 3, 2, 2, 1, 0, 1, 2, 5, 3, 0, 3, 1, 2, 2, 2, 1, 0, 1, 4]

然而,当您为所有项目重复使用相同的随机数时,您会得到一个偏向于非常低数字的分布:

reuse [92, 50, 34, 19, 23, 16, 13, 9, 9, 9, 11, 10, 6, 7, 8, 5, 5, 6, 4, 2, 2, 3, 2, 3, 3, 6, 6, 1, 4, 3, 5, 2, 2, 1, 1, 2, 3, 4, 3, 4, 1, 3, 1, 0, 0, 1, 5, 3, 1, 2, 0, 2, 0, 1, 1, 6, 2, 0, 2, 2, 4, 2, 2, 0, 2, 2, 2, 0, 3, 0, 4, 1, 2, 1, 4, 2, 2, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 1, 3, 1, 0, 1, 2, 0, 4, 3, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 1, 1, 3, 0, 1, 1, 0, 2, 0, 1, 2, 0, 1, 1, 4, 1, 1, 1, 2, 1, 0, 1, 2, 0, 2, 1, 1, 2, 0, 1, 1, 0, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 4, 1, 0, 2, 0, 1, 2, 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 4, 1, 0, 2, 1, 0, 0, 2, 1, 1, 3, 3, 2, 0, 1, 0, 2, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 0, 3, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 4, 1, 0, 0, 2, 0, 1, 1, 0, 0, 3, 1, 3, 2, 2, 1, 3, 1, 2, 0, 1, 1, 3, 0, 3, 1, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 3, 1, 0, 2, 3, 1, 1, 0, 1, 3, 3, 1, 1, 1, 0, 2, 1, 1, 4, 1, 1, 1, 2, 0, 3, 1, 1, 0, 4, 1, 1, 0, 1, 3, 1, 0, 1, 1, 0, 3, 3, 0, 2, 4, 0, 1, 2, 1, 6, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 4, 2, 0, 1, 2, 0, 1, 4, 1, 2, 0, 5, 2, 2, 0, 6, 2, 2, 1, 3, 0, 3, 1, 1, 0, 3, 1, 4, 2, 0, 1, 0, 1, 2, 3, 1, 1, 3, 0, 0, 0, 1, 1, 4, 3, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 2, 1, 4, 5, 1, 1, 3, 0, 1, 1, 1, 3, 1, 1, 0, 3, 3, 1, 3, 0, 1, 0, 0, 1, 1, 3, 2, 1, 0, 3, 1, 1, 3, 1, 3, 1, 2, 2, 2, 0, 0, 5, 1, 3, 0, 1, 4, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 1, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 3, 3, 3, 2, 1, 2, 3, 3, 3, 1, 2, 2, 2, 4, 2, 1, 5, 2, 2, 0]

这里的数学是什么？为什么你不能重复使用相同的随机数？

Answer 1

编辑,回应评论:

油藏采样应该起作用的方式是:您希望从每个现有箱中精确选择正确比例的样本,以便以相同的概率组成一个额外的箱.在你的sample()循环中,假设你随机抽取了一个item箱子,你需要从概念中选择每个箱子中的样本1/(item + 1).

但是,fixed()选择决定和前一个bin号都取决于相同的固定32位数.这意味着从每个箱中取出样品的可能性将不均匀.

考虑在sample()循环的第三次迭代期间发生了什么.您有三个现有的箱(0,1和2),并且您想要在每个箱中挑选1/4的样本并将它们添加到新创建的箱3中.

请注意,fixed()bin 1 中的所有32位数字都是偶数(因为第一遍选择了所有可被2整除的数字),而bin 0中的所有数字都将是奇数(因为偶数被移动到bin 1).第二遍将所有可被3整除的数字移动到bin 2(到目前为止应该是OK,并且不会改变bin 0和1中的偶数/奇数除法).

第三遍然后将所有fixed()可被4整除的数字移动到bin 3.但是,这将从bin 1中选择一半的数字(因为所有偶数的一半可以被4整除),而且没有来自bin 0的数字(因为它们是都很奇怪).因此,即使新垃圾箱的预期尺寸应该是正确的,旧垃圾箱的预期尺寸也不再相同.

这就是如何fixed()产生不均匀的分布:如果该数字以可预测的方式取决于用于选择原始分档的数字,则可以违反通过选择随机数来选择每个分箱的精确分数的隐式假设.

随机数的基本属性是,从统计意义上说,每个样本必须独立地分布在前面的样本中.基于随机数的算法取决于该属性.

伪随机数发生器(PRNG)实际上并不是随机的; 如你所知,他们的结果实际上是一个固定的序列.PRNG结果是故意加扰的,因此它们就像大多数用途的实际随机数一样.但是,如果PRNG对于特定应用程序而言"弱",则PRNG的内部工作可以以奇怪的方式与应用程序的细节交互,以非常随机的结果.

通过重新使用相同的随机数,你在这里尝试的是建立一个糟糕的PRNG.实际结果取决于应用程序如何使用随机数的详细信息......

即使fixed()是故意破坏的PRNG,许多商业图书馆PRNG也"弱",并且最终可能会与某些应用程序发生类似的奇怪交互.实际上,"弱点"与应用程序相关 - 虽然有一些统计测试被广泛用于尝试揭示弱PRNG,但无法保证您的应用程序不会偶然发现甚至一些奇怪的相关性一个"强大的"PRNG.