Random Behavior in the Output of Simple Programs

by
Andrew K. Musselman
Dr. W. Dan Curtis

What do we mean when we say that a data set is random?

	•  It is "irregular"

	•  It appears "unpredictable," with no apparent 
guiding rule

	

How do we detect randomness in output?

	•  Visually?

	•  Look for "regularities," recognizable structure, 
periodicity

	

But the absence of these does not always imply randomness

Is this sequence random?

	1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 
      1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0 , 1, 0, 1, 1, 0, 1, 1, 
      0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 
      0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 
      0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
      1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 
      0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 
      1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 
      1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0

Using Statistical Tests to Detect Randomness

    	 •  NIST made a test suite to evaluate pseudo-random number  generators.  
    		(C source and docs available from  http://csrc.nist.gov/rng/ )

    	•  We implemented  several of these tests in Mathematica.

    	•  We tested output of elementary  cellular automata.

The Tests

•  Frequency test
 Compares the fraction of 1s in the sequence with the expected (1/2). 
•  Block-Frequency test
This test divides the data sequence into non-overlapping blocks of a 		    specified length M and then compares the number of 1s in each block 		    with the expected value of (M/2).  
•  Runs test
This test counts the number of runs of 0s and of 1s
 •  Longest Run of Ones in a Block test
This test focuses on the longest run of 1s within M-bit blocks, where M  	   has a value which depends on the overall length of the data sequence. 
 •  Spectral test
This test focuses on the sequence of absolute values of the         		    components of the discrete Fourier transform of the data sequence.

Rule 30  (Single black cell initial conditions)

Center column is random

Rule 30  (Random initial conditions)

Rows and columns are random

Rule 135 (Random initial conditions)

Rows and columns are random

Rule 126 (Random initial conditions)

Rows are non-random, though columns are random

Rule 22 (Random initial conditions)

Rows are non - random, columns are non - random

Rule 225 (Random initial conditions)

Rows and columns are random

Proportion of Black Cells with Random Initial Condition

There is a higher density at 0.5


        About 62 rules out of 256 exhibit a proportion of one half

Stochastic Cellular Automata



	•  Use simple CA rule

	 

	 and

	

	•  A Bernoulli distribution with success probability p

	

	

	Introduce random noise "from the environment"

	

	At each level, for each cell, reverse the cell color with probability p

Rule 126 (Perturbed single black cell initial conditions)

.58 black cells                                  .50 black cells
                              rows not random                              rows not random
                               columns not random                       columns not random

Next:

	•  Start with random initial conditions and  introduce probability p 		    random noise "from the environment" at each  level.  

	•  For each rule tested, we get a definite  black fraction in the output
	
	•  Fraction is depends  on p and is generally different from that of the 		    deterministic CA.

Rule 126 (Perturbed random initial conditions)

.58 black cells                                  .50 black cells
                              rows not random                              rows not random
                               columns not random                       columns not random

Rule 126 (Dependence of black cell fraction on Bernoulli  p )

Rule 30 (Dependence of black cell fraction on Bernoulli  p )

Future Work

1.   Convert the NIST Test Suite to allow for testing data with differing proportions of ones and zeros

2.   Continue to port the NIST Test Suite

      
3.   Work on how to evaluate the randomness of 2 - 
        dimensional data sets (and beyond)

Conclusions

1.    Statistical analysis can inform us in ways visual interpretation cannot

      
2.    Visual interpretation can inform us in ways statistical analysis may miss

      
3.    The NIST Test Suite can be a useful tool for analyzing the behavior of cellular automata

Thank You

References

\(Knuth, 
      Donald, “The\ Art\ of\ Computer\ Programming, 
        vol\ 2 \*"", Second Ed., Addison Wesley, 1998.

Ruhkin,  Andrew, et al, “A Statistical Test Suite for Random and  Pseudorandom Number Generators for Cryptographic Applications ”, National Institute of Standards and Technology  (NIST Special Publication 800-22), May, 2001. Accompanying C source code and  documentation from http://csrc.nist.gov/rng/

Wolfram, Stephen,  “A New Kind of Science”,  Wolfram-Media, Inc., 2002."\)

Appendix