# Statisfaction

## the much smaller world of pseudo-random generation

Posted in General by nicolaschopin on 16 September 2013

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 $n$ times, I obtain one out of $2^n$ possible outcomes, with probability $2^{-n}$. In the real world, if I use a computer to toss $n$ coins, the number of possible outcomes (for these \$n\$ successive tosses) is bounded by $2^{32}$. 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 $2^{32}$ with $2^n$ when $n$ 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 $n$ successive coin tosses, but rather at some summary of dimension $d\ll 2^{32}$. 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.