EC-406 Simulation Lab - Unit 4: Monte Carlo Simulation & Random Variate Generation

Priority: High (Frequently appears in both theory and lab problems)

4.1 Fundamentals of Random Number Generation

• 4.1.1 Properties of Good Random Numbers

  • Uniformity: Each number in the range has equal probability.

  • Independence: No correlation between successive numbers.

  • Reproducibility: Same seed yields same sequence (for debugging).

  • [Exam Tip: Distinguish between true randomness (physical) vs pseudo-randomness (algorithmic)]

• 4.1.2 Linear Congruential Generator (LCG)

  • Formula:

$$X_{n+1} = (aX_n + c) \mod m$$

- **Parameters**: multiplier $a$, increment $c$, modulus $m$, seed $$\displaystyle X_0 $$.

- **Period**: Length before sequence repeats. Max theoretical period = $m$ if:

    1. $c$ and $m$ are relatively prime.

    2. $a-1$ is divisible by all prime factors of $m$.

    3. $a-1$ is divisible by 4 if $m$ is divisible by 4.

- *[Common Pitfall: Poor parameter choice leads to short cycles and patterns]*

4.2 Testing Random Number Generators

• 4.2.1 Frequency Test (Chi-Square)

  • Purpose: Test uniformity.

  • Formula:

$$\chi^2 = \sum_{i=1}^{k} \frac{(O_i - E_i)^2}{E_i}$$

- Where $$\displaystyle O_i $$ = observed frequency, $$\displaystyle E_i = n/k $$ (expected), $n$ = total numbers, $k$ = intervals.

- **Decision**: Reject uniformity if $$\displaystyle \chi^2 > \chi^2_{\alpha, k-1} $$.

• 4.2.2 Runs Test

  • Purpose: Test independence.

  • Steps:

    1. Count runs (consecutive numbers above/below median).

    2. Expected runs: $$\displaystyle E(R) = \frac{2n_1 n_2}{n} + 1 $$, where $$\displaystyle n_1 $$, $$\displaystyle n_2 $$ are counts above/below median.

    3. Variance: $$\displaystyle Var(R) = \frac{2n_1 n_2(2n_1 n_2 - n)}{n^2(n-1)} $$.

  • Statistic: $$\displaystyle Z = \frac{R - E(R)}{\sqrt{Var(R)}} \sim N(0,1) $$.

• 4.2.3 Autocorrelation Test

  • Purpose: Check correlation between $$\displaystyle X_i $$ and $$\displaystyle X_{i+k} $$.

  • Formula:

$$\rho_k = \frac{\frac{1}{n-k} \sum_{i=1}^{n-k} (X_i - \bar{X})(X_{i+k} - \bar{X})}{\frac{1}{n} \sum_{i=1}^{n} (X_i - \bar{X})^2}$$

- **Decision**: $$\displaystyle |\rho_k| > \frac{1.96}{\sqrt{n}} $$ indicates significant correlation.

4.3 Random Variate Generation Techniques

• 4.3.1 Inverse Transform Method

  • Concept: If $U \sim Uniform(0,1)$, then $$\displaystyle X = F^{-1}(U) $$ has CDF $F(x)$.

  • Steps:

    1. Generate $U \sim Uniform(0,1)$.

    2. Compute $$\displaystyle X = F^{-1}(U) $$.

  • Examples:

    • Exponential ($\lambda$): $$\displaystyle X = -\frac{1}{\lambda} \ln(1-U) \equiv -\frac{1}{\lambda} \ln U $$.

    • Uniform $(a,b)$: $$\displaystyle X = a + (b-a)U $$.

    • Erlang ($k, \lambda$): Sum of $k$ exponentials.

  • [Key Limitation: Requires invertible CDF]

• 4.3.2 Acceptance-Rejection Method

  • Concept: Generate from proposal $g(y)$, accept with probability $$\displaystyle \frac{f(y)}{c g(y)} $$.

  • Requirements:

    1. Find $c$ such that $f(y) \leq c g(y)$ for all $y$.

    2. $g(y)$ easy to sample from.

  • Efficiency: $$\displaystyle \frac{1}{c} $$ (probability of acceptance).

  • [Exam Tip: Choose $g(y)$ similar in shape to $f(y)$ to minimize $c$]

4.4 Input Data Analysis

• 4.4.1 Identifying Input Distributions

  • Use historical data to fit distributions (e.g., exponential for interarrival times, normal for processing times).

  • Goodness-of-Fit Tests:

    • Chi-Square: For grouped data.

    • Kolmogorov-Smirnov (K-S): Compares empirical CDF $$\displaystyle S_n(x) $$ with theoretical $F(x)$.

    • Statistic: $$\displaystyle D = \sup_x |S_n(x) - F(x)| $$.

  • [Common Pitfall: K-S test is more powerful for continuous distributions]

4.5 Output Analysis

• 4.5.1 Types of Simulations

  • Terminating: Clear start and end (e.g., bank closing).

  • Steady-State: Long-run behavior (e.g., manufacturing system).

  • [Exam Note: Steady-state requires warm-up period; use deleted means method]

• 4.5.2 Confidence Intervals for Means

  • For $n$ independent replications:

$$\bar{X} \pm t_{\alpha/2, n-1} \frac{S}{\sqrt{n}}$$

    where $\bar{X}$ = overall mean, $S$ = sample std dev.

- **Batch Means Method**: For correlated outputs (steady-state), divide into batches, treat batch means as independent.

- *[Key Assumption: Outputs must be approximately normally distributed or $n$ large (CLT)]*

4.6 Variance Reduction Techniques

• 4.6.1 Antithetic Variates

  • Use pairs $(U, 1-U)$ to induce negative correlation.

  • Estimate: $$\displaystyle \hat{\theta} = \frac{1}{2n} \sum_{i=1}^{n} [h(U_i) + h(1-U_i)] $$.

  • Variance Reduction: Effective when $h(\cdot)$ is monotonic.

• 4.6.2 Control Variates

  • Use a related variable $Y$ with known mean $E[Y]$.

  • Adjusted estimator: $$\displaystyle \hat{\theta}_{cv} = \bar{h} - \beta (\bar{Y} - E[Y]) $$, where $$\displaystyle \beta = \frac{Cov(h,Y)}{Var(Y)} $$.

  • [Exam Tip: Choose $Y$ highly correlated with $h$ for maximum reduction]

[!TIP] Exam Strategy

• Short Answers: Memorize LCG formula, inverse transform examples (exponential, uniform), and steps for chi-square/K-S tests.

• Problems: Practice deriving random variates for simple distributions (exponential, uniform, triangular) and computing confidence intervals.

• Common Questions: "Explain antithetic variates" or "Derive exponential variate using inverse transform."

• Avoid: Confusing runs test with autocorrelation; mixing up degrees of freedom for chi-square ($k-1$ vs $k-1-p$).