COMP 1103 · Randomness: Can Computers Be Random?

Led by Knuthian Algorithm Simulacrum

Can a deterministic machine produce randomness? The surprisingly deep mathematics of pseudorandom number generation. Based on Knuth.

1. Module 1

   What Is Randomness?

   Led by Knuthian Algorithm Simulacrum

   The question

   A sequence is pseudorandom if no feasible test can distinguish it from a truly random sequence. Why is this the right definition — and why is human intuition about randomness so systematically wrong?

   Outcome

   The student can explain why true randomness is impossible from algorithms.

   Sub-units

   1. ○ 1.1 True vs Pseudorandom Open this unit → ✓ ↻
   2. ○ 1.2 Why Intuition Fails Open this unit → ✓ ↻
   Begin the course → Print certificate of completion
2. Module 2

   Linear Congruential Generators

   Led by Knuthian Algorithm Simulacrum

   The question

   X_{n+1} = (aX_n + c) mod m. With good parameters: good sequences. With bad parameters: obvious patterns. The spectral test reveals the difference. What makes parameters good or bad?

   Outcome

   The student can identify bad LCG parameters and explain the spectral test.

   Sub-units

   1. ○ 2.1 Break a Bad LCG Open this unit → ✓ ↻
   2. ○ 2.2 The Spectral Test Open this unit → ✓ ↻
   Open this module → Print certificate of completion
3. Module 3

   Better Generators: Mersenne Twister and Beyond

   Led by Knuthian Algorithm Simulacrum

   The question

   The Mersenne Twister passes every statistical test — but given 624 consecutive outputs, an adversary can predict all future outputs. Why does this matter, and what do cryptographic PRNGs require instead?

   Outcome

   The student can explain why statistical and cryptographic randomness are different requirements.

   Sub-units

   1. ○ 3.1 Cryptographic vs Statistical Open this unit → ✓ ↻
   Open this module → Print certificate of completion
4. Module 4

   Monte Carlo Methods

   Led by Knuthian Algorithm Simulacrum

   The question

   Estimate pi by throwing random points at a square. It works. Why? And why does the accuracy of any Monte Carlo simulation depend entirely on the quality of the underlying PRNG?

   Outcome

   The student can implement Monte Carlo pi estimation and explain convergence.

   Sub-units

   1. ○ 4.1 Estimate Pi Open this unit → ✓ ↻
   Open this module → Print certificate of completion
5. Module 5

   Randomness, Uncertainty, and Truth

   Led by Knuthian Algorithm Simulacrum

   The question

   A simulation run with a fixed seed is deterministic but represents genuine uncertainty in the system being modelled. We use deterministic processes to represent genuine ignorance. Can a machine be random — and does the answer matter?

   Outcome

   The student can take a defended position on machine randomness.

   Sub-units

   1. ○ 5.1 Final Essay: Can a Machine Be Random? Open this unit → ✓ ↻
   Open this module → Print certificate of completion