Randomness tests - Revision history

Martin.zima: improved formatting

2016-01-25T10:56:22Z

improved formatting

Martin.zima: adding a few illustrations + corrections

2016-01-25T10:50:36Z

adding a few illustrations + corrections

Martin.zima: more tests

2016-01-25T01:36:20Z

more tests

Martin.zima: tests wip

2016-01-24T23:53:35Z

tests wip

Martin.zima: created (work in progress)

2016-01-24T22:58:22Z

created (work in progress)

New page

When dealing with random values and their sources (often commonly referred-to as random number generators, RNGs), it is important to know what behavior we may expect from used generators. To ensure the used RNG implementations meet certain levels of required quality (randomness), one can carry out various tests specifically designed to verify such properties (sometimes called ‘randomness tests’). In the worse-case scenarios, use of an inappropriate randomization source may have fatal consequences for the systems involved – ranging from simulation results being completely irrelevant to serious security vulnerabilities because of cryptographic weaknesses.

== Introduction ==

In the [[Pseudorandom_number_generators|previous chapters]] of this textbook, we have explained what pseudorandom number generators (PRNGs) are, their areas of application and why is it both difficult and important for computers to generate truly random numbers (or at least try to). Even when using quality seed sources (which may also include various truly random values), as long we are using deterministic algorithms to generate the output values, the best result we can get is just pseudo-random. However, given such algorithm or, in general, any other (possibly black-boxed or unknown) value source, we might want to analyze and measure the actual ‘randomness’ of their output, and in consequence also the quality of the considered source.

== Definition ==

Because the requirements for such source will greatly differ, we should first start off by defining what a ‘random value’ means in our context of system simulations. To consider a set of values random, we usually should be able to state that independently for every single item, the probability of it having a certain value should be equal to probability of having any other value (or at least for it to appear so to a certain degree). In terms of our random number generators, this would mean we usually will require that the probability of occurrence of all possible values will correspond to a certain probability distribution, usually the '''uniform distribution''' (this is the case for most PRNGs). In consequence, the resulting set of values should be absent of any detectable, non-random patterns.

