This short article aims to introduce the beauty of probabilistic (or randomized) algorithms, which allow problems to be solved that could not be solved otherwise due to difficulties generated by combinatorial explosion.

The idea is older than computers. Gauss, in 1791, thought about probabilistic arguments to calculate the number of products consisting of exactly k distinct prime factors below a given bound; the case k = 1 led to the famous prime number theorem [1]: if P(x) denotes the number of primes less than or equal to x, then P(x) is well approximated by x/log(x). The notion of probability also leads to a statistical estimate of the number p, as proposed in a famous experiment by the 18th-century French scientist Georges Louis LeClerc, Comte de Buffon. By repeatedly tossing a needle onto a lined paper, he found that, after n tosses, the estimate for p is (2n/k), where k is the number of times the needle intersects a line in the paper.

It is convenient to distinguish between the so-called Las Vegas probabilistic algorithms, those that use a random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time, and the Monte Carlo algorithms, those that may produce an incorrect result.

This paper analyzes, even if briefly and using computer jargon, important paradigmatic problems such as the count-distinct problem (finding the cardinality of a multiset), the nearest-neighbor search (for example, “finding items that are similar within a set”), and the reliable broadcast problem (for example, “reliably broadcasting messages among a large number of peers across ... the Internet”).

Even if it may be debatable whether they are really algorithms, as it has been said--in some cases, probabilistic algorithms are the only practical means of solving a problem--they tend not to be noticed precisely because they work.