Editing Monte Carlo algorithm (section)

== 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" />