Random Number (part 1: 6.1–6.3)
Open in the Padhaiko app6.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, .
Two Fundamental Statistical Properties
A sequence of random numbers on must satisfy two essential statistical properties:
- 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:
- 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:
- Fast and low-memory: Requires minimal arithmetic operations per number so millions of samples run quickly.
- Reproducible: Starting from the same seed must reproduce the exact same stream (vital for debugging and variance-reduction techniques like Common Random Numbers).
- Long Period (Cycle Length): Must not repeat before the simulation finishes (modern generators such as Mersenne Twister have period ).
- Portable: Produces identical streams across different CPUs, compilers, and operating systems.
6.2 Generation of pseudo-random numbers
True Random vs. Pseudo-Random Numbers
- True Random Numbers: Derived from unpredictable physical phenomena (thermal resistor noise, radioactive decay, atmospheric noise); cannot be reproduced on demand.
- Pseudo-Random Numbers (PRNs): Generated deterministically by a mathematical recurrence starting from an initial seed . Although completely deterministic, a well-designed Pseudo-Random Number Generator (PRNG) passes statistical tests for uniformity and independence.
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:
- Degeneration to zero: If the middle digits ever become , all subsequent outputs remain forever.
- Short, unpredictable cycles: Sequences often fall into tiny repeating loops (e.g., ).
- Sensitivity to seed: Difficult to guarantee period length analytically without running the generator.
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.
Linear Congruential Generator (LCG)
An LCG produces a sequence of integers in via the modular recurrence:
where:
- is the seed (),
- is the multiplier (),
- is the increment (),
- is the modulus ().
- If , the generator is a Mixed LCG.
- If , the recurrence simplifies to , called a Multiplicative LCG.
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).
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:
- Relatively prime increment: (no common divisor ).
- Prime factor divisibility: Every prime factor of divides .
- Multiple of condition: If divides , then also divides .
Special Period Rules for Multiplicative LCG ()
- Power-of-two modulus (): Maximum possible period is , achieved when is odd and or (i.e., ).
- Prime modulus ( prime): Maximum possible period is , achieved when is a primitive root modulo (e.g., the classic Park–Miller generator uses and ).
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.
| Feature | Mixed LCG () | Multiplicative LCG () | Additive (Lagged Fibonacci) |
|---|---|---|---|
| Recurrence | |||
| Seed Requirement | Any | (odd if ) | initial seeds |
| Max Period | (via Hull–Dobell) | ( prime) or () | Exceeds (very long for large lag ) |
Worked Out Examples
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 .
The first four random numbers are . Because , the period is only —predicted by the Hull–Dobell Theorem since prime factor of does not divide .
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 :
The generated cycle is with , achieving the theoretical maximum period of .
3
- Generate pseudo-random numbers using the arithmetic (Fibonacci) congruential method with seeds and .
- 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 .
- Arithmetic congruential sequence: .
- Midsquare sequence from : .
Exercises
Practice Exercises — Random Number Generation
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:
- Speed & low memory overhead;
- Reproducibility from a given seed;
- Long cycle/period without repetition;
- Portability across hardware/software platforms.
Random numbers must be uniform on (mean , variance ) and independent. A good PRNG is fast, reproducible, portable, and has a very long period.
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.
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.
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 ():
- (holds).
- Only prime factor of is , and (holds).
- and (holds).
All three conditions hold, so this LCG has full period .
Generating and :
By Hull–Dobell, the LCG achieves full period . From , the first four numbers are .
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 .
The first four values are (), and the generator achieves its maximum prime-modulus period of ().
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.
, , . Short-lag additive generators suffer from serial correlation among consecutive outputs.