What is a Monte Carlo algorithm?
The first time I heard the phrase “Monte Carlo Method”, my mind immediately wandered to the picturesque coasts of Monte Carlo in Monaco (in my defense, I was probably in dire need of a vacation at the time).
If you watch a lot of TV and movies, you’re probably already familiar with the famous Monte Carlo Casino, the Casino de Monte-Carlo, the architecture of which has inspired similar designs in Las Vegas as well as the fictional resort in Ian Fleming’s Casino Royale.
If you’re a statistician or probabilist, chances are you’ve heard about the night where the roulette wheel at the Monte Carlo Casino spun red 26 times in a row. If your intuition tells you that the game was rigged, or something must have been wrong with the roulette wheel, you’re right. In fact, there have been multiple occasions where gamblers were able to “break the bank” at Monte Carlo. Some of these gamblers reportedly used flaws in the designs of the roulette wheel to predict what the outcome of any given roll would be.
Where am I going with this? What does a famous casino in Monaco have to do with scientific computing?
If you had to take a guess, you might suggest that Monte Carlo methods have some aspect of stochasticity (a fancy word for randomness), much like games of chance at a casino. Congratulations – you would be right!
Indeed, the defining feature of Monte Carlo algorithms is the use of randomness to solve problems which themselves may be deterministic (a fancy word for non-random).
Let’s not worry about the details of Monte Carlo methods for now – we will go over many methods in later posts.