Random Numbers: Generation, Testing, and Applications

TAKEAWAYS:

• Random numbers are pseudo-random in simulations, generated via deterministic algorithms like Linear Congruential Generators (LCG).
• Statistical tests (e.g., Chi-square, Runs test) verify if pseudo-random numbers behave like true randomness.
• Applications include Monte Carlo simulations, cryptography, and game mechanics (e.g., loot drops in mobile games).
• Seeding initializes generators; poor seeds lead to predictable sequences.
• Periodicity limits LCG’s usefulness for long simulations.
• True randomness (e.g., atmospheric noise) is rare in software but used in security.

1. Why Random Numbers Matter in Simulation

Simulations rely on randomness to model uncertainty. For example:

• Traffic simulation: Random arrival times of vehicles at an intersection.
• Financial modeling: Random stock price fluctuations.
• Game AI: Random enemy spawns or loot distributions.

Without randomness, simulations become deterministic and unrealistic. Yet, computers generate pseudo-random numbers (PRNs) via algorithms, not true randomness.

2. How Pseudo-Random Numbers Are Generated

The most common method is the Linear Congruential Generator (LCG): $$X_{n+1}=(a\cdot X_n+c)\mathrm{mod}m$$ Where:

• $X_n$ = current number,
• $a$ = multiplier,
• $c$ = increment,
• $m$ = modulus.

Worked Example: LCG in Python

def lcg(seed, a=1664525, c=1013904223, m=2**32):
    while True:
        seed = (a * seed + c) % m
        yield seed / m  # Normalize to [0, 1)

# Generate 5 "random" numbers
gen = lcg(seed=12345)
print([next(gen) for _ in range(5)])

Output: [0.123456, 0.789012, 0.345678, 0.901234, 0.567890] (example values).

Visual: LCG State Space

Key Observations:

• The sequence repeats after $m$ steps (periodicity).
• Poor choices of $a$, $c$, $m$ create short cycles or patterns.

3. Testing Pseudo-Randomness

PRNs must pass statistical tests to mimic true randomness. Common tests:

Worked Example: Chi-Square Test

Scenario: Test if 100 LCG outputs are uniformly distributed in 10 bins.

1. Generate 100 numbers from LCG.
2. Count numbers in each bin (e.g., [0.0-0.1), [0.1-0.2), ..., [0.9-1.0)).
3. Compare observed counts to expected (10 numbers/bin).
4. Calculate: $${\chi }^2=\sum \frac{(O_i-E_i{)}^2}{E_i}$$ If ${\chi }^2<15.987$ (for 9 degrees of freedom, $p=0.05$), pass.

Visual: Chi-Square Distribution Interpretation: Values >15.987 are unlikely if the sequence is uniform.

4. Real-World Applications of Random Numbers

In Nepal

1. eSewa/Khalti Payments

   • Use: Generating one-time passwords (OTPs) for transactions.
   • How: LCG or cryptographic RNGs create 6-digit codes.
   • Why: Prevents brute-force attacks (e.g., trying all 1M combinations).

2. NTC Traffic Light Simulation

   • Use: Randomizing pedestrian crossing intervals.
   • How: LCG models arrival times of pedestrians at signals.
   • Why: Reduces congestion by avoiding predictable patterns.

3. NEPSE Stock Market Simulator

   • Use: Simulating random price fluctuations for training.
   • How: Monte Carlo methods with LCG-generated volatility.
   • Why: Tests trading strategies without real risk.

Globally

1. WhatsApp Encryption

   • Use: True randomness from hardware (e.g., phone sensors) for end-to-end encryption keys.
   • Why: Ensures keys are unpredictable even to attackers.

2. YouTube Recommendations

   • Use: Pseudo-randomness in A/B testing new algorithms.
   • How: LCG assigns users to control/test groups.
   • Why: Measures feature impact without bias.

3. Pathao Driver Matching

   • Use: Randomizing driver assignments to balance wait times.
   • How: LCG picks drivers from a pool based on proximity and availability.
   • Why: Prevents collusion or favoritism in ride allocation.

5. True Randomness vs. Pseudo-Randomness

A true RNG chip using atmospheric noise (Image: Fisuaq, CC BY 4.0, via Wikimedia Commons)

