Random Number Generation & Statistical Tests in Simulation

TAKEAWAYS:

• Pseudo-random numbers (LCG/MCG) are deterministic but appear random for simulations, while true randomness comes from physical entropy (e.g., atmospheric noise).
• Statistical tests (KS, Chi-square) verify if generated numbers are uniform and independent—critical for valid simulation outputs.
• Inverse transform converts uniform random numbers to any distribution (e.g., exponential for Ncell call arrival times), while acceptance-rejection samples from complex distributions.
• Monte Carlo uses random sampling to estimate solutions (e.g., Daraz’s inventory risk analysis) and relies on the Law of Large Numbers for accuracy.
• Output analysis methods (point estimation, confidence intervals) quantify simulation results’ reliability (e.g., predicting eSewa transaction delays).

---

1. True vs. Pseudo-Random Numbers

Definitions and Properties

Random numbers are essential for simulations to model uncertainty. There are two types:

How PRNs Work: Linear Congruential Generator (LCG)

The most common PRN algorithm: $$X_{n+1}=(a\cdot X_n+c)\mathrm{mod}m$$

• Parameters:
  • $X_0$: Seed (starting value)
  • $a$: Multiplier
  • $c$: Increment
  • $m$: Modulus (controls range)

Example: Generate 10 random integers using LCG with $m=1000$, $a=19$, $c=6$, $X_0=13$.

Output: 13, 255, 861, 487, 343, 940, 738, 250, 656, 140

Real-World Tie-In: Nepal’s Ncell uses PRNs to simulate call arrival times in its network traffic models. A poorly seeded LCG could create artificial patterns, overloading servers during peak hours (e.g., 6–9 PM).

---

2. Statistical Tests for Randomness

Simulations require random numbers that pass uniformity and independence tests.

A. Kolmogorov-Smirnov (KS) Test for Uniformity

Purpose: Checks if a sequence is uniformly distributed between [0,1]. Steps:

1. Sort the sequence and plot the empirical distribution function (ECDF).
2. Compute $D=\max |F_n(x)-F(x)|$, where:
   • $F_n(x)$ = ECDF (step function).
   • $F(x)$ = Uniform CDF ($F(x)=x$ for $0\le x\le 1$).
3. Compare $D$ to critical values (e.g., $D_{0.05,10}=0.41$).

Example: Test the sequence 0.35, 0.77, 0.12, 0.33, 0.88, 0.45, 0.19 for uniformity at $\alpha =0.05$.

Critical Value Table:

B. Chi-Square Test for Uniformity

Purpose: Divides [0,1] into $k$ bins and checks if counts match expectations. Formula: $${\chi }^2=\sum \frac{(O_i-E_i{)}^2}{E_i},E_i=\frac{n}{k}$$ Example: Test 0.54, 0.73, 0.98, 0.11, 0.68, 0.45 for uniformity with $k=3$ bins.

C. Poker Test for Independence

Purpose: Checks if digits in a sequence are independent (e.g., no repeated pairs). Steps:

1. Split numbers into groups of 4 digits (e.g., 1234, 5678).
2. Count how often all 4 digits are unique (no repeats).
3. Compare to expected frequency under independence.

Example: In 1,000 four-digit numbers, 525 had all unique digits.

• Expected: $10\times 9\times 8\times 7/10^4=0.504$ per number → 504 expected.
• Observed: 525 → Not significantly different (passes independence).

Real-World Tie-In: eSewa uses random number tests to detect fraud in transaction IDs. If the Poker test fails, IDs may be algorithmically generated (e.g., 1111, 2222), flagging potential hacking.

---

3. Generating Non-Uniform Random Variates

Simulations often need numbers from specific distributions (e.g., exponential for call times).

A. Inverse Transform Method

Idea: Use the inverse of the CDF to transform uniform random numbers. Steps:

1. Generate $U\sim \text{Uniform}(0,1)$.
2. Compute $X=F^{-1}(U)$, where $F$ is the target CDF.

Example: Generate exponential random variables with rate $\lambda =0.5$. $$F(x)=1-e^{-\lambda x}⟹F^{-1}(U)=-\frac{\ln (1-U)}{\lambda }$$ Trace:

B. Acceptance-Rejection Method

Idea: Sample from a proposal distribution and accept/reject based on a bound. Steps:

