Paradigms for Probabilistic Algorithms

Now when we have seen examples of classes probabilistic algorithms it is appropriate to state a few general principles that lies at the heart of almost all such algorithms. I many algorithms several of these principles are employed.

Random sampling. The idea that a random sample from a population is representative of the population as a whole is used in many probabilistic algorithms.

Foiling an adversary. For a deterministic algorithm it is possible to find a problem instance for which the algorithm fares poorly (worst case). This is normally impossible for a probabilistic algorithm because its detailed behavior is unpredictable (worst case -> average case).

Random re-ordering. For some problems like data structuring, foiling an adversary can be achieved just by initially randomly re-ordering the input data before the application of a deterministic algorithm.