Random Number Generation: From Intuition to Precision
Imagine you're playing a board game with a single die. Before every move, you roll it. You don't know which face will come up — it could be 1, 2, 3, 4, 5, or 6. But you do know one thing: over many rolls, each number appears roughly the same number of times. That's the core idea behind random number generation: producing a sequence of numbers where each outcome is unpredictable individually, yet the overall pattern follows a known distribution.
A random number generator (RNG) is a process — either physical or computational — that produces such a sequence. In the physical world, rolling a die, flipping a coin, or measuring radioactive decay are genuine sources of randomness. In computing, we usually simulate randomness using algorithms, because true randomness is hard to capture and slow to produce.
The Intuition: What Makes a Number "Random"?
A single number, say 42, is not random or non-random by itself. Randomness is a property of the process that produced it, not the number itself. So when we talk about random number generation, we're really talking about generating a sequence of numbers that satisfies two key properties:
- Unpredictability: Given the entire history of numbers generated so far, you cannot predict the next number with any certainty better than pure chance.
- Uniformity (for a uniform generator): Over a long run, each possible number appears with equal frequency. For a fair six-sided die, each face appears about 1/6 of the time.
If you roll a die 60 times and get 60 sixes, the process is still "random" in principle — but it's almost certainly a loaded die. A good RNG must pass statistical tests that check for both unpredictability and uniformity.
The Precise Statement
A random number generator is a deterministic or non-deterministic algorithm or physical process that produces a sequence of numbers X1,X2,X3,… such that:
- Each Xi is drawn from a specified probability distribution (most commonly the uniform distribution on [0,1) or {0,1,…,m−1}).
- The sequence is independent and identically distributed (i.i.d.) — meaning the value of Xi does not depend on any previous Xj, and all Xi share the same distribution.
- For a pseudo-random number generator (PRNG), the sequence is actually deterministic: given an initial seed value, the entire sequence is fixed. But the sequence appears random to any statistical test that does not know the seed.
A uniform PRNG on integers {0,1,…,m−1} satisfies:
P(Xi=k)=m1for all k∈{0,1,…,m−1}
and Xi is independent of Xj for i=j.
How Computers Generate Random Numbers (Pseudo-Randomness)
True randomness is expensive. Instead, computers use pseudo-random number generators — deterministic algorithms that produce sequences that look random. The most famous family is the linear congruential generator (LCG):
Xn+1=(a⋅Xn+c)modm
where a, c, and m are carefully chosen constants, and X0 is the seed. For example, the classic rand() in C often used a=1103515245, c=12345, m=231.
The seed is crucial: same seed → same sequence. That's useful for debugging (reproducible results) but dangerous if you need true unpredictability (e.g., cryptography). For security, use a cryptographically secure PRNG (CSPRNG) or a hardware random number generator.
Common Pitfalls
A common mistake is to assume that a PRNG produces "truly random" numbers. It does not — it's deterministic. If an attacker knows the algorithm and can observe enough outputs, they can reconstruct the seed and predict all future numbers. This is why you never use rand() for passwords or encryption keys.
Another trap: modulo bias. If you generate a random integer in {0,1,…,m−1} by taking rand() % m, and RAND_MAX + 1 is not a multiple of m, some remainders are slightly more likely than others. Always use rejection sampling or a proper library function.
Where You'll Meet This
- Simulations: Monte Carlo methods for estimating π, simulating dice rolls, or modeling physical systems.
- Games: Shuffling a deck of cards, generating enemy positions, procedural terrain.
- Cryptography: Generating keys, nonces, and initialization vectors (requires true randomness or CSPRNG).
- Machine Learning: Random initialization of weights, shuffling training data, dropout.
The key takeaway: random number generation is not about "getting a random number" — it's about creating a process that behaves like a fair die, whether through physics or clever mathematics.