为什么这看起来不是随机的？

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%。 但数据并没有反映这一点。你知道吗

Answer 1

如果这是一个完全平坦的分布，你会期望平均值为100，这意味着每个人的猜测是不同的。但是，您知道这样的场景要比有重复的场景随机性小得多。在一个随机序列中你会得到重复的数字这一事实应该是令人欣慰的。你知道吗

你在这里所做的就是在非常小的集合中测量某种唯一性：ie1000次重复的实验，涉及100个随机值。如果您使用某种引导算法进行采样，您可能会更好地理解这一点。你知道吗

如果你有一点点的信心去衡量这个分布的话，也许你会有更多的信心去衡量这个分布。你知道吗

可能是伪随机发生器具有在与范围相同长度的序列内产生大约60-70%的非重复值的特性。但是，您需要使用更多的样本以及不同的随机种子进行实验。否则你的结果毫无意义。你知道吗

Answer 2

您的代码用于查找由100人（每个人猜测1到100之间的数字）所做的唯一猜测的平均数。 至于为什么会收敛到63左右。。。你应该把你的问题发到数学堆栈交换上。你知道吗

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

这个算法有一个可怕的复杂度，所以在这一点上我得到了一个内存错误。如您所见，随着人数和猜测范围的不断增加，唯一结果的百分比不断下降。你知道吗

用随机数重复测试：

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

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