How to test random numbers?

问题:

i have written in matlab, a program, which is supossed to generate random numbers between 0 and 1. i have test it only with the runstest in matlab, and te result is that the sequence is random. i have seen the histograms too, and they have a beta distribution. i want to test this rng whith other test, such as diehard, ent, or nist, but i don't know how. can someone explain how to use them, or suggest me some other randomness tests. thank you

回答1:

With most tests you can supply a large file of random numbers (integer or floating point) and run various tests on that sample file. DIEHARD worked that way, if I remember correctly and some others do, too. If you really want to see your generator fail, you could try using TestU01 by Pierre L'Ecuyer which has enough tests in it to let nearly every generator fail at least one test :-)

Still, for most test suites there is extensive documentation, at least I know this for DIEHARD, the test suite from NIST SP 800-22 as well as DieHarder and TestU01 (links go to the docs). The methods for supplying random numbers to test are usually different but mentioned in the respective documentation.

回答2:

The tests available are:

Dieharder - http://www.phy.duke.edu/~rgb/General/dieharder.php

TestU01 - http://simul.iro.umontreal.ca/testu01/tu01.html

RaBiGeTe - http://cristianopi.altervista.org/RaBiGeTe_MT/

NIST STS - http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

PractRand - http://pracrand.sourceforge.net/

Any of those can test bits from a file. Some (PractRand, Dieharder, not sure about TestU01) can test data piped in standard input. Some also support linking your PRNG directly to the test suite, dynamically (only RaBiGeTe offers real support for dynamically linking your PRNG to it) or statically.

Quality is not equal. If you have plenty of bits of PRNG output, PractRand can find the widest variety of biases quickest (full diclosure: I wrote PractRand), followed by TestU01. If you don't have plenty of bits, RaBiGeTe might do better. NIST STS and Dieharder generally underperform.

Convenience of interface is also not equal. PractRand and Dieharder are set up for command line automation. PractRand and TestU01 tend to have the easiest output to interpret in my opinion. Dieharder isn't bad in that regard. RaBiGeTe and NIST STS, well... they both promote what seems to me like overcomplicated & useless visualizations of distributions of test results.

Also, NIST STS and Dieharder both have false positive issues.

There's also ENT, can't find a link for it at the moment... it has a fairly convenient interface IIRC but is not very good at finding bias.

回答3:

There are many things to test if you want to test your RNG on your own. Here are a few basic features that may reveal your number sequence to be not truly random or maybe indistinguishable from random?

Take a look at:

1. The distribution - you have already done some analysis on your distribution. You want each possible number to have the same probability of occurring.

2. Cyclic behavior - does the same sequence repeat itself over and over again? The repetitive sequence may be quite long.

3. Occurence of duplicates (...C B B A F F...) , triplets (...C B A A A F...) etc. Statistically in a sequence of random numbers you have a certain probability of dulplicates (the same number generated twice in a row), triplets etc. Calculate this probability and check if your sequence of pseudo random numbers has the same probability of duplicates occurring?

Note that for most of these tests you need to have a quite long sequences of random numbers in order to be able to get sensible and accurate results from statistical analysis.

I assumed peudo random number sequences of integers, which is easily fixed by multiplying your [0, 1] numbers by an appropriate constant.

回答4:

For your particular use-case, I recommend writing down the 0 and 1 numbers generated by your rng as characters to a file and then use that file as input data for the test suite program.

Note that the sequence has to be at least 1000 characters long to be tested by STS.

When you run it, don't forget to use the flag -F 'a', to tell the program that the input file is made of ASCII 0 and 1 chars.

---

I also recommend trying this unofficial version of the NIST Statistical Test Suite, where I have fiddled with the original NIST source code and tried to optimize it.

---

For your convenience, here is the command I would suggest that you use to run the tests with it (after having compiled the program from the sources with $ make):

$ ./sts -v 1 -i 32 -I 1 -w . -F 'a' /path/to/input/file

You might want to increase the number of bitstreams tested (indicated by the -i flag) to a bigger one to use more data from the input. For example, you can choose:

number of bitstreams = (number of 1 and 0 bits you generated) / 1048576

Once all the tests have been run, the program will generate a report in a file called result.txt, that you can use to evaluate the quality of your rng.

---

Note that this program it’s not NIST-official though. Also, our test-suite modifications did not undergo 3rd party testing; so it’s AS-IS with no guarantees whatsoever.

