probabilistic method

The probabilistic method was pioneered by Erdős Pál (known to Westerners as Paul Erdős) and initially used for solving problems in graph theoryMathworldPlanetmath, but has acquired ever wider applications. Broadly, the probabilistic method is somewhat the opposite of extremal graph theory. Instead of considering how a graph can behave in the most extreme case, we consider how a collectionMathworldPlanetmath of graphs behave “on average”, whereby we can formulate a probability spaceMathworldPlanetmath. The fruits reaped by this method are often raw existence theoremsMathworldPlanetmath, usually deduced from the fact that the nonexistence of whatever of graph would a zero probability. For instance, by means of the probabilistic method, Erdős proved the existence of a graph of arbitrarily high girth and chromatic numberMathworldPlanetmath, a very counterintuitive result. Graphs tend to get enormous as the chromatic number and girth increase, thereby severely hindering necessary computations to explicitly construct them, so an existence theorem is most welcome.

In all honesty, probabilistic proofs are nothing more than counting proofs in disguise, since determining the probabilities of interest will invariably involve detailed counting arguments. In fact, we could remove from any probabilistic proof any mention of a probability space, although the result may be significanltly less transparent. Also, the advantage of using probability is that we can employ all the machinery of probability theory. Markov chainsMathworldPlanetmath, martingalesMathworldPlanetmath, expectations (, probabilistic inequalities, and many other results, all become the tools of the trade in dealing with seemingly static objects of combinatorics and number theoryMathworldPlanetmathPlanetmath.


  • 1 Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, Inc., second edition, 2000. 0996.05001.
  • 2 Paul Erdős and Joel Spencer. Probabilistic methods in combinatorics. Academic Press, 1973. 0308.05001.
Title probabilistic method
Canonical name ProbabilisticMethod
Date of creation 2013-03-22 13:05:53
Last modified on 2013-03-22 13:05:53
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 15
Author bbukh (348)
Entry type Topic
Classification msc 05C80
Classification msc 11K99
Related topic GraphTheory
Related topic ProofOfCrossingLemma
Related topic RamseysTheorem2