Why is there no standard test for random number generators?

Question

I've been looking at this problem for the last year, and can't understand why there's no standard way to test for randomness in the real world. It seems to be that it's just what make you comfortable.

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

Randomness testing issues 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. Compression /entropy estimate is totally wrong but the chi test is useful. The NIST user manual is >100 pages long - good luck. TestU01 - has compilation issues on certain platforms. 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 (read: money) required".

Consider what happens in the real world that we live in, not on an academic's bookshelf:-

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. They stake their business model on this.

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

ERNIE for the UK Premium Bonds. They use basic statistics tests for frequency and correlation. Effectively home brew and not using a published suite.

The two latter examples seem to suggest that the current Zeitgeist is being molded by financial bodies. Random numbers are a form of maths, a reasonably established discipline. Why isn't there a tried and tested program suite that everyone uses, and it's output says yea or ney?

Supplemental: Following responses and further research, I'm starting to think that perhaps these questions of validating randomness are somewhat scholastic. There is no standard test for random number generators; because there is no need for such. My 3 1/2 rules for an excellent random number generator:-

1. The generator must pass some recognised test which may be like Diehard, or home brewed.

2. The organisational body fronting /validating (see 1) the generator must have gravitas.

3. The generation algorithm /methodology must sound convincing (see 2).

4. For true random number generators, the entropy source has to be self evidently naturally random.

I have inferred these rules from observations of what really seems to happen in commercial, financial and legal environments.

Answer 1

Since you've appealed to math, we need to do some math. Let us assume that an algorithm were provably a cryptographically secure PRNG. We need to be a little more precise in our definition there (I'm still going to be sloppy, but hopefully the intuition will hold).

By CSPRNG, I mean a function R(t) = r which returns a single, totally unpredictable value at a given time. This function must be computable in polynomial time. Rather than say "polynomial time" over and over again, I'm going to call it "quickly."

Given that function, let's talk about its inverse: R-1(r) = t. Given some output value, R-1(r) returns some time value for which r would be the output.

So if I told you that R-1(1) = 5, you could verify that very quickly by plugging 5 into R and making sure it returned 1. Things that can be verified quickly are called "NP" and R-1 is a member.

But if I asked you, what is R-1(1), you could not solve that quickly. If you could solve that quickly, then we would violate the rule that R(t) is "totally unpredictable." Things you can solve in polynomial time are called "P". So R-1 is not a member.

Ah, so we have found a function that is provably in NP but is provably not in P. That means P≠NP. Yes! We have solved one of the greatest math questions in existence. We all have this intuition that there probably are functions that are like this, but no one has been able to prove it.

So, in order to build a mathematically provable PRNG, step one is to solve one of the Millennium Prize Problems. In the meantime, we just have elaborate unit testing. And as long as we rely on testing, rather than proofs, we can't get the kind of assurance you're looking for. We can just find bugs; we can't ensure correctness.

Answer 2

A standardised, conclusive, binary result PRNG test has not been developed because it is not possible.

First of all, whatever output you deem to be not acceptable, there is some non-zero possibility that a perfect random number generator could legitimately produce it. Right away you're faced with the risk of false failures, so the result of the test cannot be an absolute yes or no.

Second, any PRNG will have some kind of detectable signature if you know the algorithm and can collect enough information about its state. If a hypothetical test knew every possible PRNG algorithm and was able to test for long enough to determine its working state then it would definitively reject all PRNGs tested. By definition no PRNG is adequate according to this test.

Third, already mentioned. Once you nail down a "reasonable" subset of patterns somebody can immediately make a PRNG which passes everything deemed reasonable but is a catastrophic failure on the first characteristic excluded from your list.

In short, we know that all PRNGs should eventually fail a perfect test because they are deterministic machines and by their very definition not random. The test batteries that exist are merely tools comparable to spellcheckers, in that they can highlight common errors but they can't tell you whether or not you're doing it right.

Answer 3

If there was a single standard test then there would probably be a certain amount of over-fitting. You could use genetic algorithms to tweak parameters to pass that specific test. It is more useful to have a large variety of fairly different tests, which in fact describes the current situation. Think of it like the immune system. A healthy immune system can resist a whole host of pathogens and not just a single standard pathogen.