Random Numbers: Generation, Testing, and Applications

TAKEAWAYS:

• Random numbers are pseudo-random in simulations, generated via deterministic algorithms (e.g., Linear Congruential Generators) but appearing random.
• Statistical tests (e.g., Chi-square, Runs test) verify if generated sequences are truly random.
• Applications include Monte Carlo simulations, cryptography, and game design (e.g., Pathao’s ride-matching).
• Seeding controls PRNG reproducibility; poor seeds lead to predictable sequences.
• Periodicity and uniformity are critical for high-quality PRNGs.
• Real-world examples: WhatsApp’s end-to-end encryption (random keys), Ncell’s call routing (randomized load balancing).

1. Why Random Numbers Matter in Simulation

Simulations rely on randomness to model uncertainty. For example:

• Monte Carlo simulations (used in finance, physics, and AI) estimate probabilities by repeating random trials.
• Cryptography (e.g., WhatsApp’s Signal Protocol) uses random numbers to generate secure keys.
• Game design (e.g., Pathao’s ride-matching algorithm) assigns random priorities to drivers to balance load.

2. Pseudo-Random Number Generators (PRNGs)

PRNGs are deterministic algorithms that produce sequences appearing random but repeatable if seeded identically. Key types:

A. Linear Congruential Generator (LCG)

The simplest PRNG, defined by: $$X_{n+1}=(a\cdot X_n+c)\mathrm{mod}m$$

• Parameters:
  • $X_n$: Current value (seed).
  • $a$: Multiplier (controls period).
  • $c$: Increment (controls offset).
  • $m$: Modulus (controls range).
• Example: Generate 5 numbers with $X_0=3$, $a=5$, $c=7$, $m=11$.

  n | X_n | Calculation
  --- | --- | ---
  0 | 3 | Seed
  1 | 8 | (5*3 + 7) mod 11 = 22 mod 11
  2 | 3 | (5*8 + 7) mod 11 = 47 mod 11
  3 | 8 | (5*3 + 7) mod 11 = 22 mod 11
  4 | 3 | (5*8 + 7) mod 11 = 47 mod 11
  5 | 8 | ...
  

  Observation: The sequence repeats every 2 steps (periodicity = 2). Poor choice of $a,c,m$ leads to short periods.

B. Mersenne Twister

A high-quality PRNG with:

• Period: $2^{19937}-1$ (practically infinite for most uses).
• Uniformity: Passes rigorous statistical tests.
• Used in: Python’s random module, financial risk modeling.

3. Testing Randomness

Generated sequences must pass statistical tests to ensure fairness. Key tests:

Worked Example: Chi-square Test

• Hypothesis: Numbers are uniformly distributed in [0,1).
• Steps:
  1. Generate 1000 numbers from a PRNG.
  2. Divide into 10 bins (e.g., [0.0–0.1), [0.1–0.2), ..., [0.9–1.0)).
  3. Count numbers per bin (e.g., Bin 1: 98, Bin 2: 112, ...).
  4. Calculate ${\chi }^2=\sum \frac{(O_i-E_i{)}^2}{E_i}$, where $E_i=100$ (expected count).
  5. Compare to critical value (e.g., ${\chi }_{0.05,9}^2=16.92$). If ${\chi }^2<16.92$, accept uniformity.

4. Applications in Nepal

A. Pathao’s Ride-Matching Algorithm

• Problem: Assign drivers to riders fairly to minimize wait times.
• Solution: Use PRNGs to randomize driver selection order, reducing bias.
• Example: Two drivers (A, B) compete for a rider. Assign a random score (e.g., A: 0.7, B: 0.3). Higher score gets the ride.

B. Ncell’s Call Routing

• Problem: Distribute calls evenly across servers to prevent overload.
• Solution: Use random hashing to assign calls to servers.
• Example: Hash caller ID with a random seed → Server 3 gets the call.

C. NEPSE Stock Simulations

• Problem: Model stock price fluctuations under uncertainty.
• Solution: Monte Carlo simulation with PRNGs to generate random price changes.
• Example: Simulate 1000 price paths for a stock starting at Rs. 1000, with daily changes of $\pm 5\%$ (randomly selected).

flowchart TD
    A["Rider requests ride"] --> B["Generate random scores for all drivers"]
    B --> C["Assign ride to driver with highest score"]
    C --> D["Update driver availability"]

5. Common Pitfalls

6. Real-World Example: WhatsApp’s Encryption

• Problem: Secure end-to-end encryption requires unique keys per chat.
• Solution: Use a Cryptographically Secure PRNG (CSPRNG) to generate keys.
• How:
  1. Combine user input (e.g., password) with a random seed.
  2. Feed into a CSPRNG (e.g., ChaCha20) to produce a 256-bit key.
  3. Encrypt messages with AES-256 using this key.

flowchart LR
    A["User Input + Random Seed"] --> B["CSPRNG (ChaCha20)"]
    B --> C["256-bit Key"]
    C --> D["AES-256 Encryption"]
    D --> E["Encrypted Message"]

Exam Tip

1. Memorize LCG formula and recognize when to use it (e.g., simple simulations).
2. Know statistical tests: Chi-square for uniformity, Runs for patterns.
3. Application focus: Link PRNGs to Monte Carlo, cryptography, or load balancing (e.g., Pathao/Ncell).
4. Avoid common mistakes:
   • Using poor seeds (e.g., seed = 1).
   • Ignoring periodicity in LCG.
5. Practical question: Given a PRNG output, calculate Chi-square or identify non-randomness.

Visual Summary:

mindmap
  root((Random Numbers in Simulation))
    PRNGs
      LCG
      Mersenne Twister
    Tests
      Chi-square
      Runs
    Applications
      Pathao (ride-matching)
      WhatsApp (encryption)
      Ncell (call routing)