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.

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
Source: https://en.wikipedia.org/wiki/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

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Discover more from Statistics for Data Analyst

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

Continue reading

Scroll to Top