Your Ad Here
Tests for Randomness

A discussion about distinguishing a random sequence from a non-random sequence.

Contents

1998-11-14 Scott Nelson: "There is no known way to prove randomness. There's a pretty strong argument that randomness can't even be tested properly."
1998-11-15 Douglas A. Gwyn: "What *can* be done (in many cases) is to measure the information in favor of some hypothesis (about the source) over some other hypothesis...."
1998-11-16 Mok-Kong Shen: "For random bit sequences I recommend Maurer's test...."
1998-11-16 Andrew: "The tests I was most interested in would also include an amplitude (distance) or a two dimensional space."
1998-11-16 Scott Nelson: "Some of the tests in the Diehard battery test in 2, 3, 4 and 5 dimensions."
1998-11-17 Douglas A. Gwyn: "If that pattern continues as the sequence is extended, then the sequence is certainly *not* random."
1998-12-10 bob_jenkins@my-dejanews.com: "The test for that is called the 'run test'."
1998-12-11 Terry Ritter: "In my experience, Runs-Up and Runs-Down are far more powerful than they may appear."
1998-12-11 Tony T. Warnock: "I've found the same thing."

Subject: Re: Tests for Randomness
Date: Sat, 14 Nov 1998 17:41:05 GMT
From: scott@helsbreth.org (Scott Nelson)
Message-ID: <3652bce8.168156049@news.inreach.com>
References: <364C7F53.9F43FCA3@aspco.com>
Newsgroups: sci.crypt
Lines: 30

On Fri, 13 Nov 1998 13:49:55 -0500, Andrew  wrote:

>Can anyone e-mail me some information on how one can best analyze a set
>of data to dtermine if it is a random sequence or non random one?  Any
>help would be greatly appreciated.
>
Short answer:
No.

Long answer:
There is no known way to prove randomness.
There's a pretty strong argument that randomness can't even
be tested properly.  And the (poor) tests we have are really
only useful when applied to very large sets.  As a rule of
thumb, you need about n squared data points to achieve 
a confidence of 1/n in the results (which shouldn't be 
confused with confidence in the randomness of the generator)
Some of the tests in Diehard use over 2 million 32 bit 
samples.

