What are Monte Carlo Methods?

“Monte Carlo methods” is a technical term for a technique you’ve used since you were a small child.

Say you flip a coin. How often do you expect it to come up heads? Well, if we assume the coin won’t land on its edge, each face has the same chance of coming up, so half the time.

Say you roll a six-sided die. How often do you expect it to land on six? Same sort of argument. One in six.

Now imagine you’re a kid, and I again ask you how often you expect to roll a six. By kid, I mean someone who won’t be able to work out the exact answer given above.

How would you try to answer this? I suspect you’d roll the die a couple of times, see how large a proportion of the rolls come up sixes, and use that as a guess.

If so, congratulations! You discovered Monte Carlo methods even before your enthusiasm for maths was killed by algebra.

That’s really all Monte Carlo methods are: instead of working out the exact answer, you take a few random samples and use them to make a guess.

If it’s too much of an imaginative stretch to need to do this for such a simple problem, say I put a board game in front of you where you move your piece according to a roll of several dice. I then ask you how often you’ll land on a particular square by the end of the game.

To guess at an answer, you can then play the game a couple of times, and keep track of how many times you land on the square in each game.

Past a certain point in schooling, it’s easy to forget about making estimates like this. The questions usually posed to you, when being taught algebra and probability, are set up so that you can obtain the exact answer by hand. You can’t make a Monte Carlo estimate in an exam, using just pencil and paper. It’s not technically illegal to take dice into an exam, but rolling them will drive everyone else in the room crazy.

Once you look at real-life applications, however, you often find problems where you just can’t find the exact answer. The maths involved might be horrendous, or impossible. You simply mightn’t know everything you’d need to know to calculate the answer, because the needed information is impossible to observe.

So, what do you do? Well, you go back to rolling dice. At least, you get a computer to roll dice for you.

Usually Monte Carlo methods are a bit more advanced – in particular, we can often get some idea of how accurate we expect the estimate to be – but this constitutes the basics.

Hang on, though. We need to generate a lot of random samples for this to work, right? Won’t that take a while?

Yes, it will. Monte Carlo methods can take a long time to give an accurate. If your problem involves, say, predicting the weather, then the equivalent of rolling a die is now running a complete weather simulation. Depending on how sophisticated the model is, and how far ahead you’re forecasting, that can take hours, or days.

However, this is much less time than we’d expect to take finding the exact solution. The kid takes a while to roll his dice, and he would have spent less time finding the exact answer if he knew how to calculate it. Since he doesn’t, however, what we really need to compare against is how long he’d wait before he could work out how to do so. That’s probably years away. What if you need an answer now? Get rolling.

There are ways we can reduce the time these estimates take. Different methods make better use of the samples, so we can get away with using less samples, and still estimate with the same accuracy. Some are easier to implement. Some are specially designed to work very well for whatever particular problem the designer is working on. Some make better use of the way that modern computers are built – I’ll talk about this in another post. It’s a very general framework, so there’s a lot of flexibility.

Since there is a lot of flexibility, what you use depends on the problem. So, we’d better look at one. Next time, I’ll give an example of using these methods on a slightly more complex set of problems, commonly known as Pólya’s Urn. That’s a technical term mathematicians invented to justify playing at lucky dip boxes all day, on which we’ll be using a technique you’ve used since you were a child. Statistics is a very serious subject.

Advertisements

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