Charta is on Google Play: practise on the go. Get the app
Charta

Outline how pseudo-random numbers are generated.

FRM® Part I · Quantitative Analysis · Simulation and Bootstrapping · FRM1.QA.13.e

The idea

Computers generate pseudo-random numbers with a deterministic algorithm. A common example is the linear congruential generator, where the first value is the seed. Next = (a × x + c) mod m. Here x is the current state, and a, c and m are fixed constants. Each state is scaled to a uniform number between 0 and 1. u = x ÷ m. The sequence looks random, passes statistical tests for uniformity and independence, and is fully reproducible. The same seed gives the same stream, and the stream repeats once its period is exhausted. Other distributions come from transforming the uniforms. For normals, the inverse transform gives a draw. z = N⁻¹(u). Box-Muller is another route to normals. Practical points are a long period, one distinct seed per parallel process, and not reusing draws. A frequent exam error is to treat identical seeds as giving independent runs.

Formulas

Linear congruential generator

x(n + 1) = (a × x(n) + c) mod m

x(n)
the current state, with x(0) the seed
a
the multiplier
c
the increment
m
the modulus
mod
take the remainder after dividing by m

Each state becomes a uniform number u = x ÷ m. The same seed gives the same stream, and the stream repeats once its period is exhausted.

A practice question

From the question bank, with the reason each wrong option is wrong.

Which statement best describes how a computer generates the pseudo-random numbers used in simulation?

  1. A deterministic algorithm, started from a seed, gives a sequence that looks random. - correct
  2. A hardware device measures physical noise such as thermal fluctuation to produce each number.Why not: Describes true random number generation; pseudo-random generators are algorithmic.
  3. The program samples values from the previous simulation's output and shuffles them.Why not: Reuses earlier output and does not use a generating algorithm.
  4. A series of independent coin flips is made by the operating system and converted into numbers.Why not: Suggests genuine randomness; pseudo-random numbers come from a deterministic recurrence.

Pseudo-random numbers come from a deterministic recurrence, for example a linear congruential generator x(n+1) = (a x(n) + c) mod m, with u(n) = x(n) / m giving values on (0,1). They look random, but the sequence is fully determined by the seed and repeats after its period.

A harder one

A simple linear congruential generator uses x(n+1) = (5 x(n) + 3) mod 16 with seed x(0) = 7, and converts each state to a uniform number as u = x / 16. What is the third uniform number generated after the seed, u(3)?

  1. 0.6875Why not: Omits the additive constant of 3 in the recurrence.
  2. 0.5000 - correct
  3. 0.0625Why not: Counts the seed as the first number, so it reports the second generated state.
  4. 8Why not: Reports the raw integer state instead of dividing by the modulus 16 to scale it onto (0,1).

x(1) = (35 + 3) mod 16 = 6; x(2) = (30 + 3) mod 16 = 1; x(3) = (5 + 3) mod 16 = 8. Dividing by 16 gives u(3) = 0.5000.

The hardest tier

A generator has a period of 2^24 = 16,777,216 numbers. Each simulated path needs 12 independent standard normal draws, generated with the Box-Muller method, which converts each pair of uniforms into two normals. How many complete paths can be simulated before the stream starts to repeat?

  1. 1,398,101 - correct
  2. 16,777,216Why not: Treats every number in the period as a separate path and ignores that each path uses 12 draws.
  3. 2,796,202Why not: Assumes each path needs only 6 uniforms; Box-Muller uses two uniforms for every two normals, so 12 normals need 12 uniforms.
  4. 201,326,592Why not: Multiplies the period by 12, when the number of draws per path divides the period.

Box-Muller needs two uniforms for two normals, so each path consumes 12 uniforms. The stream repeats after 16,777,216 numbers, so complete paths = 16,777,216 / 12 = 1,398,101 (rounded down). A longer run would reuse the same paths.

In the app: 6 practice questions on this outcome, spaced review that brings it back before you forget it.

Start free →

More in Simulation and Bootstrapping