Random Number Generator

Probability Theory, Pseudorandom Algorithms & Cryptographic Entropy

Random number generation is a fundamental primitive in applied mathematics, Monte Carlo numerical simulations, stochastic statistical modeling, algorithmic cryptography, and computational game theory. A discrete uniform random variable $X \sim \mathcal{U}\{a, b\}$ assigns equal probability mass across all finite integers within the closed interval $[a, b] \subset \mathbb{Z}$.

Discrete Uniform Probability Distribution

For any discrete integer $k$ within the contiguous domain $a \le k \le b$, the Probability Mass Function (PMF), cumulative distribution function (CDF), expected value (mean $\mu$), and variance $\sigma^2$ evaluate to:

P(X = k) = \frac{1}{b - a + 1}, \qquad E[X] = \frac{a + b}{2}, \qquad \operatorname{Var}(X) = \frac{(b - a + 1)^2 - 1}{12}

Pseudorandom Number Generators (PRNG) & Linear Congruential Recurrence

Deterministic computing architectures approximate physical randomness through algorithmic Pseudorandom Number Generators (PRNGs). One of the most historically significant PRNG formulations is the Linear Congruential Generator (LCG), parameterized by modulus $m$, multiplier $a$, increment $c$, and seed value $X_0$:

X_{n+1} = (a X_n + c) \pmod m

According to the Hull-Dobell Theorem, an LCG achieves its maximum theoretical period of length $m$ if and only if:

$\gcd(c, m) = 1$ (increment $c$ and modulus $m$ are coprime).
Every prime factor of $m$ divides $a - 1$.
If $m$ is divisible by 4, then $a - 1$ must be divisible by 4.

Box-Muller Transform for Gaussian (Normal) Distributions

When sampling continuous random variables distributed normally $Z \sim \mathcal{N}(\mu, \sigma^2)$, the Box-Muller transformation projects two independent standard uniform variables $U_1, U_2 \sim \mathcal{U}(0, 1)$ onto independent standard normal variates $Z_0, Z_1$:

Z_0 = \sqrt{-2 \ln U_1} \cos(2\pi U_2), \qquad Z_1 = \sqrt{-2 \ln U_1} \sin(2\pi U_2)

Scaling and shifting converts standard normal $Z_0$ to any targeted mean $\mu$ and standard deviation $\sigma$: $$X = \mu + \sigma \cdot Z_0$$

Cryptographically Secure PRNG (CSPRNG) vs. Standard PRNG

Standard runtime random functions (such as `Math.random()`, typically backed by the xorshift128+ algorithm) prioritize computational throughput over cryptographic security and are predictable if prior internal state registers are exposed. In contrast, Cryptographically Secure PRNGs (CSPRNG) (such as `crypto.getRandomValues()` utilizing hardware entropy pools and AES-CTR or ChaCha20 primitives) satisfy the next-bit unpredictability test: given the first $k$ output bits, no polynomial-time algorithm can predict bit $k+1$ with probability exceeding $\frac{1}{2} + \epsilon$.

Fisher-Yates Non-Replacing Sampling Algorithm

Generating $k$ unique random integers from $[a, b]$ without duplicates uses the optimal $O(k)$ Fisher-Yates (Knuth) Shuffle. Starting with array $A$ of length $n = b - a + 1$:

For index $i$ descending from $n - 1$ down to $n - k$: $$\text{Pick random integer } j \in [0, i]$$ $$\text{Swap elements } A[i] \longleftrightarrow A[j]$$
The trailing $k$ elements form a perfectly unbiased, uniformly distributed random subset without replacement.