Las Vegas algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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. Recently, stochastic local search (SLS) algorithm is 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. Due to nature of Las Vegas algorithm, it is hard to analyze most of the time.[2]

History[edit]

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 Overview[edit]

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 RTA,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(RTA,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(RTA,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, limt→∞ P(RTA,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[edit]

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(RT ≤ tmax), 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[edit]

Analogy[edit]

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[edit]

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 Θ(n2) when the pivot is the smallest or the largest element.
  • However, through randomization, where the pivot is randomly picked and is neither smallest nor biggest element, the quicksort can be done in Θ(nlogn).

Note that the probability that the pivot is middle value element every time is 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[edit]

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[edit]

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[edit]

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 t1 steps. If A(x) stops during the run time then A(x) is done; otherwise, repeat the process from the beginning for another t2 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 TA(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 TA(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[edit]

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]:

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 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[edit]

Notes[edit]

  1. ^ Steven D. Galbraith (2012). Mathematics of Public Key Cryptography. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.
  2. ^ Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).
  3. ^ * László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
  4. ^ Babai, László. “Monte-Carlo algorithms in graph isomorphism testing.” (1979).
  5. ^ H.H. Hoos and T. St¨utzle. Evaluating Las Vegas Algorithms — Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.
  6. ^ Randomized Algorithms. Brilliant.org. Retrieved 23:54, October 24, 2018, from https://brilliant.org/wiki/randomized-algorithms-overview/
  7. ^ "From Las Vegas to Monte Carlo: Randomized Algorithms in Machine Learning Systems". Towards Data Science. 2018-09-07. Retrieved 2018-10-25.
  8. ^ Barringer, Howard (December 2010). "Randomized Algorithms - a Brief Introduction" (PDF). www.cs.man.ac.uk. Retrieved 2018-12-08.
  9. ^ Luby, Michael (27 September 1993). "Optimal Speedup of Las Vegas algoritms". Information Processing Letters. 47: 173–180.
  10. ^ 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.
  11. ^ Procaccia, Ariel (5 November 2015). "Great Theoretical Ideas in Computer Science" (PDF) (Power Point). Retrieved 3 November 2018.

References[edit]

  • 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]