In mathematics, the probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error.

This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis, as well as in computer science (e.g. randomized rounding) and information theory.

Introduction

If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero. Thus, by contraposition, if the probability that a random object chosen from the collection has that property is nonzero, then some object in the collection must possess the property.

Similarly, showing that the probability is (strictly) less than 1 can be used to prove the existence of an object that does not satisfy the prescribed properties.

Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value.

Alternatively, the probabilistic method can also be used to guarantee the existence of a desired element in a sample space with a value that is greater than or equal to the calculated expected value, since the non-existence of such element would imply every element in the sample space is less than the expected value, a contradiction.

Common tools used in the probabilistic method include Markov's inequality, the Chernoff bound, and the Lovász local lemma.

Two examples due to Erdős

Although others before him proved theorems via the probabilistic method (for example, Szele's 1943 result that there exist tournaments containing a large number of Hamiltonian cycles), many of the most well known proofs using this method are due to Erdős. The first example below describes one such result from 1947 that gives a proof of a lower bound for the Ramsey number.

First example

Suppose we have a complete graph vertices) that it is possible to color the edges of the graph in two colors (say red and blue) so that there is no complete subgraph vertices which is monochromatic (every edge colored the same color).

vertices as follows:

over all possible subsets, the expected value are the same color:

comes because there are two possible colors).

is

The sum of expectations is the expectation of the sum (regardless of whether the variables are independent-subgraphs) is

-subgraphs in this random coloring is a non-negative integer). It follows that if

-subgraphs.

By definition of the Ramsey number must grow at least exponentially.

A weakness of this argument is that it is entirely nonconstructive. The problem of finding such a coloring has been open for more than 50 years.

Second example

A 1959 paper of Erdős (see reference cited below) addressed the following problem in graph theory: given positive integers and , does there exist a graph containing only cycles of length at least , such that the chromatic number of is at least ?

It can be shown that such a graph exists for any and , and the proof is reasonably simple. Let be very large and consider a random graph on vertices, where every edge in exists with probability . We show that with positive probability, satisfies the following two properties:

1. Property 1. contains at most cycles of length less than .

Proof. Let be the number cycles of length less than . The number of cycles of length in the complete graph on vertices is

and each of them is present in with probability . Hence by Markov's inequality we have

1. Thus for sufficiently large , property 1 holds with a probability of more than .

2. Property 2. contains no independent set.

Proof. Let be the size of the largest independent set in . Clearly, we have

when

1. Thus, for sufficiently large , property 2 holds with a probability of more than .

For sufficiently large , the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1).

Here comes the trick: since has these two properties, we can remove at most vertices from to obtain a new graph vertices that contains only cycles of length at least . can only be partitioned into at least independent sets, and, hence, has chromatic number at least .

This result gives a hint as to why the computation of the chromatic number of a graph is so difficult: even when there are no local reasons (such as small cycles) for a graph to require many colors the chromatic number can still be arbitrarily large.

See also

• Interactive proof system

• Las Vegas algorithm

• Incompressibility method

• Method of conditional probabilities

• Probabilistic proofs of non-probabilistic theorems

• Random graph

Additional resources

• Probabilistic Methods in Combinatorics, MIT OpenCourseWare

References

• Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. .

• J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.

• Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics

• Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, , 2017

• Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp.296;

Footnotes