Probabilistic Method

Probabilistic Method is a general methodology developed by Paul Erdös starting in the late 1940s [Mathematics Unlimited, pp. 1095-1096]. The idea of the method is that in order to prove the existence of an object one designs a non-deterministic algorithm that may or may not produce the desired object. Having the probability of failure less than one guarantees the existence of the object.

An informal example comes from an article by Noga Alon and Michael Krivelevich:

Suppose that m teams basketball teams compete in a tournament and any two teams play each other exactly once. The organizers wish to award n prizes at the end of the tournament. It would be embarrassing if there ended up being a team that had not won a prize despite beating all the teams that had won a prize. However, unlikely though it might sound, it is quite possible that this will be the case whatever n teams they choose, at least if m is large enough. To demonstrate this is easy if one uses the probabilistic method, which is one of the most powerful techniques in combinatorics. For any fixed n, and all sufficiently large m, if the results of all the games are chosen randomly (and uniformly and independently), then there is a very high probability that for any n teams there is another team that beats all of them. Probabilistic combinatorics, which is one of the most active areas in modern combinatorics, started with the realization that probabilistic reasoning often provides simple solutions to problems of this type, problems that are often very hard to solve in any other way.

Here's an example (Erdös, 1963).

Proposition

Let A_k, k = 1, ..., m be subsets of a set Ω, each with n elements: |A_k| = n, k = 1, ..., m. If m < 2^n-1, then there exists a bichromatic coloring of Ω such that no A_k is monochromatic.

Proof

Let F be a collection of n-sets (sets with exactly n elements), and assume that |F| = m < 2^n-1. Color Ω randomly with two colors, all colorings being equally likely. For A ∈ F let E_A be the event that A is monochromatic. Since there are two such colorings and |A| = n, probability P(E_A) of the event E_A is given by

P(E_A) = 2×2^-n = 2^1-n.

Since the events E_A are not necessarily disjoint,

P(∪_A∈F E_A) < ∑_A∈F P(E_A) = m2^1-n < 1.

So the probability that at least one A∈F is monochromatic is less than 1. Thus there bound to be a bichromatic coloring with no monochromatic A's.

Note that, for example, if |Ω| = m = 2n-1 then, for any bichromatic coloring of Ω, there is a monochromatic subset A, |A| = n.

We may apply similar reasoning to the problem of awards in a basketball tournament.

If the results of the tournament are random, then the probability that there is no team that won against a selection of n teams is (1 - 2^-n)^{m - n}. There are C(n, m) such selections. This leads a condition:

C(m, n)(1 - 2^-n)^{m - n} < 1.

If this condition holds, there is a non-zero probability that, for every selection of n teams, there is a team that beats them all.

Reference

N. Alon, M. Krivelevich, Extremal and Probabilistic Combinatorics, in The Princeton Companion to Mathematics, T. Gowers (ed.), Princeton University Press, 2008
M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
J. Spencer, Discrete Probability, in Mathematics Unlimited - 2001 and Beyond, B. Engquist, W. Schmid (eds), Springer, 2001

41162375