Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates, but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex.
Las Vegas algorithms are prominent in the field of artificial intelligence, and in other areas of computer science and operations research. In AI, stochastic local search algorithms are considered to be of Las Vegas type. Recently, SLS algorithms have been used to address NP-complete decision problems and NP-hard combinatorial optimization problems. However, some systematic search methods, such as modern variants of the Davis–Putnam algorithm for propositional satisfiability, also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms.
History
Las Vegas algorithms were introduced by László Babai in 1979, in the context of the graph isomorphism problem, as a dual to Monte Carlo algorithms. Babai introduced the term "Las Vegas algorithm" alongside an example involving coin flips: the algorithm depends on a series of independent coin flips, and there is a small chance of failure. However, in contrast to Monte Carlo algorithms, the Las Vegas algorithm can guarantee the correctness of any reported result.Example
// Las Vegas algorithm
repeat:
k = RandInt
if A 1,
return k;
As mentioned above, Las Vegas algorithms always return correct results. The code above illustrates this property. A variable k is generated randomly; after k is generated, k is used to index the array A. If this index contains the value 1, then k is returned; otherwise, the algorithm repeats this process until it finds 1. Although this Las Vegas Algorithm is guaranteed to find the correct answer, it does not have a fixed runtime; due to the randomization, it is possible for arbitrarily much time to elapse before the algorithm terminates.
Definition
This section provides the conditions which characterize an algorithm's being of Las Vegas type.An algorithm A is a Las Vegas algorithm for problem class X, if
whenever for a given problem instance x∈X it returns a solution s, s is guaranteed to be a valid solution of x
on each given instance x, the run-time of A is a random variable RTA,x
There are three notions of completeness for Las Vegas algorithms:
- complete Las Vegas algorithms can be guaranteed to solve each solvable problem within run-time tmax, where tmax is an instance-dependent constant.
some tmax such that P = 1.
- approximately complete Las Vegas algorithms solve each problem with a probability converging to 1 as the run-time approaches infinity. Thus, A is approximately complete, if for each instance x, limt→∞ P = 1.
- essentially incomplete Las Vegas algorithms are Las Vegas algorithms which are not approximately complete.
Application scenarios
Las Vegas algorithms have different criteria for the evaluation based on the problem setting. These criteria are divided into three categories with different time limits since Las Vegas algorithms do not have set time complexity. Here are some possible application scenarios:Type1: There are no time limits, which means the algorithm runs until it finds the solution.
Type2: There is a time limit tmax for finding the outcome.
Type3: The utility of solution is determined by the time required to find the solution.
Note that Type1 and Type2 are special cases of Type3.
For Type 1 where there is no time limit, the average run-time can represent the run-time behavior. This is not the same case for the Type 2.
Here, P, which is the probability of finding a solution within time, describes its run-time behavior.
In case of Type 3, its run-time behavior can only be represented by the run-time distribution function rtd: R → defined as rtd = P or its approximation.
The run-time distribution is the distinctive way to describe the run-time behavior of a Las Vegas algorithm.
With this data, we can easily get other criteria such as the mean run-time, standard deviation, median, percentiles, or success probabilities P for arbitrary time-limits t.
Applications
Analogy
Las Vegas algorithms arise frequently in search problems. For example, one looking for some information online might search related websites for the desired information. The time complexity thus ranges from getting "lucky" and finding the content immediately, to being "unlucky" and spending large amounts of time. Once the right website is found, then there is no possibility of error.Randomized QuickSort
INPUT:
# A is an array of n elements
def randomized_quicksort:
if n = 1:
return A # A is sorted.
else:
i = random.randrange # Will take a random number in the range 1~n
X = A # The pivot element
"""Partition A into elements < x, x, and >x # as shown in the figure above.
Execute Quicksort on A and A.
Combine the responses in order to obtain a sorted array."""
A simple example is randomized QuickSort, where the pivot is chosen randomly, and divides the elements into three partitions: elements less than pivot, elements equal to pivot, and elements greater than pivot. The randomized QuickSort require a lot of resources but always generate the sorted array as an output.
It is obvious that QuickSort always generates the solution which in this case the sorted array. Unfortunately, the time complexity is not that obvious. It turns out that the running time depends on which element we pick as a pivot.
- The worst case Θ when the pivot is the smallest or the largest element.
- However, through randomization, where the pivot is randomly picked and is exactly a middle value each time, the QuickSort can be done in Θ.
In the case of average case, it is hard to determine since the analysis does not depend on the input distribution but on the random choices that the algorithm makes. The average of QuickSort is computed over all possible random choices that the algorithm might make when making the choice of pivot.
Although the worst-case running time is Θ, the average-case running time is Θ. It turns out that the worst-case does not happen often. For large value of n, the running time is Θ with a high probability.
Note that the probability that the pivot is middle value element every time is one out of n numbers which is very rare. However, it is still same running time when the split is 10%-90% instead of a 50%–50% because the depth of the recursion tree will still be O with O times taken each level of recursion.
Randomized Greedy Algorithm for Eight Queens Problem
Eight queens problem is usually solved with a backtracking algorithm. However, a Las Vegas algorithm can be applied; in fact, it is more efficient than backtracking.Place 8 queens on a chessboard so that no one attacks another. Remember that a queen attacks other pieces on the same row, column and diagonals.
Assume that k rows, 0 ≤ k ≤ 8, are successfully occupied by queens.
If k = 8, then stop with success. Otherwise, proceed to occupy row k + 1.
Calculate all positions on this row not attacked by existing queens. If there are none, then fail. Otherwise, pick one at random, increment k and repeat.
Note that the algorithms simply fails if a queen cannot be placed. But the process can be repeated and every time will generate different arrangement.
Complexity class
The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP.It turns out that
which is intimately connected with the way Las Vegas algorithms are sometimes constructed. Namely the class RP consists of all decision problems for which a randomized polynomial-time algorithm exists that always answers correctly when the correct answer is "no", but is allowed to be wrong with a certain probability bounded away from one when the answer is "yes". When such an algorithm exists for both a problem and its complement, the two algorithms can be run simultaneously and repeatedly: run each for a constant number of steps, taking turns, until one of them returns a definitive answer. This is the standard way to construct a Las Vegas algorithm that runs in expected polynomial time. Note that in general there is no worst case upper bound on the run time of a Las Vegas algorithm.
Optimal Las Vegas Algorithm
In order to make Las Vegas algorithm optimal, the expected run time should be minimized. This can be done by:- The Las Vegas algorithm A runs repeatedly for some number t1 steps. If A stops during the run time then A is done; otherwise, repeat the process from the beginning for another t2 steps, and so on.
- Designing a strategy that is optimal among all strategies for A, given the full information about the distribution of TA.
Relation to Monte Carlo algorithms
Las Vegas algorithms can be contrasted with Monte Carlo algorithms, in which the resources used are bounded but the answer may be incorrect with a certain probability. By an application of Markov's inequality, 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:
| 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 Monte Carlo algorithm to Las Vegas algorithm without a way to test the algorithm. On the other hand, changing Las Vegas algorithm to 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:
Assume that there is an array with the length of even n. Half of the array are 0's and the rest half are 1's. The goal here is to find an index that contains a 1.
//Las Vegas algorithm
repeat:
k = RandInt
if A 1,
return k;
//Monte Carlo algorithm
repeat 300 times:
k = RandInt
if A 1
return k
return "Failed"
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.