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 recurrence relation defines the generator:
\[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:
- $m>0$; $m$ is usually large
- $0<a<m$; ($a$ is the multiplier)
- $0\le c<m$ ($c$ is the increment)
- $0\le X_0 <m$ ($X_0$ is seed value or starting value)
- $c$ and $m$ are relatively prime numbers (there is no common factor between $c$ and $m$).
- $a-1$ is a multiple of every prime factor $m$
- $a-1$ is multiple of 4 if $m$ is multiple of 4
“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.
FAQs about linear congruential generator (LCG)
- What is meant by a linear congruential generator?
- How are random numbers generated?
- What are the conditions for linear congruential generators?
- What is meant by a multiplicative or mixed congruential generator?
Read more about the pseudo-random process and Random number Generation
Read from Wikipedia about Linear Congruential Generator (LCG)
