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.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

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 

bulletDownload executable
bullet Download Source  (Note: the Random64 procedure  in our Mathslib unit now resides in our library zip file of commonly used units.  Library file DFFVLIB14 or later is required to recompile this program )
bulletDownload current library file (DFFLibV15) required to recompile Chi_Squared_RNG_Testing.

Suggestions for Further Explorations

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

Modified: July 29, 2017

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