Randomized algorithm: Difference between revisions

Revision as of 21:10, 12 May 2019

Revision as of 09:46, 17 July 2019

Line 4:

A '''randomized algorithm''' is an [[algorithm]] that employs a degree of [[randomness]] as part of its logic. The algorithm typically uses [[Uniform distribution (discrete)|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.

One has to distinguish between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite ([[Las Vegas algorithm]]s, for example [[Quicksort]]<ref>{{Cite journal|last=Hoare|first=C. A. R.|date=July 1961|title=Algorithm 64: Quicksort|url=http://doi.acm.org/10.1145/366622.366644|journal=Commun. ACM|volume=4|issue=7|pages=321–|doi=10.1145/366622.366644|issn=0001-0782}}</ref>), and algorithms which have a chance of producing an incorrect result ([[Monte Carlo algorithm]]s, for example the [[Monte Carlo algorithm]] for the [[Minimum feedback arc set|MFAS]] problem<ref>{{Cite journal|last=Kudelić|first=Robert|date=2016-04-01|title=Monte-Carlo randomized algorithm for minimal feedback arc set problem|url=http://www.sciencedirect.com/science/article/pii/S1568494615007978|journal=Applied Soft Computing|volume=41|pages=235–246|doi=10.1016/j.asoc.2015.12.018}}</ref>) or fail to produce a result either by signaling a failure or failing to terminate.

In the second case, random performance and random output, the term "algorithm" for a procedure is somewhat questionable. In the case of random output, it is no longer formally [[Effective method|effective]].<ref>"Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time." Henri Cohen (2000). ''A Course in Computational Algebraic Number Theory''. Springer-Verlag, p. 2.</ref>

Line 162:

* 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>

* The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.<ref>{{citation|last1=Dyer|first1=M.|last2=Frieze|first2=A.|last3=Kannan|first3=R.|title=A random polynomial-time algorithm for approximating the volume of convex bodies|journal=[[Journal of the ACM]]|volume=38|issue=1|year=1991|pages=1–17|doi=10.1145/102782.102783|url=http://portal.acm.org/citation.cfm?id=102783}}</ref> [[Imre Bárány|Bárány]] and [[Zoltán Füredi|Füredi]] showed that no deterministic algorithm can do the same.<ref>{{citation|last1=Füredi|first1=Z.|author1-link=Zoltán Füredi|last2=Bárány|first2=I.|year=1986|contribution=Computing the volume is difficult|title=[[Symposium on Theory of Computing|Proc. 18th ACM Symposium on Theory of Computing]] (Berkeley, California, May 28–30, 1986)|publisher=ACM|___location=New York, NY|pages=442–447|doi=10.1145/12130.12176|isbn=0-89791-193-8|title-link=Symposium on Theory of Computing}}</ref> This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black box.

* A more complexity-theoretic example of a place where randomness appears to help is the class [[IP (complexity)|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]].<ref>{{citation|last=Shamir|first=A.|authorlink=Adi Shamir|title=IP = PSPACE|journal=Journal of the ACM|volume=39|issue=4|year=1992|pages=869–877|doi=10.1145/146585.146609}}</ref> However, if it is required that the verifier be deterministic, then IP = [[NP (complexity)|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 limited Turing machine <!-- the Turing machine has infinite tape --> can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to [[Primitive recursive|primitive recursive functions]].<ref>{{citation

Line 180:

| series = Natural Computing Series

| title = Algorithmic Bioprocesses

| year = 2009| url = https://authors.library.caltech.edu/26121/1/etr090.pdf }}.</ref>

==See also==

Line 202:

* Rajeev Motwani and P. Raghavan. [http://portal.acm.org/citation.cfm?id=234313.234327 Randomized Algorithms.] A survey on Randomized Algorithms.

* {{Citation|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 978-0-201-53082-7| author-link = Christos Papadimitriou }} Chapter 11: Randomized computation, pp.&nbsp;241–278.

* {{cite journal|doi=10.1016/0022-314X(80)90084-0|title=Probabilistic algorithm for testing primality|journal=Journal of Number Theory|volume=12|pages=128–138|year=1980|last1=Rabin|first1=Michael O.}}

* M. O. Rabin (1980), ''[https://www.sciencedirect.com/science/article/pii/0022314X80900840/pdf?md5=6f748cd82fa8efa1a637efab5f632baa&pid=1-s2.0-0022314X80900840-main.pdf&_valck=1 Probabilistic Algorithm for Testing Primality]'', Journal of Number Theory, 12:128–38.

* A. A. Tsay, W. S. Lovejoy, David R. Karger, ''Random Sampling in Cut, Flow, and Network Design Problems'', Mathematics of Operations Research, 24(2):383–413, 1999.