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
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
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
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
,
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
, and
real analysis
In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include conv ...
, as well as in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
(e.g.
randomized rounding
Within computer science and operations research,
many combinatorial optimization problems are computationally intractable to solve exactly (to optimality).
Many such problems do admit fast ( polynomial time) approximation algorithms—that is, alg ...
), 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.
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
In probability theory, Markov's inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant. It is named after the Russian mathematician Andrey Markov, ...
, the
Chernoff bound
In probability theory, the Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, the result is d ...
, and the
Lovász local lemma In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows one ...
.
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
A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses:
# One or more competitions held at a single venue and concentr ...
containing a large number of
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
s), 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
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
on vertices. We wish to show (for small enough values of ) 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 on vertices which is monochromatic (every edge colored the same color).
To do so, we color the graph randomly. Color each edge independently with probability of being red and of being blue. We calculate the expected number of monochromatic subgraphs on vertices as follows:
For any set
of
vertices from our graph, define the variable
to be if every edge amongst the
vertices is the same color, and otherwise. Note that the number of monochromatic
-subgraphs is the sum of
over all possible subsets
. For any individual set
, the
expected value of
is simply the probability that all of the
edges in
are the same color:
:
(the factor of comes because there are two possible colors).
This holds true for any of the
possible subsets we could have chosen, i.e.
ranges from to
. So we have that the sum of