随机几乎是随机的？

我做了这个来testingrandint的随机性： 

>>> 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次迭代。 这是从标准库中得到的最好结果吗？

生日悖论，或者为什么PRNGs比你想像的更频繁地产生重复。

OP的问题有几个问题。 一个是上面提到的生日悖论 ，第二个就是你所生成的生日的悖论 ，这本质上并不能保证给定的数字不会被重复。

生日悖论适用于在生成器期间给定值可能出现不止一次的情况，因此重复可能发生在一个样本值内。 生日悖论的影响是，得到这样的重复的真正可能性是相当大的，它们之间的平均周期小于本来可能想到的。 被感知的和实际的可能性之间的这种不一致使得生日悖论成为认知偏差的一个很好的例子，其中一个天真的直觉估计可能是疯狂的错误。

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

你的问题的第一部分是你正在接受一个随机数生成器的暴露值，并将其转换为一个更小的数字，所以可能值的空间减less了。 尽pipe一些伪随机数发生器在它们的周期内不重复值，但是这种转换将域更改为更小的值。 较小的域使'不重复'条件失效，因此可以预期重复的可能性很大。

一些algorithm，如线性同余PRNG （ A'=AX|M ）确保整个周期的唯一性。 在LCG中，生成的值包含累加器的整个状态，不保持附加状态。 发生器是确定性的，不能在该周期内重复一个数字 – 任何给定的累加器值都可能意味着只有一个可能的连续值。 因此，每个值只能在发生器的周期内发生一次。 然而，这样的PRNG的周期相对较小 – 对于LCGalgorithm的典型实现，约为2 ^ 30，并且不可能大于不同值的数目。

并不是所有的PRNGalgorithm都有这个特点。 有些可以在这段时间内重复给定的值。 在OP的问题中， Mersenne Twisteralgorithm（用在Python的随机模块中）有一个非常长的时间 – 远远大于2 ^ 32。 与线性同余PRNG不同，由于累加器包含附加状态，因此结果不完全是前一个输出值的函数。 用32位整数输出和〜2 ^ 19937的周期，它不可能提供这样的保证。

Mersenne Twister是一种stream行的PRNGalgorithm，因为它具有良好的统计特性和几何特性，并且具有非常长的周期 – 在仿真模型上使用的PRNG特性。

  • 良好的统计特性意味着algorithm产生的数字是均匀分布的，没有数字出现的概率显着高于其他数字。 差的统计特性会在结果中产生不必要的偏差。

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

  • 很长的一段时间意味着你可以在序列到达开始之前产生大量的数字。 如果一个模型需要大量的迭代，或者必须从多个种子运行，那么典型的LCG实现中可用的2 ^ 30左右的离散数字可能是不够的。 MT19337algorithm有一个非常长的时期 – 2 ^ 19337-1，或约10 ^ 5821。 相比之下，宇宙中的primefaces总数约为10 ^ 80。

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

生日悖论简而言之

这个问题最初定义为房间里任何两个人共享同一个生日的概率。 关键是房间里的任何两个人都可以分享生日。 人们往往天真地误解了这个问题，因为房间里的某个人和某个特定的人共享一个生日的可能性，这是认知偏差的来源，往往会导致人们低估这个概率。 这是不正确的假设 – 对于特定的个体没有任何要求，任何两个人都可以匹配。

This graph shows the probability of a shared birthday as number of people in the room increases. For 23 people the probability of two sharing a birthday is just over 50%.

任何两个个体之间发生匹配的概率比与特定个体匹配的概率要高得多，因为匹配不必是特定的date。 相反，你只需要find两个共享同一个生日的人。 从这个图表（可以在维基百科的主页上find），我们可以看到，我们只需要在房间里有23个人就有50％的机会find两个这样匹配的人。

从维基百科的这个话题我们可以得到一个很好的总结。 在OP的问题中，我们有4500个可能的“生日”，而不是365个。对于生成的任意给定数量的随机值（等同于“人”），我们想知道序列中出现任何两个相同值的概率。

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

对于100个数字的序列，我们有可能匹配的（ 100 * 99）/ 2 = 4950 http://mathurl.com/yc4cdsr.png对（参见理解问题; ）（即第一个可以匹配第二个，第三等，第二可以匹配第三，第四等等），所以可能匹配的组合的数量不仅仅是100。

从计算概率，我们得到1 – （4500！/（4500 ** 100 *（4500 – 100）！）的expression式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的合理预期结果。 （也许有人可以validation这一点，并发表评论，如果是错误的）。 由此我们可以看出，OP观察到的匹配数字之间的运行时间似乎是相当合理的。

脚注：使用混洗来获得伪随机数的唯一序列

从S.Mark得到一个保证唯一的一组随机数的方法。 海报所指的技术需要一系列数字（你提供的数据，所以你可以使它们独一无二），并随机sorting。 从混洗arrays中依次绘制数字会给出一系列保证不重复的伪随机数。

脚注：密码安全PRNGs

MTalgorithm不具有密码安全性，因为通过观察数字序列来推断发生器的内部状态相对容易。 其他algorithm（如Blum Blum Shub）用于密码应用，但可能不适用于仿真或一般的随机数应用。 密码安全PRNGs可能是昂贵的（可能需要计算）或可能不具有良好的几何特性。 在这种types的algorithm的情况下，主要的要求是通过观察一系列值来推断发生器的内部状态在计算上是不可行的。

在指责Python之前，你应该真正刷一些概率和统计理论。 从阅读有关生日悖论开始

顺便说一句，Python中的random模块使用梅森扭曲器 PRNG，这被认为是非常好的，有一个巨大的时期，并进行了广泛的testing。 所以，放心，你已经掌握好了。

如果你不想重复使用，那么生成顺序数组并使用random.shuffle

作为尼姆布斯答案的答案：

http://xkcd.com/221/

替代文字

真正的随机性绝对包括在整个可能值被耗尽之前重复的值。 否则就不是随机的，因为你可以预测一个值不会重复多久。

如果你掷骰子的话，你一定会得到3个六连胜。

Python的随机实现其实是相当先进的：

您从500 <= x <= 5000范围内生成4500随机数。 然后检查每个数字是否已经生成过。 生日问题告诉我们两个数字匹配的概率是多less？

您也可以反转公式来计算在生成副本的机会超过50%之前必须生成多less个数字。 在这种情况下，经过79次迭代后，你有>50%机会find重复的数字。

这不是一个中继器。 中继器是当你重复相同的序列 。 不只是一个号码。

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

想想另一种方式：

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

所以当你达到45/4500时，那个插入有1％的机会被重复，并且随着每个后续插入，这个概率会不断增加。

要创build一个真正testing随机函数的能力的testing，增加可能的随机值的范围（例如：500-500000）您可能会或可能不会得到一个愚蠢的。 但是平均来说，你会得到更多的迭代。

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

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

 from random import randint y = 21533456 uniques = [] for i in range(y): x1 = str(randint(500, 5000)) x2 = str(randint(500, 5000)) x3 = str(randint(500, 5000)) x4 = str(randint(500, 5000)) x = (x1 + ", " + x2 + ", " + x3 + ", " + x4) if x in uniques: raise Exception('We duped the sequence %d at iteration number %d' % (x, i)) else: raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y)) uniques.append(x)
Interesting Posts