为什么这似乎不是随机的？

Question

我正在运行一个过程，就像那些人们试图猜测0到100之间数字的游戏，有100个人在猜测。然后我计算了有多少不同的猜测。

import random
def averager(times):
    tests=[]
    for i in range(times):
        l=[]
        for i in range(0,100):
            l.append(random.randint(0,100))
        tests.append(len(set(l)))
    return (sum(tests))/len(tests)

print(averager(1000))

由于某种原因，不同猜测次数的平均值为63.6。

这是为什么呢？是python随机库存在缺陷吗？

在一个人们需要猜测1到10之间数字的场景中，

第一个人有100％的机会猜出以前未猜过的数字，

第二个人有90％的机会猜出以前未猜过的数字，

第三个人有80％的机会猜出以前未猜过的数字，

等等...

根据我的推理，猜测新数字的平均机会是55％。但数据并不反映这一点。

- David Greydanus

---

我假设你期望它更接近50？ - SethMMorton

还有，你为什么要做 set(l)？不同的人可能会猜到相同的数字。 - SethMMorton

不，这是你推理的缺陷。你期望的结果是什么，为什么？ - John La Rooy

先考虑一个更简单的情况。假设只有两个人，每个人可以猜测0或1，那么猜测列表将是[0,0]、[0,1]、[1,0]或[1,1]。那么不同猜测的期望数量是多少？ - DSM

你需要阅读一下“生日悖论”(Birthday Paradox)的相关知识。 - Mark Ransom

Answer 1

您的代码是用于查找100个人每次猜测1到100之间数字时所做的平均猜测次数。 至于为什么它会收敛于约63左右的数字...您应该将您的问题发布到数学Stack Exchange。

- twj

Answer 2

如果这是一个完全平坦的分布，你会期望平均值为100，意味着每个人的猜测都不同。然而，你知道这种情况比有重复的情况要少得多。在随机序列中出现重复数字的事实应该让人感到安慰。

在这里，你所做的只是在非常小的集合内测量某种独特性：即 100个随机值的实验重复1000次。如果你使用某种引导算法进行抽样，你可能会更好地理解这一点。

此外，如果你将重复次数扩大到数百万次，并且可能测量样本分布（而不仅仅是平均值），你会对自己得到的结果更有信心。

可能伪随机生成器具有一种特征，可以在与范围相同长度的序列中产生大约60-70％的非重复值。然而，你需要尝试更多的样本以及不同的随机种子。否则，你的结果就毫无意义了。

- paddy

Answer 3

我修改了你的代码，使其可以接受已生成的序列作为输入，而不是计算随机数：

def averager(seqs):
    tests = []
    for s in seqs:
        tests.append(len(set(s)))
    return float(sum(tests))/len(tests)

然后我编写了一个函数，用于返回任何给定人数和猜测范围的所有可能选择：

def combos(n, limit):
    return itertools.product(*((range(limit),) * n))

（Python 让我着迷的一点是，它非常容易将函数分解成简单的部分。）

然后我开始使用越来越大的数字进行测试：

for n in range(2,100):
    x = averager(combos(n, n))
    print n, x, x/n

2 1.5 0.75
3 2.11111111111 0.703703703704
4 2.734375 0.68359375
5 3.3616 0.67232
6 3.99061213992 0.66510202332
7 4.62058326038 0.660083322911
8 5.25112867355 0.656391084194

这个算法的复杂度非常高，所以在这一点上我遇到了MemoryError。正如您所看到的，随着人数和猜测范围的增加，唯一结果的百分比不断下降。

使用随机数字重复测试：

def rands(repeats, n, limit):
    for i in range(repeats):
        yield [random.randint(0, limit) for j in range(n)]

for n in range(10, 101, 10):
    x = averager(rands(10000, n, n))
    print n, x, x/n

10 6.7752 0.67752
20 13.0751 0.653755
30 19.4131 0.647103333333
40 25.7309 0.6432725
50 32.0471 0.640942
60 38.3333 0.638888333333
70 44.6882 0.638402857143
80 50.948 0.63685
90 57.3525 0.63725
100 63.6322 0.636322

正如您所看到的，结果与我们之前看到的以及您自己的观察一致。我相信一些组合数学可以解释这一切。

- Mark Ransom