Randomized algorithm
A randomized algorithm is generally classified by its error as one of four types:
- zero-sided;
- one-sided;
- one-sided complementary; or
- two-sided.
A randomized algorithm with zero-sided error is said to be of Las Vegas type, whereas it is of Monte Carlo type if it has a two-sided error.
An algorithm with one-sided error may be combined with an algorithm having one-sided complementary error to yield a Las Vegas type algorithm with zero-sided error.
A Las Vegas algorithm always produces the correct result when and if it terminates, but termination is not guaranteed except in the probabilistic sense of a finite expected running time.
Algorithms with one-sided error are subject to “Type I” errors only, but the probability of error is bounded away from one.
Algorithms with one-sided complementary error are subject to “Type II” errors only, and likewise the probability of error is bounded away from one.
Algorithms with two-sided error are subject to both “Type I” and “Type II” errors [1], but the conditional probabilities of “Type I” and “Type II” errors are strictly less than one half and bounded away from one half.
An algorithm with one-sided, one-sided complementary, or two-sided error may be run repeatedly until any desired statistical significance of the result is attained.
Complexity classes ZPP, RP, co-RP and BPP are defined based on the existence of randomized algorithms that run in polynomial time [2].
