5. Pseudo-random number generation

At the heart of the use of randomness for computation lies the problem of generating pseudo-random numbers. This is what we call the production of sequences of numbers that behave, from a statistical point of view, like realizations of sequences of i.i.d. random variables. The words in italics are important: we're talking about sequences (usually long sequences) of numbers. If we wanted to "produce" a single uniform binary value (a '0' or a '1' with probability 1/2), we could just as easily write '0' as '1' - both possibilities are equally "good". If we needed a real number that behaved like a realization of a uniform a.v. on [0, 1], we could write 0.0, or 0.5, or 0.12345 - it makes no difference. It's quite a different matter to produce 10 ⁶ numbers behaving like a possible realization of 10 ⁶ v.a....