<div style="background-color: #F6FDEA; border: 1px solid #D6E434; padding: 0.7em; margin-left: 2em; margin-right: 2em;">For simplicity, we will now omit the extra intricacies that cryptographically-secure pseudo-random number generators (CSPRNGs) entail and focus on the more general case of regular pseudo-random number generators. CSPRNGs are usually also required to guarantee to be unpredictable - given a number of previously generated values (but not the generator's internal state), it should be impossible (using reverse engineering or other methods) to predict any future values - aka passing the next-bit test. They usually also have a lot more sophisticated seed-derivation procedure and in general they serve a slightly different purpose than the other generators - proper design and testing of a CSPRNG is a complicated case of its own.</div>

The problem with testing randomness is that given any (pseudo-random-generated) data, one can never truly determine their real randomness - and can only make a good guess at best (on a side note - I remember seeing this humorously commented in a Dilbert strip a long time ago <ref>Dilbert Comic Strip on 2001-10-25. Dilbert by Scott Adams [online]. 2001 [2016-01-24]. Available at: http://dilbert.com/strip/2001-10-25</ref>). Although we cannot determine whether the true randomness of data, there is a number of options available to measure and quantify how much random the generated values appear to be - or to be more precise, how well the values fit the aforementioned 'randomness' specifications. Whether a generator passes such test is then only a matter of the limits of what we accept as sufficiently random - either the test results fall into our considered ranges and the generator succeeds, or they do not and it fails (and these criteria will differ for different PRNG use scenarios). To carry out most of those tests, we usually will operate on a set of data of specific fixed length - for obvious reasons, we cannot test an infinitely long (or generally too long, for that matter) dataset, meaning the values will usually be only a part of the random sequences a generator can produce - yet it still should be long enough (or the test should get repeated enough times) to 1) statistically eliminate the effect of patterns that will always occur in any shorter sequences by a chance and 2) to reveal possible algorithm deficiencies that might occur over longer periods of values (like recurring patterns after a full cycle of all values of a PRNG).

== Tests ==

One of the first authors to discuss PRNG randomness testing was Donald Knuth in his book The Art of Computer Programming: Volume 2: Seminumerical Algorithms (1969) <ref name="knuth">KNUTH, Donald Ervin. The art of computer programming. 3rd ed. Reading: Addison-Wesley Publishing Company, 1998, xiii, 762 s. Classic work newly updated and revised. ISBN 0-201-89684-2.</ref>, presenting a complete battery of statistical tests mostly operating on empirical data of the generators. This battery of test was later adapted and extended by George Marsaglia in 1996 in his Diehard Battery of Tests of Randomness, also accompanied by test implementations in ANSI C language <ref>The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness. Florida State University Department of Statistics [online]. [2016-01-24]. Available at: http://stat.fsu.edu/pub/diehard/</ref>.

Some of the most common tests included in those batteries are described in following chapters.

=== Equidistribution test ===

One of the discussed requirements that a sequence must meet in order to be considered random is the uniform distribution of values in it. To verify that assumption, we can verify the frequency of every possible value in the result set and compare it with an expected probability distribution (i.e. uniform distribution). Generally speaking, there are two common methods that may be used to achieve this, the first being the Kolmogorov–Smirnov test. An alternative approach to this is using the (Pearson's) Chi-squared test, which is usable if we consider a smaller group of discrete values.

Because the equidistribution of single values itself is only a part of the requirements ensuring randomness, Knuth <ref name="knuth"/> also suggests extending this method to testing the frequency of pairs or other longer specific subsequences in the resulting sequence as a whole. Every of the combinations in one of those considered groups should be 'uniformly distributed in an independent manner'.

=== Autocorrelation ===

Autocorrelation (also known as serial correlation) is a term in statistics describing a correlation between values of a function or data at different points in time.

=== Gap test ===

== External links ==

* [http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/CUJ/1996/9606/dwyer/dwyer.htm Testing Random Number Generators - Jerry Dwyer and K.B. Williams, 1996]
* [http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/CUJ/1996/9608/dwyer/dwyer.htm Testing Random Number Generators, Part 2 - Jerry Dwyer and K.B. Williams, 1996]
* [http://stat.fsu.edu/pub/diehard/ The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness]

== References ==

<references />

@@ Line 7: / Line 7: @@
 == Definition ==
-Because the requirements for such source will greatly differ, we should first start off by defining what a ‘random value’ means in our context of system simulations. To consider a set of values random, we usually should be able to state that independently for every single item, the probability of it having a certain value should be equal to probability of having any other value (or at least for it to appear so to a certain degree). In terms of our random number generators, this would mean we usually will require that the probability of occurrence of all possible values will correspond to a certain probability distribution, usually the '''uniform distribution''' (this is the case for most PRNGs). In consequence, the resulting set of values should be absent of any detectable, non-random patterns.
+Because the requirements for such source will greatly differ, we should first start off by defining what a ‘random value’ means in our context of system simulations. To consider a set of values random, we usually should be able to state that independently for every single item, the probability of it having a certain value should be equal to probability of having any other value (or at least for it to appear so to a certain degree). In terms of our random number generators, this would mean we usually will require that the probability of occurrence of all possible values will correspond to a certain probability distribution, usually the '''uniform distribution''' (this is the case for most PRNGs). In consequence, the resulting set of values should be '''absent of''' any detectable, non-random '''patterns'''.
-The problem with testing randomness is that given any (pseudo-random-generated) data, one can never truly determine their real randomness - and can only make a good guess at best (on a lighter note - there is a Dilbert comic strip humorously commenting this fact <ref>Dilbert Comic Strip on 2001-10-25. Dilbert by Scott Adams [online]. 2001 [2016-01-24]. Available at: http://dilbert.com/strip/2001-10-25</ref>). Although we cannot determine whether the true randomness of data, there is a number of options available to measure and quantify how much random the generated values appear to be - or to be more precise, how well the values fit the aforementioned 'randomness' specifications. Whether a generator passes such test is then only a matter of the limits of what we accept as sufficiently random - either the test results fall into our considered ranges and the generator succeeds, or they do not and it fails (and these criteria will differ for different PRNG use scenarios). To carry out most of those tests, we usually will operate on a set of data of specific fixed length - for obvious reasons, we cannot test an infinitely long (or generally too long, for that matter) dataset, meaning the values will usually be only a part of the random sequences a generator can produce - yet it still should be long enough (or the test should get repeated enough times) to 1) statistically eliminate the effect of patterns that will always occur in any shorter sequences by a chance and 2) to reveal possible algorithm deficiencies that might occur over longer periods of values (like recurring patterns after a full cycle of all values of a PRNG).
+[[File:Unif_pmf_graph.png|thumb|center|[[Probability distributions#Uniform distribution - discrete|Discrete uniform distribution]]]]
 <div style="background-color: #F6FDEA; border: 1px solid #D6E434; padding: 0.7em; margin-left: 2em; margin-right: 2em; font-size: 0.9em">For simplicity, we omit the extra intricacies that '''cryptographically-secure pseudo-random number generators''' (CSPRNGs) entail and focus on the more general case of regular pseudo-random number generators. CSPRNGs are usually required to guarantee to be unpredictable - given a number of previously generated values (but not the generator's internal state), it should be impossible (using reverse engineering or other methods) to successfully predict any future values - aka passing the next-bit test. They usually also have a lot more sophisticated seed-derivation procedure and in general they serve a slightly different purpose than the other generators - proper design and testing of a CSPRNG is a complicated case of its own.</div>
@@ Line 17: / Line 19: @@
 Some of the most common tests included in those batteries are described in following chapters.
 === Equidistribution test ===
@@ Line 41: / Line 41: @@
 === Poker test ===
-Poker test, as the name inspired by the classic card game suggests, is observing the amount of matching values in a number of groups of five elements. Based on the amount of distinct values (cards), we make a Chi-squared test comparing the counts with an expected probability distribution <ref name="knuth"/>.
+Poker test, as the name inspired by the classic card game suggests, is observing the '''number of matching values''' in a number of groups of five elements. Based on the amount of distinct values (cards), we make a Chi-squared test comparing the counts with an expected probability distribution <ref name="knuth"/>.
 === Spectral test ===
@@ Line 60: / Line 60: @@
 === Other tests ===
-Among other commonly suggested tests we may also mention the Monte Carlo PI value estimation, simple arithmetic mean or information entropy calculation (which may also be easily tested by simply compressing the considered data using any well known compression software and compare the compression ratios) <ref>ENT. Pseudorandom Number Sequence Test Program [online]. [cit. 2016-01-25]. Available at: http://www.fourmilab.ch/random/</ref>, gap test, coupon-collector test, tests using Walsh-Hadamard transform <ref>Feldman, F. 1987. Fast Spectral Tests for Measuring Nonrandomness and the DES. Advances in Cryptology -- CRYPTO '87. 243-254. Springer-Verlag.</ref>, birthday spacing test (measuring distances between randomly chosen points on a large interval) and many other similar tests <ref name="diehard"/>.
+Among other commonly suggested tests we may also mention the '''Monte Carlo PI value estimation''', simple arithmetic mean or information '''entropy calculation''' (which may also be easily tested by simply compressing the considered data using any well known compression software and compare the compression ratios) <ref>ENT. Pseudorandom Number Sequence Test Program [online]. [cit. 2016-01-25]. Available at: http://www.fourmilab.ch/random/</ref>, gap test, coupon-collector test, tests using '''Walsh-Hadamard transform''' <ref>Feldman, F. 1987. Fast Spectral Tests for Measuring Nonrandomness and the DES. Advances in Cryptology -- CRYPTO '87. 243-254. Springer-Verlag.</ref>, birthday spacing test (measuring distances between randomly chosen points on a large interval) and many other similar tests <ref name="diehard"/>.
 == Recommended reading ==

@@ Line 3: / Line 3: @@
 == Introduction ==
-In the [[Pseudorandom_number_generators|previous chapters]] of this textbook, we have explained what pseudorandom number generators (PRNGs) are, their areas of application and why is it both difficult and important for computers to generate truly random numbers (or at least try to). Even when using quality seed sources (which may also include various truly random values), as long we are using deterministic algorithms to generate the output values, the best result we can get is just pseudo-random. However, given such algorithm or, in general, any other (possibly black-boxed or unknown) value source, we might want to analyze and measure the actual ‘randomness’ of their output, and in consequence also the quality of the considered source.
+In the [[Pseudorandom_number_generators|previous chapters]] of this textbook, we have explained what '''pseudorandom number generators''' (PRNGs) are, their areas of application and why is it both difficult and important for computers to generate truly random numbers (or at least try to). Even when using quality seed sources (which may also include various truly random values), as long we are using deterministic algorithms to generate the output values, the best result we can get is just pseudo-random. However, given such algorithm or, in general, any other (possibly black-boxed or unknown) value source, we might want to analyze and measure the actual ‘randomness’ of their output, and in consequence also the quality of the considered source.
 == Definition ==
@@ Line 11: / Line 11: @@
 The problem with testing randomness is that given any (pseudo-random-generated) data, one can never truly determine their real randomness - and can only make a good guess at best (on a lighter note - there is a Dilbert comic strip humorously commenting this fact <ref>Dilbert Comic Strip on 2001-10-25. Dilbert by Scott Adams [online]. 2001 [2016-01-24]. Available at: http://dilbert.com/strip/2001-10-25</ref>). Although we cannot determine whether the true randomness of data, there is a number of options available to measure and quantify how much random the generated values appear to be - or to be more precise, how well the values fit the aforementioned 'randomness' specifications. Whether a generator passes such test is then only a matter of the limits of what we accept as sufficiently random - either the test results fall into our considered ranges and the generator succeeds, or they do not and it fails (and these criteria will differ for different PRNG use scenarios). To carry out most of those tests, we usually will operate on a set of data of specific fixed length - for obvious reasons, we cannot test an infinitely long (or generally too long, for that matter) dataset, meaning the values will usually be only a part of the random sequences a generator can produce - yet it still should be long enough (or the test should get repeated enough times) to 1) statistically eliminate the effect of patterns that will always occur in any shorter sequences by a chance and 2) to reveal possible algorithm deficiencies that might occur over longer periods of values (like recurring patterns after a full cycle of all values of a PRNG).
-<div style="background-color: #F6FDEA; border: 1px solid #D6E434; padding: 0.7em; margin-left: 2em; margin-right: 2em; font-size: 0.9em">For simplicity, we omit the extra intricacies that cryptographically-secure pseudo-random number generators (CSPRNGs) entail and focus on the more general case of regular pseudo-random number generators. CSPRNGs are usually required to guarantee to be unpredictable - given a number of previously generated values (but not the generator's internal state), it should be impossible (using reverse engineering or other methods) to successfully predict any future values - aka passing the next-bit test. They usually also have a lot more sophisticated seed-derivation procedure and in general they serve a slightly different purpose than the other generators - proper design and testing of a CSPRNG is a complicated case of its own.</div>
+<div style="background-color: #F6FDEA; border: 1px solid #D6E434; padding: 0.7em; margin-left: 2em; margin-right: 2em; font-size: 0.9em">For simplicity, we omit the extra intricacies that '''cryptographically-secure pseudo-random number generators''' (CSPRNGs) entail and focus on the more general case of regular pseudo-random number generators. CSPRNGs are usually required to guarantee to be unpredictable - given a number of previously generated values (but not the generator's internal state), it should be impossible (using reverse engineering or other methods) to successfully predict any future values - aka passing the next-bit test. They usually also have a lot more sophisticated seed-derivation procedure and in general they serve a slightly different purpose than the other generators - proper design and testing of a CSPRNG is a complicated case of its own.</div>
 == Tests ==
@@ Line 17: / Line 17: @@
 Some of the most common tests included in those batteries are described in following chapters.
 === Equidistribution test ===
-One of the discussed requirements that a sequence must meet in order to be considered random is the uniform distribution of values in it. To verify that assumption, we can verify the frequency of every possible value in the result set and compare it with an expected probability distribution (i.e. uniform distribution). Generally speaking, there are two common methods that may be used to achieve this, the first being the Kolmogorov–Smirnov test. An alternative approach to this is using the (Pearson's) Chi-squared test, which is usable if we consider a smaller group of discrete values.
+One of the discussed requirements that a sequence must meet in order to be considered random is the '''uniform distribution''' of values in it. To verify that assumption, we can verify the frequency of every possible value in the result set and compare it with an expected probability distribution (i.e. uniform distribution). Generally speaking, there are two common methods that may be used to achieve this, the first being the '''Kolmogorov–Smirnov test'''. An alternative approach to this is using the (Pearson's) '''Chi-squared test''', which is usable if we consider a smaller group of discrete values.
 Because the equidistribution of single values itself is only a part of the requirements ensuring randomness, Knuth <ref name="knuth"/> also suggests extending this method to testing the frequency of pairs or other longer specific subsequences in the resulting sequence as a whole. Every of the combinations in one of those considered groups should be 'uniformly distributed in an independent manner'.
@@ Line 26: / Line 28: @@
 === Autocorrelation ===
-Autocorrelation (also known as serial correlation) is a term in statistics describing a correlation between values of a function at different points in time or different elements in a value sequence. As proposed by Knuth <ref name="knuth"/>, for every single value, we compute the serial correlation coefficient between the value and a value preceding it. However, it is also be possible to calculate and measure many other variants of this coefficient for other consecutive elements. Truly random sequences should tend to have a smaller autocorrelation coefficient between its elements.
+Autocorrelation (also known as '''serial correlation''') is a term in statistics describing a correlation between values of a function at different points in time or different elements in a value sequence. As proposed by Knuth <ref name="knuth"/>, for every single value, we compute the serial correlation coefficient between the value and a value preceding it. However, it is also be possible to calculate and measure many other variants of this coefficient for other consecutive elements. Truly random sequences should tend to have a '''smaller autocorrelation coefficient''' between its elements.
 Given consecutive values Y1, Y2, ..., YN and lag k, the autocorrelation coefficient is defined as follows:
 [[File:Randomness-test-formula-3.gif]]
 === Run tests ===
-The idea behind this kind of test is to count the "runs up" and "runs down" in the output sequence. A "run up" is an ascending subsequence of numbers, where for every element [[File:Randomness-test-formula-1.gif]], and conversely [[File:Randomness-test-formula-2.gif]] for descending "run downs". The counts of these runs and their length should adhere to a certain probability distribution. Wald–Wolfowitz runs test is a specific case of this test targeting sequences of binary values.
+The idea behind this kind of test is to count the "runs up" and "runs down" in the output sequence. A "run up" is an ascending subsequence of numbers, where for every element [[File:Randomness-test-formula-1.gif]], and conversely [[File:Randomness-test-formula-2.gif]] for descending "run downs". The counts of these runs and their length should adhere to a certain probability distribution. Wald–Wolfowitz runs test is a specific case of this test targeting sequences of binary values. [http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/CUJ/1996/9606/dwyer/dwyer.htm]
 === Spectral test ===
-Unlike the most of previously mentioned tests, the spectral test operates on a full cycle (period) of a PRNG, more specifically a [[Pseudorandom_number_generators|linear congruential generator]] (LCG, a type of PRNG) <ref>WILLIAMS, Williams a Jerry DWYER. Testing Random Number Generators, Part 2. Dr. Dobb's Journal [online]. 1996 [2016-01-25]. Available at: http://drdobbs.com/184403208</ref>. This test examines the lattice structures of those LCG-generated values by projecting values of every n consecutive elements onto n (theoretical) dimensions.
+Unlike the most of previously mentioned tests, the spectral test operates on a '''full cycle''' (period) of a PRNG, more specifically a [[Pseudorandom_number_generators|linear congruential generator]] (LCG, a type of PRNG) <ref>WILLIAMS, Williams a Jerry DWYER. Testing Random Number Generators, Part 2. Dr. Dobb's Journal [online]. 1996 [2016-01-25]. Available at: http://drdobbs.com/184403208</ref>. This test examines the lattice structures of those LCG-generated values by projecting values of every n consecutive elements onto n (theoretical) dimensions and measures their random distribution [https://www.cs.indiana.edu/~kapadia/project2/node20.html] [http://random.mat.sbg.ac.at/tests/theory/spectral/] [http://random.mat.sbg.ac.at/results/karl/server/node3.html].
 [[File:Randu.png|thumb|center|RANDU LCG implementation failing the test in three dimensions (notice that all of the points fall in one of the planes), source: [https://commons.wikimedia.org/wiki/File:Randu.png|Wikimedia.org]]]
 === Other tests ===
-Among other commonly suggested tests we may also mention the Monte Carlo PI value estimation, simple arithmetic mean or information entropy calculation (which may also be easily tested by simply compressing the considered data using any well known compression software and compare the compression ratios) <ref>ENT. Pseudorandom Number Sequence Test Program [online]. [cit. 2016-01-25]. Available at: http://www.fourmilab.ch/random/</ref>, gap test, coupon-collector test, birthday spacing test (measuring distances between randomly chosen points on a large interval) and many other similar tests <ref name="diehard"/>.
+Among other commonly suggested tests we may also mention the Monte Carlo PI value estimation, simple arithmetic mean or information entropy calculation (which may also be easily tested by simply compressing the considered data using any well known compression software and compare the compression ratios) <ref>ENT. Pseudorandom Number Sequence Test Program [online]. [cit. 2016-01-25]. Available at: http://www.fourmilab.ch/random/</ref>, gap test, coupon-collector test, tests using Walsh-Hadamard transform <ref>Feldman, F. 1987. Fast Spectral Tests for Measuring Nonrandomness and the DES. Advances in Cryptology -- CRYPTO '87. 243-254. Springer-Verlag.</ref>, birthday spacing test (measuring distances between randomly chosen points on a large interval) and many other similar tests <ref name="diehard"/>.
-== External links ==
+== Recommended reading ==
 * [http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/CUJ/1996/9606/dwyer/dwyer.htm Testing Random Number Generators - Jerry Dwyer and K.B. Williams, 1996]
@@ Line 51: / Line 68: @@
 * [http://stat.fsu.edu/pub/diehard/ Diehard Battery of Tests of Randomness - The Marsaglia Random Number CDROM]
 * [http://www.fourmilab.ch/random/ ENT - A Pseudorandom Number Sequence Test Program]
 == References ==
 <references />

@@ Line 9: / Line 9: @@
 Because the requirements for such source will greatly differ, we should first start off by defining what a ‘random value’ means in our context of system simulations. To consider a set of values random, we usually should be able to state that independently for every single item, the probability of it having a certain value should be equal to probability of having any other value (or at least for it to appear so to a certain degree). In terms of our random number generators, this would mean we usually will require that the probability of occurrence of all possible values will correspond to a certain probability distribution, usually the '''uniform distribution''' (this is the case for most PRNGs). In consequence, the resulting set of values should be absent of any detectable, non-random patterns.
-<div style="background-color: #F6FDEA; border: 1px solid #D6E434; padding: 0.7em; margin-left: 2em; margin-right: 2em;">For simplicity, we will now omit the extra intricacies that cryptographically-secure pseudo-random number generators (CSPRNGs) entail and focus on the more general case of regular pseudo-random number generators. CSPRNGs are usually also required to guarantee to be unpredictable - given a number of previously generated values (but not the generator's internal state), it should be impossible (using reverse engineering or other methods) to predict any future values - aka passing the next-bit test. They usually also have a lot more sophisticated seed-derivation procedure and in general they serve a slightly different purpose than the other generators - proper design and testing of a CSPRNG is a complicated case of its own.</div>
+The problem with testing randomness is that given any (pseudo-random-generated) data, one can never truly determine their real randomness - and can only make a good guess at best (on a lighter note - there is a Dilbert comic strip humorously commenting this fact <ref>Dilbert Comic Strip on 2001-10-25. Dilbert by Scott Adams [online]. 2001 [2016-01-24]. Available at: http://dilbert.com/strip/2001-10-25</ref>). Although we cannot determine whether the true randomness of data, there is a number of options available to measure and quantify how much random the generated values appear to be - or to be more precise, how well the values fit the aforementioned 'randomness' specifications. Whether a generator passes such test is then only a matter of the limits of what we accept as sufficiently random - either the test results fall into our considered ranges and the generator succeeds, or they do not and it fails (and these criteria will differ for different PRNG use scenarios). To carry out most of those tests, we usually will operate on a set of data of specific fixed length - for obvious reasons, we cannot test an infinitely long (or generally too long, for that matter) dataset, meaning the values will usually be only a part of the random sequences a generator can produce - yet it still should be long enough (or the test should get repeated enough times) to 1) statistically eliminate the effect of patterns that will always occur in any shorter sequences by a chance and 2) to reveal possible algorithm deficiencies that might occur over longer periods of values (like recurring patterns after a full cycle of all values of a PRNG).
 == Tests ==
-One of the first authors to discuss PRNG randomness testing was Donald Knuth in his book The Art of Computer Programming: Volume 2: Seminumerical Algorithms (1969) <ref name="knuth">KNUTH, Donald Ervin. The art of computer programming. 3rd ed. Reading: Addison-Wesley Publishing Company, 1998, xiii, 762 s. Classic work newly updated and revised. ISBN 0-201-89684-2.</ref>, presenting a complete battery of statistical tests mostly operating on empirical data of the generators. This battery of test was later adapted and extended by George Marsaglia in 1996 in his Diehard Battery of Tests of Randomness, also accompanied by test implementations in ANSI C language <ref>The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness. Florida State University Department of Statistics [online]. [2016-01-24]. Available at: http://stat.fsu.edu/pub/diehard/</ref>.
+One of the first authors to discuss PRNG randomness testing was Donald Knuth in his book The Art of Computer Programming: Volume 2: Seminumerical Algorithms (1969) <ref name="knuth">KNUTH, Donald Ervin. The art of computer programming. 3rd ed. Reading: Addison-Wesley Publishing Company, 1998, xiii, 762 s. Classic work newly updated and revised. ISBN 0-201-89684-2.</ref>, presenting a complete battery of statistical tests mostly operating on empirical data of the generators. This battery of test was later adapted and extended by George Marsaglia in 1996 in his Diehard Battery of Tests of Randomness, also accompanied by test implementations in ANSI C language <ref name="diehard">The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness. Florida State University Department of Statistics [online]. [2016-01-24]. Available at: http://stat.fsu.edu/pub/diehard/</ref>.
 Some of the most common tests included in those batteries are described in following chapters.
@@ Line 27: / Line 26: @@
 === Autocorrelation ===
-Autocorrelation (also known as serial correlation) is a term in statistics describing a correlation between values of a function or data at different points in time. As proposed by Knuth <ref name="knuth"/>, for every single value, we compute the serial correlation coefficient between the value and a value preceding it. However, it is also be possible to calculate and measure many other variants of this coefficient for other consecutive elements. Truly random sequences should tend to have a smaller autocorrelation coefficient between its elements.
+Autocorrelation (also known as serial correlation) is a term in statistics describing a correlation between values of a function at different points in time or different elements in a value sequence. As proposed by Knuth <ref name="knuth"/>, for every single value, we compute the serial correlation coefficient between the value and a value preceding it. However, it is also be possible to calculate and measure many other variants of this coefficient for other consecutive elements. Truly random sequences should tend to have a smaller autocorrelation coefficient between its elements.
 === Run tests ===
-The idea behind this kind of test is to count the "runs up" and "runs down" in the output sequence. A "run up" is an ascending subsequence of numbers, where for every element [[File:Randomness-test-formula-1.gif]], and conversely [[File:Randomness-test-formula-2.gif]] for descending "run downs". The counts of these runs and their length should adhere to a certain probability distribution.
+The idea behind this kind of test is to count the "runs up" and "runs down" in the output sequence. A "run up" is an ascending subsequence of numbers, where for every element [[File:Randomness-test-formula-1.gif]], and conversely [[File:Randomness-test-formula-2.gif]] for descending "run downs". The counts of these runs and their length should adhere to a certain probability distribution. Wald–Wolfowitz runs test is a specific case of this test targeting sequences of binary values.
 == External links ==