Randomized algorithms: Difference between revisions
Content deleted Content added
mNo edit summary |
#redirect Randomized algorithm |
||
| Line 1: | Line 1: | ||
#redirect [[Randomized algorithm]] |
|||
A '''randomized algorithm''' is an [[algorithm]] equipped with a source of random [[bit|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 <math>n = |V[G]|</math>. |
|||
It can be shown that this algorithm outputs a minimum cut with |
|||
probability at least <math>n^{-2}</math>, thus running it |
|||
<math>n^{2} \log(n)</math> 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. |
|||
Revision as of 07:59, 17 March 2004
Redirect to: