math - 在水库采样中重复使用随机数

Question

最近被问到另一个问题:Given an unknown length list, return a random item in it by scanning it only 1 time

我知道你不应该，我只是无法对为什么不进行规范的解释。



看示例代码:

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

编辑，回应评论:

水库采样的工作方式是:您希望从每个现有 bin 中选择正确比例的样本，以便以相同的概率组成一个额外的 bin。在您的 sample()循环，假设您随机采样了 item 之一bins，您需要从每个 bin 中以概率 1/(item + 1) 选择样本.

但是，与 fixed() , 选择决策和之前的 bin 编号都取决于相同的固定 32 位编号。这意味着从每个 bin 中移除样本的可能性将不均匀。

考虑在 sample() 的第三次迭代期间会发生什么环形。您有三个现有的 bin(0、1 和 2)，并且您希望在每个 bin 中选取 1/4 的样本并将它们添加到新创建的 bin 3。

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

第三遍然后移动所有 fixed()可以被 4 整除的数字进入 bin 3。但是，这将从 bin 1 中选择一半的数字(因为所有偶数的一半都可以被 4 整除)，并且没有 bin 0 中的数字(因为它们都是奇数)。因此，即使新 bin 的预期大小应该是正确的，旧 bin 的预期大小也不再相同。

就是这样fixed()生成不均匀分布:如果该数字以可预测的方式依赖于用于选择原始 bin 的数字，则违反了隐含假设，即您可以通过选择一个随机数来选择每个 bin 的确切分数。

在统计意义上，随机数的基本属性是每个样本必须独立于前面的样本分布。基于随机数的算法依赖于这个属性。

伪随机数生成器 (PRNG) 实际上不是随机的；如你所知，他们的结果实际上是一个固定的序列。 PRNG 结果被故意打乱，以便它们在大多数情况下表现得足够像实际的随机数。但是，如果 PRNG 对于特定应用程序“弱”，则 PRNG 的内部工作可以以奇怪的方式与应用程序的细节交互，从而产生非常非随机的结果。

您在这里尝试通过重新使用相同的随机数来构建错误的 PRNG。实际结果取决于应用程序如何使用随机数的详细信息......

即使 fixed()是一个故意破坏的 PRNG，许多商业图书馆 PRNG 是“弱”的，最终可能会与某些应用程序发生类似的奇怪交互。实际上，“弱点”是与应用程序相关的——虽然有广泛使用的统计测试试图暴露弱 PRNG，但不能保证您的应用程序不会偶然发现偶数的一些奇怪的相关性“强”PRNG。