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.

About these ads
Tagged with: ,

One Response

Subscribe to comments with RSS.

  1. […] a recent post Nicolas discussed some limitation of pseudo-random number generation. On a related note there’s  a feature of random variables that I find close to […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 53 other followers

%d bloggers like this: