Re:“RNG broken for last 4 months”
by compbio on Tuesday February 17, 2015 @09:10PM
(#9066615)
Proving "randomness" is impossible, akin to finding the shortest program to reproduce a larger string (Kolmogorov complexity). Strings are Kolmogorov Random when they can not possibly be compressed any further by any program: Kolmogorov Random strings simply have no predictable information left to use for further compression. But Kolmogorov Complexity (KC) can not be computed, since that causes a paradox, much like "A description of the natural number that can not be described in less than fifty English words".
But we can of course talk about a degree of randomness, like we can also try to approach KC. Good randomness is all about unpredictability (given the first half of a random string, can you use that to predict the second half?), but that does not mean that proper randomness should be void of identifiable patterns (such as "00000000111111111" in a random binary string). Such orderly-looking patterns do appear in proper randomness, because the absence of those patterns would make the randomness more predictable, not less.
You can measure level of randomness with statistical methods [1], compression [2], visual methods [3] and die-hard tests [4]
[1] A simple method is the chi-square test.
[2] Compression ratio tells us something about the randomness. Random data can not be compressed by everyday-use compressors. That no one claimed the money for the challenge to compress RAND's digits in a binary file tells us something about the rigor that team had in coming up with random numbers. The more you can compress a string, the more order it contains and the more predictable it is.
[3] You can plot random points inside a circle. After a lot of points are added, you should see no patterns and a properly, evenly spaced circle. Another method are Moiré patterns: Take a field of random noise, copy it, slightly rotate it, and overlay. Non-random patterns will become more visible. But these patterns are visible without Moiré rotation too when using very basic PRNG's like the standard Python random library.
But we can of course talk about a degree of randomness, like we can also try to approach KC. Good randomness is all about unpredictability (given the first half of a random string, can you use that to predict the second half?), but that does not mean that proper randomness should be void of identifiable patterns (such as "00000000111111111" in a random binary string). Such orderly-looking patterns do appear in proper randomness, because the absence of those patterns would make the randomness more predictable, not less.
You can measure level of randomness with statistical methods [1], compression [2], visual methods [3] and die-hard tests [4]
[1] A simple method is the chi-square test.
[2] Compression ratio tells us something about the randomness. Random data can not be compressed by everyday-use compressors. That no one claimed the money for the challenge to compress RAND's digits in a binary file tells us something about the rigor that team had in coming up with random numbers. The more you can compress a string, the more order it contains and the more predictable it is.
[3] You can plot random points inside a circle. After a lot of points are added, you should see no patterns and a properly, evenly spaced circle. Another method are Moiré patterns: Take a field of random noise, copy it, slightly rotate it, and overlay. Non-random patterns will become more visible. But these patterns are visible without Moiré rotation too when using very basic PRNG's like the standard Python random library.
[4] The programmer's way of brute-forcing a lot of simulation runs to see if the PRNG works as expected: http://en.wikipedia.org/wiki/Diehard_tests