Statistical randomness

<h2 id="tests">Tests</h2>
Main article: <a href="/facts/Randomness_test/My9XgtxB">Randomness test</a>
The first tests for random numbers were published by <a href="/facts/M.G._Kendall/Vo8Sq4eb">M.G. Kendall</a> and <a href="/facts/Bernard_Babington_Smith/y4HIYI9z">Bernard Babington Smith</a> in the <a href="/facts/Journal_of_the_Royal_Statistical_Society/14Twyyg1">Journal of the Royal Statistical Society</a> in 1938.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> They were built on statistical tools such as <a href="/facts/Pearson%2527s_chi-squared_test/rGtoKuU6">Pearson's chi-squared test</a> that were developed to distinguish whether experimental phenomena matched their theoretical probabilities. Pearson developed his test originally by showing that a number of dice experiments by <a href="/facts/W.F.R._Weldon/GAfNv9Wj">W.F.R. Weldon</a> did not display "random" behavior.
Kendall and Smith's original four tests were <a href="/facts/Statistical_hypothesis_testing/yv9RPF6U">hypothesis tests</a>, which took as their <a href="/facts/Null_hypothesis/C8NwSE9J">null hypothesis</a> the idea that each number in a given random sequence had an equal chance of occurring, and that various other patterns in the data should be also distributed equiprobably.

<ul><li>The frequency test, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, 2s, 3s, etc.</li>
<li>The serial test, did the same thing but for sequences of two digits at a time (00, 01, 02, etc.), comparing their observed frequencies with their hypothetical predictions were they equally distributed.</li>
<li>The poker test, tested for certain sequences of five numbers at a time (AAAAA, AAAAB, AAABB, etc.) based on hands in the game <a href="/facts/Poker/bYSg9eCS">poker</a>.</li>
<li>The gap test, looked at the distances between zeroes (00 would be a distance of 0, 030 would be a distance of 1, 02250 would be a distance of 3, etc.).</li></ul>
If a given sequence was able to pass all of these tests within a given degree of significance (generally 5%), then it was judged to be, in their words "locally random". Kendall and Smith differentiated "local randomness" from "true randomness" in that many sequences generated with truly random methods might not display "local randomness" to a given degree — very large sequences might contain many rows of a single digit. This might be "random" on the scale of the entire sequence, but in a smaller block it would not be "random" (it would not pass their tests), and would be useless for a number of statistical applications.
As random number sets became more and more common, more tests, of increasing sophistication were used. Some modern tests plot random digits as points on a three-dimensional plane, which can then be rotated to look for hidden patterns. In 1995, the statistician <a href="/facts/George_Marsaglia/Jlu1Defc">George Marsaglia</a> created a set of tests known as the <a href="/facts/Diehard_tests/6jj2Kylt">diehard tests</a>, which he distributes with a <a href="/facts/CD-ROM/JwuaYLJv">CD-ROM</a> of 5 billion <a href="/facts/Pseudorandom/kfs1wfhY">pseudorandom</a> numbers. In 2015, <a href="/facts/Yongge_Wang/NnJyFQFX">Yongge Wang</a> distributed a Java software package <a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> for statistically distance based randomness testing.
<a href="/facts/Pseudorandom_number_generator/sIrCxIBq">Pseudorandom number generators</a> require tests as exclusive verifications for their "randomness," as they are decidedly not produced by "truly random" processes, but rather by deterministic algorithms. Over the history of random number generation, many sources of numbers thought to appear "random" under testing have later been discovered to be very non-random when subjected to certain types of tests. The notion of <a href="/facts/Quasi-random/phAlucUw">quasi-random</a> numbers was developed to circumvent some of these problems, though pseudorandom number generators are still extensively used in many applications (even ones known to be extremely "non-random"), as they are "good enough" for most applications.
Other tests:

