# Randomized Algorithm

A Randomized Algorithm is an algorithm that uses a random function in its conditional logic.

**AKA:**Probabilistic Algorithm.**Context:**- It can solve a Randomization Task.
- It can range from being a Las Vegas Randomized Algorithm to being a Monte Carlo Randomized Algorithm.

**Example(s):****Counter-Example(s):****See:**Non-Deterministic Algorithm, Approximate Algorithm.

## References

### 2013

- (Wikipedia, 2013) ⇒ http://en.wikipedia.org/wiki/Randomized_algorithm
- A
**randomized algorithm**is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses 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 to reduce the expected running time or memory usage, but always terminate with a correct result (Las Vegas algorithms) in a bounded amount of time, and probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo algorithms) or fail to produce a result either by signalling 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.

^{[1]}However, in some cases, probabilistic algorithms are the only practical means of solving a problem.^{[2]}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.

- A

- ↑ "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. - ↑ "In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the 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, section 1.2.*

- http://en.wikibooks.org/wiki/Algorithms/Randomization
- There are two main types of randomized algorithms: Las Vegas algorithms and Monte-Carlo algorithms. In Las Vegas algorithms, the algorithm may use the randomness to speed up the computation, but the algorithm must always return the correct answer to the input. Monte-Carlo algorithms do not have the former restriction, that is, they are allowed to give
*wrong*return values. However, returning a wrong return value must have a small probability*, otherwise that Monte-Carlo algorithm would not be of any use.*

- There are two main types of randomized algorithms: Las Vegas algorithms and Monte-Carlo algorithms. In Las Vegas algorithms, the algorithm may use the randomness to speed up the computation, but the algorithm must always return the correct answer to the input. Monte-Carlo algorithms do not have the former restriction, that is, they are allowed to give

### 2005

- (Klinberg & Tardos, 2005) ⇒ Jon Kleinberg, and Éva Tardos. (2005). “Algorithm Design." Addison-Wesley. ISBN:0-321-29535-8
- Chapter 13: Randomized Algorithms http://www.aw-bc.com/info/kleinberg/assets/downloads/ch13.pdf

### 1995

- (Motwani & Raghavan, 1995) ⇒ Rajeev Motwani, and Prabhakar Raghavan. (1995). “Randomized Algorithms." Cambridge University Press. ISBN:0521474655