Lesson 1: Pseudorandom Number Generation

1 Modelling context

A Monte Carlo simulation requires a source of random values. In practice, that source is never truly random — it is a deterministic algorithm that produces a sequence of values that behaves like a random sequence for the purposes of the simulation. These values are called pseudorandom.

The fact that the sequence is deterministic is not a defect. It is precisely what makes simulation reproducible: if the seed is recorded, the same sequence can be regenerated, and the same experiment can be rerun. But it also means that the randomness of the sequence is a property to be verified, not assumed, and that poor choices of generator can produce visible artefacts in the simulation.

Deterministic source, random behaviour

The generator is deterministic; the sequence is designed to pass statistical tests for randomness. Both facts matter. The determinism gives reproducibility; the statistical behaviour gives usability.

2 Learning objectives

By the end of this lesson you will be able to

Describe the mechanism of a linear congruential generator.
Explain the role of the seed and the concept of period.
Test a pseudorandom sequence for uniformity and independence.
Recognise common failure modes of pseudorandom generators.
Document the generator and seed in a reproducible simulation.

3 Prerequisite review

Uniform distribution: The continuous distribution on [0, 1) with constant density 1. The standard output of a pseudorandom generator.
Modular arithmetic: x mod m is the remainder of x divided by m. Fundamental to the LCG.
Independence: Successive values in the sequence should have no discernible relationship. Correlation between successive values is a common failure mode of poor generators.
Chi-square test: A statistical test for whether an observed frequency distribution matches an expected one. Used to test uniformity.

4 Mathematical formulation

Linear congruential generator

The linear congruential generator (LCG) produces a sequence of integers via the recurrence

x_{n+1} = ( a x_n + c ) mod m

where a is the multiplier, c is the increment, and m is the modulus. The seed is x_0. The output value is

u_n = x_n / m

which lies in [0, 1). The values u_n are approximately uniformly distributed.

The generator is fully deterministic: given x_0 and the parameters a, c, m, the entire sequence is determined. The seed plays the role of the "randomness" — different seeds produce different sequences.

Period

The period of a generator is the number of values it produces before the sequence repeats. Since the state space is finite (there are only m possible states), every generator has a finite period. A good generator has a period long enough that the sequence never repeats within the runtime of the simulation.

For an LCG, the maximum possible period is m. It is achieved when c ≠ 0, gcd(c, m) = 1, a − 1 is divisible by every prime factor of m, and a − 1 is divisible by 4 if m is divisible by 4. The Hull–Dobell theorem gives the exact conditions.

Testing a pseudorandom sequence

A pseudorandom sequence is tested for two properties: uniformity and independence.

Uniformity. Divide [0, 1) into k equal bins. For a sample of size N, each bin should contain approximately N/k values. The chi-square statistic

χ² = Σ (O_i − E_i)² / E_i

where O_i is the observed count and E_i = N/k is the expected count, tests whether the deviations are consistent with random fluctuation.

Independence. Plot consecutive pairs (u_n, u_{n+1}) in the unit square. For a good generator, the points appear uniformly scattered with no visible structure. For a poor generator, they may lie on a small number of lines or lattice points.

Figure 4.5. Scatter plots of consecutive pseudorandom pairs. A good generator produces uniformly scattered points (left). A poor generator produces points on a small number of lattice lines (right), a phenomenon known as lattice structure.

Lattice structure in LCGs

All LCGs have lattice structure when consecutive values are plotted in two or more dimensions. Good parameter choices keep the lattice fine enough that the structure is invisible; poor choices leave visible lines. Modern generators (e.g. Mersenne Twister) do not have this problem, which is one reason they are preferred in practice.

5 Worked example

A small LCG by hand

Consider the LCG with parameters a = 5, c = 1, m = 16, and seed x_0 = 1.

Step 1 — Generate the sequence.

