Quicksort Quicksort is a familiar, commonly used algorithm in which randomness can be useful. Many deterministic versions of this algorithm require
O(
n2) 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.
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 bounded from above. This technique is known as
randomized incremental construction.
Min cut Input: A
graph G(
V,
E)
Output: A
cut partitioning the vertices into
L and
R, with the minimum number of edges between
L and
R. Recall that the
contraction of two nodes,
u and
v, in a (multi-)graph yields a new node
u ' with edges that are the union of the edges incident on either
u or
v, except from any edge(s) connecting
u and
v. Figure 1 gives an example of contraction of vertex
A and
B. After contraction, the resulting graph may have parallel edges, but contains no self loops. Karger's{{cite journal
begin i = 1
repeat repeat Take a random edge (u,v) ∈ E in G replace u and v with the contraction u'
until only 2 nodes remain obtain the corresponding cut result Ci i = i + 1
until i = m output the minimum cut among C1, C2, ..., Cm.
end In each execution of the outer loop, the algorithm repeats the inner loop until only 2 nodes remain, the corresponding cut is obtained. The run time of one execution is O(n), and
n denotes the number of vertices. After
m times executions of the outer loop, we output the minimum cut among all the results. The figure 2 gives an example of one execution of the algorithm. After execution, we get a cut of size 3. {{math proof|1=If
G is not connected, then
G can be partitioned into
L and
R without any edge between them. So the min cut in a disconnected graph is 0. Now, assume
G is connected. Let be the partition of
V induced by {{math|1 =
C :
C = { {
u,
v} ∈
E :
u ∈
L,
v ∈
R }}} (well-defined since
G is connected). Consider an edge {
u,
v} of
C. Initially,
u,
v are distinct vertices.
As long as we pick an edge , and do not get merged. Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of
L and the other consisting of the vertices of
R. As in figure 2, the size of min cut is 1, and
C = {(
A,
B)}. If we don't select (
A,
B) for contraction, we can get the min cut.}}
Analysis of algorithm The probability that the algorithm succeeds is 1 − the probability that all attempts fail. By independence, the probability that all attempts fail is \prod_{i=1}^m \Pr(C_i\neq C)=\prod_{i=1}^m(1-\Pr(C_i=C)). By lemma 1, the probability that is the probability that no edge of
C is selected during iteration
i. Consider the inner loop and let denote the graph after
j edge contractions, where . has vertices. We use the chain rule of
conditional possibilities. The probability that the edge chosen at iteration
j is not in
C, given that no edge of
C has been chosen before, is 1-\frac{k}. Note that still has min cut of size
k, so by Lemma 2, it still has at least \frac{(n-j)k}{2} edges. Thus, 1-\frac{k}\geq 1-\frac{2}{n-j}=\frac{n-j-2}{n-j}. So by the chain rule, the probability of finding the min cut
C is \Pr[C_i=C] \geq \left(\frac{n-2}{n}\right)\left(\frac{n-3}{n-1}\right)\left(\frac{n-4}{n-2}\right)\ldots\left(\frac{3}{5}\right)\left(\frac{2}{4}\right)\left(\frac{1}{3}\right). Cancellation gives \Pr[C_i=C] \geq \frac{2}{n(n-1)}. Thus the probability that the algorithm succeeds is at least 1- \left(1-\frac{2}{n(n-1)}\right)^m. For m = \frac{n(n-1)}{2}\ln n, this is equivalent to 1-\frac{1}{n}. The algorithm finds the min cut with probability 1 - \frac{1}{n}, in time O(mn) = O(n^3 \log n). ==Derandomization==