Simulations and Random Number Generation - Exploring Linear Congruential Generator

Simulations and Random Number Generation - Exploring Linear Congruential Generator

What does simulation mean?

Well, it says, we are using a model (Mathematical representation of a system) where the computer is used to act like a given system.

And we can see a simulation type called Monte Carlo simulations. It just uses internally generated (pseudo) random numbers for the simulation.

So why do we need simulations?

Sometimes it is impossible to deal with complex systems. Otherwise, it may be a time-consuming task and incur lots of money when it operates. By creating a model (Or mathematical representation of a system) we can mimic its behavior. Then it allows us to explore various scenarios, predict outcomes, and understand the underlying mechanisms of a given system.

Sometimes, in a real system, you may not have full control over the system. But here we can have a controlled environment. So it's a cost-effective, flexible, and risk-free method to have.

On the other hand, you may have some disadvantages like accuracy problems, interpretation challenges, and problems with randomness. Also, you may encounter some additional computational costs as well.

Exploring Randomness in Simulations

One essential component of many simulations is the generation of random numbers. In this context, pseudo-random number generators (PRNGs) are often employed to produce sequences of numbers that simulate randomness. The Linear Congruential Generator (LCG) is one of the oldest and simplest PRNGs, using a mathematical formula to generate a sequence of numbers. Understanding how different parameters affect the quality of generated numbers can help improve the effectiveness of simulations. For instance, the LCG's effectiveness in producing random sequences depends on careful selection of its parameters.

The recurrence relation for an LCG is given by:

Xn+1 =( a ⋅ Xn + c ) mod m

Where

  • ( Xn ) is the current value in the sequence.
  • ( Xn+1 ) is the next value in the sequence.
  • ( a ) is the multiplier.
  • ( c ) is the increment.
  • ( m ) is the modulus.

If c = 0, then the generated is named as multiplicative congruential generator. If a = 1, then it is called as addictive congruential generator.

As we see here, it's obvious that the sequence of generated random numbers is more sensitive to a and m . If you choose the parameters carefully, it can generate a long period before repeating. That means it takes some time to generate the same numbers again making it more useful for simulations or other tasks where you need a lot of random numbers.

The quality of the numbers that LCGs produce heavily depends on the specific values you choose for the parameters m (the modulus) and a (the multiplier). If you choose poor values for these parameters, the sequence can become very predictable and not random at all. See here for some common values.

For example, if you set a=1 and c=1, the sequence will just count up by 1 each time(like 1, 2, 3, 4, and so on). Even though this sequence has a long period (it will eventually repeat after a while), it's not random at all—it's just a simple counting sequence.

If you choose a different value for the c, the sequence might spread out. But it could still show an obvious pattern. It means the sequence isn't random at all.

Let's see this using a code example. Here we divided the value of current variable by m to generate uniformly distributed values on the interval (0,1).

def lcg(seed, a, c, m, n):
    numbers = []
    current = seed
    for _ in range(n):
        current = (a * current + c) % m
        r_number = current / m
        numbers.append(r_number)
    return numbers

# Define the parameters for the LCG
seed = 4
a = 2
c = 2
m = 10
n = 10  # Number of random numbers to generate

generated_numbers = lcg(seed, a, c, m, n)
print("Generated numbers with poor parameters:", generated_numbers)

Generated numbers with poor parameters: [0.0, 0.2, 0.6, 0.4, 0.0, 0.2, 0.6, 0.4, 0.0, 0.2]

Here you can see a pattern of 0.0, 0.2, 0.6, 0.4

Let's change the value of c.

seed = 4
a = 2
c = 10
m = 10
n = 10  # Number of random numbers to generate

generated_numbers = lcg(seed, a, c, m, n)
print("Generated numbers with poor parameters:", generated_numbers)

Generated numbers with poor parameters: [0.8, 0.6, 0.2, 0.4, 0.8, 0.6, 0.2, 0.4, 0.8, 0.6]

Even though the numbers are different, still the first 4 numbers (0.8, 0.6, 0.2, 0.4 ) are repeated. So we can confirm that the value of c does not affect the randomness of the generated numbers.

# Define the parameters for the LCG
seed = 42
a = 1664525
c = 1013904223
m = 2**32
n = 100  # Number of random numbers to generate

generated_numbers = lcg(seed, a, c, m, n)
print("Generated numbers with better parameters:", generated_numbers)

Generated numbers with better parameters: [0.2523451747838408, 0.08812504541128874, 0.5772811982315034, 0.22255426598712802, 0.37566019711084664, 0.02566390484571457, 0.4472812858875841, 0.1184600037522614, 0.8738137057516724, 0.9946342753246427, 0.8532027236651629, 0.49967672815546393, 0.6420009464491159, 0.8614561874419451, 0.5964697764720768, 0.0907501564361155, 0.14020979800261557, 0.950088276527822, 0.9245554457884282, 0.8894689562730491, 0.5505083699245006, 0.1805165521800518, 0.5500854735728353, 0.2589667965658009, 0.9431216625962406, 0.8215009802952409, 0.15529390866868198, 0.8293947107158601, 0.4669222899246961, 0.060704877600073814, 0.02245523571036756, 0.5372887724079192, 0.8299602644983679, 0.8453321186825633, 0.6809180665295571, 0.38075808389112353, 0.5856568452436477, 0.6963971555233002, 0.7113653940614313, 0.7186180767603219, 0.9902874475810677, 0.44975284952670336, 0.09792640875093639, 0.1915941252373159, 0.4473786160815507, 0.12700111605226994, 0.7687648774590343, 0.5937204719521105, 0.8046440596226603, 0.3894113814458251, 0.21576908486895263, 0.27205946622416377, 0.01908474904485047, 0.27797185257077217, 0.3339683373924345, 0.8828661148436368, 0.955878077307716, 0.1926985988393426, 0.8713010295759887, 0.5823229453526437, 0.33668108214624226, 0.31432744674384594, 0.12935927300713956, 0.9799701818265021, 0.10297273122705519, 0.9215136868879199, 0.8057350877206773, 0.43295623315498233, 0.7100602698046714, 0.3066645935177803, 0.1185931561049074, 0.5092334938235581, 0.11737463087774813, 0.2435297565534711, 0.6040951393079013, 0.6978244571946561, 0.4906799078453332, 0.20967422612011433, 0.22730055614374578, 0.6942831412889063, 0.8818218896631151, 0.8169594695791602, 0.6971692244987935, 0.8394768270663917, 0.401640658499673, 0.15315714105963707, 0.12629026523791254, 0.5398131092078984, 0.6516722498927265, 0.9878206634894013, 0.4259626686107367, 0.7470372593961656, 0.4302643754053861, 0.045539623126387596, 0.07725242315791547, 0.8257249020971358, 0.9787312077824026, 0.7997019765898585, 0.1686512071173638, 0.3865950028412044]

But look at this. In these 100 numbers, you can't see a repeated pattern. These numbers are not truly random since these numbers can be replicated or re-generated with the same seed value (Seed value is the initial value of Xₙ ), a and m. But they appear to be random even for long sequences if we choose the right parameters. Actually this sequence is identically and independently uniformly distributed on the interval (0,1).

I hope you got the idea. If subscribe to me for reading more like this. It encourages me to write more.

Chanaka Prasanna
I gather knowledge from everywhere and simplify it for you.