x_1 = (5·1 + 1) mod 16 = 6 mod 16 = 6       u_1 = 6/16 = 0.375
x_2 = (5·6 + 1) mod 16 = 31 mod 16 = 15     u_2 = 15/16 = 0.9375
x_3 = (5·15 + 1) mod 16 = 76 mod 16 = 12    u_3 = 12/16 = 0.75
x_4 = (5·12 + 1) mod 16 = 61 mod 16 = 13    u_4 = 13/16 = 0.8125
x_5 = (5·13 + 1) mod 16 = 66 mod 16 = 2     u_5 = 2/16 = 0.125
...

Step 2 — Determine the period.

Continuing the sequence, we find:

x_0 = 1, x_1 = 6, x_2 = 15, x_3 = 12, x_4 = 13, x_5 = 2,
x_6 = 11, x_7 = 8, x_8 = 9, x_9 = 14, x_10 = 7, x_11 = 4,
x_12 = 5, x_13 = 10, x_14 = 3, x_15 = 0, x_16 = 1, ...

The sequence returns to x_0 = 1 after 16 steps, so the period is 16 — the maximum possible for m = 16. This confirms the Hull–Dobell conditions are satisfied for this parameter choice.

Step 3 — Test for uniformity.

Divide [0, 1) into 4 bins: [0, 0.25), [0.25, 0.5), [0.5, 0.75), [0.75, 1). Over the full period, each bin contains exactly 4 values. This is perfect uniformity — expected for a full-period LCG.

Step 4 — Test for independence.

Plot the consecutive pairs (u_n, u_{n+1}) in the unit square. With a period of 16, the plot shows only 16 points, and they lie on a small number of lines. The lattice structure is visible even for this "good" parameter choice, because the modulus is small.

Step 5 — Realistic scale.

In practice, m would be in the billions, the period would exceed 10¹⁸, and the lattice structure would be invisible at the resolution of any practical plot. The example above illustrates the mechanism at a tractable scale.

6 Verification check

Checks to perform

Histogram of the values. The histogram of u_n over many samples should be approximately flat.
Mean and variance. For a uniform distribution on [0, 1), the mean is 0.5 and the variance is 1/12 ≈ 0.0833. The sample mean and variance should be close to these.
Scatter plot of consecutive pairs. Plot (u_n, u_{n+1}) for a large sample. Look for visible lattice structure.
Chi-square test for uniformity. Divide the unit interval into bins and compute the chi-square statistic. Compare against the chi-square distribution with the appropriate degrees of freedom.
Reproducibility check. Rerun with the same seed and confirm that the sequence is identical. Rerun with a different seed and confirm that the sequence is different.

7 Interpretation

The pseudorandom sequence is the raw material of a Monte Carlo simulation. Its properties determine what the simulation can claim.

The seed is part of the inputs. A simulation without a recorded seed is not reproducible, and the result cannot be independently verified.
The generator's quality matters. A poor generator produces a sequence with visible patterns, and the simulation may inherit those patterns as spurious results.
The period must exceed the runtime. A sequence that repeats during the simulation is no longer a random sample.

Use a library generator

In practice, use the generator provided by your language or spreadsheet — Mersenne Twister or a similar high-quality generator. Do not implement your own LCG unless you have a specific reason and understand the parameter selection. Modern library generators have far better statistical properties than any ad hoc implementation.

8 Uncertainty and limitations

The properties of a pseudorandom sequence are not guaranteed by the fact that it "looks random." They must be verified, at least for the generator being used.

Limitations of pseudorandom generators
Issue	Consequence
Finite period	The sequence eventually repeats, invalidating independence
Lattice structure	Visible patterns in multidimensional plots; correlation between successive values
Poor seed choice	Certain seeds produce degenerate sequences (e.g. all zeros)
Inadequate generator	Statistical tests fail; simulation inherits non-random behaviour

Randomness is a property to verify

The uniformity and independence of the pseudorandom sequence should be verified before the simulation is run, not assumed. For a new generator, use a standard statistical test suite.

9 Common implementation errors

Watch for these

