理解“随机性”

Understanding "randomness"

提问人:Trufa 提问时间:10/18/2010 最后编辑:Arsen KhachaturyanTrufa 更新时间:7/5/2021 访问量:98424

问:

我无法解决这个问题,哪个更随机?

rand()

或者

rand() * rand()

我发现这是一个真正的脑筋急转弯,你能帮我吗?


编辑:

凭直觉,我知道数学上的答案是它们同样是随机的,但我不禁想,如果你“运行随机数算法”两次,当你将两者相乘时,你会创造出比只做一次更随机的东西。

数学 语言不可知 随机数

评论

164赞 dan04 10/18/2010
“更随机”是什么意思?
56赞 bnaul 10/18/2010
正如其他人所说,这两个量的分布不同。请参阅 mathworld.wolfram.com/UniformProductDistribution.html,了解您实际获得的分发。将其与单个均匀随机数进行比较,其中区间中的所有值的可能性相等,因此概率密度函数是一条水平直线。
45赞 detly 10/18/2010
我强烈建议阅读 Daily WTF 上的 Random Stupidity。特别是阅读此评论,他们分析了这个新随机数的输出。从中得到的信息是:对随机数的任意操作不一定会导致随机输出
51赞 detly 10/18/2010
另外:凭直觉,我知道数学上的答案是它们同样是随机的——如果你能仅凭直觉做数学,我们就不需要所有这些血腥的符号:P
94赞 Dr. belisarius 10/18/2010
不要把统计学和直觉带到同一个派对上......

答:

23赞 abelenky 10/18/2010 #1

“随机”与“更随机”有点像问哪个零更零。

在这种情况下,是 PRNG,因此不是完全随机的。(事实上,如果种子是已知的,这是可以预测的)。将其乘以另一个值使其不再或多或少随机。rand

真正的加密类型 RNG 实际上是随机的。通过任何类型的函数运行值都不能为其添加更多熵,并且很可能会消除熵,使其不再随机。

评论

3赞 Matthew Scharley 10/18/2010
请注意,这不是平方,因为每个调用都返回不同的值。不过,其他一切都是准确的。
2赞 abelenky 10/20/2010
@thenonhacker:根据你自己的描述,序列“1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10...”是随机的。它是均匀分布的,所有数字都有公平的机会。没有峰值或偏置。你真的认为这个序列是随机的吗???您需要更改您的定义。随机与输出无关,随机与用于创建输出的过程有关。
2赞 Kennet Belenky 10/20/2010
@CurtainDog:文本压缩保持熵水平不变,同时减少表达相同熵量所需的位数。
4赞 Kennet Belenky 10/20/2010
@thenonhacker,@abelenky:均匀的分发很容易。在随机数生成器中,重要的是随机数生成器状态下的位数。零态随机数生成器(例如 4、4、4、4、4 等)是完全可预测的。一次性垫的状态与其生成的值数量一样多,因此无法预测。两个 PNRG 的卷积将产生一个 PNRG,其熵位数与它们都包含的位数一样多,减去它们的协方差。
1赞 CurtainDog 10/20/2010
@Kennet - 谢谢,你已经为我解决了这个问题。@abelenky - 很酷,我现在明白了。
82赞 Matthew Scharley 10/18/2010 #2

两者都不是“更随机”。

rand()基于伪随机种子(通常基于当前时间,该时间总是在变化)生成一组可预测的数字。将序列中的两个连续数字相乘会生成一个不同但同样可预测的数字序列。

关于这是否会减少碰撞,答案是否定的。由于将两个数字相乘的影响,它实际上会增加碰撞,其中 .结果将是一个较小的部分,导致结果偏向频谱的低端。0 < n < 1

一些进一步的解释。在下文中,“不可预测”和“随机”是指某人根据以前的数字猜测下一个数字的能力,即。一个神谕。

给定种子,它生成以下值列表:x

0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...

rand()将生成上述列表,并将生成:rand() * rand()

0.18, 0.08, 0.08, 0.21, ...

这两种方法将始终为同一种子生成相同的数字列表,因此预言机同样可以预测。但是,如果你看一下将两个调用相乘的结果,你会发现它们都低于,尽管在原始序列中分布得不错。由于两个分数相乘的影响,这些数字是有偏差的。由此产生的数字总是较小,因此更有可能发生碰撞,尽管仍然同样不可预测。0.3

评论

9赞 Thilo 10/18/2010
+1 请注意,另一方面,它变得越来越“随机”(如果随机是指均匀分布)。rand()+rand()+rand()...
4赞 user359996 10/18/2010
@Thilo 不,它没有......?如果一个随机变量均匀分布在 (0,1) 范围内,并且您对变量进行采样 n 次,并取和,则它将均匀分布在 (0,n) 范围内。
5赞 Matthew Scharley 10/18/2010
@Trufa只是相信它实际上是随机的,不要试图“增强”它的随机性。不要多次设置种子。任何单个种子都是完全可以的,只要它本身是半随机的。我见过的许多实现都使用 UNIX 纪元作为种子,它每秒都在变化,并且每次变化都是唯一的。rand()
61赞 Liam 10/18/2010
@user359996 rand()+rand() 不是均匀分布的。加上两个骰子,你更有可能得到 7 而不是 2。
4赞 Matthew Scharley 10/20/2010
@thenonhacker 在我的帖子中查看我对随机性的定义。仅仅因为值倾向于频谱的一端并不能增加产生的确切值的可预测性,这就是我使用随机这个词时所指的。然后,我继续单独解决偏见问题。
1492赞 Dr. belisarius 10/18/2010 #3

只是一个澄清

尽管每当您尝试发现伪随机变量的随机性或其乘法时,前面的答案都是正确的,但您应该知道,虽然 Random() 通常是均匀分布的,但 Random() * Random() 不是。

