2
$\begingroup$

In a computer program I've written I am using the computer languages random number function to simulate the tossing of a coin. The random number function returns either -1 (= tails) or +1 (= heads). My computer program does 25 runs of 100,000,000 tosses and sums the (-1's and +1's to calculate the excess of heads over tails at the end of each run. I ran this twice but looking at the results I"m not sure if the random number generator is "random". In the first run all the positive runs (more heads than tails) are grouped together and all the negative runs are also grouped together. The second run looks more random (positive and negative runs mixed together).

1) In general are there tests or techniques that can be used to test a computer languages pseudo-random number generator?

2) Given the two runs below are there tests that can be used to test whether the runs appear random or not.

Test 1 25 runs 13740 12294 15062 26770 38254 42206 32122 23616 28974 19018 23282 37556 34830 34002 46992 46822 26620 7628 4894 -916 -21784 -19776 -16956 -15990 -11362

Test 2 25 runs 7052 -9646 -9310 2702 2702 -8208 -9666 -13964 -8568 -10972 4118 -8550 542 -8916 -16292 -30136 -42644 -53952 -66220 -75202 -62796 -61592 -62152 -80168 -82076

$\endgroup$
3
$\begingroup$

There are many many tests. First these are all statistical tests. You first decide on a $p$-value, your cutoff, usually 5% for normal everyday use (gaming, scientific simulations stuff) and 1% for very stringent applications like cryptographic applications. Then you run one of these statistical tests which returns a $p$-value which you compare with your cutoff. The smaller the returned $p$-value the better. If the returned $p$-value is less than your cutoff then consider the test "passed" meaning your random number generator is "probably" good. If the returned $p$-value is larger than your cutoff then your random number generator has failed.

There are no tests to tell you with certainty that your RNG is truly random. There are only tests to tell you if your RNG is bad. If you fail a test then your RNG has obvious patterns in it. If it doesn't fail then you don't know, it may have other patterns in it. So if your RNG passes a test then you can have some faith that it is probably good. The more test you pass obviously the more confidence you have on your RNG.

I looked into this very carefully a few years ago and there are about 40 tests more commonly employed and they are kind of split up in two different "suites" which have become a defacto standard. If you change the -1 to 0 then you can treat them like binary bits, your RNG is spitting out bits.

  • The basic tests include counting zero and one to see if they are roughly equal.
  • You can also count the subsequences 00,01,10,11 to see if they roughly occur quarter of the time each.
  • You can also count the subsequences 000,001,010,100,011,101,110,111 to see if they roughly occur 12.5% each.
  • You can also count all subsequences of length four.....and so on.

  • You can take a subsequence of length 9, form a 3x3 matrix and determine its binary rank which will tell you if the vectors are linearly independent or not.

  • You take a subsequence of length 16, form a 4x4 matrix and determine its binary rank....
  • You can take a subsequence of length 25, for a 5x5 matrix and ....

  • You can also pick a length (powers of two are faster) and take the DFT to look at the spectrum to see if there are any other periodicities.

And so on. The two batteries are the Diehard tests and the suite developed by NIST to test cryptographic strength RNG. I like the one by NIST. They have extensive documentation which is a pretty cool document in its own right. And they provide the suite to you. Get on a linux machine. Download it. Compile it and run pointing to your file with the random bits in it. You literally just pick the tests and it runs them and give you all the $p$-values. It is super easy, has a ton of tests, and is optimized and fast. The documentation provides complete theory and details behind the tests and how is the $p$-value computed and to be interpreted and how to use the tests. Very well done indeed. If you have any math interests, I would recommend taking a good look at the entire document, learned some really cool stuff.

The more tests your RNG passes the better and I would very very impressed if it passes all of them. You should expect to pass most and fail a few. Even the best of the best RNGs fail one test or another. So just because you fail a few, your RNG is not automatically crap. Lastly, you just keep coming up with more and more tests but you stop after a while. After a while you are reasonably sure if your RNG is "good" or not. There is no one definitive test. Also, coming up with a good RNG is very very difficult so instead of cooking up one of your own you might want to get any one of the million libraries out there to do random number generation for you.

$\endgroup$
  • $\begingroup$ Thanks for the link to these tests $\endgroup$ – Harry Spier Feb 22 '14 at 2:59
2
$\begingroup$

There are many tests. You can do the test you are doing, which looks for an imbalance in the number of $\pm 1$'s. You can calculate the chance of each imbalance using the binomial distribution, then do a chi-square test to see if the results are as expected. You can also look at runs of $2,3,4,\dots$ numbers and make sure that the distribution of each bit pattern is as expected. You can look at every $17$th bit to make sure there is not a bias there. You cannot prove the RNG is good, you can only prove it is bad by detecting something wrong. Each test you do gives a chance to prove it bad.

$\endgroup$
2
$\begingroup$

Knuth's "Seminumerical Algorithms" (second in his "Art of Computer Programming") contains a thorough discussion of a number of tests for randomness. Somewhere in the documentation for your language/library the PRNG used should be documented. Before starting down the long chase for the perfect generator, consider carefully what you are going to use it for. Cryptography has very different requirements than simulation or a game. But if you don't trust the random number generator in your language, by all means get one of the many open source ones instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.