Saturday, January 9, 2010

Nonrandom random generators

I often glean insights from odd sources. Over the holidays I read Pythagoras’ Revenge (Princeton University Press, 2009), a mathematical mystery by Arturo Sangalli. His goal was not to write the best mystery ever (he didn’t) but to introduce mathematical concepts, “some of them rather challenging and with philosophical undertones, in an entertaining way.” (p. ix)

One of these concepts is that “all random number algorithms being used in computer programs are in fact only pseudo random, and not simply for lack of ingenuity on the part of the mathematicians who created them but due to the existence of an essential barrier inherent in the concept of ‘randomness’ itself.” The problem is this: randomness is equivalent to incompressibility. That is, there is no shorter way to describe a random binary sequence than to list all its bits. So “any sequence s whose bits are obtained by executing a computer program is automatically compressible (for the program is a compressed version of s) and hence it is nonrandom.” (p. 72)

I doubt that this nonrandom quality of so-called random generators will create dramatic errors in trading algorithms; we don’t use particularly long sequences. The problem arises when “billions of those random numbers are employed to simulate the evolution of a complex system.” In this case “the accuracy of the final results may directly depend on the quality of the ‘randomness’ built into the program.” (p. 71)

But even though we shouldn’t lie awake at night worrying about the reliability of the random generators we use, I thought this point was worth sharing. I for one love tramping around in the world of paradoxes and quasi-paradoxes.

No comments:

Post a Comment