An Overview of Randomized Algorithms

A randomized algorithm makes random choices during its execution. The behavior of such an algorithm may thus be random even on a fixed input. The process of designing and analyzing a randomized algorithm focuses on establishing that it is likely to behave “well” on every input. The likelihood in such a statement depends only on the probabilistic choices made by the algorithm during execution and not on any assumptions about the input. It is especially important to distinguish a randomized algorithm from the averagecase analysis of algorithms, where one analyzes an algorithm assuming that its input is drawn from a fixed probability distribution. With a randomized algorithm, in contrast, no assumption is made about the input.