PadhaikoAll subjects

Random Number (part 1: 6.1–6.3)

Simulation and Modeling (ENCT 353)

Open in the Padhaiko app

6.1 Properties of random numbers

A sequence of random numbers used in stochastic simulation must behave statistically like independent samples drawn from a continuous Uniform distribution, .

Definition

Two Fundamental Statistical Properties

A sequence of random numbers on must satisfy two essential statistical properties:

  1. Uniformity: Every sub-interval of equal length within has an equal probability of containing a generated value. The probability density function is:

with theoretical mean and variance:

  1. Independence: The value of any generated number must not influence or be predictable from any other number () in the sequence (zero autocorrelation across lags).

Practical Engineering Requirements for Generators

Besides uniformity and independence, a good random number generator for simulation should be:


6.2 Generation of pseudo-random numbers

Definition

True Random vs. Pseudo-Random Numbers

Early Historical Approach: Midsquare Method

Proposed by John von Neumann (1946), the midsquare method starts with an -digit integer seed (typically digits), squares it to obtain a -digit number (left-padding with zeros if needed), extracts the middle digits as , and sets .

Why Midsquare Is Not Used in Practice:


6.3 Random number generation: Linear and arithmetic congruential methods

The Linear Congruential Method (LCM), introduced by D. H. Lehmer (1951), is the foundational algebraic method for generating pseudo-random integers and values.

Definition

Linear Congruential Generator (LCG)

An LCG produces a sequence of integers in via the modular recurrence:

where:

Period Length and Hull–Dobell Theorem

Because , an LCG can take at most distinct states before repeating; hence its maximum possible period is (or for multiplicative LCGs, since must be avoided).

Theorem

Hull–Dobell Theorem (Full Period for Mixed LCG)

A mixed LCG achieves the full period for any seed if and only if all three conditions hold:

  1. Relatively prime increment: (no common divisor ).
  2. Prime factor divisibility: Every prime factor of divides .
  3. Multiple of condition: If divides , then also divides .

Special Period Rules for Multiplicative LCG ()

Arithmetic (Additive) Congruential Method

An arithmetic (additive) congruential generator removes multiplication entirely and computes each term by summing two or more previous terms modulo :

For lag , this gives the Fibonacci generator initialized with two seeds . While simple and capable of periods exceeding (up to in lagged Fibonacci generators like ), short-lag Fibonacci generators () exhibit strong serial correlation ( tends to lie between its predecessors or wrap predictably) and therefore require large lags (e.g., ) or combination with another generator.

Comparison of Linear and Additive Congruential Generators
FeatureMixed LCG ()Multiplicative LCG ()Additive (Lagged Fibonacci)
Recurrence
Seed RequirementAny (odd if ) initial seeds
Max Period (via Hull–Dobell) ( prime) or ()Exceeds (very long for large lag )

Worked Out Examples

Example 1

1

Use the mixed linear congruential method with , , , and to generate the first pseudo-random numbers . Then apply the Hull–Dobell Theorem to explain the observed period.

Generating and :

Notice that , so the sequence already repeats with period instead of !

Checking the three Hull–Dobell conditions for , , :

Because condition (2) fails ( is not divisible by , whereas e.g. gives divisible by both and and ), the generator cannot reach full period and collapses to period .

Answer:

The first four random numbers are . Because , the period is only —predicted by the Hull–Dobell Theorem since prime factor of does not divide .

Example 2

2

Generate a complete cycle of random numbers using the multiplicative congruential method with seed . Verify that the achieved period equals the theoretical maximum for .

Checking theoretical maximum period conditions for :

  • Seed is odd.
  • Multiplier satisfies .

Therefore, the generator attains the maximum possible multiplicative period for , which is .

Iterating and :

Answer:

The generated cycle is with , achieving the theoretical maximum period of .

Example 3

3

  1. Generate pseudo-random numbers using the arithmetic (Fibonacci) congruential method with seeds and .
  2. Generate the first numbers using the -digit midsquare method starting from seed .

Part 1 — Arithmetic Congruential Method ():

Part 2 — Midsquare Method from :

  • ( digits). Taking the middle digits gives .
  • ( digits). Taking the middle digits gives .
Answer:
  1. Arithmetic congruential sequence: .
  2. Midsquare sequence from : .

Exercises

Practice Exercises — Random Number Generation

Question 1

State the two fundamental statistical properties of pseudo-random numbers on , derive their theoretical mean and variance, and list four desirable properties of a simulation random number generator.

Statistical Properties, Mean, and Variance: The two core properties are uniformity ( on ) and independence ( independent of for ).

Four Desirable Generator Properties:

  1. Speed & low memory overhead;
  2. Reproducibility from a given seed;
  3. Long cycle/period without repetition;
  4. Portability across hardware/software platforms.
Answer:

Random numbers must be uniform on (mean , variance ) and independent. A good PRNG is fast, reproducible, portable, and has a very long period.

Question 2

Distinguish between true random numbers and pseudo-random numbers, and explain why the midsquare method is unsuitable for serious simulation studies.

True vs. Pseudo-Random Numbers: True random numbers originate from physical stochastic processes (e.g., thermal noise) and cannot be replayed identically. Pseudo-random numbers are computed deterministically from a seed using an algorithm, making experiments reproducible for debugging and variance reduction while mimicking true randomness.

Defects of the Midsquare Method: Squaring and taking the middle digits can rapidly collapse into a zero trap () or a tiny repeating cycle, and its period length cannot be guaranteed mathematically beforehand.

Answer:

True random numbers come from non-reproducible physical noise, whereas pseudo-random numbers are reproducible deterministic sequences imitating . Midsquare is unsuitable because it suffers from zero degeneration and short, unpredictable cycles.

Question 3

Test whether the mixed LCG achieves the full period of using the Hull–Dobell Theorem, and generate the first random numbers starting from seed .

Checking Hull–Dobell conditions ():

  1. (holds).
  2. Only prime factor of is , and (holds).
  3. and (holds).

All three conditions hold, so this LCG has full period .

Generating and :

Answer:

By Hull–Dobell, the LCG achieves full period . From , the first four numbers are .

Question 4

For the prime-modulus multiplicative LCG with seed , generate the first values and , and determine the full cycle length of this generator.

Generating values modulo :

Determining the full period: Continuing from : , , , , , . Because is a primitive root modulo prime , all non-zero residues appear, giving period .

Answer:

The first four values are (), and the generator achieves its maximum prime-modulus period of ().

Question 5

Use the arithmetic congruential generator with and to compute , and briefly state one key limitation of short-lag additive generators.

Iterating the additive recurrence:

Limitation of short-lag additive generators: In a lag- Fibonacci generator , consecutive triples satisfy predictable ordering constraints (e.g., we can never observe ), causing strong serial dependence that fails independence tests unless large lags or combined generators are used.

Answer:

, , . Short-lag additive generators suffer from serial correlation among consecutive outputs.

← Markov ChainsRandom Number (part 2: 6.4–6.6) →