The Art of Computer Programming: Random Numbers

When you step back to think about it, a <i>huge</i> amount of CS theory papers rely on this hand-wavy definition of &quot;randomness&quot; to prove something. Oddly, though, if you actually press a CS theory person for a mathematical definition of this concept, they virtually always draw a blank.<p>As a student I remember thinking that this was <i>incredibly</i> alarming. Without a good understanding of this concept, how can we be sure any of what we&#x27;re saying is even remotely correct?<p>What Knuth has given us here is the ideal treatment of the subject, essentially putting the question of what randomness is, to rest for good. He starts by taking a comprehensive, entertaining history of the landscape (in short: researchers ping-ponged between having definitions of randomness so strict that nothing was random, and so loose that they were all pathologically predictable) before finally proving a theorem that completely solves the problem.<p>It is a monumental accomplishment in the field, and it is quite shocking to me that it&#x27;s still so obscure. It&#x27;s one of my favorite results in all of CS, anywhere.<p>If you haven&#x27;t had the chance, I highly recommend the rest of this volume (Seminumerical Algorithms). It is just stuffed with other surprising, amazing results.

This reminds me of a (somewhat) funny situation that happened to me one time. My parents bought some Lotto tickets and wanted to play, so they filled most of the combinations themselves and left two of them for me. I was annoyed by having to do that, so I take the tickets, and ask my dad, &quot;So, you know that every combination is equally likely to win?&quot;, and he casually replies something like, &quot;Yeah, sure, I&#x27;m not dumb&quot;.<p>So just to get done with it, I pick 1, 2, 3, 4, 5, 6 and 7 on one combo and 8, 9, 10, 11, 12, 13 and 14 on the other. I give it to him, when he throws his hands in the air and angrily says, &quot;What the hell? You just wasted two combinations, these numbers are never going to get drawn!&quot;<p>It handily illustrates how hard it is to grasp the concept of true randomness and probability, and even if you do get it, sometimes you&#x27;ll be caught off guard and your psychological biases will kick in.

Once you&#x27;ve got pseudorandom bits working, the next step is generating variates from different distributions. Luc Devroye has a nice book on this freely available online, &quot;Non-Uniform Random Variate Generation&quot;. <a href="http://luc.devroye.org/rnbookindex.html" rel="nofollow">http:&#x2F;&#x2F;luc.devroye.org&#x2F;rnbookindex.html</a>

Do the Monte Carlo people all know about Barash and Shchur&#x27;s work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn&#x27;t exist just a few years ago. You still need to be careful in various ways, but this helps a lot. A lot, a lot.<p>[1] <a href="http://arxiv.org/pdf/1307.5866.pdf" rel="nofollow">http:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1307.5866.pdf</a>

I feel compelled to share this quote from the author of <i>cfengine</i> with whom I have had some emails of late, because it neatly summarizes a more holistic, physics-inspired approach to the computational world&#x27;s obsession with invariance, which could be seen as present in the quest for &#x27;randomness&#x27;.<p><i>The simplest idea of stability is constancy, or invariance. A thing that has no possibility to change is, by definition, immune to external pertubations. [...] Invariance is an important concept, but also one that has been shattered by modern ideas of physics.</i> What was once considered invariant, is usually only apparently invariant on a certain scale. <i>When one looks in more detail, we find that we may only have invariance of an average.</i> - Mark Burgess, <i>In Search of Certainty: The Science of Our Information Infrastructure</i> (2013)<p>This accords well with the opening quotation <i>Lest men suspect your tale untrue, Keep probability in view.</i> - John Gay, English poet and dramatist and member of the Scriblerus Club (1727) <a href="https://en.wikipedia.org/wiki/John_Gay" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;John_Gay</a>

I&#x27;m not sure why, but I struggled with the concept of randomness in my algorithms class. On the last day of class, the professor signed his book, &quot;May you one day explain randomness to all of us&quot;

This is old material, right? Or is Knuth publishing a new fascicle?