随机数发生器测试 [英] random number generator test

问题描述

如何测试如果随机数发生器产生的实际随机数？

How will you test if the random number generator is generating actual random numbers?

我的做法：一是建立大小为M，其中M为质数的哈希值。然后取数              由随机数发生器产生，并取模分枝              看看它填补了所有的散列或者只是在某些部分。              这就是我的方法。我们可以证明它的可视化？

My Approach: Firstly build a hash of size M, where M is the prime number. Then take the number generated by random number generator, and take mod with M. and see it fills in all the hash or just in some part. That's my approach. Can we prove it with visualization?

由于我对测试非常少的知识。您能否给我建议对这个问题进行彻底的方法吗？在此先感谢

Since I have very less knowledge about testing. Can you suggest me a thorough approach of this question? Thanks in advance

推荐答案

您应该知道，你不能的保证的随机数生成器是否正常工作。请注意在范围内，即使是完美的均匀分布[1,10] - 有一个10 ^{获得在10个号码随机抽样的10倍10 -10} 机会

You should be aware that you cannot guarantee the random number generator is working properly. Note that even a perfect uniform distribution in range [1,10] - there is a 10^-10 chance of getting 10 times 10 in a random sampling of 10 numbers.

是否有可能？当然不是。

Is it likely? Of course not.

那么 - 什么的可以的我们做

So - what can we do?

我们可以的统计学证明该组合（10,10，...，10）是不大可能的如果随机数发生器被确实均匀分布的。这个概念被称为 假设检验 。用这种方法，我们可以说用的x％的确定性水平 - 我们可以拒绝假设，即数据取从均匀分布

We can statistically prove that the combination (10,10,....,10) is unlikely if the random number generator is indeed uniformly distributed. This concept is called Hypothesis testing. With this approach we can say "with certainty level of x% - we can reject the hypothesis that the data is taken from a uniform distribution".

一个常见的​​方式做到这一点，使用的 Pearson的卡方检验 ，我们的想法是与你相似 - 你填写一张表格 - 检查什么的观察的（产生的）数数的每个细胞，什么是预计的对于在零假设下各细胞数（你的情况的数量，预期的是 K / M - ，其中M是所述范围的大小，而k是数字的总数拍摄）。
您然后做一些操作上的数据（详情参见本操作到底是什么维基百科的文章） - 并获得了一些（检验统计量）。然后检查是否这个数字的可能的取自卡方分布 。如果是 - 你不能拒绝零假设，如果它不是 - 你可以肯定为x％的把握认为该数据是不是从一个统一的随机数发生器

A common way to do it, is using Pearson's Chi-Squared test, The idea is similar to yours - you fill in a table - check what is the observed (generated) number of numbers for each cell, and what is the expected number of numbers for each cell under the null hypothesis (in your case, the expected is k/M - where M is the range's size, and k is the total number of numbers taken).
You then do some manipulation on the data (see the wikipedia article for more info what this manipulation is exactly) - and get a number (the test statistic). You then check if this number is likely to be taken from a Chi-Square Distribution. If it is - you cannot reject the null hypothesis, if it is not - you can be certain with x% certainty that the data is not taken from a uniform random generator.

编辑：示例：
您有一个立方体，并且要检查它是否公平（在均匀分布[1,6] ）。它扔200次（例如），并创建下表：

example:
You have a cube, and you want to check if it is "fair" (uniformly distributed in [1,6]). Throw it 200 times (for example) and create the following table:

number:                1       2         3         4          5          6
empirical occurances: 37       41        30        27         32         33
expected occurances: 33.3      33.3      33.3      33.3       33.3       33.3

现在，根据Pearson的测试中，统计量是：

Now, according to Pearson's test, the statistic is:

X = ((37-33.3)^2)/33.3 + ((41-33.3)^2)/33.3 + ... + ((33-33.3)^2)/33.3 
X = (18.49 + 59.29 + 10.89 + 39.69 + 1.69 + 0.09) / 33.3
X = 3.9

有关随机 C〜卡方（5），被高于 3.9 是<$ C的概率$ C>〜0.45 （这不是不可能的） ¹ 。

For a random C~ChiSquare(5), the probability of being higher then 3.9 is ~0.45 (which is not improbable)¹.

因此​​，我们的不能的拒绝零假设，我们可以得出这样的结论数据的也许的均匀分布[1,6]

So we cannot reject the null hypothesis, and we can conclude that the data is probably uniformly distributed in [1,6]

（1）我们通常拒绝零假设，如果该值越小则0.05，但是这是非常情况下依赖

(1) We usually reject the null hypothesis if the value is smaller then 0.05, but this is very case dependent.

这篇关于随机数发生器测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！