Proving "randomness" is impossible, akin to finding the shortest program to reproduce a larger string (Kolmogorov complexity). Strings are Kolmogorov Random whe

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. [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 http://en.wikipedia.org/wiki/Diehard_tests