Random Numbers in Stochastic Programming – Lecture Notes
1. Why Random Numbers?
- Simulation requires random draws ξ ~ P.
- Deterministic computers approximate randomness.
- Good random numbers ensure unbiased Monte Carlo.
2. Types of Random Generators
- True randomness: physical sources (rare in computing).
- Pseudo-random: deterministic algorithm produces sequence.
- Need long period, uniformity, low correlation.
3. Pseudo-Random Generators
- Linear Congruential Generator (LCG):
x_{n+1} = (ax_n + c) mod m
Uniform u_n = x_n / m ∈ (0,1).
- Parameters a, c, m crucial for quality.
4. Properties of Good RNG
- Uniform distribution in [0,1].
- Independence between draws.
- Long period avoids repetition.
- Portability and reproducibility.
5. Testing Random Numbers
- Statistical tests: chi-square, Kolmogorov-Smirnov.
- Spectral test for multidimensional uniformity.
- Empirical distribution should converge to U(0,1).
6. Variance Reduction
- Pure randomness is inefficient.
- Techniques:
* Antithetic Variates
* Control Variates
* Importance Sampling
* Latin Hypercube Sampling
- Goal: reduce Var(g■) for same N.
7. Quasi-Monte Carlo
- Uses low discrepancy deterministic sequences.
- Examples: Sobol, Halton.
- Convergence O((log N)^k / N) vs O(1/sqrt(N)).
- Requires smoothness and bounded variance.
8. Practical Considerations
- RNG seed determines reproducibility.
- For stochastic optimization, update samples carefully.
- In simulation, independence across runs important.