随机几乎没有随意？

Question

我这样做是为了测试randint的随机性:

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

我尝试了大约10倍以上,我得到的最好结果是在转发器之前迭代了121次.这是您从标准库中获得的最佳结果吗？

Answer 1

生日悖论,或者为什么PRNG比你想象的更频繁地产生重复.

OP的问题有几个问题在起作用.一个是上面提到的生日悖论,第二个是你生成的东西的性质,这本身并不能保证给定的数字不会重复.

生日悖论适用于在生成器期间给定值可能出现多次的情况 - 因此重复可能发生在值的样本中.生日悖论的影响是,获得这样的重复的真实可能性是非常显着的,并且它们之间的平均周期小于原本可能想到的.在Percived和实际概率之间的这种不和使得生日悖论成为认知偏差的一个很好的例子,其中一个天真的直觉估计可能是非常错误的.

关于伪随机数发生器(PRNG)的快速入门

问题的第一部分是您正在获取随机数生成器的公开值并将其转换为更小的数字,因此可能值的空间会减少.尽管某些伪随机数生成器在其周期内不重复值,但此转换会将域更改为更小的值.较小的域使"无重复"条件无效,因此您可以预期重复的可能性很大.

一些算法,例如线性同余PRNG(A'=AX|M)确实保证了整个时期的唯一性.在LCG中,生成的值包含累加器的整个状态,并且不保持其他状态.发生器是确定性的,并且不能在该周期内重复一个数字 - 任何给定的累加器值只能表示一个可能的连续值.因此,每个值只能在发生器的周期内发生一次.然而,这种PRNG的周期相对较小 - 对于LCG算法的典型实现大约为2 ^ 30 - 并且不可能大于不同值的数量.

并非所有PRNG算法都具有此特性; 有些人可以在这段时间内重复给定的值.在OP的问题中,Mersenne Twister算法(在Python的随机模块中使用)具有很长的周期 - 远大于2 ^ 32.与线性同余PRNG不同,结果不仅仅是先前输出值的函数,因为累加器包含附加状态.对于32位整数输出和~2 ^ 19937的周期,它不可能提供这样的保证.

Mersenne Twister是一种流行的PRNG算法,因为它具有良好的统计和几何特性以及非常长的周期 - 在仿真模型上使用的PRNG具有理想的特性.

• 良好的统计特性意味着算法生成的数字均匀分布,没有数字出现的概率明显高于其他数字.不良的统计特性可能会在结果中产生不必要的偏差.

• 良好的几何特性意味着N个数字的集合不位于N维空间中的超平面上.差的几何特性会在仿真模型中产生虚假的相关性并扭曲结果.

• 很长一段时间意味着您可以在序列回绕到开始之前生成大量数字.如果模型需要大量迭代或必须从多个种子运行,那么典型LCG实现中可用的2 ^ 30左右的离散数可能是不够的.MT19337算法具有非常长的周期 - 2 ^ 19337-1,或大约10 ^ 5821.相比之下,宇宙中的原子总数估计约为10 ^ 80.

由MT19337 PRNG产生的32位整数不可能表示足够的离散值,以避免在如此大的时间段内重复.在这种情况下,重复值可能会发生,并且在样本足够大的情况下不可避免.

生日悖论简而言之

此问题最初定义为房间中任何两个人共享同一个生日的概率.关键是房间里的任何两个人都可以分享生日.人们倾向于天真地将问题误解为房间中某人与特定个体分享生日的可能性,这是认知偏差的来源,经常导致人们低估概率.这是不正确的假设 - 没有要求匹配对于特定的个人,任何两个人都可以匹配.

任何两个人之间发生比赛的概率远远高于与特定个人匹配的概率,因为比赛不必是特定日期.相反,你只需要找到两个共享同一个生日的人.从这个图表(可以在主题的维基百科页面上找到),我们可以看到我们只需要在房间里有23个人,因此有50%的机会以这种方式找到两个匹配.

从关于这个主题的维基百科条目,我们可以得到一个很好的总结. 在OP的问题中,我们有4,500个可能的"生日",而不是365.对于生成的给定数量的随机值(等于'人'),我们想知道序列中出现的任何两个相同值的概率.

计算生日悖论对OP问题的可能影响

对于100个数字的序列,我们有(100*99)/ 2 = 4950 http://mathurl.com/yc4cdsr.png对(请参阅了解问题)可能匹配(即第一个可能与第二个匹配,第三个等,第二个可以匹配第三个,第四个等等,所以可能匹配的组合数量不仅仅是100个.

从计算概率我们得到一个表达式1 - (4500!/(4500**100*(4500 - 100)!)http://mathurl.com/ybfweny.png.下面的Python代码片段很简单评估匹配对发生的概率.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

对于在从4500个可能值的总体中采样的100个数字内发生的匹配,这产生了p = 0.669的明显结果.(也许有人可以验证这一点并发表评论,如果它是错的).由此可以看出,OP观察到的匹配数之间的运行长度似乎非常合理.

脚注:使用shuffling获得一个独特的伪随机数序列

请参阅下面的S. Mark中的答案,了解获得有保证的唯一随机数集的方法.海报所引用的技术采用一系列数字(您提供的数字,因此您可以使它们成为唯一的)并将它们随机排列.从混洗数组中依次绘制数字将为您提供一系列伪随机数,保证不会重复.

脚注:密码安全的PRNG

MT算法不具有加密安全性,因为通过观察数字序列来推断生成器的内部状态相对容易.诸如Blum Blum Shub之类的其他算法用于加密应用,但可能不适用于模拟或一般随机数应用.密码安全的PRNG可能很昂贵(可能需要进行bignum计算)或者可能没有良好的几何特性.在这种类型的算法的情况下,主要要求是通过观察一系列值来推断发生器的内部状态在计算上是不可行的.

Answer 2

在指责Python之前,你应该真正了解一些概率和统计理论.首先阅读生日悖论

顺便说一句,randomPython中的模块使用了Mersenne twister PRNG,它被认为是非常好的,具有很长的时间并且经过了广泛的测试.所以请放心,你很好.

Answer 3

如果您不想要重复的,请生成顺序数组并使用random.shuffle

Answer 4

作为Nimbuz答案的答案:

http://xkcd.com/221/

Answer 5

真正的随机性肯定包括在整个可能值集耗尽之前重复值.否则它不会是随机的,因为您可以预测值不会重复多长时间.

如果你曾经掷过骰子,你肯定经常排成3个六分......

Answer 6

Python的随机实现实际上是最先进的:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

Answer 7

您正在4500从 range生成随机数500 <= x <= 5000。然后您检查每个数字是否之前已生成。在生日的问题告诉我们的概率就是两个那些数字匹配给定的n尝试了一系列的d。

您还可以反转公式来计算您必须生成多少个数字，直到生成重复的机会超过50%. 在这种情况下，您有>50%机会在79迭代后找到重复的数字。

Answer 8

那不是复读机。重复器是指重复相同的序列。不只是一个数字。