我无法理解这个,哪个更随机?

rand()

OR:

rand() * rand()

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


编辑:

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


当前回答

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

此外,如果没有仔细的构造,对随机值执行算术往往会导致较少的随机性。上面的一张海报引用了“rand()+rand(()+rand()…”(例如,k倍),这实际上会倾向于rand(返回值范围的平均值的k倍。(这是一种随机行走,步数与平均值对称。)

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

几乎所有对均匀随机输入的操作序列都是非均匀随机的,从而提高了可预测性。小心的话,我们可以克服这一特性,但这样就可以更容易地在实际需要的范围内生成一个均匀分布的随机数,而不是在算术上浪费时间。

其他回答

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

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

高偏差:sqrt(rand(范围^2))中间偏差峰值:(rand(range)+rand(range))/2低:偏差:范围-sqrt(rand(范围^2))

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

根据您的计算机体系结构,相乘数字最终会得到更小的解决方案范围。

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

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

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

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

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

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

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

只是一个澄清

尽管每当你试图发现伪随机变量或其乘法的随机性时,前面的答案都是正确的,但你应该知道,虽然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出色的撕裂功能

公认的答案很好,但有另一种方法可以回答你的问题。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等于将位向左移动一位(意义更大),然后用零填补空白。所以很明显,信息量是一样的——只是移动了一点。)

在浮点数应用程序中,数字范围中的这种差距是无法解决的,因为浮点数范围内在地具有根本无法表示的差距:在每两个可表示的浮点数之间的差距中存在无限数量的缺失实数!所以无论如何,我们必须学会与差距共处。

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

但至少如果你从比特角度来看,你的直觉可能会让你走得更远。比特真的很容易——甚至计算机都能理解。