A discussion about distinguishing a random sequence from a non-random sequence.
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 <Andrew@aspco.com> 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 <scott@helsbreth.org>
Subject: Re: Tests for Randomness Date: Sun, 15 Nov 1998 07:26:57 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> 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 <mok-kong.shen@stud.uni-muenchen.de> 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 <Andrew@aspco.com> 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 <Andrew@aspco.com> 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 <scott@helsbreth.org>
Subject: Re: Tests for Randomness Date: Tue, 17 Nov 1998 10:02:50 GMT From: "Douglas A. Gwyn" <DAGwyn@null.net> 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 <Andrew@aspco.com> 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 <Andrew@aspco.com> 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" <u091889@cic-mail.lanl.gov> 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. Tony
Terry Ritter, his current address, and his top page.
Last updated: 1999-01-19