Not recording the seed. Without the seed, the simulation is not reproducible. Record it in the spreadsheet, script, or documentation.
Reseeding at every step. Reseeding the generator between steps destroys the sequence; each new sequence starts from the same point, producing correlated values.
Using a small-modulus generator. Small m means short period and visible lattice structure. Modern library generators do not have this problem.
Assuming different seeds produce independent simulations. Different seeds produce different sequences from the same generator; they are not truly independent in a strong sense.
Ignoring the effect of a poor seed choice. Some seeds produce degenerate sequences. Verify the sequence is not constant or nearly constant.
Using the same seed for a completely different problem. This can produce coincidental agreement. Use different seeds for different problems, or use the same seed deliberately to control for random variation.

10 Independent modelling task

Your turn

Implement the LCG x_{n+1} = (5 x_n + 1) mod 16 with seed 1 in a spreadsheet. Generate the full sequence and verify the period is 16.
Repeat with a = 3, c = 0, m = 16, x_0 = 1. What is the period? Does it satisfy the Hull–Dobell conditions?
Use a larger modulus: a = 1103515245, c = 12345, m = 2³¹, seed x_0 = 1. Generate 1000 values and plot a histogram. Test for uniformity.
Plot the consecutive pairs (u_n, u_{n+1}) for the large-modulus generator. Do you see lattice structure?
Compare against the generator provided by your spreadsheet software. Is the built-in generator visibly better?

This exercise forms part of Laboratory 8 and the random-number validation component of Assignment 4.

11 Reflection prompt

Reflect before continuing

Why does it matter that pseudorandom values are deterministic?

Two or three sentences. Consider both the positive consequences (reproducibility) and the potential risks (visible patterns from a poor generator).

12 Lesson summary

Key takeaways

A pseudorandom generator is a deterministic algorithm. The seed determines the entire sequence.
The linear congruential generator is the simplest useful PRNG. x_{n+1} = (a x_n + c) mod m.
The period is the number of values before the sequence repeats. It must exceed the runtime of the simulation.
Uniformity and independence must be verified. Histograms, chi-square tests, and scatter plots of consecutive pairs are the standard tools.
Record the seed. Without it, the simulation is not reproducible.
Use a library generator. Modern generators have far better statistical properties than ad hoc implementations.

Coming next

Lesson 2 develops the transformation of uniform values to other distributions, including inverse transform and acceptance–rejection.

§ Self-quiz, practice, and homework

Practice exercises

For the LCG x_{n+1} = (7 x_n + 3) mod 10 with seed x_0 = 2, generate the sequence. What is the period?
Generate 1000 uniform values using your spreadsheet's built-in random function. Compute the sample mean and variance and compare to 0.5 and 0.0833.
Plot the histogram of the values from exercise 2 with 10 bins. Are the bins approximately equal in height?
Plot the scatter of consecutive pairs (u_n, u_{n+1}) from your spreadsheet's generator. Do you observe lattice structure?

Homework problems

Implement an LCG. Implement the LCG x_{n+1} = (a x_n + c) mod m with a = 1664525, c = 1013904223, m = 2³², seed 1. Generate 10,000 uniform values. Compute the mean and variance, test for uniformity with a chi-square test, and plot the consecutive-pair scatter. Write a 500-word report on the sequence's properties.
Bad parameters. Investigate the LCG with a = 4, c = 1, m = 9. Generate the sequence and compute the period. Compare against the Hull–Dobell conditions. Discuss what a poorly chosen generator would do to a Monte Carlo simulation.
Seed sensitivity. For a fixed generator, run 100 simulations each with a different seed. Record the estimate and the confidence interval for each. Does the seed choice affect the expected result? Does it affect individual runs?

Mini project

Produce a "generator quality report" for your spreadsheet or programming environment's built-in pseudorandom generator. Include: the generator's name and algorithm (if documented), the maximum period, a uniformity test, an independence test via consecutive-pair scatter, and a reproducibility check. Submit a two-page report. This is part of Laboratory 8.