Las Vegas & Monte Carlo Algorithms

Las Vegas & Monte Carlo Algorithms

The Las Vegas and the Monte Carlo algorithms, respectively, are both characterized as random algorithms. So what does this mean? At this point in the course, not much to me; but after scouring the Internet and reading many different iterations of each I decomposed my sources down to five. And even with these five, I still came away with a multitude of different meanings. With these five sites, I took a little information from each to create my own conclusions.

It seems to be that the Las Vegas algorithm is an algorithm that will always give the correct answer, or it will give no answer at all. If it gives no answer at all, then it will continue executing until it does. Should a randomized algorithm give a wrong answer, then it is considered a Monte Carlo algorithm. The Monte Carlo can give the correct answer; just it's not always reliable. So it seems that a Las Vegas algorithm is trustworthy and a Monte Carlo algorithm is not so trust worthy. I guess that means the people of Monte Carlo are untrustworthy, but the people of Las Vegas are "benevolent." Actually, the names of these two algorithms have nothing to do with the cities (or country); all I know is there is a lot of gambling in each.

In a way a Las Vegas Algorithm, such as a Quicksort, is a Monte Carlo but in a narrow way. They both use randomization in choosing the correct "pivot" to use. But to make a generic Monte Carlo algorithm into a Las Vegas then you would need to add some type of means of checking if the correct pivot was taken as well as the correct answer was given. To me a Monte Carlo algorithm is a light weight way to solve a question where the Las Vegas is much slower, but very precise.

After narrowing my search to five, I spent most of my time gathering my understanding to two sites. The Computer Science department at Cal. Berkeley gave a very good and straight forward rendition of the questioned algorithms at http://www.cs.berkeley.edu. Unfortunately, after beginning this research about a week ago, and putting it together this evening, the .pdf file is no longer there. The other site at the West Virginia University gave a more detailed and scientific description of each at http://www.csee.wvu.edu.

Main Sources: