我无法理解这个,哪个更随机?
rand()
OR:
rand() * rand()
我发现这是一个真正的脑筋急转弯,你能帮我吗?
编辑:
直觉上,我知道数学上的答案是它们是同样随机的,但我不禁想,如果你在将两者相乘时“运行随机数算法”两次,你会创建比只做一次更随机的东西。
我无法理解这个,哪个更随机?
rand()
OR:
rand() * rand()
我发现这是一个真正的脑筋急转弯,你能帮我吗?
编辑:
直觉上,我知道数学上的答案是它们是同样随机的,但我不禁想,如果你在将两者相乘时“运行随机数算法”两次,你会创建比只做一次更随机的东西。
当前回答
很容易证明两个随机数之和不一定是随机的。假设你有一个6面骰子。每个数字有1/6的机会出现。现在假设你有2个骰子,并将结果相加。这些总数的分布不是1/12。为什么?因为某些数字比其他数字更多。它们有多个分区。例如,数字2仅是1+1的和,但7可以由3+4、4+3或5+2等组成,因此它出现的机会更大。
因此,在本例中,对随机函数应用变换(在这种情况下为加法)不会使其更随机,或必然保持随机性。在上述骰子的情况下,分布偏向于7,因此随机性较小。
其他回答
使用实现原始多项式的线性反馈移位寄存器(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结果。
假设你有一个简单的硬币翻转问题,偶数被认为是正面,奇数被认为是反面。逻辑实现是:
rand() mod 2
在足够大的分布范围内,偶数的数量应该等于奇数的数量。
现在考虑一个小小的调整:
rand() * rand() mod 2
如果其中一个结果是偶数,那么整个结果应该是偶数。考虑4种可能的结果(偶*偶=偶,偶*奇=偶,奇*偶=偶数,奇*奇=奇数)。现在,在足够大的分布范围内,答案应该是75%的时间。
如果我是你,我敢打赌。
这条评论实际上更多的是解释为什么不应该基于您的方法实现自定义随机函数,而不是讨论随机性的数学财产。
公认的答案很好,但有另一种方法可以回答你的问题。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或1。
random()是(0,1)之一,但random(()*random(是(0,0,0,1)之一
你可以清楚地看到,在第二种情况下,获得0的机会绝不等于获得1的机会。
当我第一次发布这个答案时,我希望尽可能简短,以便阅读它的人一眼就能理解random()和random(*random)之间的区别,但我无法阻止自己回答最初的广告垃圾问题:
哪个更随机?
如果random()、random(()*random()、random()+random(()、(random(+1)/2或任何其他不会导致固定结果的组合具有相同的熵源(或者在伪随机生成器的情况下具有相同的初始状态),那么答案将是它们具有相同的随机性(差异在于它们的分布)。我们可以看到的一个完美的例子是Craps游戏。你得到的数字将是随机的(1,6)+随机的(6,6),我们都知道得到7的几率最高,但这并不意味着掷两个骰子的结果比掷一个骰子的效果更随机。
当你对随机数的组合会发生什么感到怀疑时,你可以利用你在统计理论中学到的经验。
在OP的情况下,他想知道X*X=X^2的结果是什么,其中X是沿统一[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/(2sqrt(y)
Y的分布如下:fY(Y)=fX(x(Y))|dx/dy |=1/(2 sqrt(Y)
我们还没有完成,我们必须得到Y的域,因为0<=x<1,0<=x^2<1因此Y在范围[0,1)内。如果你想检查Y的pdf是否真的是pdf,请在域中集成它:从0到1集成1/(2 sqrt(Y)),实际上,它会弹出为1。此外,请注意所述函数的形状看起来像belisarious发布的内容。
至于X1+X2+…+Xn,(其中Xi ~一致[0,1]),我们可以求助于中心极限定理,它适用于存在矩的任何分布。这就是Z检验存在的原因。
用于确定生成的pdf的其他技术包括雅可比变换(这是cdf技术的广义版本)和MGF技术。
编辑:作为澄清,请注意,我所说的是结果转换的分布,而不是其随机性。这实际上是一个单独的讨论。我实际上得到的是(rand())^2。对于rand()*rand((),它要复杂得多,无论如何,这不会导致任何类型的均匀分布。