证明一个随机生成的数字是分布均匀 [英] Prove a random generated number is uniform distributed

问题描述

有人问我这个问题进行了采访。

I was asked this question in an interview.

给定一个随机数发生器生成一个数值之间[0，N）时，如何   为了证明这个数字被均匀分布的。

Given a random number generator to generate a number between [0,N), how to prove this number is uniform distributed.

我不知道如何解决这个问题，任何建议？

I am not sure how to approach this problem, any suggestion?

推荐答案

要证明，你需要知道的算法被使用，并显示在图形方面，该组所有国家都构成了一个循环，不存在子循环，并且该状态空间模的基数N是零，因此，没有集发生更多/更少频率比其他状态。这是我们如何知道梅森难题，例如，是均匀分布的，即使在64位版本为2 ¹⁹⁹³⁷ -1，不可能是宇宙的一生中列举的一个周期的长度。

To prove it, you need to know the algorithm being used and show in graph terms that the set of all states constitutes a cycle, that there are no subcycles, and that the cardinality of the state space modulo N is zero so that there is no set of states that occur more/less frequently than others. This is how we know that Mersenne Twister, for instance, is uniformly distributed even though the 64 bit version has a cycle length of 2¹⁹⁹³⁷-1 and could never be enumerated within the lifetime of the universe.

否则，您使用的统计测试，测试一致性的假设。统计不能证明其结果，无法否定的假说。较大的样本大小，越引人注目未能推翻一个假设是，但它绝不是证明。 （这种观点导致更多的通信问题与非统计人员/非科学家比什么都重要，我知道。）有许多测试一致性，包括卡方检验，安德森 - 达林和柯尔莫哥洛夫 - 斯米尔诺夫以仅举几例。

Otherwise you use statistical tests to test the hypothesis of uniformity. Statistics can't prove a result, it fails to disprove the hypothesis. The larger your sample size is, the more compelling the failure to disprove a hypothesis is, but it is never proof. (This perspective causes more communications problems with non-statisticians/non-scientists than anything else I know.) There are many tests for uniformity, including chi-square tests, Anderson-Darling, and Kolmogorov-Smirnov to name just a few.

所有的均匀性测试将通过价值，如0,1,2的序列，...，N-1,0,1，...所以均匀性是不够的说你有一个良好的发电机。你还应该对序列相关性检验与测试，如间距测试，运行向上/运行下，运行速度高于/低于平均值，生日的测试，等等。

All of the uniformity tests will pass sequences of values such as 0,1,2,...,N-1,0,1,... so uniformity is not sufficient to say you have a good generator. You should also be testing for serial correlation with tests such as spacings tests, runs-up/runs-down, runs above/below the mean, "birthday" tests, and so on.

一个pretty的COM prehensive套件创建乔治马尔萨利亚在他的职业生涯中，出版于1995年，他戏称为的死硬测试的（因为它是测试一个重型电池）

A pretty comprehensive suite of tests for uniformity and serial correlation was created by George Marsaglia over the course of his career, and published in 1995 as what he jokingly called the "Diehard tests" (because it's a heavy duty battery of tests).

这篇关于证明一个随机生成的数字是分布均匀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！