这是一个通过伪随机变量模拟的均匀随机分布样本

Histogram of Random()

        BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]

虽然这是将两个随机变量相乘后得到的分布:

Histogram of Random() * Random()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] * 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

所以,两者都是“随机的”,但它们的分布却大不相同。

另一个例子

2 * Random() 均匀分布时:

Histogram of 2 * Random()

        BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]

Random() + Random() 不是!

Histogram of Random() + Random()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

中心极限定理

中心极限定理指出,随着项的增加,Random() 的总和趋于正态分布

只需四个术语,您就可以得到:

Histogram of Random() + Random() + Random() + Random()

BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
                   Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
                   {50000}],
         0.01]]  

在这里,您可以通过将 1、2、4、6、10 和 20 个均匀分布的随机变量相加来查看从均匀分布到正态分布的道路:

Histogram of different numbers of random variables added

编辑

几个学分

感谢 Thomas Ahle 在评论中指出,最后两张图像中显示的概率分布称为 Irwin-Hall 分布

感谢 Heike 的精彩 torn[] 功能

评论

42赞 Thilo 10/18/2010
+1.由于 OP 可能想要均匀分布,这应该是公认的答案。如果你这样做了,你最终会得到一个带有脂肪中心的“2d6”型分布。rand()+rand()
8赞 Trufa 10/18/2010
这很有趣,但它让我内心深处感到这是多么的反直觉。在我阅读了更多关于分发的内容后,我会更全面地了解。谢谢!
47赞 johncip 10/18/2010
@Trufa:也许这将有助于部分直觉,至少对于总和而言。想象一下,取一个轧制模具的“平均值”。现在想象一下取两个骰子的平均值。现在一百个。当你添加更多的骰子时,平均获得 1 或 6 的机会会发生什么变化?
3赞 Dr. belisarius 10/19/2010
@matt b 图表是 Mathematica 中的单行代码。代码是每个图形前面的粗体文本。Mathematica 是一门很棒的绘图语言!
5赞 Kennet Belenky 10/20/2010
@thenonhacker:是的,直方图确实表现出偏见,但它们并没有表现出非随机性。有偏见的随机数的随机性并不低。至于用户最初问题的正确答案是,“不要试图变得聪明,你只会让事情变得更糟”,这个答案确实传达了这一点。
26赞 staticsan 10/18/2010 #4

关于“随机性”的一些事情是违反直觉的。

假设 的平坦分布,以下将得到非平坦分布:rand()

  • 高偏置:sqrt(rand(range^2))
  • 偏置在中间达到峰值:(rand(range) + rand(range))/2
  • 低:偏置:range - sqrt(rand(range^2))

还有很多其他方法可以创建特定的偏置曲线。我做了一个快速测试,它得到了一个非常非线性的分布。rand() * rand()

24赞 Eric Towers 10/18/2010 #5

大多数 rand() 实现都有一些周期。也就是说,在大量调用之后,序列会重复。重复输出的顺序在一半的时间内,因此从这个意义上说,它是“不那么随机的”。rand() * rand()

