Editing Monte Carlo algorithm (section)

{{Short description|Type of randomized algorithm}}
{{distinguish|Monte Carlo method}}
{{More footnotes needed|date=August 2011}}

In [[computing]], a '''Monte Carlo algorithm''' is a [[randomized algorithm]] whose output may be incorrect with a certain (typically small) [[probability]]. Two examples of such algorithms are the [[Karger's algorithm|Karger–Stein algorithm]]<ref>{{Cite journal|last1=Karger|first1=David R.|last2=Stein|first2=Clifford|date=July 1996|title=A New Approach to the Minimum Cut Problem|journal=J. ACM|volume=43|issue=4|pages=601–640|doi=10.1145/234533.234534|s2cid=5385337|issn=0004-5411|doi-access=free}}</ref> and the Monte Carlo algorithm for [[minimum feedback arc set]].<ref>{{Cite journal|last=Kudelić|first=Robert|date=2016-04-01|title=Monte-Carlo randomized algorithm for minimal feedback arc set problem|journal=Applied Soft Computing|volume=41|pages=235–246|doi=10.1016/j.asoc.2015.12.018}}</ref>

The name refers to the [[Monte Carlo Casino|Monte Carlo casino]] in the [[Monaco|Principality of Monaco]], which is well-known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by [[Nicholas Metropolis]].<ref>{{Cite journal|last=Metropolis |first=N. |authorlink=Nicholas Metropolis|url=http://library.lanl.gov/la-pubs/00326866.pdf|title=The beginning of the Monte Carlo method|journal=[[Los Alamos Science]]|issue=1987 Special Issue dedicated to Stanislaw Ulam|pages=125–130|year=1987 }}</ref>

[[Las Vegas algorithm]]s are a [[dual (mathematics)|dual]] of Monte Carlo algorithms and never return an incorrect answer. However, they may make random choices as part of their work. As a result, the time taken might vary between runs, even with the same input.

If there is a procedure for verifying whether the answer given by a Monte Carlo algorithm is correct, and the probability of a correct answer is bounded above zero, then with probability one, running the algorithm repeatedly while testing the answers will eventually give a correct answer. Whether this process is a Las Vegas algorithm depends on whether halting with probability one is considered to satisfy the definition.