Randomized algorithm: Difference between revisions

Revision as of 14:46, 20 April 2021

Revision as of 19:16, 3 May 2021

Line 30:

This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is

:<math> \lim_{n \to \infty} \sum_{i \mathop = 1}^{n} \frac{i}{2^i} = 2</math>

Since it is constant the expected run time over many calls is <math>\Theta(1)</math>. (See [[Big O notation]])

Line 47:

If an ‘''a''’ is found, the algorithm succeeds, else the algorithm fails. After ''k'' iterations, the probability of finding an ‘''a''’ is:

<div style="text-align:center;">

<math>\Pr[\mathrm{find~a}] = 1 - (1/2)^k</math>

<math>

\Pr[\mathrm{find~a}]=1-(1/2)^k

</math>

</div>

Line 58 ⟶ 56:

In the example above, the Las Vegas algorithm always outputs the correct answer, but its running time is a random variable. The Monte Carlo algorithm (related to the [[Monte Carlo method]] for simulation) is guaranteed to complete in an amount of time that can be bounded by a function the input size and its parameter ''k'', but allows a ''small probability of error''. 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.

==Computational complexity==

==Computational complexity==<!-- [[Probabilistic complexity]] and [[Probabilistic computational complexity]] redirect here -->

[[Computational complexity theory]] models randomized algorithms as ''[[probabilistic Turing machine]]s''. Both [[Las Vegas algorithm|Las Vegas]] and [[Monte Carlo algorithm]]s are considered, and several [[complexity class]]es are studied. The most basic randomized complexity class is [[RP (complexity)|RP]], which is the class of [[decision problem]]s 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 (complexity)|ZPP]].

Line 103 ⟶ 101:

'''repeat'''

'''repeat'''

Take a random edge (u,v) ∈ E in G

replace u and v with the contraction u'

'''until''' only 2 nodes remain

Line 115 ⟶ 113:

example of one execution of the algorithm. After execution, we get a cut of size 3.

'''Lemma 1''': Let ''k'' be the min cut size, and let {{math|1=''C'' = {{mset|''e''₁, ''e''₂, ..., ''e''_''k''}}}} be the min cut. If, during iteration ''i'', no edge {{math|''e'' ∈ ''C''}} is selected for contraction, then {{math|1=''C''_''i''&nbsp; =&nbsp; ''C''}}.

'''Proof''': 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 ''V''=''L''∪''R'' be the partition of ''V'' induced by ''C'' : ''C''&nbsp;=&nbsp;{ {''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 {{tmath|f \neq e}}, {{mvar|u}} and {{mvar|v}} 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.

'''Lemma 2''': If ''G'' is a multigraph with ''p'' vertices and whose min cut has size ''k'', then ''G'' has at least ''pk''/2 edges.

Line 126 ⟶ 124:

'''Analysis of algorithm'''

The probability that the algorithm succeeds is 1&nbsp;&minus;−&nbsp;the probability that all attempts fail. By independence, the probability that all attempts fail is

<math display="block">

<div style="text-align:center;">

<math>

\prod_{i=1}^m \Pr(C_i\neq C)=\prod_{i=1}^m(1-\Pr(C_i=C)).

</math>

</div>

By lemma 1, the probability that {{math|1=''C''_''i''&nbsp; =&nbsp; ''C''}} is the probability that no edge of ''C'' is selected during iteration ''i''. Consider the inner loop and let {{math|''G''_''j''}} denote the graph after ''j'' edge contractions, where {{math|1=''j''&nbsp; ∈&nbsp; {{mset|0, 1,... …, ''n''&nbsp;&minus;&nbsp; − 3}}}}. {{math|''G''_''j''}} has {{math|1=''n''&nbsp;&minus;&nbsp; − ''j''}} vertices. We use the chain rule of [[Conditional probability|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 <math>1-\frac{k}{|E(G_j)|}</math>. Note that {{math|''G''_''j''}} still has min cut of size ''k'', so by Lemma 2, it still has at least <math>\frac{(n-j)k}{2}</math> edges.

Line 138 ⟶ 135:

So by the chain rule, the probability of finding the min cut ''C'' is

<math display="block">

\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).

</math>

Cancellation gives <math>\Pr[C_i=C] \geq \frac{2}{n(n-1)}</math>. Thus the probability that the algorithm succeeds is at least <math>1- \left(1-\frac{2}{n(n-1)}\right)^m</math>. For <math>m = \frac{n(n-1)}{2}\ln n</math>, this is equivalent to <math>1-\frac{1}{n}</math>. The algorithm finds the min cut with probability <math>1 - \frac{1}{n}</math>, in time <math>O(mn) = O(n^3 \log n)</math>.

==Derandomization==

Line 155 ⟶ 152:

==Where randomness helps==

When the model of computation is restricted to [[Turing machine]]s, 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 2^{''k''&minus;1−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. <!-- Does the randomized lookup still have the same worst-case performance? Yes. -->

* The natural way of carrying out a numerical computation in [[embedded systems]] or [[cyber-physical system]]s is to provide a result that approximates the correct one with high probability (or Probably Approximately Correct Computation (PACC)). The hard problem associated with the evaluation of the discrepancy loss between the approximated and the correct computation can be effectively addressed by resorting to randomization<ref>{{citation|title=Intelligence for Embedded Systems|first1=Cesare|last1=Alippi|publisher=Springer|year=2014|isbn=978-3-319-05278-6}}.</ref>

* In [[communication complexity]], the equality of two strings can be verified to some reliability using <math>\log n</math> bits of communication with a randomized protocol. Any deterministic protocol requires <math>\Theta(n)</math> bits if defending against a strong opponent.<ref>{{citation|title=Communication Complexity|first1=Eyal|last1=Kushilevitz|first2=Noam|last2=Nisan|publisher=Cambridge University Press|year=2006|isbn=9780521029834}}. For the deterministic lower bound see p.&nbsp;11; for the logarithmic randomized upper bound see pp.&nbsp;31–32.</ref>