If you weren’t living in a cave you should know that I’ve been fairly interested in random number generators. Not just the pseudo- kind, of course, but I can’t really do much research about real RNGs without some proper funding. And sufficient motivation, because data collection is tedious. (The real reason is more like because I’m really clumsy with objects, and handling a hardware RNG so much probably isn’t going to make it last long.)
I recently torrented TAOCP (feeling guilt, will buy the book another time), just for volume 2 actually, because Seminumerical Algorithms. Which contains a chapter on pseudorandom number generators. It’s fairly interesting, but the age of the book precludes inclusion of more recent (but still rather dated) algorithms like ISAAC, but I’m pretty fine with just studying about simpler RNGs (by which I actually mean PRNG, but that’s an extra letter) if that means I get more solid (instead of empirical) results.
Summarising from the book, a sequence can be defined as random if every string of every length appears with the same probability. Hold on, this sounds just like the definition of normality… yeah. There’s actually a hardly-known RNG that uses the digits of a proven-to-be-normal-in-binary number, with the seed being where the digit reading starts. But there are simpler normal numbers. Considering for now just normality in base 2, a binary analogue of the Champernowne constant, could theoretically function as a perfect random number generator, but the obvious flaw is obvious:
The seed is essentially the random number itself. In other words, this is effectively like using a very large random number table. Sure, it’s random, but only asymptotically; it’s impossible to have a uniform distribution over the nonnegative integers, so there’ll inherently be some bias, and therefore predictability given sufficiently many digits of output, by autocorrelating and stuff.
(Last edited on February 24, 2011 at 2:08 pm. DRAFT QUEUE CLEARING.)
