3.1 Equidistribution

• 3.1.1 Linear Congruential Generators

  $ \begin{eqnarray} I_{n+1} = \left[ a I_{n} + b \right] \; mod \; m \end{eqnarray} $
  
  where $a$ is some (odd) multiplicative factor, $m$ is the largest integer (hardware-dependent, e.g. $m=2^{32}$), and $b$ is relatively prime with respect to $m$.

  To obtain random numbers $x_{n}$ of type real, equidistributed over the interval $(0,1)$, divide $I_{n}$ by $m$.

  $\Longrightarrow$ Library or internal routines RAND, RND, RAN etc.
  
  To minimize serial correlations:
  

  "Erasing tracks:"

  • 1. Produce a list $RLIST(i)$ of $Z$ equidistributed random numbers $x_{i}$ in $(0,1); i=1 \dots Z$. (e.g., $Z=97$.)
  • 2. Sample an additional random number $y$ in $(0,1)$.
  • 3. Determine a pointer index $j$ in $[1,Z]$ according to $ j=1+int( y \cdot Z) $
    ($ int(r)$ ... largest integer smaller than the real number $r$.)
  • 4. Use the element $RLIST(j)$ corresponding to $j$ as the output random number.
  • 5. Put $y=RLIST(j)$ and replace $RLIST(j)$ by a new random number $\in (0,1)$; return to (2).




• 3.1.2 Shift Register Generators

  (Also "Tausworthe" or "XOR" generators.) Originally for the production of random bits, but one may always generate 16, 32, etc. bits at a time and combine them to a computer word.

  Let bits $b_{1}, b_{2}, .. b_{n}$ be already given; then
  

  $ \begin{eqnarray} b_{n+1}&=&b_{k} \oplus b_{m} \oplus \dots \oplus b_{n} , \end{eqnarray} $
  
  
  with $k < m < .. < n$, and $ \oplus $ ... "exclusive or" (XOR)

  To find optimal indices $(k,m,\dots,n)$: see the theory of "primitive polynomials modulo 2".
  
  "Exhaustive" property: Starting such a recursion with an arbitrary combination of $n$ bits (except $0 \dots 0$), all possible configurations of $n$ bits will be realized just once before a new cycle begins.
  
  
  
  EXAMPLE: $(1,3)$ is one of the optimal combinations. Starting with the sequence $\{b_{1},b_{2},b_{3}\}$ $=\{101\}$ and applying $b_{4}=b_{3} \oplus b_{1}$ etc., we find the sequence, reading from left to right,
  
  

  $ 101 001 110 100 111 010 011 101 \dots $
  
  
  It is evident that indeed all possible 3-bit groups (except $000$) occur before the sequence repeats.
  
  
  A very popular prescription is the "R250" algorithm of Kirkpatrick-Stoll, based on $m=103$ and $n=250$:
  
  
  $ \begin{eqnarray} && I_{s}=I_{s-103} \oplus I_{s-250} \end{eqnarray} $
  
  
  For the first $250$ random integers, use a linear congruential generator.