This is a geeky post. You've been warned.
Nature Science Update points to a new technical report that explains how a commonly used type of random number generator fails.
Like many good papers, it is based on a problem in Knuth's Art of Computer Programming. In this case it is exercise 3.3.2.31.
We measure the probablity that a run of length w (w odd) contains more "heads" than "tails" when produced by a recurrence relation in Z2. This probablity is almost never close to 1/2!
In the paper they explain why generators that generate random bits of 0 or 1 are fundamentally flawed. (This is oppossed to PNG's that generate 32 random bits at a time, etc.) They forcus on linear feedback shift register (LFSR) generators. It is pretty interesting reading. (Does that make me a geek? I read CS tech reports for fun, and I admit it.) Bear this in mind the next time you need a good pseudo-random number generator.
Comments