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, I have an indescribable sense that they might hint at the physical structure of our universe, how time and information are intertwined, and that they might be interchangeable.

The Monte Carlo algorithm uses random sampling to approximate solutions to complex problems. Imagine throwing darts at a table. Throw a million randomly and they'd presumably scatter uniformly. Pick a point, draw a circle, count the darts inside, and 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. Quick Sort is a good example. Pick a pivot at random, split the values by comparing them with it, smaller to one side and bigger to the other, and repeat 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 wrong results. Imagine by chance all the thrown darts landed inside the circle. The table and circle would come out the same area and the result would be drastically wrong. 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 pick the smallest value in the subset every time. The runtime would be terrible. You bet (risk) accuracy on the promise of quick results.

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... So 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?

They're even exchangeable. You can often convert a Monte Carlo into a Las Vegas by repeatedly running the Monte Carlo until a certain confidence level is reached. Going the other way, you can prematurely stop a Las Vegas algorithm and accept a potentially incorrect result. These conversions resemble how we can reduce NP problems into another, though I have yet to look closely at whether they have a more intimate link to them.

So what does this mean?

Maybe time and information are the same physical property, and we observe it in two different ways due to some Exquisite Geometric Nature of the Universe. But this is yet to be proven and might even be the answer to the P-NP problem.