Random Number Testing (fwd)

[Jim Choate <ravage@ssz.com>]

Hi Fred,

Forwarded message:

> Subject: Random Number Testing
> Date: Tue, 26 Mar 1996 18:00:26 -0800 (PST)
> From: Fred <admin@dcwill.com>
> 
> The limitation seems to be in the testing process.
> 
> An inviolable rule of test and measurement is that the testing process
> must have a higher degree of accuracy and precision than is expected from
> the item under test. If all you have is a non-graduated stick one meter 
> long, you can't measure increments of less than one meter unless you add 
> some additional resolution to the system (such as a human's judgment
> that the object is four sticks, plus about another third of a stick,
> long).

Not if I am allowed geometry. I believe such situations are a test of
lateral thinking more than any fundamental insite into nature.

> 
> Our ability to synthesize pseudo-random data, and the degree to which
> it approaches true random data, is limited by our ability to discern
> between the two. If the best testing process available yields the
> same results for the output of a true RNG and a particular PRNG, what
> can be done to improve the randomness of the PRNG? How could we tell
> the difference based on the data itself? 

What are you defining as random? The definition I use in practice is basicly
that if I am given 100% intelligence on a stream of numbers the odds of my
succesfully choosing the next number is never higher than chance.

All data is random (by definition) until the pattern(s) can be discerned.
In this context pseudo-random has a definite meaning, namely that it takes a
long time to amass enough information about the data stream to break the
chance boundary. The question quickly becomes, how do you test various
sequences against one another for robustness? It seems to me that it has to
be done statisticaly.

One aspect of this is what I call the 'ghost' pattern. In short, in the
process of analyzing some random data a pattern is found. Is it possible
that there could be more than one pattern (ie interpretation) of the data?
Is it possible for a data stream to contain two (or more) messages
coherently? If a message does contain two or more coherent messages, how
does this affect the size of the data? Can this occur only on messages above
a certain size?