Monte Carlo Algorithms vs. Las Vegas Algorithms

If you do any research on Monte Carlo algorithms, you’re bound to stumble upon another term called Las Vegas algorithms. Like Monte Carlo, the name Las Vegas was picked simply because it’s another casino location. Don’t read too much into the name; casinos in Las Vegas operate just like the Monte Carlo one does.

Both Monte Carlo and Las Vegas algorithms are randomization algorithms, but have opposite natures, as follows:

• A Monte Carlo algorithm is a randomization algorithm that is guaranteed to be fast but has a chance, albeit a small one, of producing the wrong answer.

• A Las Vegas algorithm is a randomization algorithm that is guaranteed to be correct, but has a chance, albeit a small one, of being slow.

Virtually all the randomization algorithms we’ve dealt with up until this chapter have been Las Vegas algorithms. Preshuffling an array before inserting it into a binary search tree is a Las Vegas algorithm since the BST is guaranteed to be “accurate”—which in this context means properly structured—no matter what. We do the preshuffling to increase the likelihood that the tree will be fast by being well-balanced, but we can’t guarantee that the tree will be fast. After all, we may be super unlucky and our shuffling may produce numbers that are in ascending order. In sum, this is a randomization algorithm that is guaranteed to be correct but has a small chance of being slow.

Randomized Quicksort is also a Las Vegas algorithm. No matter what, the data will be properly sorted by the time we’re done. At the same time, we randomize the pivot to increase the odds that the sorting will take place quickly. However, we can’t guarantee that the sorting will be fast, since we might choose unlucky pivots. Again, this is a randomization algorithm that will definitely be correct but might run slowly in a small percentage of cases.

Monte Carlo algorithms, on the other hand, work the other way around. By sacrificing accuracy, we guarantee that the algorithm will run quickly. For example, if we decide to only poll 500 residents of the city, we guarantee that the speed of our algorithm will be whatever time it takes to poll 500 people. So, again, it’s an algorithm that will definitely be fast but may not be entirely accurate.

When we think about Las Vegas and Monte Carlo algorithms further, we’ll see that they utilize randomization to achieve different goals. Specifically, they use randomization to help address their own weak points.

The purpose of randomization within Las Vegas algorithms is to increase speed. Although a Las Vegas algorithm, by definition, is not guaranteed to be fast, it uses randomization to increase the likelihood of being fast. (Think about Randomized Quicksort, for example.)

Monte Carlo algorithms, by contrast, use randomization to increase accuracy. The speed guarantee of Monte Carlo is achieved by techniques like cutting corners—such as polling only 500 people instead of the entire city. However, cutting corners has the side effect of reducing accuracy. Randomization is used to mitigate this side effect and help keep the algorithm as accurate as possible.

In any case, we can now put a bow on our definition of Monte Carlo algorithms. A Monte Carlo algorithm is a randomization algorithm that is guaranteed to be fast and is likely, but not guaranteed, to be correct.