!!! Overview
[{$pagename}] is an [algorithm] that employs a degree of randomness as part of its logic.[{$pagename}]s 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].

[{$pagename}]s 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 algorithm]s are the only practical means of solving a problem.[4]!! [{$pagename}] [Classification]
Types of [{$pagename}]:
* [Monte Carlo algorithm]s
** may return an answer that is not correct.
** Example: primality testing
** Subtypes: one-sided vs. two-sided errors
* [Las Vegas algorithm]s
** 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:
[{ReferringPagesPlugin before='*' after='\n' }]
----
* [#1] - [Randomized_algorithm|Wikipedia:Randomized_algorithm|target='_blank'] - based on information obtained 2019-05-03