Still, applying the tests we have, as bad as they are,
is better than nothing.  Take a look at 
http://stat.fsu.edu/~geo/diehard.html 
(If you're a C programmer, you might prefer DiehardC -
ftp://helsbreth.org/pub/helsbret/random )

-----------------------------------
Shameless plug for random web site:
http://www.helsbreth.org/random
Scott Nelson 


Subject: Re: Tests for Randomness
Date: Sun, 15 Nov 1998 07:26:57 GMT
From: "Douglas A. Gwyn" 
Message-ID: <364E8229.5584A45@null.net>
References: <3652bce8.168156049@news.inreach.com>
Newsgroups: sci.crypt
Lines: 13

Scott Nelson wrote:
> There's a pretty strong argument that randomness can't even
> be tested properly.

What *can* be done (in many cases) is to measure the information
in favor of some hypothesis (about the source) over some other
hypothesis; for example, that the observed sequence was generated
by a uniform-random source rather than a source with certain
other specified characteristics.

That changes an ill-posed question "Is it random?" into an
answerable question where the answer has useful mathematical
properties.


Subject: Re: Tests for Randomness
Date: Mon, 16 Nov 1998 19:33:47 +0100
From: Mok-Kong Shen 
Message-ID: <3650700B.A1122213@stud.uni-muenchen.de>
References: <364C7F53.9F43FCA3@aspco.com>
Newsgroups: sci.crypt
Lines: 11

Andrew wrote:
> 
> Can anyone e-mail me some information on how one can best analyze a set
> of data to dtermine if it is a random sequence or non random one?  Any
> help would be greatly appreciated.

For random bit sequences I recommend Maurer's test which is described 
in Menezes et al., Handbook of Applied Cryptography. It is very simple 
to implement. I have a Fortran code for that.

M. K. Shen


Subject: Re: Tests for Randomness
Date: Mon, 16 Nov 1998 14:17:33 -0500
From: Andrew 
Message-ID: <36507A4D.503FCABC@aspco.com>
References: <364C7F53.9F43FCA3@aspco.com>
Newsgroups: sci.crypt
Lines: 54

I appreciate all those who have responded to my original post.  While I
have not had the opportunity to examine in detail all of the information
and related web sites, I have noticed one thing.  I will attempt to
explain, to the best of my abilities, a question.  Please forgive me for
any incorrect use of terminology.

A majority of the tests for randomness which were recommended to me,
dealt primarily with sequencing or one dimensional space.  The tests I
was most interested in would also include an amplitude (distance) or a
two dimensional space.  For example:

Suppose you have the following sequence:    5 -1 4 -2 6 -1 5 -2 4 0 5 -1

because it generally follows: positive, negative, positive, negative
.... it might appear that this is a randomly distributed set of values.
The graph would look like this:




Looking more closely, if you looked at the graph of the result of the
data it would look like this:



With this graph you can clearly see a "trend" in the data that is
present.  Using the average "step size" and number of iterations one
could calculate the randomness of where you ended up from where you
started.

I was hoping that people on this list might know of additional tests
which would take that set of data and indicate if it was random or not.

Again, Any advice or assistance is greatly appreciated.  I look forward
to hearing from you all.  Thanks for your time.

Andrew


Andrew wrote:

> Can anyone e-mail me some information on how one can best analyze a
> set
> of data to dtermine if it is a random sequence or non random one?  Any
>
> help would be greatly appreciated.
>
> Thanks for your time.
>
> Regards,
>
> Andrew
> andrew@aspco.com



Subject: Re: Tests for Randomness
Date: Mon, 16 Nov 1998 21:45:28 GMT
From: scott@helsbreth.org (Scott Nelson)
Message-ID: <36508f0f.11893416@news.inreach.com>
References: <36507A4D.503FCABC@aspco.com>
Newsgroups: sci.crypt
Lines: 39

On Mon, 16 Nov 1998 14:17:33 -0500, Andrew  wrote:

>I appreciate all those who have responded to my original post.  While I
>have not had the opportunity to examine in detail all of the information
>and related web sites, I have noticed one thing.  I will attempt to
>explain, to the best of my abilities, a question.  Please forgive me for
>any incorrect use of terminology.
>
>A majority of the tests for randomness which were recommended to me,
>dealt primarily with sequencing or one dimensional space.  
>
[example snipped]

>I was hoping that people on this list might know of additional tests
>which would take that set of data and indicate if it was random or not.
>
>Again, Any advice or assistance is greatly appreciated.  I look forward
>to hearing from you all.  Thanks for your time.
>

I think you need to learn a bit more of the nomenclature before 
you ask again.  If I roll a die 10 times and get the sequence
1,2,3,4,5,6,6,6,6,6 that sequence is just as random as the 
sequence 5,2,3,5,1,2,4,6,2,2 or any other, but I suspect 
you would reject the first as "not random enough"

Some of the tests in the Diehard battery test in 2, 3, 4 and 5 
dimensions.  _Any_ sequence generated by a pseudo random 
generator will fail to be random when viewed in enough dimensions,
though "enough" might be larger than is practical.  For instance, 
a cryptographically secure pseudo random number generator shouldn't 
fail until the number of dimensions is greater than the key space.

Not sure if that answers your question or not, but I hope it helps.

----------------------------------------
DiehardC 1.03 now available via ftp from
ftp://helsbreth.org/pub/helsbret/random
Scott Nelson 


Subject: Re: Tests for Randomness
Date: Tue, 17 Nov 1998 10:02:50 GMT
From: "Douglas A. Gwyn" 
Message-ID: <365149A3.E3F4031F@null.net>
References: <36507A4D.503FCABC@aspco.com>
Newsgroups: sci.crypt
Lines: 8

Andrew wrote:
> Suppose you have the following sequence:    5 -1 4 -2 6 -1 5 -2 4 0 5 -1
> because it generally follows: positive, negative, positive, negative
> .... it might appear that this is a randomly distributed set of values.

You need to distinguish between the set and the sequence.
If that pattern continues as the sequence is extended,
then the sequence is certainly *not* random.


Subject: Re: Tests for Randomness
Date: Thu, 10 Dec 1998 23:39:02 GMT
From: bob_jenkins@my-dejanews.com
Message-ID: <74pm2m$9nn$1@nnrp1.dejanews.com>
References: <36507A4D.503FCABC@aspco.com>
Newsgroups: sci.crypt
Lines: 17

In article <36507A4D.503FCABC@aspco.com>,
  Andrew  wrote:

> Suppose you have the following sequence:    5 -1 4 -2 6 -1 5 -2 4 0 5 -1
>
> because it generally follows: positive, negative, positive, negative
> .... it might appear that this is a randomly distributed set of values.

The test for that is called the "run test".  It measures how long a run of
strictly increasing values you have.  It's one of the standard tests, not a
particularly powerful one though.

- Bob Jenkins
http://ourworld.compuserve.com/homepages/bob_jenkins

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    


Subject: Re: Tests for Randomness
Date: Fri, 11 Dec 1998 05:15:11 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3670a993.3798156@news.io.com>
References: <74pm2m$9nn$1@nnrp1.dejanews.com>
Newsgroups: sci.crypt
Lines: 37


On Thu, 10 Dec 1998 23:39:02 GMT, in
<74pm2m$9nn$1@nnrp1.dejanews.com>, in sci.crypt
bob_jenkins@my-dejanews.com wrote:

>In article <36507A4D.503FCABC@aspco.com>,
>  Andrew  wrote:
>
>> Suppose you have the following sequence:    5 -1 4 -2 6 -1 5 -2 4 0 5 -1
>>
>> because it generally follows: positive, negative, positive, negative
>> .... it might appear that this is a randomly distributed set of values.
>
>The test for that is called the "run test".  It measures how long a run of
>strictly increasing values you have.  

That sounds like "Runs-Up."


>It's one of the standard tests, not a
>particularly powerful one though.

In my experience, Runs-Up and Runs-Down are far more powerful than
they may appear.  In contrast to many other randomness tests, Runs-Up
and Runs-Down can expose correlations (errors of conditional
probability), to some extent. 

For small value ranges it is necessary to use the exact formulation
for the expectations, which is not in Knuth II.  See:

   http://www.io.com/~ritter/ARTS/RUNSUP.HTM

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM



Subject: Re: Tests for Randomness
Date: Fri, 11 Dec 1998 08:12:06 -0700
From: "Tony T. Warnock" 
Message-ID: <36713646.6494E470@cic-mail.lanl.gov>
References: <3670a993.3798156@news.io.com>
Newsgroups: sci.crypt
Lines: 48


Terry Ritter wrote:.

> In my experience, Runs-Up and Runs-Down are far more powerful than
> they may appear.  In contrast to many other randomness tests, Runs-Up
> and Runs-Down can expose correlations (errors of conditional
> probability), to some extent.
>
> For small value ranges it is necessary to use the exact formulation
> for the expectations, which is not in Knuth II.  See:
>
>    http://www.io.com/~ritter/ARTS/RUNSUP.HTM
>

I've found the same thing. These are also fairly easy to implement.