Editing Monte Carlo algorithm

{{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.

==One-sided vs two-sided error==
While the answer returned by a [[deterministic algorithm]] is always expected to be correct, this is not the case for Monte Carlo algorithms. For [[decision problem]]s, these algorithms are generally classified as either '''false'''-biased or '''true'''-biased. A '''false'''-biased Monte Carlo algorithm is always correct when it returns '''false'''; a '''true'''-biased algorithm is always correct when it returns '''true'''. While this describes algorithms with ''one-sided errors'', others might have no bias; these are said to have ''two-sided errors''. The answer they provide (either '''true''' or '''false''') will be incorrect, or correct, with some bounded probability.

For instance, the [[Solovay–Strassen primality test]] is used to determine whether a given number is a [[prime number]]. It always answers '''true''' for prime number inputs; for composite inputs, it answers '''false''' with probability at least {{frac|1|2}} and '''true''' with probability less than {{frac|1|2}}. Thus, '''false''' answers from the algorithm are certain to be correct, whereas the '''true''' answers remain uncertain; this is said to be a ''{{frac|1|2}}-correct false-biased algorithm''.

==Amplification==
For a Monte Carlo algorithm with one-sided errors, the failure probability can be reduced (and the success probability amplified) by running the algorithm ''k'' times. Consider again the Solovay–Strassen algorithm which is ''{{frac|1|2}}-correct false-biased''. One may run this algorithm multiple times returning a '''false''' answer if it reaches a '''false''' response within ''k'' iterations, and otherwise returning '''true'''. Thus, if the number is prime then the answer is always correct, and if the number is composite then the answer is correct with probability at least 1&minus;(1&minus;{{frac|1|2}})<sup>''k''</sup>&nbsp;=&nbsp;1&minus;2<sup>''&minus;k''</sup>.

For Monte Carlo decision algorithms with two-sided error, the failure probability may again be reduced by running the algorithm ''k'' times and returning the [[majority function]] of the answers.

==Complexity classes==
The [[complexity class]] [[Bounded-error probabilistic polynomial|BPP]] describes [[decision problem]]s that can be solved by polynomial-time Monte Carlo algorithms with a bounded probability of two-sided errors, and the complexity class [[RP (complexity)|RP]] describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one-sided error: if the correct answer is '''false''', the algorithm always says so, but it may answer '''false''' incorrectly for some instances where the correct answer is '''true'''.<ref name=":0">{{Cite book |last1=Kudelić |first1=Robert |last2=Ivković |first2=Nikola |last3=Šmaguc |first3=Tamara |chapter=A Brief Overview of Randomized Algorithms |series=Lecture Notes in Networks and Systems |date=2023 |volume=720 |editor-last=Choudrie |editor-first=Jyoti |editor2-last=Mahalle |editor2-first=Parikshit N. |editor3-last=Perumal |editor3-first=Thinagaran |editor4-last=Joshi |editor4-first=Amit |title=IOT with Smart Systems |chapter-url=https://link.springer.com/chapter/10.1007/978-981-99-3761-5_57 |language=en |location=Singapore |publisher=Springer Nature |pages=651–667 |doi=10.1007/978-981-99-3761-5_57 |isbn=978-981-99-3761-5}}</ref> In contrast, the complexity class [[ZPP (complexity)|ZPP]] describes problems solvable by polynomial expected time Las Vegas algorithms. {{nowrap|ZPP ⊆ RP ⊆ BPP}}, but it is not known whether any of these complexity classes is distinct from each other; that is, Monte Carlo algorithms may have more computational power than Las Vegas algorithms, but this has not been proven.<ref name=":0" /> Another complexity class, [[PP (complexity)|PP]], describes decision problems with a polynomial-time Monte Carlo algorithm that is more accurate than flipping a coin but where the error probability cannot necessarily be bounded away from {{frac|1|2}}.<ref name=":0" />

== Classes of Monte Carlo and Las Vegas algorithms ==
Randomized algorithms are primarily divided by its two main types, Monte Carlo and Las Vegas, however, these represent only a top of the hierarchy and can be further categorized.<ref name=":0" />

* Las Vegas
** Sherwood—"performant and effective special case of Las Vegas"
** [[Numerical algorithm|Numerical]]—"numerical Las Vegas"
* Monte Carlo
** [[Atlantic City algorithm|Atlantic City]]—"bounded error special case of Monte Carlo"
** Numerical—"numerical approximation Monte Carlo"

"Both Las Vegas and Monte Carlo are dealing with decisions, i.e., problems in their [[Decision problem|decision version]]."<ref name=":0" /> "This however should not give a wrong impression and confine these algorithms to such problems—both types of [[randomized algorithm]]s can be used on numerical problems as well, problems where the output is not simple ‘yes’/‘no’, but where one needs to receive a result that is numerical in nature."<ref name=":0" />
{| class="wikitable"
|+Comparison of Las Vegas and Monte Carlo algorithms
!
!Efficiency
!Optimum
!Failure (LV) / Error (MC)
|-
|Las Vegas (LV)
|Probabilistic
|Certain
|<math><\tfrac{1}{2}</math>
|-
|Sherwood
|Certain, or Sherwood probabilistic 
(stronger bound than regular LV)
|Certain
|0
|-
|Numerical
|Probabilistic, certain, or 
Sherwood probabilistic
|Certain
|<math><\tfrac{1}{2}</math>or 0
|-
|Monte Carlo (MC)
|Certain
|Probabilistic
|<math><1</math>(probability which through repeated runs grows sub-exponentially 
will inhibit usefulness of the algorithm; typical case is <math><\tfrac{1}{2}</math>)
|-
|Atlantic City
|Certain
|Probabilistic
|<math><\tfrac{1}{4}</math>
|-
|Numerical
|Certain
|Probabilistic
|<math><1</math>(algorithm type dependent)
|}
Previous table represents a general framework for Monte Carlo and Las Vegas randomized algorithms.<ref name=":0" /> Instead of the mathematical symbol <math><</math> one could use <math>\leq</math>, thus making probabilities in the worst case equal.<ref name=":0" />

==Applications in computational number theory and other areas==
Well-known Monte Carlo algorithms include the Solovay–Strassen primality test, the [[Baillie–PSW primality test]], the [[Miller–Rabin primality test]], and certain fast variants of the [[Schreier–Sims algorithm]] in [[computational group theory]].

For algorithms that are a part of [[Stochastic optimization|Stochastic Optimization]] (SO) group of algorithms, where probability is not known in advance and is empirically determined, it is sometimes possible to merge Monte Carlo and such an algorithm "to have both probability bound calculated in advance and a Stochastic Optimization component."<ref name=":0" /> "Example of such an algorithm is [[Ant colony optimization algorithms|Ant Inspired]] Monte Carlo."<ref name=":0" /><ref name=":1">{{Cite journal |last1=Kudelić |first1=Robert |last2=Ivković |first2=Nikola |date=2019 |title=Ant inspired Monte Carlo algorithm for minimum feedback arc set |url=https://doi.org/10.1016/j.eswa.2018.12.021 |journal=Expert Systems with Applications |volume=122 |pages=108–117 |doi=10.1016/j.eswa.2018.12.021 |issn=0957-4174}}</ref> In this way, "drawback of SO has been mitigated, and a confidence in a solution has been established."<ref name=":0" /><ref name=":1" />

==See also==
* [[Monte Carlo method]]s, algorithms used in physical simulation and [[computational statistics]] based on taking random samples
* [[Atlantic City algorithm]]
* [[Las Vegas algorithm]]

== References==
=== Citations ===
{{Reflist}}

=== Sources ===
{{refbegin}}
* {{cite book |title = Randomized Algorithms |last1=Motwani |first1=Rajeev |author1-link = Rajeev Motwani |last2=Raghavan |first2=Prabhakar |author2-link = Prabhakar Raghavan |publisher=Cambridge University Press |location=[[New York City|New York]] |isbn = 0-521-47465-5 |year=1995 }}
* {{cite book |title=Introduction to Algorithms |last1=Cormen |first1=Thomas H. |last2 = Leiserson |first2=Charles E. |last3=Rivest |first3=Ronald L. |last4=Stein |first4=Clifford |author1-link = Thomas H. Cormen |author2-link = Charles E. Leiserson |author3-link = Ronald Rivest |author4-link = Clifford Stein |year=2001 |publisher = MIT Press and McGraw-Hill |location=[[Boston]] |edition=2nd |chapter = Ch 5. Probabilistic Analysis and Randomized Algorithms |isbn = 0-262-53196-8 |title-link=Introduction to Algorithms }}
* {{cite book |title = Algorithms: Sequential, Parallel, and Distributed |last1 = Berman |first1 = Kenneth A. |last2=Paul |first2=Jerome L. |publisher=Course Technology |location=[[Boston]] |chapter = Ch 24. Probabilistic and Randomized Algorithms |isbn = 0-534-42057-5 |year=2005 }}
{{refend}}

[[Category:Randomized algorithms]]