Part of a series on Probabilistic data structures
Random trees Random binary tree · Treap Rapidly-exploring random tree Other Bloom filter · Skip list Related Randomized algorithm
Computer science Portal · v • d • e

A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.

In both cases, random performance and random output, the term "algorithm" for a procedure is somewhat questionable, as it is no longer formally effective.^[1] However, in some cases, probabilistic algorithms are the only practical means of solving a problem.^[2]

In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

Contents 1 Motivation 2 Computational complexity 3 History 4 Applications 4.1 Quicksort 4.2 Randomized incremental constructions in geometry 4.3 Graph cuts 5 Derandomization 6 Where randomness helps 7 See also 8 Notes 9 References

[edit] Motivation

As a motivating example, consider the problem of finding an 'a' in an array of n elements, given that half are 'a's and the other half are 'b's. The obvious approach is to look at each element of the array, but this would take very long (n/2 operations) if the array were ordered as 'b's first followed by 'a's. There is a similar drawback with checking in the reverse order, or checking every second element. In fact, with any strategy at all in which the order in which the elements will be checked is fixed, i.e, a deterministic algorithm, we cannot guarantee that the algorithm will complete quickly for all possible inputs. On the other hand, if we were to check array elements at random, then we will quickly find an 'a' with high probability, whatever be the input.

Randomized algorithms are particularly useful when faced with a malicious "adversary" or attacker who deliberately tries to feed a bad input to the algorithm (see worst-case complexity and competitive analysis (online algorithm)) such as in the Prisoner's dilemma. It is for this reason that randomness is ubiquitous in cryptography. In cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore either a source of truly random numbers or a cryptographically secure pseudo-random number generator is required. Another area in which randomness is inherent is quantum computing.

