我无法理解这个,哪个更随机?
rand()
OR:
rand() * rand()
我发现这是一个真正的脑筋急转弯,你能帮我吗?
编辑:
直觉上,我知道数学上的答案是它们是同样随机的,但我不禁想,如果你在将两者相乘时“运行随机数算法”两次,你会创建比只做一次更随机的东西。
我无法理解这个,哪个更随机?
rand()
OR:
rand() * rand()
我发现这是一个真正的脑筋急转弯,你能帮我吗?
编辑:
直觉上,我知道数学上的答案是它们是同样随机的,但我不禁想,如果你在将两者相乘时“运行随机数算法”两次,你会创建比只做一次更随机的东西。
当前回答
用更离散的数字来考虑可能会有所帮助。考虑一下要生成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之间的浮点数。
其他回答
我们可以通过使用Kolmogorov复杂性如果数字序列不能被压缩,那么它是我们在这个长度上可以达到的最随机的。。。我知道这种测量更多的是理论上的选择。。。
公认的答案很好,但有另一种方法可以回答你的问题。PachydermPuncher的答案已经采用了这种替代方法,我只是将其扩展一点。
思考信息理论最简单的方法是用最小的信息单位,一个比特。
在C标准库中,rand()返回一个0到rand_MAX范围内的整数,根据平台的不同,这个限制可能会有不同的定义。假设RAND_MAX恰好被定义为2^n-1,其中n是某个整数(这恰好是Microsoft实现中的情况,其中n为15)。然后我们可以说,一个好的实现将返回n位信息。
想象一下,rand()通过翻转硬币找到一位的值来构造随机数,然后重复直到它有一批15位。然后,这些位是独立的(任何一个位的值都不会影响同一批中其他位具有特定值的可能性)。因此,独立考虑的每个比特都像一个介于0和1之间的随机数,并且在该范围内“均匀分布”(可能是0和1)。
位的独立性确保了由一批位表示的数字也将在其范围内均匀分布。这很明显:如果有15位,允许的范围是0到2^15-1=32767。该范围内的每个数字都是唯一的位模式,例如:
010110101110010
并且如果比特是独立的,则没有模式比任何其他模式更可能发生。因此,该范围内所有可能的数字都有相同的可能性。反之亦然:如果rand()产生均匀分布的整数,那么这些数字是由独立的位组成的。
因此,将rand()看作是一条生产比特的生产线,它恰好以任意大小的批量提供比特。如果您不喜欢大小,请将批分成单独的位,然后按您喜欢的数量将它们放回一起(尽管如果您需要的特定范围不是2的幂,则需要缩小数字,目前最简单的方法是转换为浮点)。
回到你最初的建议,假设你想从15个批次到30个批次,向rand()请求第一个数字,将其移位15位,然后向其添加另一个rand(()。这是一种在不影响均匀分布的情况下组合对rand(的两个调用的方法。它的工作原理很简单,因为放置信息位的位置之间没有重叠。
这与通过乘以常数来“拉伸”rand()的范围非常不同。例如,如果你想将rand()的范围加倍,你可以乘以2,但现在你只能得到偶数,而不能得到奇数!这并不完全是一个平稳的分布,并且可能是一个严重的问题,具体取决于应用程序,例如,假设允许奇数/偶数下注的轮盘游戏。(从位的角度考虑,你可以直观地避免这个错误,因为你会意识到,乘以2等于将位向左移动一位(意义更大),然后用零填补空白。所以很明显,信息量是一样的——只是移动了一点。)
在浮点数应用程序中,数字范围中的这种差距是无法解决的,因为浮点数范围内在地具有根本无法表示的差距:在每两个可表示的浮点数之间的差距中存在无限数量的缺失实数!所以无论如何,我们必须学会与差距共处。
正如其他人所警告的那样,直觉在这一领域是有风险的,特别是因为数学家无法抵抗实数的诱惑,因为实数是一种充满了粗糙的无限和明显的悖论的可怕的令人困惑的东西。
但至少如果你从比特角度来看,你的直觉可能会让你走得更远。比特真的很容易——甚至计算机都能理解。
大多数这种分布发生是因为你必须限制或规范随机数。
我们将其标准化为全部为正,符合范围,甚至符合指定变量类型的内存大小限制。
换句话说,因为我们必须将随机调用限制在0和X之间(X是变量的大小限制),所以我们将有一组介于0和X的“随机”数。
现在,当你将随机数与另一个随机数相加时,总和将介于0和2X之间。。。这会使值偏离边缘点(当两个随机数在较大范围内时,将两个小数字相加和将两个大数字相加的概率非常小)。
想象一下这样一个例子,你有一个接近于零的数字,你将它与另一个随机数相加,它肯定会变大,远离0(这对于大数字是正确的,因为随机函数不可能两次返回两个大数字(接近于X的数字)。
现在,如果你用负数和正数设置随机方法(跨越零轴),情况将不再如此。
例如,假设RandomReal({-x,x},50000,.01),那么你会得到负数和正数的偶数分布,如果你将随机数相加,它们将保持其“随机性”。
现在我不确定Random()*Random(()从负到正的跨度会发生什么。。。这将是一个有趣的图表。。。但我现在得回去写代码了-P
只是一个澄清
尽管每当你试图发现伪随机变量或其乘法的随机性时,前面的答案都是正确的,但你应该知道,虽然random()通常是均匀分布的,但random(*random)却不是。
实例
这是通过伪随机变量模拟的均匀随机分布样本:
BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]
这是两个随机变量相乘后得到的分布:
BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] *
RandomReal[{0, 1}, 50000], {50000}], 0.01]]
所以,两者都是“随机”的,但它们的分布是非常不同的。
另一个例子
当2*Random()均匀分布时:
BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]
随机()+随机()不是!
BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] +
RandomReal[{0, 1}, 50000], {50000}], 0.01]]
中心极限定理
中心极限定理指出,随着项的增加,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个均匀分布的随机变量相加,可以看到从均匀分布到正态分布的道路:
Edit
几个学分
感谢Thomas Ahle在评论中指出,最后两张图片中显示的概率分布称为Irwin Hall分布
感谢Heike出色的撕裂功能
两者都不是“更随机”的。
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以下,尽管在原始序列中分布良好。由于两个分数相乘的影响,这些数字是有偏差的。由此产生的数字总是较小,因此更可能发生碰撞,尽管仍然无法预测。