Randomized algorithms

A randomized algorithm is an algorithm equipped with a source of random bits, that it uses to supplement its input. The algorithm typically uses these bits to guide its behavior, in the hope of achieving good behavior in expectation. Formally, the algorithm's performance will be a random variable determined by the random bits, with (hopefully) good expected value.

Example 1

One good example of a randomized algorithm is a Monte Carlo algorithm (i.e. one using the Monte Carlo Method). For example, suppose we have an event, E, whose probability we would like to estimate. Say you are playing blackjack, you have 19 and E is the event that you win. Your algorithm uses its source of random bits to generate K random hands the dealer could have, and determines what in fraction of them you win, W. Then W/K is a good estimate for the probability that you win, as K becomes large.

Example 2

A more complex example, but one more representative of the use of randomized algorithms in computer science, is one of David Karger's randomized minimum cut algorithms:

 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 self-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^{-2}$, thus running it $n^{2}\log(n)$ times and taking the smallest output cut, we find a minimum cut with high probability.

Relations to Complexity Theory

There are complexity classes denoting the decision problems computable by randomized algorithms with various properties. For example, RP is the class of randomized polynomial-time problems.

Formally, a language L is in RP if and only if there exists a polynomial-time randomized algorithm A such that for all x ∈ L, Pr(A accepts x) > 3/4, and for all x ∉ L, Pr(A accepts x) = 0.