{"id":157,"date":"2015-12-17T17:15:25","date_gmt":"2015-12-18T01:15:25","guid":{"rendered":"http:\/\/www.howardklein.net\/?p=157"},"modified":"2015-12-17T17:15:25","modified_gmt":"2015-12-18T01:15:25","slug":"random-adventures","status":"publish","type":"post","link":"https:\/\/www.howardklein.net\/?p=157","title":{"rendered":"Random() Adventures"},"content":{"rendered":"

Better to remain silent and be thought a fool than to speak and to remove all doubt.<\/em><\/p>\n

Often, but probably incorrectly<\/a>, attributed to Mark Twain<\/p>\n

 <\/p>\n

The idea of writing about random number generation (I mean, pseudo<\/em>-random number generation, but that term involves way too much typing) makes me extremely nervous.\u00a0 When it comes to that topic, I think of two groups of people:<\/p>\n

    \n
  1. The High Priesthood. The individuals (one or two dozen, in my imagination) who develop, test and understand these generators<\/li>\n
  2. The thousands who make fools of themselves writing about random numbers on the Internet.<\/li>\n<\/ol>\n

    I am definitely not in the first category; I\u2019ll keep my fingers crossed that this post doesn\u2019t put me solidly into the second.<\/p>\n

    Back in the day, when dinosaurs roamed the earth and computers were Big Machines in Large Rooms with Raised Floors, there was a popular expression in the industry \u2013 No one ever got fired for buying IBM<\/a>.<\/em> The Mersenne Twister<\/a> is the IBM of pseudo-random number generators.\u00a0 It\u2019s not the fastest or most efficient generator.\u00a0 It may or may not deliver the \u201cbest\u201d results (a debate I\u2019ll leave to the aforementioned priesthood). But it is fast enough, good enough and best-known of the modern vintage of random number generators \u2013 so it has become a de facto standard.\u00a0 If you were to recommend a different generator that I haven\u2019t heard of, I\u2019d probably ask how it compares to the Mersenne Twister.\u00a0 Python\u2019s random<\/code> module uses MT19937, the most commonly used (and heavily tested) version of Mersenne Twister.\u00a0 The standard library designers definitely could have chosen worse.\u00a0 But is it good enough for our discrete event simulator?<\/p>\n

    <\/p>\n

    Law<\/a> (Ch. 7) lists five properties of a \u201cgood\u201d random number generator for simulation purposes:<\/p>\n

      \n
    1. The output should be uniformly distributed on the interval [0, 1] and uncorrelated.<\/li>\n
    2. It should be efficient \u201cenough\u201d, in terms of both speed and memory requirements.<\/li>\n
    3. The output should be reproducible \u2013 i.e., given an initial state (such as seed), it should always generate the same output.<\/li>\n
    4. To facilitate simulation output analysis, it should be able to generate multiple independent (uncorrelated) streams of sufficient length.<\/li>\n
    5. It should be portable, ensuring that given an initial state, the output is the same on every target computing platform.<\/li>\n<\/ol>\n

      The generator provided by the random module fulfills properties 1, 2, 3 and 5.\u00a0 The fourth is, however, a bit more problematic.<\/p>\n

      The canonical way to generate multiple independent streams is to divide a single stream into multiple non-overlapping substreams, each of which should meet the same statistical randomness tests as the main stream and be independent of each other.\u00a0 Many random number generators include functions that can be used to initialize substreams from a single stream, either through a jump-ahead or other means.\u00a0 The Python 3.x random module does not.<\/p>\n

       <\/p>\n

      First, a bit of history is in order\u2026<\/p>\n