Overview#

Randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.Randomized algorithms 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.

Randomized algorithms requires distinguishing 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 algorithms, for example Quicksort[1]), and algorithms which have a chance of producing an incorrect result (Monte Carlo algorithms, for example the Monte Carlo algorithm for the MFAS problem[2]) 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.[3] However, in some cases, probabilistic algorithms are the only practical means of solving a problem.[4]!! Randomized algorithm Classification Types of Randomized algorithm:

• Monte Carlo algorithms
  • may return an answer that is not correct.
  • Example: primality testing
  • Subtypes: one-sided vs. two-sided errors
• Las Vegas algorithms
  • may not return an answer at all, but if they do the answer is guaranteed to be correct.
  • Example: factoring
• Sherwood algorithms
  • always give the correct answer. (Sometimes also called Las Vegas.)
  • Example: Quicksort

Complexity classes:#

• Randomized Polynomial time (RP): A language is in RP if there is a polynomial-time (Monte Carlo) algorithm that never accepts words that are not in the language, and has probability at least 1/2 of accepting words in the language
• Zero-error Probabilistic Polynomial (ZPP) Like RP, except the algorithm is Sherwood, so it always accepts if the word is in the language
• Bounded-error Probabilistic Polynomial (BPP) Like RP, except that the algorithm has probability at least 3/4 of accepting if the word is in the language, and probability at most 1/4 of accepting if the word is not in the language.

Turing Machine#

More Information#

There might be more information for this subject on one of the following:

• Algorithm
• Cryptographic Primitive
• Las Vegas algorithm
• Monte Carlo algorithm
• Nondeterministic algorithms
• Turing Machine

---

• [#1] - Randomized_algorithm - based on information obtained 2019-05-03