In the example above, the randomized algorithm always outputs the correct answer, but its running time is a random variable. Sometimes we want the algorithm to complete in a fixed amount of time (as a function of the input size), but allow a small probability of error. The former type are called Las Vegas algorithms, and the latter are Monte Carlo algorithms (related to the Monte Carlo method for simulation). Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm (via Markov's inequality), by having it output an arbitrary, possibly incorrect answer if it fails to complete within a specified time. Conversely, if an efficient verification procedure exists to check whether an answer is correct, then a Monte Carlo algorithm can be converted into a Las Vegas algorithm by running the Monte Carlo algorithm repeatedly till a correct answer is obtained.

[edit] Computational complexity

Computational complexity theory models randomized algorithms as probabilistic Turing machines. Both Las Vegas and Monte Carlo algorithms are considered, and several complexity classes are studied. The most basic randomized complexity class is RP, which is the class of decision problems for which there is an efficient (polynomial time) randomized algorithm (or probabilistic Turing machine) which recognizes NO-instances with absolute certainty and recognizes YES-instances with a probability of at least 1/2. The complement class for RP is co-RP. Problem classes having (possibly nonterminating) algorithms with polynomial time average case running time whose output is always correct are said to be in ZPP.

The class of problems for which both YES and NO-instances are allowed to be identified with some error is called BPP. This class acts as the randomized equivalent of P, i.e BPP represents the class of efficient randomized algorithms.

[edit] History

Historically, the first randomized algorithm was a method developed by Michael O. Rabin for the closest pair problem in computational geometry. The study of randomized algorithms was spurred by the 1977 discovery of a randomized primality test (i.e., determining the primality of a number) by Robert M. Solovay and Volker Strassen. Soon afterwards Michael O. Rabin demonstrated that the 1976 Miller's primality test can be turned into a randomized algorithm. At that time, no practical deterministic algorithm for primality was known.

The Miller-Rabin primality test relies on a binary relation between two positive integers k and n that can be expressed by saying that k "is a witness to the compositeness of" n. It can be shown that

• If there is a witness to the compositeness of n, then n is composite (i.e., n is not prime), and
• If n is composite then at least three-fourths of the natural numbers less than n are witnesses to its compositeness, and
• There is a fast algorithm that, given k and n, ascertains whether k is a witness to the compositeness of n.

Observe that this implies that the primality problem is in Co-RP.

If one randomly chooses 100 numbers less than a composite number n, then the probability of failing to find such a "witness" is (1/4)¹⁰⁰ so that for most practical purposes, this is a good primality test. If n is big, there may be no other test that is practical. The probability of error can be reduced to an arbitrary degree by performing enough independent tests.

Therefore, in practice, there is no penalty associated with accepting a small probability of error, since with a little care the probability of error can be made astronomically small. Indeed, even though a deterministic polynomial-time primality test has since been found, it has not replaced the older probabilistic tests in cryptographic software nor is it expected to do so for the foreseeable future.

[edit] Applications

[edit] Quicksort

Quicksort is a familiar, commonly-used algorithm in which randomness can be useful. Any deterministic version of this algorithm requires O(n²) time to sort n numbers for some well-defined class of degenerate inputs (such as an already sorted array), with the specific class of inputs that generate this behavior defined by the protocol for pivot selection. However, if the algorithm selects pivot elements uniformly at random, it has a provably high probability of finishing in O(n log n) time regardless of the characteristics of the input.

[edit] Randomized incremental constructions in geometry

In computational geometry, a standard technique to build a structure like a convex hull or Delaunay Triangulation is to randomly permute the input points and then insert them one by one into the existing structure. The randomization ensures that the expected number of changes to the structure caused by an insertion is small, and so the expected running time of the algorithm can be upper bounded. This technique is known as randomized incremental construction^[3].

[edit] Graph cuts

Randomized algorithms can also be used to solve graph theory problems, as demonstrated by this randomized minimum cut algorithm:

 find_min_cut(undirected graph G) {     while there are more than 2 nodes in G do {         pick an edge (u,v) at random in G         contract the edge, while preserving multi-edges         remove all loops     }     output the remaining edges } 

Here, contracting an edge (u,v) means adding a new vertex w, replacing any edge (u,x) or (v,x) with (w,x), and then deleting u and v from G.

Let n = |V[G]|. It can be shown that this algorithm outputs a minimum cut with probability at least n⁻², thus running it n²log(n) times and taking the smallest output cut, we find a minimum cut with high probability.

[edit] Derandomization

Randomness can be viewed as a resource, like space and time. Derandomization is then the process of removing randomness (or using as little of it as possible). From the viewpoint of computational complexity, derandomizing an efficient randomized algorithm is the question, Is P = BPP ?

There are also specific methods that can be employed to derandomize particular randomized algorithms:

• the method of conditional expectation, and its generalization, pessimistic estimators
• discrepancy theory (which is used to derandomize geometric algorithms)
• the exploitation of limited independence in the random variables used by the algorithm, such as the pairwise independence used in universal hashing
• the use of expander graphs (or dispersers in general) to amplify a limited amount of initial randomness (this last approach is also referred to as generating pseudorandom bits from a random source, and leads to the related topic of pseudorandomness)

[edit] Where randomness helps

When the model of computation is restricted to Turing machines, it is currently an open question whether the ability to make random choices allows some problems to be solved in polynomial time that cannot be solved in polynomial time without this ability; this is the question of whether P = BPP. However, in other contexts, there are specific examples of problems where randomization yields strict improvements.

• Based on the initial motivating example: given an exponentially-long string of 2^k characters, half a's and half b's, a random access machine requires at least 2^k-1 lookups in the worst-case to find the index of an a; if it is permitted to make random choices, it can solve this problem in an expected polynomial number of lookups.
• In communication complexity, the equality of two strings can be verified using logn bits of communication with a randomized protocol. Any deterministic protocol requires Θ(n) bits.
• The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time^[4] . Bárány and Füredi showed that no deterministic algorithm can do the same^[5]. This is true unconditionally, i.e without relying on any complexity-theoretic assumptions.
• A more complexity-theoretic example of a place where randomness appears to help is the class IP. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP = PSPACE^[6]. However, if it is required that the verifier be deterministic, then IP = NP.
• In a Chemical Reaction Network (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a Turing machine can be simulated with arbitrarily high probability of running correctly for all time, only if a random CRN is used. With a simple nondeterministic CRN (any possible reaction can happen next), the computational power is limited to primitive recursive functions.

[edit] See also

• Probabilistic analysis of algorithms

[edit] Notes

[edit] References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp. 91–122.
• Don Fallis. 2000. "The Reliability of Randomized Algorithms." British Journal for the Philosophy of Science 51:255-71.
• M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
• Rajeev Motwani and P. Raghavan. Randomized Algorithms. A survey on Randomized Algorithms. [1]
• Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1.  Chapter 11: Randomized computation, pp. 241–278.
• M. O. Rabin. (1980), "Probabilistic Algorithm for Testing Primality." Journal of Number Theory 12:128-38.