Randomized algorithm

Randomized algorithm is a type of algorithm that uses 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.

Overview

In the case of deterministic algorithms, the set of inputs is divided into several classes, where the algorithm behaves differently for different classes. In contrast, a randomized algorithm has the ability to make random choices, and thus can behave differently on the same input on different executions, allowing it to be correct on a larger set of inputs than deterministic algorithms.

Randomized algorithms are particularly useful when faced with a malicious "adversary" or attacker who deliberately tries to feed a bad input to the algorithm such as in the Two Armed Bandit Problem. It is for this reason that randomized algorithms are a useful tool in cryptography. In such cases, the randomness of the algorithm can be used to thwart the adversary's attempts to choose a particularly bad input.

Types of Randomized Algorithms

Randomized algorithms are subdivided into two major types, which are Las Vegas algorithms and Monte Carlo algorithms.

• Las Vegas algorithms always produce the correct result and are always expected to finish in a reasonable amount of time, but that time is a random variable.
• Monte Carlo algorithms are expected to be fast, but aren't always correct. The incorrectness is bounded by a probability parameter.

Applications

Randomized algorithms are often used in computer_science, mathematics, and related fields such as cryptography, game_theory, graph_theory, machine_learning, computational_geometry, and computational_biology. They offer several advantages over deterministic algorithms, primarily in terms of simplicity and speed.

See Also

• Probabilistic algorithm
• Heuristic
• Quantum computing