Unit 4.2
Simulation Design
How randomness is generated, transformed, controlled, and turned into an efficient experiment.
- Unit 4.1
- Unit 4.2
§ Overview
Unit 4.1 developed the estimator and its sampling error. Unit 4.2 develops the mechanics and the design: how randomness is generated, how uniform values are transformed to useful distributions, and how experiments are designed to reduce variance.
The unit begins with pseudorandom number generation, including the linear congruential generator and the concepts of period and reproducibility. It then covers the transformation of uniform values to other distributions via inverse transform and acceptance–rejection. The closing lesson addresses replication and variance reduction, including antithetic variates, control variates, and common random numbers.
Lesson 1
Pseudorandom number generation
Lesson 2
Transforming random inputs
Lesson 3
Replication, variance reduction, and convergence
Laboratory 8
Random-number and output validation
§ Learning outcomes
By the end of Unit 4.2 you will be able to
- Describe the mechanism of a pseudorandom number generator and the role of the seed.
- Verify the uniformity and independence of a pseudorandom sequence.
- Transform uniform values to other distributions using inverse transform and acceptance–rejection.
- Design a simulation experiment that uses replication and variance reduction deliberately.
- Diagnose convergence and select a sample size for a target precision.
§ Lessons
Pseudorandom number generation
How deterministic algorithms produce usable randomness, and how to seed and validate them.
Lesson 2Transforming random inputs
Inverse transform, acceptance–rejection, and common distributions used in simulation.
Lesson 3Replication, variance reduction, and convergence
Design experiments that reduce variance rather than just adding runs.
§ Pseudorandom generation
A pseudorandom number generator (PRNG) is a deterministic algorithm that produces a sequence of numbers that passes statistical tests for randomness. The sequence is not truly random — it is entirely determined by an initial value called the seed — but it behaves like a random sequence for practical purposes.
The simplest useful PRNG is the linear congruential generator (LCG):
x_{n+1} = ( a x_n + c ) mod m
where a, c, and m are chosen
constants and x_0 is the seed. The output
u_n = x_n / m is approximately uniform on
[0, 1).
| Property | Meaning |
|---|---|
| Uniformity | Values are approximately uniformly distributed on [0, 1) |
| Independence | Successive values are approximately independent |
| Long period | The sequence does not repeat within the intended runtime |
| Reproducibility | The same seed produces the same sequence |
| Efficiency | Generation is fast enough not to dominate runtime |
Pseudorandom is not truly random
The sequence is entirely determined by the seed. Reproducibility depends on recording the seed. If the seed is not recorded, the simulation is not reproducible, even if the code is unchanged.
§ Variance reduction
The standard error of a Monte Carlo estimator scales as
1/√N. Reducing the standard error by a factor of
k requires k² times as many samples. For
expensive simulations, this is impractical, and variance-reduction
techniques offer a better route: reduce the variance of the estimator
itself, without increasing the number of samples.
| Technique | Idea | Typical gain |
|---|---|---|
| Antithetic variates | Pair each sample with its complement | Moderate |
| Control variates | Subtract an estimate of a known quantity | Large when a good control exists |
| Importance sampling | Sample more from regions that matter | Large for rare-event estimation |
| Common random numbers | Use the same random stream to compare alternatives | Large for comparative studies |
| Stratified sampling | Sample separately in each stratum | Moderate |
Choose the technique that fits the problem
Variance reduction is not universal. Antithetic variates work well for monotone functions; control variates require a correlated known quantity; importance sampling requires a good proposal distribution. Match the technique to the structure of the problem.
§ Key terms
- Seed
- The initial value that determines the entire sequence of pseudorandom numbers. Recording the seed is required for reproducibility.
- Period
- The number of values the generator produces before the sequence repeats. A good generator has a period much larger than the number of samples required.
- Inverse transform
-
A method for generating samples from a distribution by inverting its
cumulative distribution function. If
U ~ Uniform(0,1)andFis a CDF, thenX = F⁻¹(U)has CDFF. - Acceptance–rejection
- A method for generating samples from a distribution by sampling from a simpler proposal distribution and accepting or rejecting each sample according to a ratio.
- Antithetic variates
-
A variance-reduction technique that pairs each sample
Uwith its complement1 − U, exploiting negative correlation to reduce the variance of the average. - Control variate
- A correlated random variable whose expectation is known exactly. Subtracting a multiple of its deviation from the target estimator reduces the variance.
- Importance sampling
- A technique that samples from a proposal distribution different from the target, with weights that correct the distribution. Particularly effective for estimating rare-event probabilities.
- Common random numbers
- A technique for comparing two or more system configurations using the same random stream. Reduces the variance of the difference between the configurations.
§ Self-check
Check your understanding
Question 1
A pseudorandom number generator is:
Show answer
A deterministic algorithm. The sequence is fully determined by the seed.
Question 2
Inverse transform generates samples from a distribution F by computing:
Show answer
F⁻¹(U). If U is uniform, F⁻¹(U) has the distribution with CDF F.
Question 3
Antithetic variates reduce variance by:
Show answer
Exploiting negative correlation between paired samples. Each sample U is paired with 1 − U.
Question 4
Importance sampling is particularly effective for:
Show answer
Estimating rare-event probabilities. Naive sampling rarely hits the rare region; importance sampling focuses on it.
Question 5
Common random numbers are used to:
Show answer
Reduce the variance of comparisons between system configurations. The same random stream is used for all configurations, so differences are not contaminated by independent noise.