Monte Carlo and Las Vegas Algorithm

Many people know Monte Carlo algorithms, but few know about Las Vegas algorithms. As the name keenly suggests, both use some bets and rewards. Still, in the end, I have an indescribable sense that they might hint at the physical structure of our universe of how time and information are intertwined and, finally, that they might be interchangeable.

The Monte Carlo algorithm uses random sampling to approximate solutions to complex problems. Imagine throwing a dart at a table. You randomly throw a million darts, and they would assumably uniformly disperse. If you pick a point, draw a circle, and count the darts, you can estimate the ratio between the circle's and table's areas. From there, you can calculate pi.

Las Vegas Algorithm is similar, but slightly more sophisticated. A good example is Quick Sort. You randomly select a pivot. Divide the value by comparing it with the pivot (i.e., smaller to one side, bigger to the other) and repeat the same process on the left and right subsets.

Now the exciting part begins. While we randomly bet on something, we get significantly different results when our bet gets screwed.

• If unlucky in Monte Carlo, we get the wrong results. Imagine, just by chance, all of the thrown darts made inside the circle. The area of the table and circle would be the same, and we would get drastically wrong results. You bet (risk) on time on the promise of accurate results.
• If unlucky in Las Vegas, we take a significantly longer run time. Imagine, by chance, we choose the smallest value in the subset every time. The runtime would be terrible. You bet (risk) accuracy on the promise of quick results.

Indeed, finding the correct answer fast and accurately is prohibited by the P-NP nature of the universe (at least, that's what we think so far...). Therefore, these are two approximations of getting fast and accurate results. But isn't it fascinating that you can sacrifice run time to improve accuracy and sacrifice accuracy to improve run time?

More interestingly, they are even exchangeable. From Monte Carlo to Las Vegas, you can often convert a Monte Carlo into Las Vegas by repeatedly running the Monte Carlo until a certain confidence level is reached. From Las Vegas to Monte Carlo, you can prematurely stop a and accept a potentially incorrect result. These conversions resemble how we can reduce NP problems into another, albeit I have yet to look closely at whether they have a more intimate link to them.