证明随机生成的数字是均匀分布的

Question

证明随机生成的数字是均匀分布的

我在接受采访时被问到这个问题.

给定一个随机数生成器生成[0,N)之间的数字,如何证明这个数是均匀分布的.

我不知道如何处理这个问题,有什么建议吗？

Answer 1

为了证明这一点,你需要知道正在使用的算法,并用图形术语表示所有状态的集合构成一个循环,没有子循环,并且模N的状态空间的基数为零,因此没有比其他更多/更少发生的状态集.例如,我们知道Mersenne Twister是均匀分布的,即使64位版本的周期长度为2 ¹⁹⁹³⁷ -1,并且在宇宙的生命周期内永远无法枚举.

否则,您使用统计检验来检验均匀性假设.统计数据无法证明结果,也未能证明这一假设.样本量越大,反驳假设的失败就越大,但它永远不会证明.(这种观点导致非统计学家/非科学家的沟通问题比我所知道的更多.)有许多统一性测试,包括卡方检验,Anderson-Darling和Kolmogorov-Smirnov等等.

所有的均匀性测试都会传递一系列值,如0,1,2,...,N-1,0,1,......所以均匀性不足以说明你有一个好的发电机.您还应该测试与测试的串行关联,例如间距测试,启动/运行,在平均值之上/之下运行,"生日"测试等等.

George Marsaglia在其职业生涯中创建了一套非常全面的均匀性和序列相关性测试,并于1995年出版,他开玩笑地称之为" Diehard测试 "(因为它是一个重型测试电池).

当Mersene Twister在64b中均匀分布时,你自相矛盾,并且周期长度为2 ^ {19937} -1,因为2 ^ 64不会除2 ^ {19937} -1.因此,鸽子洞原则中的一些数字比其他数字更常见.虽然偏差可能过于微不足道 - 但它在技术上仍然不统一. (10认同)
谢谢@MichaelAnderson,你是对的.MT19937%2 ^ 64留下2 ^ 64 -1的余数.所有零位的状态都是不可达的,因此为-1.如果你可以枚举整个状态空间,在将所有19937位向量投影到64位空间之后,你会发现有2 ^(19937-64)-1个零和2 ^(19937-64)的其他所有,所以严格来说它并不统一.实际上,在我们可以在有限时间内绘制的任何样本中都不会出现差异,并且在22 ^ 19873中的幅度为1,有效但不是数学上为零. (7认同)

Answer 2

Blu*_*n93 19

对于黑盒测试(您无法访问源代码),您无法证明它是均匀分布的(UD).但是,您可以执行统计测试以找出它是UD的可能性.多次运行生成器(比如N*X次),0到N之间的每个数字应该出现在X次左右.

这完全忽略了它是否是随机数,它只关注均匀性.但是,如果您要运行无限测试,它只能证明发生器是均匀分布的.最好的情况是,在第一次N*X迭代期间,您有一个发生器均匀的概率,但它很简单,易于实现.

@Heuster:问题不是询问RNG的随机性,而是询问它的分布,这是一个重要的区别. (22认同)

Answer 3

Ant*_*ima 9

没有办法证明它,因为发生器可能首先产生均匀分布,然后偏离到非均匀分布.

Answer 4

Old*_*ank 7

由于这是一次采访,真正的问题不是要证明统一分配,真正的问题是要为工作选择.我建议采用一种方法,快速决定面试官是否正在寻找有关高等数学的有趣讨论,或者正在测试你的实践思维.我的猜测是,面试官很有可能会寻找后者.一个好的面试答案可能是这样的:"这一切都取决于随机数发生器需要什么.如果它在音乐播放器上起到随机播放的作用,我会让它生成100个数字,检查平均值是否等于N/2接下来简要介绍一下这些数字,并且可以在这一点上得到满足.如果目的与加密有关,那将是一个不同的故事,我会开始做研究,但最终可能不会自己证明,而是依赖现有的,独立的证据".

归档时间：	11 年，4 月前
查看次数：	5903 次
最近记录：	5 年，11 月前