How to test random numbers?

Question

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

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

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

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

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

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

View more solutions

Comments

[Rich]

That's kind of a monobit test. But still very short of a real test suite like the ones he mentioned (ok, ent doesn't count).

[dmckee --- ex-moderator kitten]

Good start. Next up is to generate ordered pairs and see that they are evenly distributed in the plane, then ordered triples...and you still aren't "really" doing it...

[Erkki Nokso-Koivisto]

by following the sourceforge link, one finds a page explaining that the code has moved to: code.google.com/p/randomnumbertestsuite-nist