Chi Squared Random # Testing

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

This program eventually tests our Random Number Generators (actually Delphi's for 32-bit and a local implementation for 64-bit numbers) to determine if the numbers generated are at least uniformly distributed across a range. . There are many algorithms to test randomness; this program explores the Chi-Squared statistic which measures the deviation of random samples from the expected distribution. There are three pages presented here presented in the order I wrote them.

Background & Techniques

Chi-Squared from "Numerical Recipes in Pascal"

The first experiment replicates the Demo program which came with Chi-Square 1 procedure, ChsOne, (single random variable vs. one of known distribution).  The demo program was implemented to see that this Chi-Squared procedure was successfully converted from old "Numerical Recipes for Pascal" code to use "Extended" variable type and to run under Delphi as ChsOneExt.  As yet I have no idea what it does or whether the results match although "Numerical Recipes in Pascal" book is on order so more information may be available soon.  I did note that the test "fudges" degrees of freedom to match the number of bins (categories) rather than (bins - 1) which is normally correct.   More about this and the "Numerical Recipes" code later.

Donald Knuth's Random Number Testing

The second experiment in the program is based on Chapter 3 of Donald Knuth's classic work "The Art of Computer Programming" which dedicates 170 pages to generating and testing random numbers. Virtually all software Random Number Generators (RNGs) are called "Pseudo" generators because after the first number, each value returned is based on the last value returned. Since there are only a finite number of values, eventually a returned number will repeat and a new identical cycle begins.

This suggests that one good test would be to determine if the RNG generates all values within its range of values, but I have not found or  figured how to conduct such a test. Almost all tests I've seen are statistical sampling tests. The Chi-Squared is the first of many found in in Knuth's chapter. I've duplicated it here to validate my implementation of the  method.

The "Type 1"  Chi-Squared test compares an observed distribution of experimental results for a single variable with a theoretical distribution. Knuth threw 2 standard dice 144 times (says it got too boring to do more), and compares the number of occurrences of each sum to the theoretical count of sums (from 2 (rolling two 1's) to 12 (rolling two 6's). For 144 throws the theoretical distribution of the 11 possible sums from 2 through 12 are (4, 8, 12, 16, 20, 24, 20, 16, 12, 8, 4) and the observed counts for those sums was (2, 4, 10, 12,  22, 29, 21, 15, 4, 9, 6). The Chi-Squared statistic is calculated as the sum of the quotient of the squared differences of each (observed count - expected count) divided by the expected count. In this case Chi-Squared = (2-4)2/4 + (4 -8)2/8 + (19-12)2/12 + .... + (6-4)2/4 = 7.1458.

The significance of this number is based on the degrees of freedom (number of sum bins -1). Knuth has a lookup table for several degrees of freedom values which allow estimating the probability that the differences from drawing a random sample from the theoretical distribution will be greater than or equal to the observed differences. Knuth argues convincingly that for a single test we should expect the probabilities to fall in the 0.25 to 0.75 range. If the value is high there very little chance that the true distribution would produce a Chi-Sq value this high.. On the other hand if all values are close to expected, Chi-Squared is low and our trial does reflect the true distribution of sums, but but it's highly unlikely than a random sample would bee this close to expected counts across the board.  Such a result in  single trial makes it  likely that the "books were cooked" (e.g. the dice thrower could control the sum thrown and deliberately tried to match the theoretical distribution) and this is not a true random sample.   Knuth says that probability results between .25 and .75 (Chi-Sq between 6.7 and 12.6)  which should occur half the time and indicates that our dice results are probably random. 

I call this a weak test for confirming randomness because Chi-Sq values would have to be < 3.9 or > 18.5 for us to be 95% sure that the dice were loaded after 144 throws. Knuth's .25 to .75 probability range will occur only half the time even if the observed sample is from a random distribution. In my test,  we'll take advantage of the computer to generate many more samples and multiple trials for our Random Number Generators.

My Random Number Tests

This experiment was the motivation for entire program while looking for a way to validate the "randomness" of the 64 bit random number generator recently (November 2013) implemented in our Mathslib unit. On-line searches for ways to verify the quality of an RNG led me to Knuth which led me to the Chi-Squared test.

The Chi-Squared test is not a very strong indicator of randomness For a given set of numbers placed into bins based on their value, the statistic is applied to differences between the observed frequency and the expected frequency for the assumed distribution of the
population. Random numbers have a theoretical uniform distribution so each bin should have the same value. One test is to count the number of occurrences of each of the digits 0 through 9. when generating random numbe in that range.   Another  partitioning is implemented with a "Quantile" button which divides the total range of random numbers for each length nto a specified number of bins.

Any individual trial can produce a wide range of Chi-Squared values but Chi-Squared results should be centered about the 50% critical value. Averaging many trials should produce a mean Chi-Squared value near this 50% critical value. I implemented a "Number of Trials" field to test this and in fact it seems that running 1,000 trials with 1,000 samples per trial ("only" 1 million samples in total) usually produces results in the 49% to 51% range. - good evidence that our random numbers for both 32 and 64-bit integers are at least uniformly distributed. Good enough for now.
 

Delphi 7 Programmers Note:

Be aware that the Random64 procedure when compiled under Delphi 7 or earlier uses the Random procure from our Big Integers unit with numbers limited to Int64 size.  This runs much slower than the Delphi XE version so running millions of samples may take minutes rather than seconds.

 Running/Exploring the Program 

Suggestions for Further Explorations

Additional randomness tests for runs, gaps, etc.
 
Created: December 5, 2013

Modified: July 24, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.