随机真的不随机吗？
我做了这个测试来检查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次循环才出现重复的数字。这是你从标准库中能得到的最佳结果吗？
11 个回答
生日悖论，或者说为什么伪随机数生成器（PRNG）产生重复值的频率比你想象的要高。
在提问者的问题中，有几个因素在起作用。一个是上面提到的生日悖论，另一个是你生成的内容的性质，这并不能保证某个特定的数字不会被重复。
生日悖论适用于在生成器的运行期间，某个值可能出现多次的情况——因此在一组值中可能会出现重复。生日悖论的效果是，实际上获得这种重复的可能性相当大，而它们之间的平均间隔比人们想象的要小。这种感知概率和实际概率之间的差异，使得生日悖论成为一个很好的认知偏差的例子，简单的直觉估计往往会大错特错。
伪随机数生成器（PRNG）的简要介绍
你问题的第一部分是，你正在将随机数生成器的输出值转化为一个更小的数字，这样可能的值的范围就被缩小了。虽然一些伪随机数生成器在其周期内不会重复值，但这种转换将范围变得更小。较小的范围使得“无重复”的条件失效，因此你可以预期会有相当大的重复可能性。
一些算法，比如线性同余伪随机数生成器（A'=AX|M）确实保证在整个周期内的唯一性。在LCG中，生成的值包含了累加器的整个状态，并且没有额外的状态被保存。这个生成器是确定性的，在周期内不能重复一个数字——任何给定的累加器值只能推导出一个可能的后续值。因此，每个值在生成器的周期内只能出现一次。然而，这种PRNG的周期相对较小——对于典型的LCG算法实现，大约是2^30，并且不可能大于不同值的数量。
并不是所有的PRNG算法都有这个特性；有些算法在周期内可以重复某个值。在提问者的问题中，使用的梅森旋转算法（在Python的random模块中使用）具有非常长的周期——远大于2^32。与线性同余PRNG不同，结果并不仅仅是前一个输出值的函数，因为累加器包含额外的状态。使用32位整数输出和约2^19937的周期，它不可能提供这样的保证。
梅森旋转算法是PRNG中一种流行的算法，因为它具有良好的统计和几何特性，以及非常长的周期——这些都是在模拟模型中使用PRNG时所期望的特性。
良好的统计特性意味着算法生成的数字是均匀分布的，没有数字出现的概率显著高于其他数字。差的统计特性可能会导致结果出现不必要的偏差。
良好的几何特性意味着N个数字的集合不会在N维空间中的超平面上。差的几何特性可能会在模拟模型中产生虚假的相关性，从而扭曲结果。
长周期意味着你可以生成很多数字，而不会在序列回绕到开始之前重复。如果一个模型需要大量的迭代，或者必须从多个种子开始运行，那么典型的LCG实现提供的约2^30个离散数字可能不够。MT19337算法的周期非常长——2^19337-1，约为10^5821。相比之下，宇宙中的原子总数估计约为10^80。
MT19337 PRNG生成的32位整数不可能表示足够多的离散值，以避免在如此长的周期内重复。在这种情况下，重复值的出现是很可能的，并且在样本足够大的情况下是不可避免的。
生日悖论的简要总结
这个问题最初定义为房间里任何两个人共享同一天生日的概率。关键点是任何两个人都可能共享同一天生日。人们往往天真地误解这个问题，以为是房间里某个人与特定个体共享生日的概率，这就是导致认知偏差的根源，常常使人们低估这个概率。这是一个错误的假设——匹配不需要是特定个体，任何两个个体都可能匹配。
任何两个个体之间发生匹配的概率远高于与特定个体匹配的概率，因为匹配不必是特定日期。实际上，你只需要找到两个共享同一天生日的个体。从这张图（可以在维基百科的相关页面找到），我们可以看到，只需23个人在房间里，就有50%的机会找到两个匹配的人。
从维基百科的相关条目中，我们可以得到一个不错的总结。在提问者的问题中，我们有4500个可能的“生日”，而不是365个。对于生成的随机值（相当于“人”）的给定数量，我们想知道在序列中出现任何两个相同值的概率。
计算生日悖论对提问者问题的可能影响
对于100个数字的序列，我们有
对（见理解问题）可能匹配的对（即第一个可以与第二个、第三个等匹配，第二个可以与第三个、第四个等匹配，依此类推），所以可能匹配的组合数量远不止100。
从计算概率中，我们得到一个表达式
。下面的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)
这产生了一个看起来合理的结果，p=0.669，表示在从4500个可能值中抽取的100个数字中出现匹配的概率。（也许有人可以验证一下，如果错了请留言）。从中我们可以看到，提问者观察到的匹配数字之间的间隔似乎是相当合理的。
附注：使用洗牌获得唯一的伪随机数序列
请参见S. Mark的这个回答，了解如何获得保证唯一的随机数字集合。帖子提到的技术是将一组数字（你提供的，这样可以确保它们是唯一的）洗牌成随机顺序。从洗牌后的数组中按顺序抽取数字将给你一个保证不重复的伪随机数字序列。
附注：密码安全的PRNG
MT算法并不是密码安全的，因为通过观察一系列数字相对容易推测生成器的内部状态。其他算法，如Blum Blum Shub，用于加密应用，但可能不适合模拟或一般随机数应用。密码安全的PRNG可能代价高昂（可能需要大数计算）或可能没有良好的几何特性。在这种类型的算法中，主要要求是通过观察一系列值推测生成器的内部状态是计算上不可行的。