此外,如果不仔细构造,对随机值执行算术运算往往会减少随机性。上面的海报引用了“+ + ...”(比如说,k 次),这实际上将趋向于 k 乘以值范围的平均值。(这是一个随机游走,步长与该平均值对称。rand()rand()rand()rand()

具体来说,假设您的 rand() 函数返回一个 [0,1] 范围内均匀分布的随机实数。(是的,此示例允许无限精度。这不会改变结果。你没有选择一种特定的语言,不同的语言可能会做不同的事情,但下面的分析适用于任何非反常的 rand() 实现。该产品也在 [0,1) 范围内,但不再均匀分布。事实上,乘积在区间 [0,1/4) 和区间 [1/4,1] 中的可能性一样大。更多的乘法将使结果进一步偏向零。这使得结果更可预测。从广义上讲,更可预测 == 随机性更低。rand() * rand()

几乎任何对均匀随机输入的操作序列都是非均匀随机的,从而提高了可预测性。只要小心,就可以克服这个属性,但是在你实际想要的范围内生成一个均匀分布的随机数会更容易,而不是浪费时间在算术上。

评论

0赞 Jared Updike 10/19/2010
我也有这样的想法,它会以两倍的速度经历随机生成器周期。
3赞 Jander 10/20/2010
如果序列长度是偶数,则只会将其切成两半。如果是奇数,你得到 r1*r2、r3*r4、...、rn*r1、r2*r3、r4*r5,总长度相同。
7赞 Fordi 10/18/2010 #6

通常,浮点随机数基于生成零到特定范围之间的整数的算法。因此,通过使用 rand()*rand(),您实际上是在说 int_rand()*int_rand()/rand_max^2 - 这意味着您排除了任何质数 / rand_max^2。

这显着改变了随机分布。

rand() 在大多数系统上是均匀分布的,如果正确播种,很难预测。除非你有特殊的理由对它进行数学运算(即,将分布调整为所需的曲线),否则请使用它。

评论

0赞 Joris Meys 10/19/2010
@belisarius :只有当 1 是随机过程的可能结果时,情况才会如此。
0赞 Floris 10/15/2013
在我找到这个答案之前,我不得不阅读很长一段路。你陈述了一个明显的问题:的结果空间(可能值的数量)小于的结果空间 - 因为它不包括质数。得到我的投票...rand()*rand()rand()
-2赞 dvhh 10/18/2010 #7

答案是视情况而定,希望 rand()*rand() 会比 rand() 更随机,但作为:

  • 这两个答案都取决于值的位大小
  • 在大多数情况下,您根据伪随机算法生成(该算法主要是取决于计算机时钟的数字生成器,而不是那么多随机性)。
  • 使你的代码更具可读性(而不是用这种咒语随意调用一些随机的巫毒教之神)。

好吧,如果您检查上面的任何这些,我建议您选择简单的“rand()”。 因为你的代码会更具可读性(不会问自己为什么要写这个,因为......井。。。超过 2 秒),易于维护(如果您想用super_rand替换 RAND 函数)。

如果你想要一个更好的随机数,我建议你从任何提供足够噪音(无线电静电)的来源流式传输它,然后一个简单的就足够了。rand()

10赞 Wil 10/18/2010 #8

当对随机数的组合会发生什么有疑问时,您可以使用您在统计理论中学到的经验教训。

在 OP 的情况下,他想知道 X*X = X^2 的结果是什么,其中 X 是沿 Uniform[0,1] 分布的随机变量。我们将使用 CDF 技术,因为它只是一个一对一的映射。

由于 X ~ Uniform[0,1] 它的 cdf 为:fX(x) = 1 我们想要变换 Y <- X^2,因此 y = x^2 求出反函数 x(y): sqrt(y) = x 这给了我们 x 作为 y 的函数。 接下来,求导数 dx/dy: d/dy (sqrt(y)) = 1/(2 sqrt(y))

Y 的分布如下: fY(y) = fX(x(y)) |dx/dy|= 1/(2 平方(y))

我们还没有完成,我们必须得到 Y 的域。 因为 0 <= x < 1, 0 <= x^2 < 1 所以 Y 在 [0, 1] 范围内。 如果要检查 Y 的 pdf 是否确实是 pdf,请在域上进行积分:将 1/(2 sqrt(y)) 从 0 集成到 1,实际上,它弹出为 1。另外,请注意,所述函数的形状看起来像 belisarious 发布的形状。

至于像 X 1 + X2 + ... + Xn 这样的东西,(其中 Xi ~ Uniform[0,1])我们可以求助于中心极限定理,它适用于任何存在矩的分布。这就是 Z 检验实际存在的原因。

用于确定生成的 pdf 的其他技术包括雅可比变换(这是 cdf 技术的广义版本)和 MGF 技术。

编辑:澄清一下,请注意,我说的是结果转换的分布,而不是它的随机性。这实际上是为了单独讨论。此外,我实际推导出的是 (rand())^2。对于 rand() * rand(),它要复杂得多,无论如何都不会导致任何形式的均匀分布。

69赞 valadil 10/18/2010 #9

这里有一个简单的答案。以大富翁为例。你掷两个六面骰子(或2d6,对于那些喜欢游戏符号的人来说)并计算它们的总和。最常见的结果是 7,因为有 6 种可能的方式可以掷出 7(1,6、2,5、3、4、4、3、5、2 和 6,1)。而 2 只能在 1,1 上滚动。很容易看出,滚动 2d6 与滚动 1d12 不同,即使范围相同(忽略您可以在 1d12 上获得 1,这一点保持不变)。将结果相乘而不是添加结果会以类似的方式扭曲它们,您的大多数结果都位于范围的中间。如果您尝试减少异常值,这是一个很好的方法,但它无助于均匀分布。

(奇怪的是,它也会增加低滚动。假设你的随机性从 0 开始,你会看到一个 0 处的峰值,因为它会把另一个掷骰子变成 0。考虑两个介于 0 和 1(含)之间的随机数并相乘。如果其中一个结果是 0,则无论另一个结果如何,整个事情都会变成 0。从中获得 1 的唯一方法是让两个掷骰子都是 1。在实践中,这可能无关紧要,但它会形成一个奇怪的图表。

评论

4赞 Daniel Earwicker 10/19/2010
“将你的结果相乘而不是将它们相加会以类似的方式扭曲它们,你的大部分结果都出现在范围的中间。” - 将这个断言与贝利撒留答案中的第二张图对照。
3赞 user479538 10/19/2010 #10

大多数这些分布的发生是因为您必须限制或归一化随机数。

我们将其归一化为全正数,适合某个范围,甚至适合指定变量类型的内存大小约束。

换句话说,因为我们必须将随机调用限制在 0 和 X 之间(X 是变量的大小限制),所以我们将有一组介于 0 和 X 之间的“随机”数字。

现在,当您将随机数与另一个随机数相加时,总和将在 0 到 2X 之间......这会使值偏离边缘点(当您在大范围内有两个随机数时,将两个小数相加和两个大数相加的概率非常小)。

想想你有一个接近零的数字,你把它与另一个随机数相加,它肯定会变得更大,远离 0(大数字也是如此,而且不太可能有两个大数字(接近 X 的数字)由 Random 函数返回两次。

现在,如果您要使用负数和正数(在零轴上相等地跨越)来设置随机方法,则情况将不再如此。

例如,假设你会得到一个负数的均匀分布,一个正数,如果你把随机数加在一起,它们将保持它们的“随机性”。RandomReal({-x, x}, 50000, .01)

现在我不确定从负到正的跨度会发生什么......这将是一个有趣的图表......但我现在必须回去写代码。9-3Random() * Random()

20赞 PachydermPuncher 10/19/2010 #11

你要找的概念是“熵”,即字符串无序的“程度” 的位。就“最大熵”的概念而言,这个想法最容易理解。

具有最大熵的比特串的近似定义是,它不能精确地用较短的比特串来表示(即使用某种算法来 将较小的字符串展开回原始字符串)。

最大熵与随机性的相关性源于以下事实: 如果你“随机”选择一个数字,你几乎肯定会选择一个数字 其位串接近最大熵,即不能压缩。 这是我们对“随机”数字特征的最佳理解。

所以,如果你想从两个随机样本中得出一个随机数,它是“两次”作为 随机,您将两个位字符串连接在一起。实际上,你只是 将样本塞入双倍长度单词的高半部分和低半部分。

从更实际的角度来看,如果你发现自己背负着一个蹩脚的 rand(),它可以 有时有助于将几个样本放在一起,---,如果它真的收支平衡 该程序无济于事。

评论

2赞 Gabriel Mitchell 10/19/2010
我从来没有想过通过 xor 生成随机数,但我想你可以把这个概念走得很远(en.wikipedia.org/wiki/Mersenne_twister)!谢谢你的回答。
1赞 CurtainDog 10/19/2010
我真的很难找到这个答案......最大熵不是被 stackoverflow.com/questions/3956478/understanding-randomness/ 中给出的答案打败了吗 stackoverflow.com/questions/3956478/understanding-randomness/? 在这些情况下,选择的数字无法压缩,但你很难称它们为随机数。
1赞 Daniel Earwicker 10/19/2010
+1 虽然公认的答案很漂亮,但这是我的最爱。当涉及到计算机时,总是以位思考 - 比试图从现实的角度思考要少得多,而且更相关。(我写了我的答案,然后注意到了这个,所以我的只不过是这个的扩展 - 也许添加了一些熵)。
1赞 Ishtar 10/19/2010
@CurtainDog xkcd 的随机数或二进制可以压缩到零位。解压缩程序将只返回“4”。没有比这更随机的了。dilbert 的问题在于,我们不知道是否可以将其压缩到零位(通过始终返回“九”来解压缩)。它也可能返回 8,然后我们可以压缩到 1 位。减压方式:0->9、1->8。我们将有 1 个随机位。40100
35赞 Juliet 10/19/2010 #12

用更离散的数字来思考这个问题可能会有所帮助。考虑想要生成 1 到 36 之间的随机数,因此您决定最简单的方法是掷出两个公平的 6 面骰子。你得到这个:

     1    2    3    4    5    6
  -----------------------------
1|   1    2    3    4    5    6
2|   2    4    6    8   10   12
3|   3    6    9   12   15   18
4|   4    8   12   16   20   24   
5|   5   10   15   20   25   30
6|   6   12   18   24   30   36

所以我们有 36 个数字,但并不是所有的数字都得到了公平的代表,有些根本没有出现。靠近中心对角线(左下角到右上角)的数字将以最高频率出现。

描述骰子之间不公平分配的相同原则同样适用于 0.0 和 1.0 之间的浮点数。

评论

3赞 Marjan Venema 10/19/2010
+1 用于更具体地显示随机数乘以随机数时分布的变化。矩阵的帮助不仅仅是单词,甚至是分布图。
152赞 3 revs, 3 users 60%Janco #13

我想这两种方法都是随机的,尽管我的直觉会说它不那么随机,因为它会播种更多的零。一旦 是 ,总计就变成了rand() * rand()rand()00

评论

18赞 Andreas Rejbrand 10/19/2010
我对使用这条带的所有答案的回答是:我喜欢幽默,但它必须是 CW!
4赞 Andreas Rejbrand 10/19/2010
@Andomar:不,不是。一点也不。你知道CW是什么吗?
17赞 Andomar 10/19/2010
@Andreas Rejbrand:CW 是一种武器,它通过否认回答问题的人的声誉来扼杀有趣的问题。看起来它被削弱了 meta.stackexchange.com/questions/392/...... (这也许就是为什么会出现这个有趣的问题!
11赞 Richard JP Le Guen 10/20/2010
@Andomar - 是的,CW 扼杀了有趣的问题,但是(来自常见问题解答)“声誉是衡量社区对你的信任程度的粗略衡量标准。如果你在回答中包含一张有趣的、受版权保护的图片,它会让我觉得你的答案很酷,我可能会认为也很酷,但这并不能让你更值得信任——因此,理想情况下,不应该授予任何代表。这是否意味着CW,或者它是否意味着人们不应该投票支持答案是另一个问题。
13赞 mykhal 10/20/2010
漫画中的“随机生成器”巨魔可能只是一个吟诵π的专家,刚刚达到费曼的地步。顺便说一句,π数字是随机的吗? :)
51赞 3 revscrowne #14

强制性的 xkcd ...
return 4; // chosen by fair dice roll, guaranteed to be random.

评论

7赞 Trufa 10/19/2010
当“随机”一词出现时,这总是最终出现:)我一直在等它!
9赞 Andreas Rejbrand 10/19/2010
我喜欢幽默,但一定是CW。
2赞 warren 10/20/2010
@Andreas Rejbrand - 为什么这个“幽默”的答案应该是 CW?
16赞 Andreas Rejbrand 10/20/2010
如果不是CW,则每次被点赞时,声誉都会被等待在答案的海报上(到目前为止有160次)。现在,声誉就像在学校的成绩一样——它应该是技术(在这种情况下是编程)熟练程度的证书。因此,人们不应该通过发布容易被点赞但不需要这种熟练程度的东西来获得声誉。此外,信誉分数还决定了用户的权限。例如,在 10 000 分时,用户可以访问 StackOverflow 的审核工具。
13赞 Jay 10/19/2010 #15

正如其他人所说,简单的简短回答是:不,它不是更随机的,但它确实改变了分布。

假设你正在玩骰子游戏。你有一些完全公平的随机骰子。如果在每次掷骰子之前,你先把两个骰子放在一个碗里,摇晃它,随机挑选一个骰子,然后掷出那个骰子,那么掷骰子会不会“更随机”?显然,这不会有什么区别。如果两个骰子都给出随机数,那么随机选择两个骰子中的一个将没有区别。无论哪种方式,您都会得到一个介于 1 到 6 之间的随机数,在足够数量的卷中均匀分布。

我想在现实生活中,如果您怀疑骰子可能不公平,这样的程序可能会有用。例如,如果骰子略微不平衡,那么一个人倾向于在1/6的时间内给1,而另一个人往往经常给6,那么在两者之间随机选择往往会掩盖偏见。(尽管在这种情况下,1 和 6 仍然会出现比 2、3、4 和 5 多。好吧,我想这取决于不平衡的性质。

随机性有很多定义。随机级数的一个定义是,它是由随机过程产生的一系列数字。根据这个定义,如果我掷出一个公平的骰子 5 次并得到数字 2、4、3、2、5,那就是一个随机序列。如果我再掷 5 次相同的公平骰子并得到 1、1、1、1、1,那么这也是一个随机序列。

一些海报指出,计算机上的随机函数不是真正的随机函数,而是伪随机的,如果你知道算法和种子,它们是完全可预测的。这是真的,但大多数时候完全无关紧要。如果我洗一副牌,然后一次翻一张,这应该是一个随机系列。如果有人偷看卡片,结果将是完全可预测的,但根据大多数随机性的定义,这不会降低随机性。如果该系列通过了随机性的统计测试,那么我偷看卡片的事实不会改变这一事实。在实践中,如果我们把大笔钱押在你猜下一张牌的能力上,那么你偷看牌的事实就高度相关了。如果我们使用该系列来模拟我们网站访问者的菜单选择以测试系统的性能,那么您偷看的事实将完全没有区别。(只要您不修改程序以利用此知识。

编辑

我不认为我能将我对蒙蒂霍尔问题的回应变成评论,所以我会更新我的答案。

对于那些没有读过贝利撒留链接的人来说,它的要点是:游戏节目参赛者可以选择 3 扇门。一个的背后是有价值的奖品,其他的背后是毫无价值的东西。他选择了#1号门。在透露它是赢家还是输家之前,主持人打开门 #3 以显示它是输家。然后,他让参赛者有机会切换到门 #2。参赛者应该这样做还是不这样做?

答案冒犯了很多人的直觉,是他应该改变。他最初选择的获胜者的概率是 1/3,另一扇门是获胜者的概率是 2/3。我最初的直觉,以及许多其他人的直觉,是转换不会有任何好处,赔率刚刚改为 50:50。

毕竟,假设有人在主持人打开丢失的门后就打开了电视。那个人会看到剩下的两扇紧闭的门。假设他知道游戏的本质,他会说每扇门都有 1/2 的机会隐藏奖品。观众的赔率怎么可能是 1/2 : 1/2,而参赛者的赔率是 1/3 : 2/3 ?

我真的不得不考虑这个问题,才能将我的直觉打成形状。要了解它,请理解当我们谈论此类问题的概率时,我们的意思是,您根据可用信息分配的概率。对于将奖品放在门 #1 后面的工作人员,奖品在门 #1 后面的概率是 100%,它位于其他两扇门后面的概率为零。

船员的赔率与参赛者的赔率不同,因为他知道参赛者不知道的事情,即他把奖品放在哪扇门后面。同样,参赛者的赔率与观众的赔率不同,因为他知道观众不知道的事情,即他最初选择了哪扇门。这并非无关紧要,因为主人选择打开哪扇门不是随机的。他不会打开参赛者选择的门,也不会打开隐藏奖品的门。如果这是同一扇门,那就给他留下了两个选择。如果它们是不同的门,则只剩下一扇门。

那么我们如何得出 1/3 和 2/3 呢?当参赛者最初选择一扇门时,他有 1/3 的机会选出获胜者。我认为这是显而易见的。这意味着有 2/3 的机会,其他一扇门是赢家。如果主持人在不提供任何额外信息的情况下给他换球的机会,就不会有任何收获。同样,这应该是显而易见的。但一种看待它的方式是说,他有 2/3 的机会通过转换获胜。但他有 2 个选择。所以每个人只有 2/3 除以 2 = 1/3 成为赢家的机会,这并不比他原来的选择好。当然,我们已经知道了最终结果,这只是以不同的方式计算它。

但现在主持人透露,这两个选择中的一个不是赢家。因此,在他没有选择的门是赢家的 2/3 机会中,他现在知道 2 个替代方案中的 1 个不是。另一个可能是也可能不是。所以他不再有 2/3 除以 2。他开着的门为零,关着的门是 2/3。

评论

0赞 Trufa 10/19/2010
很好的类比!我想这是一个非常好的通俗英语解释,与许多其他人不同,您实际上回答了我的问题:)
0赞 Dr. belisarius 10/19/2010
@Trufa @Jay 对事件的可能预知和随机性之间的混淆是非常普遍的。让我与你分享一个有趣的故事,关于一个女人解决了一个问题,并给学术界一些更好的数学家带来了一堆耻辱。他们后来说了很多后悔的话(比如“你犯了一个错误,但看看积极的一面。如果所有这些博士都错了,这个国家将陷入一些非常严重的麻烦。所以这是故事,与您的考虑有关......享受!marilynvossavant.com/articles/gameshow.html
0赞 Trufa 10/19/2010
@belisarius是的。我说二十一点21:)开个玩笑,我明白你的意思了!
0赞 Trufa 10/19/2010
@belisarius顺便说一句,我从来没有得到过那个,我现在再试一次!
0赞 Dr. belisarius 10/19/2010
@Trufa 这是一篇文章,展示了学术界对玛丽莲声明的反应 query.nytimes.com/gst/...... (非常非常有趣)
11赞 user479885 10/19/2010 #16

假设你有一个简单的抛硬币问题,其中偶数被认为是正面,奇数被认为是反面。逻辑实现为:

rand() mod 2

在足够大的分布中,偶数的数量应等于奇数的数量。

现在考虑一个细微的调整:

rand() * rand() mod 2

如果其中一个结果为偶数,则整个结果应为偶数。考虑 4 种可能的结果(偶数 * 偶数 = 偶数,偶数 * 奇数 = 偶数,奇数 * 偶数 = 偶数,奇数 * 奇数 = 奇数)。现在,在足够大的分布中,答案应该是 75% 的时间。

如果我是你,我敢打赌。

这个评论实际上更像是解释为什么你不应该基于你的方法实现一个自定义随机函数,而不是对随机性的数学性质的讨论。

评论

1赞 Donal Fellows 10/19/2010
小心! 可能不是很随机;这实际上取决于低位的随机性,而一些 PRNG 在这方面不是很好。(当然,在某些语言中,你会得到一个浮点结果,所以你根本不能这样做......rand()%2rand()
7赞 Huub 10/19/2010 #17

乘以数字最终会得到一个较小的解决方案范围,具体取决于您的计算机体系结构。

如果您的计算机显示屏显示 16 位数字,则为 0.1234567890123 乘以一秒 0.1234567890123 会得到 0.0152415 如果你重复实验 10^14 次,你肯定会找到更少的解决方案。rand()rand()

9赞 Donal Fellows 10/19/2010 #18

这并不完全明显,但通常比 .重要的是,对于大多数用途来说,这实际上并不是很重要。rand()rand()*rand()

但首先,它们会产生不同的分布。如果这是你想要的,这不是问题,但这确实很重要。如果你需要一个特定的分布,那么就忽略整个“哪个更随机”的问题。那么为什么更随机呢?rand()

为什么更随机(假设它产生范围为 [0..1],这很常见的浮点随机数)的核心是,当您将两个 FP 数与尾数中的大量信息相乘时,您会得到一些信息丢失;IEEE双精度浮点数中没有足够的位来保存从[0..1]中均匀随机选择的两个IEEE双精度浮点数中的所有信息,并且这些额外的信息位会丢失。当然,这并不重要,因为你(可能)不会使用这些信息,但损失是真实的。生成哪个发行版(即,使用哪个操作进行组合)也并不重要。这些随机数中的每一个(最多)有 52 位随机信息——这就是 IEEE 双精度可以容纳的量——如果你将两个或多个合并为一个,你仍然被限制在最多 52 位的随机信息。rand()

随机数的大多数用法甚至没有使用随机源中实际可用的随机性。获得一个好的PRNG,不要太担心。(“善良”的程度取决于你用它做什么;在进行蒙特卡罗模拟或密码学时,你必须小心,但除此之外,你可能可以使用标准的PRNG,因为这通常要快得多。

评论

1赞 Donal Fellows 10/19/2010
这个答案确实需要与贝利撒留的宏伟答案一起阅读;它们涵盖了问题的不同方面。
14赞 Daniel Earwicker 10/19/2010 #19

公认的答案很可爱,但还有另一种方法可以回答你的问题。PachydermPuncher 的答案已经采用了这种替代方法,我只是要稍微扩展一下。

思考信息论的最简单方法是从最小的信息单位,即一位。

在 C 标准库中,返回 0 到 范围内的整数,该限制的定义可能因平台而异。假设恰好被定义为 where 是某个整数(这恰好是 Microsoft 实现中的情况,其中为 15)。然后我们会说一个好的实现会返回一些信息。rand()RAND_MAXRAND_MAX2^n - 1nnn

想象一下,通过掷硬币找到一位比特的值,然后重复直到它有一批 15 位来构造随机数。那么这些位是独立的(任何一个位的值都不会影响同一批次中其他位具有一定值的可能性)。因此,独立考虑的每个位都像一个介于 0 和 1(含 0 和 1)之间的随机数,并且在该范围内“均匀分布”(很可能是 0 和 1)。rand()

位的独立性确保了由位批次表示的数字也将均匀分布在其范围内。这在直觉上是显而易见的:如果有 15 位,则允许的范围是 0 到 = 32767。该范围内的每个数字都是唯一的位模式,例如:2^15 - 1

010110101110010

如果这些位是独立的,那么没有一种模式比任何其他模式更有可能发生。因此,该范围内所有可能的数字都具有同等的可能性。所以反之亦然:如果产生均匀分布的整数,那么这些数字是由独立的位组成的。rand()

因此,可以将其视为制造钻头的生产线,而钻头恰好可以批量供应任意尺寸的钻头。如果你不喜欢这个大小,把批次分解成单独的位,然后把它们以你喜欢的任何数量放回一起(尽管如果你需要一个不是2的幂的特定范围,你需要缩小你的数字,到目前为止,最简单的方法是转换为浮点)。rand()

回到你最初的建议,假设你想从15个批次到30个批次,要求第一个数字,将其位移15位,然后添加另一个数字。这是一种在不干扰均匀分布的情况下组合两个调用的方法。它之所以有效,仅仅是因为放置信息位的位置之间没有重叠。rand()rand()rand()

这与通过乘以常数来“拉伸”范围非常不同。例如,如果你想将范围加倍,你可以乘以二 - 但现在你只会得到偶数,永远不会得到奇数!这并不完全是一个平滑的分布,并且可能是一个严重的问题,具体取决于应用程序,例如,据说允许奇数/偶数投注的轮盘赌游戏。(通过从位的角度思考,你可以直观地避免这个错误,因为你会意识到乘以二与将位向左移动(意义更大)一位并用零填补空白是一样的。所以很明显,信息量是一样的——它只是移动了一点。rand()rand()

在浮点数应用中,无法解决数字范围中的这种差距,因为浮点范围本身就存在根本无法表示的间隙:在每两个可表示的浮点数之间的间隙中存在无限数量的缺失实数!因此,无论如何,我们都必须学会忍受差距。

正如其他人所警告的那样,直觉在这个领域是有风险的,特别是因为数学家无法抗拒实数的诱惑,实数是充满粗糙的无穷大和明显的悖论的可怕令人困惑的东西。

但至少如果你认为它是比特,你的直觉可能会让你走得更远。比特真的很容易 - 即使是计算机也可以理解它们。

评论

3赞 Donal Fellows 10/20/2010
+1:实际上,任何两个IEEE双精度浮点数之间缺少的数字比整个(数学)整数中的数字还要多。
80赞 Alin Purcaru 10/21/2010 #20

过于简单化来说明一个观点。

假设您的随机函数仅输出 或 。01

random()是 之一,但 是其中之一(0,1)random()*random()(0,0,0,1)

您可以清楚地看到,在第二种情况下获得 a 的机会绝不等同于 获得 .01


当我第一次发布这个答案时,我想让它尽可能简短,以便阅读它的人一眼就能理解 和 之间的区别,但我无法阻止自己回答最初的广告垃圾问题:random()random()*random()

哪个更随机?

由于 、 、 或任何其他不会导致固定结果的组合具有相同的熵源(或在伪随机生成器的情况下具有相同的初始状态),答案是它们同样随机(区别在于它们的分布)。我们可以看的一个完美例子是掷骰子游戏。你得到的数字将是,我们都知道得到 7 的机会最高,但这并不意味着掷两个骰子的结果比掷一个骰子的结果或多或少是随机的。random()random()*random()random()+random()(random()+1)/2random(1,6)+random(1,6)

评论

0赞 Jens Roland 3/2/2011
+1 将一些非常棘手的东西浓缩成“在不同的分布中同样随机”。非常优雅。
3赞 Jens Roland 3/2/2011
所以从技术上讲,(random()*0+9) 同样是随机的,因为它从 1 元素集中随机返回一个值:[9]。 Dilbert 卡通是对的。
2赞 Alin Purcaru 3/2/2011
@Jens罗兰,“任何其他不会导致固定结果的组合”;)。999999 <i>probably</i> 不是随机生成的,可以计算随机生成的几率。
-1赞 Loki 6/2/2011 #21

好的,所以我将尝试添加一些值来补充其他答案,说您正在创建和使用随机数生成器。

随机数生成器是具有多种特性的设备(在非常一般的意义上),可以对其进行修改以适应目的。其中一些(来自我)是:

  • 熵:如香农熵
  • 分布:统计分布(泊松分布、正态分布等)
  • 类型:数字的来源(算法、自然事件、组合等)和应用的算法。
  • 效率:执行的快速性或复杂性。
  • 模式:周期性、序列、运行等。
  • 可能还有更多......

在这里的大多数答案中,分布是主要的兴趣点,但通过混合和匹配函数和参数,您可以创建生成随机数的新方法,这些随机数将具有不同的特征,其中一些特征的评估乍一看可能并不明显。

0赞 johnny 6/2/2011 #22

使用实现基元多项式的线性反馈移位寄存器 (LFSR)。

结果将是一个 2^n 个伪随机数的序列,即在序列中没有重复,其中 n 是 LFSR 中的位数......导致均匀分布。

http://en.wikipedia.org/wiki/Linear_feedback_shift_register http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

使用基于计算机时钟的微秒的“随机”种子,或者可能是文件系统中一些不断变化的数据的 md5 结果的子集。

例如,32 位 LFSR 将从给定种子开始按顺序生成 2^32 个唯一数字(没有 2 个相同)。 顺序将始终采用相同的顺序,但对于不同的种子,起点(显然)会有所不同。 因此,如果播种之间可能重复的顺序不是问题,这可能是一个不错的选择。

我使用 128 位 LFSR 在硬件模拟器中使用种子生成随机测试,种子是不断变化的系统数据的 md5 结果。

2赞 Tom 6/3/2011 #23
  1. 没有比这更随机的东西了。它要么是随机的,要么是非随机的。随机意味着“难以预测”。这并不意味着不确定。如果 random() 是随机的,则 random() 和 random() * random() 都是相同的随机。就随机性而言,分布是无关紧要的。如果出现不均匀分布,则仅意味着某些值比其他值更有可能;它们仍然是不可预测的。

  2. 由于涉及伪随机性,因此数字具有很大的确定性。然而,在概率模型和模拟中,伪随机性通常就足够了。众所周知,使伪随机数生成器变得复杂只会使分析变得困难。它不太可能提高随机性;它通常会导致它无法通过统计测试。

  3. 随机数的所需属性很重要:可重复性和再现性、统计随机性、(通常)均匀分布和大周期是少数。

  4. 关于随机数的变换:正如有人所说,两个或多个均匀分布的总和导致正态分布。这就是加性中心极限定理。无论源发行版如何,只要所有发行版都是独立且相同的,它就适用。乘中心极限定理表示两个或多个独立且同分布的随机变量的乘积是对数正态的。其他人创建的图形看起来是指数级的,但它实际上是对数正态的。所以 random() * random() 是对数正态分布的(尽管它可能不是独立的,因为数字是从同一个流中提取的)。这在某些应用中可能是可取的。但是,通常最好生成一个随机数并将其转换为对数正态分布数。Random() * random() 可能难以分析。

有关更多信息,请参阅我在 www.performorama.org 上的书。这本书正在建设中,但相关材料在那里。请注意,章节和章节编号可能会随时间而变化。第 8 章(概率论)——第 8.3.1 和 8.3.3 节,第 10 章(随机数)。

-1赞 sashang 9/26/2011 #24

很容易证明两个随机数的总和不一定是随机的。想象一下,你有一个 6 面的骰子和卷子。每个数字都有 1/6 的出现机会。现在假设你有 2 个骰子并对结果求和。这些款项的分配不是1/12。为什么?因为某些数字比其他数字出现得更多。它们有多个分区。例如,数字 2 只是 1+1 的总和,但 7 可以由 3+4 或 4+3 或 5+2 等组成......所以它有更大的机会出现。

因此,对随机函数应用变换(在这种情况下为加法)不会使其更具随机性,也不一定保留随机性。在上面的骰子的情况下,分布偏向于 7,因此随机性较低。

1赞 HamoriZ 5/25/2012 #25

我们可以通过使用 Kolmogorov 复杂度来比较两个关于随机性的数字数组 如果数字序列不能压缩,那么它是我们在这个长度下可以达到的最随机的...... 我知道这种类型的测量更像是一种理论上的选择......

-1赞 Fabian Bigler 5/18/2013 #26

正如其他人已经指出的那样,这个问题很难回答,因为我们每个人的脑海中都有自己的随机性图景

这就是为什么,我强烈建议您花一些时间通读本网站,以更好地了解随机性:

回到真正的问题。 这个术语没有或多或少的随机性:

两者都只是随机出现

在这两种情况下 - 只是 rand() 或 rand() * rand() - 情况是一样的: 在几十亿个数字之后,序列将重复(!)对于观察者来说,这似乎是随机的,因为他不知道整个序列,但计算机没有真正的随机源——所以他也不能产生随机性。

例如:天气是随机的吗?我们没有足够的传感器或知识来确定天气是否随机。

1赞 John S. 1/16/2016 #27

实际上,当你考虑它时,它的随机性不如.原因如下。rand() * rand()rand()

从本质上讲,奇数的数量与偶数相同。说 0.04325 是奇数,比如 0.388 是偶数,0.4 是偶数,0.15 是奇数,

这意味着它有相同的机会成为偶数或奇数小数rand()

另一方面,它的赔率是否有所不同。 比方说:rand() * rand()

double a = rand();
double b = rand();
double c = a * b;

a两者都有 50% 的概率是偶数或奇数。知道这一点b

  • 偶数 * 偶数 = 偶数
  • 偶数 * 奇数 = 偶数
  • 奇数 * 奇数 = 奇数
  • 奇数 * 偶数 = 偶数

意味着有 75% 的几率是偶数,而只有 25% 的几率是奇数,这使得 的值比 更可预测,因此随机性更低。crand() * rand()rand()

评论

0赞 Teepeemm 1/16/2016
rand()通常给出一个介于 0 和 1 之间的数字。谈论它是偶数还是奇数有意义吗?
1赞 Teepeemm 1/17/2016
实际上,这表明这种方法存在一个根本缺陷:将两个双精度的 53 位相乘将得到大约 100 位的结果。但是这些位的后半部分将被丢弃。因此,当你把两个双精度值和 1 作为它们的最低有效位时,你不能说他们产品的最低有效位。0.2*0.2=0.04
0赞 David Schwartz 10/8/2016
或者,换一种说法,您已经假设对 的分布有意义的“偶数”和“奇数”的定义与对 的分布有意义的“偶数”和“奇数”的定义相同。如果不是这种情况,则此参数将失败。整数是这样,但这些不是整数。rand()rand()*rand()
0赞 2 revsSalman A #28

假设它之间返回一个数字,很明显,这将偏向于 0。这是因为乘以 之间的数字将得到小于 的数字。以下是 10000 多个随机数的分布:rand()[0, 1)rand() * rand()x[0, 1)x

google.charts.load("current", { packages: ["corechart"] });
google.charts.setOnLoadCallback(drawChart);

function drawChart() {
  var i;
  var randomNumbers = [];
  for (i = 0; i < 10000; i++) {
    randomNumbers.push(Math.random() * Math.random());
  }
  var chart = new google.visualization.Histogram(document.getElementById("chart-1"));
  var data = new google.visualization.DataTable();
  data.addColumn("number", "Value");
  randomNumbers.forEach(function(randomNumber) {
    data.addRow([randomNumber]);
  });
  chart.draw(data, {
    title: randomNumbers.length + " rand() * rand() values between [0, 1)",
    legend: { position: "none" }
  });
}
<script src="https://www.gstatic.com/charts/loader.js"></script>

<div id="chart-1" style="height: 500px">Generating chart...</div>

如果返回一个整数,则有以下分布。请注意奇数值与偶数值的数量:rand()[x, y]

google.charts.load("current", { packages: ["corechart"] });
google.charts.setOnLoadCallback(drawChart);
document.querySelector("#draw-chart").addEventListener("click", drawChart);

function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function drawChart() {
  var min = Number(document.querySelector("#rand-min").value);
  var max = Number(document.querySelector("#rand-max").value);
  if (min >= max) {
    return;
  }
  var i;
  var randomNumbers = [];
  for (i = 0; i < 10000; i++) {
    randomNumbers.push(randomInt(min, max) * randomInt(min, max));
  }
  var chart = new google.visualization.Histogram(document.getElementById("chart-1"));
  var data = new google.visualization.DataTable();
  data.addColumn("number", "Value");
  randomNumbers.forEach(function(randomNumber) {
    data.addRow([randomNumber]);
  });
  chart.draw(data, {
    title: randomNumbers.length + " rand() * rand() values between [" + min + ", " + max + "]",
    legend: { position: "none" },
    histogram: { bucketSize: 1 }
  });
}
<script src="https://www.gstatic.com/charts/loader.js"></script>

<input type="number" id="rand-min" value="0" min="0" max="10">
<input type="number" id="rand-max" value="9" min="0" max="10">
<input type="button" id="draw-chart" value="Apply">

<div id="chart-1" style="height: 500px">Generating chart...</div>