我这样做是为了测试 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 次迭代。这是您可以从标准库获得的最佳结果吗?

有帮助吗?

解决方案

生日悖论,或者说为什么 PRNG 产生重复项的频率比您想象的要高。


OP 的问题中有几个问题在起作用。其一是 生日悖论 如上所述,第二个是您所生成的内容的性质,它本身并不能保证给定的数字不会重复。

生日悖论适用于给定值在生成器期间可能多次出现的情况 - 因此在值样本中可能会出现重复。生日悖论的影响是,获得此类重复的实际可能性非常大,而且它们之间的平均周期比人们想象的要小。感知概率与实际概率之间的这种不一致使生日悖论成为一个很好的例子。 认知偏差, ,其中天真的直觉估计可能会大错特错。

伪随机数生成器 (PRNG) 快速入门

问题的第一部分是,您正在获取随机数生成器的公开值并将其转换为一个小得多的数字,因此可能值的空间减少了。虽然有些 伪随机数生成器 在此转换期间不要重复值,该转换将域更改为更小的域。较小的域会使“无重复”条件无效,因此您可以预期重复的可能性很大。

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

并非所有 PRNG 算法都具有此特征;有些可以在周期内重复给定值。在OP的问题中, 梅森扭转者 算法(用于Python的 随机的 module) 的周期非常长 - 远大于 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 位整数不可能表示足够的离散值以避免在如此长的周期内重复。在这种情况下,如果样本足够大,很可能会出现重复值,并且不可避免。

简而言之,生日悖论

这个问题最初被定义为房间里任意两个人生日相同的概率。关键是 任意两个 房间里的人可以共享生日。人们往往天真地将问题解释为房间里某人与特定个人同一天生日的概率,这是问题的根源 认知偏差 这常常导致人们低估概率。这是错误的假设 - 不需要匹配特定的个人,任何两个人都可以匹配。

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

任何两个个体之间发生匹配的概率远高于与特定个体匹配的概率,因为匹配不必是在特定日期。相反,您只需找到两个生日相同的人即可。从这张图(可以在该主题的维基百科页面上找到)中,我们可以看到,房间里只需要 23 个人,就有 50% 的机会找到两个匹配的人。

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

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

对于 100 个数字的序列,我们有 (100 * 99) / 2 = 4950对(参见 了解问题)可能匹配(即第一个可以与第二个、第三个等匹配,第二个可以与第三个、第四个等匹配。等等),所以数量 组合 可能匹配的不仅仅是 100 个。

计算概率 我们得到一个表达式 1 - (4500! / (4500**100 * (4500 - 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 个数字内发生的匹配。(也许有人可以验证这一点并发表评论,如果它是错误的)。由此我们可以看出,OP 观察到的匹配数字之间的游程长度似乎相当合理。

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

下面这个答案来自S。标记 一种获得有保证的唯一随机数集的方法。海报提到的技术采用一组数字(您提供的数字,这样您就可以使它们唯一)并将它们打乱为随机顺序。从打乱的数组中按顺序提取数字将得到一个保证不重复的伪随机数序列。

脚注:加密安全的 PRNG

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

其他提示

指责的Python之前,你应该刷了一些概率统计理论。通过阅读有关生日悖论

开始

顺便提及,在Python random模块使用梅森捻线 PRNG,这被认为非常好,有一个巨大的周期,进行了广泛的测试。所以,放心,你的好帮手是。

如果你不想但却难免重复一个,生成顺序排列并使用随机的。洗牌

作为一个答案Nimbuz的答案:

http://xkcd.com/221/

“替代文字”

真随机性绝对包括值的重复整个可能值的集合被耗尽之前。它不会是随机的,否则,你将能够预测多久的值不会重复。

如果你曾经滚动骰子,你一定得3个乱七八糟行经常...

这不是一个中继器。转发器是当你重复相同的序列。不只是一个数字。

您从一系列4500产生500 <= x <= 5000随机数。然后,您检查,看看是否为它之前已经生成的每一个号码。该生日问题告诉我们的概率就是两个那些数字来匹配给出n试行的范围d的。

您也可以反转公式计算你有多少个号码生成,直到生成一个重复的机会比50%多。在这种情况下,你有>50%迭代后发现重复号的79机会。

您定义了一个包含 4501 个值 (500-5000) 的随机空间,并且迭代了 4500 次。基本上可以保证您编写的测试中会发生碰撞。

换个角度思考一下:

  • 当结果数组为空时 P(dupe) = 0
  • 数组 P(dupe) 中的 1 个值 = 1/4500
  • 数组 P(dupe) 中的 2 个值 = 2/4500
  • ETC。

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

要创建真正测试随机函数能力的测试,请增加可能的随机值的范围(例如:500-500000) 您可能会也可能不会被骗。但平均而言,您会获得更多的迭代次数。

有关这个问题其他人,我用uuid.uuid4()和它的工作原理类似一个魅力。

有是生日悖论。考虑到这一点,你知道,你说的是要找到“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)
许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top