随机几乎没有随意？

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的问题有几个问题在起作用。一个是上面提到的birthday paradox，第二个是你正在生成的东西的性质，这本身并不能保证给定的数字不会被重复。

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

关于伪随机数发生器（PRNG）的快速入门

问题的第一部分是您正在获取随机数生成器的公开值并将其转换为更小的数字，因此可能值的空间会减少。虽然一些pseudo-random number generators在其期间不重复值，但这种转换将域变为更小的域。较小的域使“无重复”条件无效，因此您可以预期重复的可能性很大。

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

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

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

• 良好的statistical properties意味着算法生成的数字均匀分布，没有数字出现的概率明显高于其他数字。不良的统计特性可能会在结果中产生不必要的偏差。
• 好的geometric properies意味着N个数字的集合不位于N维空间中的超平面上。差的几何特性会在仿真模型中产生虚假的相关性并扭曲结果。
• 很长一段时间意味着您可以在序列回绕到开始之前生成大量数字。如果模型需要大量迭代或必须从多个种子运行，那么典型LCG实现中可用的2 ^ 30左右的离散数可能是不够的。 MT19337算法具有非常长的周期 - 2 ^ 19337-1，或大约10 ^ 5821。相比之下，宇宙中的原子总数估计约为10 ^ 80。

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

生日悖论简而言之

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

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

从Wikipedia entry on the subject我们可以得到一个nice summary.在OP的问题中，我们有4,500个可能的'生日'，而不是365.对于给定数量的随机值（等于'人'）我们想知道任何两个相同的概率值出现在序列中。

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

对于100个数字的序列，我们有可能匹配的对（参见Understanding the Problem）（即第一个可以匹配第二个，第三个等，第二个可以匹配第三个，第四个等等，所以可能匹配的组合数量不仅仅是100。

从Calculating the Probability我们得到了的表达。下面的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获得一个独特的伪随机数序列

请参阅this answer below from S. Mark获取有保证的唯一随机数集的方法。海报所引用的技术采用一系列数字（您提供的数字，因此您可以使它们成为唯一的）并将它们随机排列。从混洗数组中依次绘制数字将为您提供一系列伪随机数，保证不会重复。

脚注：密码安全的PRNG

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

Answer 2

对于有这个问题的其他人，我使用了uuid.uuid4（），它就像一个魅力。

Answer 3

有生日悖论。考虑到这一点，你意识到你所说的是找到“764,3875,4290,4378,764”或类似的东西并不是随机的，因为该序列中的数字会重复。真正的方法是将序列相互比较。我写了一个python脚本来做到这一点。

79

Answer 4

在指责Python之前，你应该真正了解一些概率和统计理论。首先阅读有关birthday paradox的信息

顺便说一句，Python中的random模块使用Mersenne twister PRNG，它被认为是非常好的，具有巨大的周期并且经过了广泛的测试。所以请放心，你很好。

Answer 5

如果您不想重复，请生成顺序数组并使用qazxsw poi

Answer 6

作为Nimbuzz答案的答案：

random.shuffle

Answer 7

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

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

Answer 8

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

• http://xkcd.com/221/
• http://en.wikipedia.org/wiki/Mersenne_twister

Answer 9

那不是转发器。转发器是指您重复相同的序列。不只是一个数字。

Answer 10

您正在从http://docs.python.org/library/random.html范围生成4500随机数。然后检查每个数字是否已生成。 500 <= x <= 5000告诉我们，如果birthday problem尝试超出范围n，那么这两个数字匹配的概率是多少。

您还可以反转公式以计算在生成重复的可能性大于d之前必须生成的数量。在这种情况下，你有50%在>50%迭代后找到重复数字的机会。

Answer 11

您已经定义了4501个值（500-5000）的随机空间，并且您正在迭代4500次。您基本上保证在您编写的测试中发生碰撞。

以另一种方式思考：

• 当结果数组为空时P（重复）= 0
• 数组P中的1个值（重复）= 1/4500
• 数组P中的2个值（重复）= 2/4500
• 等等

因此，当您达到45/4500时，该插入有1％的可能性是重复，并且该概率随着每个后续插入而不断增加。

要创建一个真正测试随机函数能力的测试，请增加可能随机值的范围（例如：500-500000）您可能会，也可能不会获得欺骗。但是你平均会得到更多的迭代。