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 run-time of Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected run time always be finite, when 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 (be effective), but it may output a symbol not part of the solution space to indicate failure in finding a solution. ^[1] Because of the nature of Las Vegas algorithm, it can be used in situations where the number of possible solutions is limited and where verifying the correctness of a candidate solution is relatively easy while calculating the solution is complex.

Las Vegas Algorithm is renowned in field of Artificial Intelligence and other areas of computer science and Operation Research. In AI field, a stochastic local search (SLS) algorithm is utilized and categorized as a type of Las Vegas algorithm. Recently, SLS algorithms have been used to solve NP complete decision problems and NP-hard combinatorial optimization problems. However, some systematic search methods such as the modern variants of the Davis Putnam algorithm for propositional satisfiability (SAT) problems also utilize non-deterministic decisions; therefore, they can be categorized as Las Vegas algorithms as well.^[2]

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.^[3] Babai^[4] defined "Las Vegas algorithm" term with an example of coin flips for the first time: all algorithms are affected by a series of independent coin flips and there are small chance of failure. However, in contrast to Monte Carlo algorithm, Las Vegas algorithm can guarantee the correctness of the decision to be made without failure.

Las Vegas Algorithm Definition

1 //Las Vegas algorithm
2 repeat:
3     k = RandInt(n)
4     if A[k] == 1,
5         return k;

As mentioned earlier, Las Vegas algorithm always gives the right results. Above code illustrates its property. A variable k is generated randomly and randomness is in fact a very important factor of Las Vegas algorithm. After k is generated, the algorithm finds the element in array A where 1 is stored. If it finds, which in this case returns the correct result, then return k. However, if it does not find the element in A, then the algorithm repeats this process until it finds 1. Although Las Vegas Algorithm is guaranteed to find the correct answer, it does not have a fixed runtime; due to the randomization, as the line 3 from the code above indicates, it is possible to take infinite time to get the results if the limit is not set.

More Details about Las Vegas Algorithm Definition

This section provides the conditions to meet in order to determine if an algorithm is Las Vegas:

an algorithm A is a Las Vegas algorithm for problem class X, if ^[5]

(1) whenever for a given problem instance x∈X it returns a solution s, s is guaranteed to be a valid solution of x

(2) on each given instance x, the run-time of A is a random variable RT_A,x

Since completeness is important factor to consider when analyzing the algorithms, here are three categories in terms of completeness for Las Vegas algorithm:

• complete Las Vegas algorithms can be guaranteed to solve each solvable problem within run-time tmax, where tmax is an instance-dependent constant.

Let P(RT_A,x ≤ t) denote the probability that A finds a solution for a soluble instance x in time within t, then A is complete exactly if for each x there exists

some tmax such that P(RT_A,x ≤ t) = 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, lim_t→∞ P(RT_A,x ≤ t) = 1.

• essentially incomplete Las Vegas algorithms are Las Vegas algorithms which are not approximately complete.

This completeness factor is crucial theoretically; however, approximate completeness is mainly of theoretical interest since the time limits for finding solutions are usually far too large to be of practical use.

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 t_max 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(RT ≤ t_max), 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 → [0,1] defined as rtd(t) = P(RT ≤ t) or its approximation.

The run-time distribution (RTD) 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(RT ≤ t) for arbitrary time-limits t.

Application of Las Vegas Algorithm

Analogy

Las Vegas algorithms occur most of the time when people search something. For example, if they are looking for some information online, they will navigate every related websites on the search engine to find the right information they want. Clicking the websites is a randomized process because they do not know what each website contains until they open the link. Thus, the time complexity ranges from getting lucky and finding the right contents on the first website to being super unlucky and spending ridiculous amount of time. Note that people know what they are looking for; therefore, once they find the website, then there is no possibility of error.^[6]

Randomized QuickSort

 1 INPUT: 
 2     Array A of n elements
 3 def Randomized_quicksort(A):
 4     If n = 1:
 5         return A # A is sorted.
 6     Else:
 7         i = Random number in range(1, n)
 8         X = A[i]    # the pivot element
 9         Partition A into elements < x, x, and >x  # as shown in the figure above.
10     Execute Quicksort on A[1 to i-1] and A[i+1 to n].
11     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.^[7]

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 Θ(n²) 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 Θ(nlogn).

The running time of QuickSort depends heavily on how well the pivot is selected. If a value of pivot is either too big or small, then the partition will be unbalanced. This case gives a poor running time. However, if the value of pivot is near the middle of the array, then the split will be reasonably well balanced. Thus its running time will be good. Since the pivot is randomly picked, the running time will be good most of the time and bad occasionally.

In 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 Θ(n²), the average-case running time is Θ(nlogn). It turns out that the worst-case does not happen often. For large value of n, the running time is Θ(nlogn) 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(logn) with O(n) times taken each level of recursion.

Randomized Greedy Algorithm for Eight Queens Problem

Eight queens problem is usually solved with backtracking algorithm. However, Las Vegas algorithm can be applied; in fact, it is more efficient than backtracking.

Place 8 queens on a chess board so that no one attacks another. Remember that a queens 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 k+1 row.

Calculate all positions on this row not attacked by existing queens. If there are none, then fail. Otherwise, pick on 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. ^[8]

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 (with the answers "yes" and "no" swapped), 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:

1. The Las Vegas algorithm A(x) runs repeatedly for some number t₁ steps. If A(x) stops during the run time then A(x) is done; otherwise, repeat the process from the beginning for another t₂ steps, and so on.
2. Designing a strategy that is optimal among all strategies for A(x), given the full information about the distribution of T_A(x).

The existence of the optimal strategy might be a fascinating theoretical observation. However, it is not practical in real life because it is not easy to find the information of distribution of T_A(x). Furthermore, there is no point of running the experiment repeatedly to obtain the information about the distribution since most of the time, the answer is needed only once for any x.^[9]

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 (typically small) 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^[10]:

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 find 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:^[11]

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.

 0 //Las Vegas algorithm
 1 repeat:
 2     k = RandInt(n)
 3     if A[k] = 1,
 4         return k;
 5         
 6 //Monte Carlo algorithm
 7 repeat 300 times:
 8     k = RandInt(n)
 9     if A[k] = 1
10         return k
11     return "Failed"

Since Las Vegas does not end until it find 1 in the array, it does not gamble with the correctness but run-time. On the other hand, Monte Carlo runs 300 times which mean 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.

See also

• Atlantic City algorithm
• Randomness

Notes

References

• Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999
• "Las Vegas algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 July 2006. (accessed May 9, 2009) Available from: [1]