Goal of Deterministic Algorithm: To prove that the algorithm solves the problem correctly (always) and quickly (typically, the number of steps should be polynomial in the size of the input) (see fig. .
Goal of Randomized Algorithm: In addition to input, algorithm takes a source of random numbers and makes random choices during execution. The behavior can vary even on a fixed input. The design of the algorithm and the analysis show that this behavior is likely to be good, on every input. The likely hood is over the random numbers only. While analyzing the algorithm, we should not be confused with the probabilistic analysis of the algorithms, where input is assumed to be from a probability distribution, which show that the algorithm works for most inputs.
There are two approaches:
For both, the probabilities/expectations are only over the random choices made by the algorithm, i.e., independent of the input. Thus independent repetitions of Monte Carlo algorithms drive down the failure probability exponentially.
The advantages of both are: Simplicity, and Performance. For many problems, a randomized algorithm is the simplest, the fastest, or both
Scope: Following are some applications of randomized (also called probabilistic) algorithms.