The Ordered Frequency Test
for Random Numbers


The Ordered Frequency Test is a frequency testing method for discrete uniform distributions. Standard frequency tests allow too many Type I errors, so a more effective frequency test is in order.

This topnotch frequency test, the OFT, involves urns and tosses, designated u and t. Given u urns into which t pebbles are tossed with uniform probability, each urn will collect from 0 to t pebbles. The unordered expected urn count, ex, is t/u for every urn.

This test is superior to other uniform frequency tests because the observed values are not compared to t/u (50-50), rather to the expected ordered frequency.

Two urns represent a coin toss. The expected highest frequency count for u=2, either heads or tails, converges to
ex + sqrt(ex/π)  which is the upper limit as t → ∞.

After a session of tosses, each urn count is ordered from lowest to highest. Good choices of expected urn counts (t/u) range anywhere from 36 up to 5 million, the smaller the better due to testing overhead and diffusion. For coin tosses where u=2, t=200 works suitably.

To obtain the frequency counts for a candidate RNG, the session values are averaged. For adequate precision, at least 400 sessions are required, with 2,000 providing acceptable results. More sessions provide greater accuracy, but higher expected urn counts (ex) provide little if any additional precision.

The testing procedure for the 2 urn OFT is:
  1. Obtain and count 200 candidate bits.
  2. Sort (order) each of the u counts from lowest to highest.
  3. Do this at least 400 times.
  4. Determine the u averages, which should compare to 94.3651521 and 105.6348479 (rounded) for u=2 and ex=100.
For the Certified Random numbers from Arrive Software, here are a sparse number of representative results:
    Averages for 2,000 sessions of 200:
  1. 94.3495 and 105.6505
  2. 94.328  and 105.672
  3. 94.468  and 105.532
    Averages for 10,000 sessions of 200:
  1. 94.3241 and 105.6759
  2. 94.3705 and 105.6295
  3. 94.3889 and 105.6111
    Averages for 100,000 sessions of 200:
  1. 94.35272 and 105.64728
  2. 94.36614 and 105.63386
  3. 94.36505 and 105.63495


Instead, what if there are 3 urns?
The equation for the highest expected urn count, with large t, where ex= t/3, is
ex + 3/2 * sqrt(ex) * sqrt(1/π) + (0.0918881...)/2
Unlike all other urns, the middle ordered urn is not scalable by sqrt(ex). Surprisingly, if not amazingly, the constant difference from ex for any number of tosses (where t mod 3=0) converges to -0.0918881.... {Examples: For t=3,000: the middle urn's expected value is approximately 999.9081... For 30,000: 9,999.9081... For 300,000: 99,999.9081... and so on.}
For 300 tosses, the expected ordered counts (rounded) are:
91.5849290896, 99.9079757193, 108.5070951911
For the Certified Random numbers from Arrive Software, here are a sparse number of representative results:
    For 2,000 sessions of 300 tosses:
  1. 91.707  and 99.9575 and 108.3355
  2. 91.5865 and 99.8465 and 108.567
  3. 91.5331 and 99.9096 and 108.5573
    For 10,000 sessions of 300 tosses:
  1. 91.5499 and 99.9027 and 108.5474
  2. 91.5879 and 99.8918 and 108.5203
  3. 91.5807 and 99.9174 and 108.5019
    For 100,000 sessions of 300 tosses:
  1. 91.6004 and 99.9151 and 108.4845
  2. 91.5775 and 99.9049 and 108.5176
  3. 91.5904 and 99.9055 and 108.5041

The Ordered Frequency Test makes less Type I errors with greater precision using less trials and is therefore a superior random number Frequency testing method. Pattern testing is an additional testing arena apart from Frequency testing for which the Arrive Software RNG has been certified using runs tests, serial correlation tests, duplicates tests, permutation tests, vertical coupon collector tests as well as others.

- Arrive Software, Home of the Fair Choice  http://arrivesoftware.com/fair