理解"随机性"

Question

我无法理解这一点,这更随机？

rand()

要么

rand() * rand()

我发现它是一个真正的脑筋急转弯,你能帮助我吗？

编辑:

直观地,我知道数学答案将是它们同样随机,但我不禁想到,如果你将两者相乘的话"运行随机数算法"两次,你会创造一些比随机更随机的东西它一次.

Answer 1

只是一个澄清

虽然每当您尝试发现伪随机变量或其乘法的随机性时,前面的答案是正确的,但您应该知道,虽然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]]

Random()+ Random()不是!

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

中心极限定理

该中心极限定理指出的和随机的()趋于一个正态分布的条款增加.

只需四个学期:

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个均匀分布的随机变量相加来看到从均匀分布到正态分布的道路:

编辑

一些学分

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

感谢Heike的精彩撕裂[]功能

Answer 2

我猜两种方法都是随机的,虽然我的gutfeel会说它rand() * rand()不那么随机,因为它会播种更多的零.只要一个rand()就是0,总变0

Answer 3

两者都不是"更随机".

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, ...

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

Answer 4

过度简化说明了一点.

假设你的随机函数只输出0或1.

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

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

当我第一次发布这个答案时,我希望尽可能地保持这个答案,以便阅读它的人能够一目了然地了解random()和之间的区别random()*random(),但我不能让自己回答原来的广告问题:

哪个更随机？

在于random(),random()*random(),random()+random(),(random()+1)/2或任何其他组合不导致固定的结果具有熵的相同的源(或伪随机在发电机的情况相同的初始状态),答案将是它们是同样的随机(所不同的在他们的分布中).我们可以看到的一个完美的例子是Craps游戏.你获得的数字将是random(1,6)+random(1,6),我们都知道得到7的机率最高,但这并不意味着滚动两个骰子的结果或多或少是随机滚动的结果.

Answer 5

这是一个简单的答案.考虑垄断.你滚动两个六面骰子(或者对于那些喜欢游戏符号的人来说是2d6)并拿走它们的总和.最常见的结果是7,因为有6种可能的方法可以滚动7(1,6 2,5 3,4 4,3 5,2和6,1).而2只能在1,1上滚动.很容易看出滚动2d6与滚动1d12不同,即使范围相同(忽略你可以在1d12上得到1,这个点保持不变).将结果相乘而不是添加结果会使它们以类似的方式偏斜,大部分结果都会出现在范围的中间.如果你试图减少异常值,这是一个很好的方法,但它无助于均匀分布.

(And oddly enough it will increase low rolls as well. Assuming your randomness starts at 0, you'll see a spike at 0 because it will turn whatever the other roll is into a 0. Consider two random numbers between 0 and 1 (inclusive) and multiplying. If either result is a 0, the whole thing becomes a 0 no matter the other result. The only way to get a 1 out of it is for both rolls to be a 1. In practice this probably wouldn't matter but it makes for a weird graph.)

Answer 6

强制性xkcd ......

Answer 7

可能有助于以更离散的数字来考虑这一点.考虑想要生成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之间的浮点数.

Answer 8

关于"随机性"的一些事情是违反直觉的.

假设分布不均rand(),以下内容将为您提供非平坦分布:

• 高偏见: sqrt(rand(range^2))
• 在中间偏见高峰: (rand(range) + rand(range))/2
• 低:偏差: range - sqrt(rand(range^2))

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

Answer 9

大多数rand()实现都有一段时间.即,经过一些大量的调用后,序列重复出现.rand() * rand()重复的输出序列只有一半的时间,因此在这个意义上它"随机性较小".

而且,如果不仔细构造,对随机值执行算术往往会导致较少的随机性.上面的海报引用了" rand()+ rand()+ rand()......"(k次,比如说),实际上往往是k值的范围值的平均值rand()返回.(这是一个随意的步行,其步骤是对称的.)

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

几乎任何关于均匀随机输入的操作序列将是非均匀随机的,从而导致可预测性增加.小心,人们可以克服这个属性,但是在你真正想要的范围内生成一个均匀分布的随机数会更容易,而不是浪费算术时间.

Answer 10

"随机"与"更随机"有点像询问哪个零更零.

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

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

Answer 11

你正在寻找的概念是"熵",即一串比特无序的"程度".根据"最大熵"的概念,这个想法最容易理解.

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

最大熵与随机性的相关性源于这样一个事实:如果你选择一个"随机"数字,你几乎肯定会选择一个其位串接近于具有最大熵的数字,也就是说,它不能被压缩.这是我们对"随机"数字特征的最佳理解.

所以,如果你想使一个随机数出两个随机样本,这是"两次"为随机的,你会串连两个位串在一起.实际上,您只需将样本填充到双倍长度字的高低两半即可.

从更实际的角度来说,如果你发现自己背负着一个糟糕的兰德(),它有时可以帮助将几个样本合在一起---但是,如果真的坏了,即使这个程序也无济于事.

Answer 12

接受的答案非常可爱,但还有另一种方法可以回答你的问题.PachydermPuncher的答案已经采用了这种替代方法,我只想稍微扩展一下.

思考信息理论的最简单方法是根据最小的信息单位,一点一点.

