Search
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
email with your comments about this program (or anything else).

 
Problem Description
This program eventually tests our Random Number Generators (actually Delphi's
for 32bit and a local implementation for 64bit 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 ChiSquared 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
ChiSquared from "Numerical Recipes in Pascal"
The first experiment replicates the Demo program which came with ChiSquare 1
procedure, ChsOne, (single random variable vs. one of known
distribution). The demo program was implemented to see that this
ChiSquared 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 ChiSquared 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" ChiSquared 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 ChiSquared 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
ChiSquared = (24)^{2}/4 + (4 8)^{2}/8 + (1912)^{2}/12
+ .... + (64)^{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
ChiSq value this high.. On the other hand if all values are close to expected,
ChiSquared 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 (ChiSq 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 ChiSq 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. Online searches for ways to
verify the quality of an RNG led me to Knuth which led me to the ChiSquared
test.
The ChiSquared 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 ChiSquared values but
ChiSquared results should be centered about the 50% critical value. Averaging
many trials should produce a mean ChiSquared 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 64bit 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
 Download
executable

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 )
 Download
current library file (DFFLibV14_12Nov2016)
required to recompile Chi_Squared_RNG_Testing.
Suggestions for Further Explorations

Additional randomness
tests for runs, gaps, etc. 


Created: December 5, 2013 
Modified:
July 24, 2016

