At Xilinx, I developed two new ways to generate truly random numbers inside an FPGA. One was submitted as a patent (11/2003, still there) and the other given upon specific customer request. My manager and I wrote “Thats So Random” to tease customers into asking us about our solutions. We had a few responses and I enjoyed helping customers out knowing that they use the fruits of my work. As part of the patent application and verification of randomness, I had to do quite a bit of reading and research. Randomness is a very interesting because it is a statistical process as opposed to other engineering problems that are deterministic in nature (keyword “spec.”) One can not prove randomness, but rather evaluate how close a sequence is to what is statistically considered to be random. The more I read about it, the more complicated it got; it took me quite some time to get a handle on what p-values actually mean, for example. There exists many tests for randomness (see NIST and Diehard for example) but they are constantly under criticism over their methods and results. In other words, there is no definitive test by the very nature of the problem, and that makes it interesting, and sometimes confusing.
Of course, Scott Adams nailed the issue in 3 comic frames…
Accounting Troll: “Over here we have our random number generator.”
Number Generator Troll: “Nine Nine Nine Nine Nine Nine”
Dilbert: “Are you sure that’s random?”
Accounting Troll: “That’s the problem with randomness: you can never be sure.”
I was thinking about randomness again when I read Michael Larsen’s “Press Your Luck” story (via Schneier.) I won’t ruin the ending for you, but he managed to find a pattern in what was supposedly a random sequence of events for a handsome reward. How many systems have this flaw? A lot would be my guess. It would be interesting to look for some as part of my future research.