在C标准库中,rand()返回0到0范围内的整数RAND_MAX,该限制可能根据平台的不同而定义.假如RAND_MAX碰巧被定义为2^n - 1其中n一些整数(这恰好是微软的实施中,在案件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与将位向左移位(更大的重要性)一个位置并用零填充间隙是相同的.显然,信息量是相同的 - 它只是移动了一点.)

数值范围中的这种间隙在浮点数应用中是无法控制的,因为浮点范围本身具有根本无法表示的间隙:在每两个可表示的浮动之间的间隙中存在无限数量的缺失实数点数!因此,无论如何,我们必须学会忍受差距.

正如其他人所警告的那样,直觉在这个领域是有风险的,特别是因为数学家无法抵抗实数的诱惑,实际数字是充满了无穷无尽和显而易见的悖论的极其令人困惑的东西.

但至少如果你认为它的位数,你的直觉可能会让你更进一步.比特非常简单 - 即使是计算机也可以理解它们.

Answer 13

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

假设你正在玩骰子游戏.你有一些完全公平,随机的骰子.如果在每次掷骰子之前,你首先将两个骰子放入一个碗中,摇晃它,随机挑选一个骰子,然后滚动那个骰子,那么模具辊是否会"更随机"？显然它没有任何区别.如果两个骰子都给出随机数,那么随机选择两个骰子中的一个将没有任何区别.无论哪种方式,你都会获得1到6之间的随机数,并且在足够数量的卷上均匀分布.

我想在现实生活中,如果您怀疑骰子可能不公平,这样的程序可能会有用.例如,如果骰子略微不平衡,那么往往比1/6的时间更频繁地给出1个,而另一个往往经常给出6个,然后在两者之间随机选择会倾向于模糊偏见.(虽然在这种情况下,1和6仍然会超过2,3,4和5.嗯,我想这取决于不平衡的性质.)

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

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

编辑

我不认为我可以将我对Monty Hall问题的回答写成评论,所以我会更新我的回答.

对于那些没有读过Belisarius链接的人来说,它的要点是:游戏节目选手可以选择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/3除以2 = 1/3的机会成为赢家,这并不比他原来的选秀好.当然我们已经知道最终结果,这只是以不同的方式计算它.

但现在主持人透露,这两个选择中的一个不是赢家.因此,在他没有选择的一个门的2/3的可能性中,他现在知道2个替代品中的1个不是它.另一个可能会也可能不会.所以他不再有2/3分开2.他打开门为零,关闭门为2/3.

Answer 14

考虑到你有一个简单的硬币翻转问题,即使被认为是头,奇数被认为是尾巴.逻辑实现是:

rand() mod 2

在足够大的分布上,偶数的数量应该等于奇数的数量.

现在考虑稍微调整一下:

rand() * rand() mod 2

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

如果我是你,我会打赌.

这个注释实际上更多地解释了为什么你不应该基于你的方法实现自定义随机函数,而不是讨论随机性的数学属性.

Answer 15

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

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

由于X~Uniform [0,1]它的cdf是:f _X(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的分布如下:f _Y(y)= f _X(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发布的.

至于诸如X ₁ + X ₂ + ... + X _{n之类的东西}(其中X _i ~Uniform [0,1])我们可以诉诸于中心极限定理,该定理适用于任何时刻存在的分布.这就是Z测试实际存在的原因.

用于确定得到的pdf的其他技术包括雅可比变换(这是cdf技术的通用版本)和MGF技术.

编辑:作为一个澄清,请注意我所说的结果转换的分布,而不是它的随机性.这实际上是为了单独讨论.我实际上得到的是(rand())^ 2.对于rand()*rand(),它要复杂得多,在任何情况下都不会导致任何种类的均匀分布.

Answer 16

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

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

核心原因 rand()更随机(假设它产生具有[0..1]范围的浮点随机数,这是非常常见的)是当你将两个FP数与尾数中的大量信息相乘时,你会得到最后一些信息丢失; 在IEEE双精度浮点数中没有足够的位来保存从[0..1]中随机选择的两个IEEE双精度浮点数中的所有信息,并且这些额外的信息位丢失.当然,这并不重要,因为你(可能)不会使用那些信息,但损失是真实的.您生成哪种分布(即,您使用哪种操作进行组合)并不重要.每个随机数都有(最多)52位的随机信息 - 那个'

大多数随机数的使用甚至没有使用随机源中实际可用的随机性.获得一个好的PRNG,不要太担心它.("善"的级别取决于你正在做什么;在进行蒙特卡罗模拟或密码学时你必须小心,否则你可以使用标准的PRNG,因为它通常要快得多.)

Answer 17

浮动随机数通常基于生成0到某个范围之间的整数的算法.因此,通过使用rand()*rand(),你实际上是在说int_rand()*int_rand()/ rand_max ^ 2 - 意味着你要排除任何素数/ rand_max ^ 2.

这显着改变了随机分布.

rand()在大多数系统上均匀分布,如果播种得当,很难预测.使用它,除非您有特殊的理由对其进行数学运算(即,将分布整形为所需的曲线).

Answer 18

乘以数字最终会在较小的解决方案范围内,具体取决于您的计算机体系结构.

如果您的计算机显示器显示16位数字rand(),则表示0.1234567890123乘以秒rand(),0.1234567890123,如果您重复实验10 ^ 14次,则会给出0.0152415,您肯定会找到更少的解决方案.