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

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()。您有三个现有的 bin（0、1 和 2），并且您希望在每个 bin 中选取 1/4 的样本并将它们添加到新创建的 bin 3 中。

请注意，bin 1 中的所有 32 位fixed()数字都是偶数（因为第一遍选择了所有可被 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。

Answer 2

如果您每次选择一个随机数，则流中的下一个项目有 1/CURRENTSIZE 的机会击败前一个选择的项目。

那么每个流一个随机数有什么问题呢？为什么它会扭曲分布？

我还没有找到完整的答案，但我有一个想法。

例如，让我们获取 100 个数字的流并选择一个随机数 0...999。现在我们从第二项的角度来看它。

什么时候赢？嗯，首先，它需要是N%2==0。所以它必须是偶数。此外，它也被流中每个 2 的倍数的每个其他倍数击败，4...6...8....10 等。但它例如在 106 上获胜。

计算它获胜的所有数字，0..999，我们得到 81 次！

现在让我们取 4，它需要是 N%4==0，并且它被 4 到 N (8...12....16) 的所有倍数击败。如果我们计算 4 能赢多少次，我们得到 45 次......！所以分配不公平。

如果您将随机数设为最大流的大小，则可以解决此问题，然后所有人都有 1 次获胜的机会，使其再次成为均匀分布。

例如，如果我们有一个 100 的流大小，我们选择一个随机数 0..199。我们知道前 100 个随机数都有恰好 1 个匹配，所以它们是均匀分布的。但是随机数 99...199 会发生什么？分布不均匀！例如，101 将仅给出 101%X==0 的 1。这适用于所有素数（101、103、107、109、113、127、131、137、139、149、151、157、163、 167、173、179、181、191、193、197、199）。所以第一个项目比其他项目有更大的获胜机会。

如果您为每个项目选择一个新的随机数，则情况并非如此，在这种情况下，可以添加机会。例如，当第一项出现时，它有机会获胜，即：

非（1/2 + 1/3 + 1/4 + 1/5 + 1/6（...等））

Answer 3

想一想：当你的固定数字真的很小时会发生什么？