Random Number Generation

I.   Introduction
     A.   What are random numbers and what is randomness?
            1.  Independence aspect of randomness -> pseudorandom numbers
            2. Unpredictability aspect of randomness -> cryptographic random numbers
            3. Uniformity aspect of randomness -> quasirandom numbers
            4. Real (physically based) random numbers
     B.   Applications that use random numbers
           1.  Statistics and simulation (randomness is a metaphor for lack of information)
           2.  Monte Carlo methods
                a.  Numerical integration
                b.  Transport Monte Carlo
                c.  Integral and partial differential equations
                d.  Quantum mechanics
                e.  Statistical mechanics
                f.   Financial computing
           3.  Applications and random numbers interact differently

II.   Pseudorandom Number Generation
      A.  Desirable properties for pseudorandom numbers
            1.  Determinism and reproducibility
            2.  Periodicity and known period length
            3.  Recurrences that can be analyzed (theoretical results)
            4.  Passing a suite of statistical tests (more below)
      B.  Well known pseudorandom number generators and some of their properties
            1.  The history of the middle-square method (obsolete)
            2.  The (Lehmer) linear congruential generator (LCG)
            3.  The shift-register generator (SRG)
            4.  The additive lagged-Fibonacci generator (ALFG)
      C.  More recent pseudorandom number generators and their properties
           1.   Linear pseudorandom generators
                 a.  Multiple recursive generators (MRG) and L'Ecuyer's implementation
                 b.  Marsaglia's generators
                      i.   Superduper
                      ii.  Add-with-carry and subtract-with-borrow generators
                 c.  Twisted generators
                      i.   Twisted GFSRs
                      ii.  Mersenne Twister
                      iii. Twisted Canadian generators
           2.   Nonlinear generators
                 a.  Multiplicative lagged-Fibonacci generator (MLFG)
                 b.  Quadratic congruential generator
                 c.  Inversive congruential generators (ICG)
                      i.   Implicit inversive congruential generator (IICG)
                      ii.  Explicit inversive congruential generator (EICG)
           3.  Combining generators
      D. Quality and testing of pseudorandom number generators
           1.  Theoretical tests
                a.  Exponential sum-based tests for equidistribution and discrepancy
                b.  Discrepancies
                     i.   Star discrepancy
                     ii.  Mean-square discrepancy
                c.  The spectral test
           2.  Empirical tests
                a.  Equidistribution tests
                b.  The DIEHARD test suite
                c.  Other suites
                d.  Applications are the best tests

III.   Other Random Numbers for Applications (See Monte Carlo Methods course!)
       A. Cryptographic random numbers
       B. Quasirandom numbers
           1.  Numerical quadrature
                a.  The curse of dimensionality and complexity
                b.  The Koksma-Hlawka inequality
           2.  Financial applications
           3.  Markov-chain-based applications

IV.  Issues for Parallel, Distributed, and Grid-based Applications
      A.  Methods of generating concurrent streams
           1. Cycle splitting with leap-ahead
               a.  Leap-frog
               b.  Blocking
               c.  Recursive halving leap ahead
           2.  Parameterization
      B.  Reproducibility and spawning
      C.  Quality and testing

V.   Available Random Number Software
      A.  Serial applications
      B.  Parallel applications

VI. Conclusions
      A.  Best practices
           1.  Sufficient random number generators
           2.  Testing generators and applications
      B.  The future of random number generation
           1.  In practice, many pseudorandom number generators are superior
           2.  Current application requirements are met with current generators
           3.  However, optimization and specialized requirements drive future applied work
           4.  Advancing testing, in theory and practice, remains important
           5.  New generators should still be sought after