the much smaller world of pseudo-random generation
I start a new course at ENSAE this year, on “Monte Carlo and simulation methods”. I intend to cover pseudo-random generators at the beginning, so I’m thinking about how to teach this material which I’m not so familiar with.
One very naive remark: in a “truly random world”, when I flip a coin times, I obtain one out of possible outcomes, with probability . In the real world, if I use a computer to toss coins, the number of possible outcomes (for these $n$ successive tosses) is bounded by . This is because a stream of pseudo-random numbers is completely determined by the seed (the starting point of the stream), and most generators are based on 32-bits seeds.
Compare with when is large, and you see that PRNG is quite a crude approximation of randomness. Of course, it’s not so bad in practice, because usually you are not interested in the exact value of a vector of successive coin tosses, but rather at some summary of dimension . Still, the pseudo-random world is much smaller than the random world it is supposed to mimic.
I found this remark quite scary, and I think I’ll use it to impress on my students the limitations of PRNG. By the way, if you like horror stories on PRNG, you might find the slides of Régis Lebrun (for a talk at BigMC he gave a few years back) quite entertaining. It was really funny to see the faces of my colleagues turning white as Régis was giving more and more evidence that we are often too confident in PRN generators and oblivious of their limitations. I suspect my own face was very much the same colour.