Paradigms for Probabilistic Algorithms

Fair choice. Deterministic algorithms for problems of fair choice like load balancing, deadlock and starvation avoidance can be rather tricky. Randomization is a powerful tool for such problems.

Breaking intractability. Some problems like multivariate integration problems with a fixed error guarantee epsilon and primality testing may be intractable because of the work involved in finding the solution. Accepting a weaker guarantee "the error is probably no more than epsilon" and "it is highly probable that the number is a prime" makes these problems tractable in a probabilistic setting.

Fingerprinting. A long string may be represented by a short fingerprint by random mapping. The original strings are likely to be identical if their fingerprints are identical so that only the fingerprints need to be compared. Hashing is a special application of this idea.