Editing Las Vegas algorithm (section)

== Relation to Monte Carlo algorithms ==
Las Vegas algorithms can be contrasted with [[Monte Carlo algorithm]]s, in which the resources used are bounded but the answer may be incorrect with a certain (typically small) [[probability]]. A Las Vegas algorithm can be converted into a Monte Carlo algorithm by running it for set time and generating a random answer when it fails to terminate. By an application of [[Markov's inequality]], we can set the bound on the probability that the Las Vegas algorithm would go over the fixed limit.

Here is a table comparing Las Vegas and Monte Carlo algorithms:<ref>Goodrich, Michael. ''Algorithm Design and Applications: Randomized Algorithms.'' Wiley, 2015'','' https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf. Oct 23, 2018.</ref>
{| class="wikitable"
!
!Running Time
!Correctness
|-
|Las Vegas Algorithm
|probabilistic
|certain
|-
|Monte Carlo Algorithm
|certain
|probabilistic
|}

If a deterministic way to test for correctness is available, then it is possible to turn a Monte Carlo algorithm into a Las Vegas algorithm. However, it is hard to convert a Monte Carlo algorithm to a Las Vegas algorithm without a way to test the algorithm. On the other hand, changing a Las Vegas algorithm to a Monte Carlo algorithm is easy. This can be done by running a Las Vegas algorithm for a specific period of time given by confidence parameter. If the algorithm finds the solution within the time, then it is success and if not then output can simply be "sorry".

This is an example of Las Vegas and Monte Carlo algorithms for comparison:<ref>{{cite web |url = https://www.cs.cmu.edu/~arielpro/15251f15/slides/lec20.pdf |title = Great Theoretical Ideas in Computer Science |last=Procaccia |first = Ariel |date = 5 November 2015 |website = www.cs.cmu.edu |type = [[Microsoft PowerPoint|PowerPoint]]
|access-date = 3 November 2018 }}</ref>

Assume that there is an array with the length of even ''n''. Half of the entries in the array are 0's and the remaining half are 1's. The goal here is to find an index that contains a 1.

<syntaxhighlight lang="java">
// A is array of length n.
n = A.length

// Las Vegas algorithm
repeat:
    k = RandInt(n);
    if A[k] == 1,
        return k;
        
// Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n);
    if A[k] == 1,
        return k;
return "Failed";
</syntaxhighlight>

Since Las Vegas does not end until it finds 1 in the array, it does not gamble with the correctness but run-time. On the other hand, Monte Carlo runs 300 times, which means it is impossible to know that Monte Carlo will find "1" in the array within 300 times of loops until it actually executes the code. It might find the solution or not. Therefore, unlike Las Vegas, Monte Carlo does not gamble with run-time but correctness.