Randomized algorithm: Difference between revisions

Revision as of 17:09, 12 March 2020

Revision as of 15:31, 1 April 2020

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|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=|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 some cases, probabilistic algorithms are the only practical means of solving a problem.<ref>"In [[primality test|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>

In common practice, randomized algorithms are approximated using a [[pseudorandom number generator]] in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.