In computing, a Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability.
The related class of Las Vegas algorithms is also randomized, but in a different way: they take an amount of time that varies randomly, but always produce the correct answer. A Monte Carlo algorithm can be converted into a Las Vegas algorithm whenever there exists a procedure to verify that the output produced by the algorithm is indeed correct. If so, then the resulting Las Vegas algorithm is merely to repeatedly run the Monte Carlo algorithm until one of the runs produces an output that can be verified to be correct.
The name refers to the grand casino in the Principality of Monaco at Monte Carlo, which is well-known around the world as an icon of gambling.
Read more about Monte Carlo Algorithm: One-sided Vs Two-sided Error, Amplification, Complexity Classes, Applications in Computational Number Theory
Famous quotes containing the words monte and/or carlo:
“...we were at last in Monte Cristo’s country, fairly into the country of the fabulous, where extravagance ceases to exist because everything is extravagant, and where the wildest dreams come true.”
—Willa Cather (1876–1947)
“If there is anything so romantic as that castle-palace-fortress of Monaco I have not seen it. If there is anything more delicious than the lovely terraces and villas of Monte Carlo I do not wish to see them. There is nothing beyond the semi-tropical vegetation, the projecting promontories into the Mediterranean, the all-embracing sweep of the ocean, the olive groves, and the enchanting climate! One gets tired of the word beautiful.”
—M. E. W. Sherwood (1826–1903)