1. Choose a proposal $g(x)$ that dominates $f(x)$ (target PDF).
2. Generate $U\sim \text{Uniform}(0,1)$ and $X\sim g(x)$.
3. Accept $X$ if $U\le \frac{f(X)}{c\cdot g(X)}$, where $c$ is a constant.

Example: Generate from $f(x)=2x$ on [0,1] using $g(x)=1$ (uniform).

• $c=2$ (since $1\ge 2x$ for all $x$).
• Trace:
  • $X=0.3$, $U=0.4$
  • Check: $0.4\le \frac{2\times 0.3}{2\times 1}=0.3$ → Reject.
  • Next $X=0.7$, $U=0.5$
  • Check: $0.5\le 0.7$ → Accept.

Real-World Tie-In: Pathao uses acceptance-rejection to model rider wait times. If arrival times follow a heavy-tailed distribution (e.g., $f(x)\propto x^{-2}$), uniform sampling would bias results. The method ensures realistic surge pricing during traffic jams.

---

4. Monte Carlo Simulation

Definition: Uses random sampling to estimate numerical results (e.g., integrals, probabilities).

How It Works

1. Problem: Estimate $\theta ={\int }_a^{b}g(x)dx$.
2. Steps:
   • Generate $X_i\sim f(x)$ (proposal distribution).
   • Compute $\theta \approx \frac{1}{n}{\sum }_{i=1}^n\frac{g(X_i)}{f(X_i)}$.

Example: Estimate $\pi$ using Monte Carlo.

Trace (100 points):

• Inside circle: 78
• $\pi \approx 4\times 78/100=3.12$ (close to 3.1416).

Real-World Tie-In: Nepal Stock Exchange (NEPSE) uses Monte Carlo to simulate portfolio risks. For example, estimating the probability that a stock’s value drops >20% in a year:

1. Sample 10,000 paths of daily returns from a normal distribution.
2. Count paths where the cumulative return < -20%.
3. Probability ≈ count/10,000.

---

5. Output Analysis Methods

After running a simulation, analyze the results statistically.

Example: A bank simulates loan default rates over 100 runs, yielding defaults: [5, 7, 4, 6, 8].

• Mean default rate: $\bar{X}=6\%$.
• 95% CI: $6\%\pm 2.78\times \frac{1.58}{\sqrt{5}}\approx [3.5\%,8.5\%]$.

---

In the Real World

1. eSewa Transaction IDs:

   • Idea: Poker test for independence.
   • How: eSewa generates 12-digit IDs. If the Poker test shows too many repeated digits (e.g., 112233), the system flags potential fraud (e.g., a hacker generating predictable IDs).

2. Ncell Network Traffic Simulation:

   • Idea: Exponential variate generation (inverse transform).
   • How: Call arrivals follow a Poisson process (interarrival times are exponential). Ncell’s simulators use LCG to generate uniform numbers, then transform them to model peak-hour congestion (e.g., 7–8 PM).

3. Daraz Inventory Management:

   • Idea: Monte Carlo for demand forecasting.
   • How: Daraz runs 10,000 simulations of daily orders for a product, sampling from historical demand distributions. The 90th percentile of the results determines safety stock levels to avoid stockouts during festivals (e.g., Dashain).

---

Exam Tip

1. LCG/MCG Questions:

   • Always show the first 3–4 iterations in your answer.
   • Memorize the formula: $X_{n+1}=(a{X}_n+c)\mathrm{mod}m$.
   • Common Pitfall: Forgetting to take modulo $m$ in each step.

2. Statistical Tests:

   • KS Test: Plot the ECDF vs. CDF and mark $D$.
   • Chi-Square: Show the table of observed vs. expected counts.
   • Poker Test: Calculate the expected frequency of all-unique-digit numbers.

3. Variate Generation:

   • For inverse transform, always write the CDF and its inverse.
   • For acceptance-rejection, draw the proposal and target PDFs and label the rejection region.

4. Monte Carlo:

   • Explain the Law of Large Numbers (more samples → better estimate).
   • For $\pi$ estimation, sketch the unit circle and grid.

5. Output Analysis:

   • If asked about confidence intervals, state the formula and plug in numbers.
   • For batch means, mention why it reduces autocorrelation.

---