回答5:

I've been looking at this problem for the last year, and I've come to the conclusion that there's no standard way to test for randomness in the real world. I think that it's just what make you comfortable. You can't prove that a sequence is random, and you can't easily prove that a sequence isn't random.

(I'm ruling out random sequences that are really really not random, like 0123456789...repeating.)

user3535668 lists some widely known tests, and a whole list of issues with them. I can add others. Diehard - how big should the input file be, and should it consist only of 32 bit integers? ENT - only seems suitable for gross errors, but the chi test is useful. The NIST user manual is >100 pages long - good luck. TestU01 - same compilation issues. And once you've shoehorned it into your computer, is it running correctly? How can you then trust the output? And how do you know if a test has failed? What level of p or KS is considered too extreme?

I would further add that you should consider the development of randomness test suites vis a vis real-politic. It's in an academic's self interest to develop tests that discredit random number generators. After all, you don't get no funding producing results that say "it's all okay, nothing found, no further research required".

Readers will disagree with this premise, but I suggest that you consider what happens in the real world that we live in, not on an academic's bookshelf. There is no standard test. Consider:-

Random.org - used an undergrad to undertake some homebrew tests for a thesis. And essentially count the number of 1's and 0's. ENT does similar.

Hotbits - champion the simplistic ENT, and a hacked version of Dieharder that most people will have difficulty in getting to execute, never mind trying to comprehend myriad test initialisers.

Academic generator papers - much recourse to Knuth's writings and homespun techniques. Some use some of the above tools. Some then accept a number of test failures within those suites.

The only example I've found so far in this man's universe that seems to carry any real weight (i.e. if it fails you go to prison type of weight) is the certification for Playtech PLC, a UK supplier of gambling software. They supply some of the largest online betting companies where real money changes hands. Still, they use homebrew tests and the Diehard test.

I personally like to:-

1. convert the subject file into a bitmap to look at it
2. compress it with 7z on the Ultra setting to see if it gets any smaller
3. take a Diehard run at it and look for stupid ps and KSs.

I think that if a file passes my personal 1 - 3, you'll have a hard time proving otherwise. Seems to me like as good a starting point as any...

回答6:

Confine the result to a specific range (possibly using the mod operator), run your code a few million times and count how many times you see each number in the range. Make sure the counts are roughly the same, and that you don't have a bias for any specific values.

回答7:

The route that I would probably go would be to do a visual analysis of the results. The code for this is simple enough, as shown in the following psudo-code based upon this article.

1. Create an image of size x by y
2. For ndx = 0 to x
  3. For ndy = 0 to y
    4. Let random be a random number between 0 and 1
    5. If random = 1, set the image point at ndx, ndy as black
6. Display the generated image

Also, Random.org has more information on the statistical analysis of algorithms, but they also use the aforementioned article as their example of visual analysis.

回答8:

I am actually looking for a similar test, was hoping to find it here but did not. I will try math.stackoverflow.com where I will probably be able to ask it as the answer is a statistical one.

My statistics knowledge is moderate enough to know what you are looking for without being able to provide the exact detail.

Essentially you are performing a regression test as to whether your numbers conform to a uniform distribution. So we can create a chi-squared model (I think). It will lead to getting a t-stat and a p-value. A higher t-stat and lower p-value means that it does not conform to the distribution (thus we reject the null hypothesis). The p-value will be between 0 and 1. If it is say 0.06 then we can reject the null hypothesis with a confidence of 94%.

And to answer those who are saying "we should not be creating random numbers", maybe not actual random numbers but we may get data in and wish to test if it fits a uniform distribution, and for programmers we may wish to test if a hash-function produces a uniform distribution across large numbers of random instances of the objects we are hashing.

As for some code for NIST testing, there is some here:

http://sourceforge.net/projects/randomanalysis/

which may give you what you want.

回答9:

@Anna I had the same question as you and have now discovered Diehard thanks to some of the other answers.

The situation with my RNG is that it creates 1's and 0's and stores them in an ASCII file. When trying to upload this file to online randomness tests, it failed - most probably because the data needs to be in binary format.

And that's indeed the case with Diehard. If you install Diehard, you will find a file called DIEHARD.DOC which talks you through the steps of how to convert your ASCII file into the required binary files (along with some other changes you may need to make to your program).

These are my first steps, anyway. Hope this helps someone.