Linear Congruential Generator (LCG)

A linear congruential generator (LCG) is an old algorithm that results in a sequence of pseudo-randomized numbers. Though, the algorithm of linear congruential generator is the oldest but best-known pseudorandom number generator method.

The building block of a simulation study is the ability to generate random numbers where a random number represents the value of a random variable uniformly distributed on (0,1).

The generator is defined by the recurrence relation:

\[X_{i+1}=(aX_i+C) \text{ Modulo } m\]

where $a$ and $m$ are given positive integers, $X_i$ is either $0,1, \dots, m-1$ and quantity $\frac{X_i}{m}$ is pseudo random number.

Conditions for Linear Congruential Generator

Some conditions are:

  1. $m>0$;  $m$ is usually large
  2. $0<a<m$;  ($a$ is the multiplier)
  3. $0\le c<m$ ($c$ is the increment)
  4. $0\le X_0 <m$ ($X_0$ is seed value or starting value)
  5. $c$ and $m$ are relatively prime numbers (there is no common factor between $c$ and $m$).
  6. $a-1$ is a multiple of every prime factor $m$
  7. $a-1$ is multiple of 4 if $m$ is multiple of 4
Linear Congruential Generator

“Two modulo-9 LCGs show how different parameters lead to different cycle lengths. Each row shows the state evolving until it repeats. The top row shows a generator with $m=9, a=2, c=0$, and a seed of 1, which produces a cycle of length 6. The second row is the same generator with a seed of 3, which produces a cycle of length 2. Using $a=4$ and $c=1$ (bottom row) gives a cycle length of 9 with any seed in [0, 8]. “

If  $c=0$, the generator is often called a multiplicative congruential method, or Lehmer RNG. If $c\neq0$ the generator is called a mixed congruential generator.

Read more about the pseudo-random process and Random number Generation

Read from Wikipedia about Linear Congruential Generator (LCG)

Leave a Comment

Discover more from Statistics for Data Analyst

Subscribe now to keep reading and get access to the full archive.

Continue reading