Question

Why are random numbers generated with linear congruential methods not truly random? Describe
the properties of the sequence of numbers these types of methods will produce.

Answer 1

A linear congruential generator (LCG) is an algorithm that produces a series of pseudo-randomized numbers calculated using a linear discontinuous linear equation. The technique reflects one of the oldest and best-known pseudorandom number generator algorithms. The concept behind them is comparatively simple to comprehend, and they are readily applied and quick, particularly on computer hardware that can provide storage-bit truncation modulo arithmetic.

The generator is defined by recurrence relation:

X_n+1 = a (X_n + d) mod m

where {\displaystyle X}X is the sequence of pseudorandom values, and

{\displaystyle m,\,0<m}m, 0 < m — the "modulus"

a,{\displaystyle a,\,0<a<m} 0 < a < m— the "multiplier"

d, 0 ≤ d < m{\displaystyle c,\,0\leq c<m} — the "increment"

{\displaystyle X_{0},\,0\leq X_{0}<m}X₀, 0 ≤ X₀ < m — the "seed" or "start value"

As we can see the method of generation is already known and we can predict the whole sequence if we know d, m and X0 therefore random numbers generated by LCG are not random.

Properties of Numbers generated by LCG

• Uncorrelated sequences – The sequences of random numbers should be serially uncorrelated
• Long-term – The generator should be long-term (ideally, the generator should not repeat; practically, repetition should only occur after a very large set of random numbers has been generated).
• Uniformity–The random number sequence should be consistent and unbiased. That is, equal random number fractions should drop into equal space'' fields.'' E.g. If random figures are to be produced on [0, 1), it would be bad practice to drop to [0, 0.1) by more than half, assuming that the sample size is big enough.
• Efficiency–It should be an effective generator. Low overhead computing massively parallel.