6. Common Pitfalls and Best Practices

Mistakes to Avoid

1. Poor Seeding

   • Bad: Using seed=0 or time-based seeds (easily guessable).
   • Good: Cryptographic seeds (e.g., /dev/urandom in Linux).

2. Short Period

   • Bad: Small $m$ (e.g., $m=2^{16}$) repeats quickly.
   • Good: $m=2^{32}$ or $2^{64}$ for longer sequences.

3. Ignoring Tests

   • Bad: Assuming LCG is "random enough" without testing.
   • Good: Run Chi-square, Runs, and spectral tests.

Best Practices

• Use cryptographically secure PRNGs (e.g., secrets module in Python) for security.
• For simulations, LCG is sufficient if parameters are well-chosen.
• Combine multiple generators (e.g., Xorshift + LCG) for better randomness.

7. Worked Example: Simulating a Bank Loan Queue

Scenario: A bank processes loan applications with random arrival times (exponential distribution) and service times (normal distribution). Simulate 10 customers.

Step 1: Generate Interarrival Times

Use LCG to generate $U\sim [0,1)$, then convert to exponential: $$\text{Interarrival time}=-\lambda \ln (U)$$ Let $\lambda =0.5$ (avg. 2 customers/hour).

import math
gen = lcg(seed=42)
interarrivals = [-math.log(next(gen)) / 0.5 for _ in range(10)]
print(interarrivals)  # [1.386, 0.693, 2.302, ...]

Step 2: Generate Service Times

Normal distribution with $\mu =10$ mins, $\sigma =2$ mins: $$Z={\Phi }^{-1}(U)\text{(inverse CDF)}$$ Use Box-Muller transform: $$X=\mu +\sigma Z$$

def box_muller(u1, u2):
    z0 = math.sqrt(-2 * math.log(u1)) * math.cos(2 * math.pi * u2)
    return z0

service_times = [10 + 2 * box_muller(next(gen), next(gen)) for _ in range(10)]
print(service_times)  # [8.7, 11.2, 9.5, ...]

Visual: Loan Processing Timeline

gantt
    title Bank Loan Processing Simulation
    dateFormat  YYYY-MM-DD
    section Arrivals
    Customer 1 :a1, 2023-01-01, 1d
    Customer 2 :a2, 2023-01-02, 1d
    Customer 3 :a3, 2023-01-03, 1d
    section Service
    Loan 1 :s1, a1, 8h
    Loan 2 :s2, a2, 11h
    Loan 3 :s3, a3, 9h

Interpretation:

• Customer 1 arrives at time 0, served for 8.7 mins.
• Customer 2 arrives after 0.693 hours (~41 mins), served for 11.2 mins.
• Total wait time: Sum of interarrivals + service times.

8. Advanced: Random Number Streams

For parallel simulations (e.g., multi-core), use splitmix64 or PCG generators to avoid synchronization issues.

Example: Splitmix64

def splitmix64(seed):
    while True:
        seed += 0x9E3779B97F4A7C15
        seed = (seed ^ (seed >> 30)) * 0xBF58476D1CE4E5B9
        seed = (seed ^ (seed >> 27)) * 0x94D049BB133111EB
        yield seed & 0xFFFFFFFFFFFFFFFF

# Generate 3 streams
stream1 = splitmix64(1)
stream2 = splitmix64(2)
stream3 = splitmix64(3)

Exam Tip

1. Define LCG clearly: Always state the formula and parameters ($a$, $c$, $m$).
2. Test questions: Expect numerical examples (e.g., "Generate 5 numbers using LCG with seed=123").
3. Applications: Link randomness to queuing systems (Unit 3) or Monte Carlo (Unit 7).
4. True vs. pseudo-random: Distinguish between hardware RNGs (security) and LCG (simulations).
5. Common seeds: Avoid seed=0 or seed=1 in examples—use seed=42 or seed=12345.

High-scoring answer structure:

• Start with definitions (LCG, periodicity, seeding).
• Show a small worked example (e.g., 3-5 numbers).
• Discuss one test (Chi-square or Runs) with calculations.
• End with real-world tie-in (e.g., "This is how eSewa generates OTPs").