<ul><li>The Monobit test treats each output bit of the random number generator as a coin flip test, and determine if the observed number of heads and tails are close to the expected 50% frequency. The number of heads in a coin flip trail forms a <a href="/facts/Binomial_distribution/UMoFMjDj">binomial distribution</a>.</li>
<li>The <a href="/facts/Wald%25E2%2580%2593Wolfowitz_runs_test/q42y5dVE">Wald–Wolfowitz runs test</a> tests for the number of bit transitions between 0 bits, and 1 bits, comparing the observed frequencies with expected frequency of a random bit sequence.</li>
<li><a href="/facts/Information_entropy/NLg4NLvt">Information entropy</a></li>
<li><a href="/facts/Autocorrelation/dm4MqK0A">Autocorrelation</a> test</li>
<li><a href="/facts/Kolmogorov%25E2%2580%2593Smirnov_test/Kr5MqpfH">Kolmogorov–Smirnov test</a></li>
<li>Statistically distance based randomness test. <a href="/facts/Yongge_Wang/NnJyFQFX">Yongge Wang</a> showed <a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> that NIST SP800-22 testing standards are not sufficient to detect some weakness in randomness generators and proposed statistically distance based randomness test.</li>
<li><a href="/facts/Spectral_density_estimation/JefWFBsx">Spectral Density Estimation</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> - performing a Fourier transform on a "random" signal transforms it into a sum of periodic functions in order to detect non random repetitive trends</li>
<li>Maurer's Universal Statistical Test</li>
<li>The <a href="/facts/Diehard_tests/6jj2Kylt">Diehard tests</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Algorithmic_randomness/n0UTETlJ">Algorithmic randomness</a></li>
<li><a href="/facts/Complete_spatial_randomness/bdyuoY75">Complete spatial randomness</a></li>
<li><a href="/facts/Normal_number/nGb5cM0y">Normal number</a></li>
<li><a href="/facts/One-time_pad/03hA9XSQ">One-time pad</a></li>
<li><a href="/facts/Random_error/q7pa7bRt">Random error</a></li>
<li><a href="/facts/Randomness/QJQBoEX5">Randomness</a></li>
<li><a href="/facts/Randomness_tests/My9XgtxB">Randomness tests</a></li>
<li><a href="/facts/Statistical_hypothesis_testing/yv9RPF6U">Statistical hypothesis testing</a></li>
<li><a href="/facts/Seven_states_of_randomness/S84kaJnt">Seven states of randomness</a></li>
<li><a href="/facts/TestU01/KgAIUzr6">TestU01</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.phy.duke.edu/~rgb/General/rand_rate.php">DieHarder</a>: A free (<a href="/facts/GNU_General_Public_License/S75KhLSX">GPL</a>) <a href="/facts/C_(programming_language)/Ky2No763">C</a> Random Number Test Suite.</li>
<li><a href="http://www.sitmo.com/doc/Generating_Normal_Distributed_Random_Numbers">Generating Normal Distributed Random Numbers</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Pi seems a good random number generator – but not always the best, Chad Boutin, Purdue University <a href="https://www.purdue.edu/uns/html4ever/2005/050426.Fischbach.pi.html" target="_blank">https://www.purdue.edu/uns/html4ever/2005/050426.Fischbach.pi.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Kendall, M.G.; Smith, B. Babington (1938). "Randomness and Random Sampling Numbers". Journal of the Royal Statistical Society. 101 (1): 147–166. doi:10.2307/2980655. JSTOR 2980655. <a href="/wiki/M.G._Kendall" target="_blank">/wiki/M.G._Kendall</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Yongge Wang. Statistical Testing Techniques For Pseudorandom generation. http://webpages.uncc.edu/yonwang/liltest/ <a href="http://webpages.uncc.edu/yonwang/liltest/" target="_blank">http://webpages.uncc.edu/yonwang/liltest/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Yongge Wang: On the Design of LIL Tests for (Pseudo) Random Generators and Some Experimental Results. PDF <a href="http://webpages.uncc.edu/yonwang/papers/liltest.pdf" target="_blank">http://webpages.uncc.edu/yonwang/papers/liltest.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Wang, Yongge; Nicol, Tony (2015). "Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL". Computers and Security. 53: 44–64. doi:10.1016/j.cose.2015.05.005. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Knuth, Donald (1998). The Art of Computer Programming Vol. 2 : Seminumerical Algorithms. Addison Wesley. pp. 93–118. ISBN 978-0-201-89684-8. <a href="978-0-201-89684-8" target="_blank">978-0-201-89684-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Statistical randomness open-in-new

Statistical randomness