---
tag: 3B55HNS754
kind: concept
name: Probabilistic method
msc: [05D40, 60C05]
sources:
  - url: https://en.wikipedia.org/wiki/Probabilistic_method
same_as:
  wikidata: Q3333679
  wikipedia: Probabilistic method
---

## Summary

The probabilistic method proves that an object with a given property exists.
It chooses an object at random and shows that it has the property with positive probability.
It is a nonconstructive method: it usually gives no explicit example.
Erdős made it a main tool of combinatorics, starting with lower bounds for [[Ramsey numbers|0K9QVPJYJF]].
Its tools include [[linearity of expectation|0P7PTC8DDE]] and [[Boole's inequality|0EGSEE9J9R]].
More refined tools are the [[Lovász local lemma|35YQ94FNV1]] and concentration inequalities.

## Explanations

### L1 human

To show that something exists, it is enough to show that a random choice finds it with a chance above zero.
For example, colour the edges of a complete graph red or blue by fair coin flips.
If the expected number of single-coloured large cliques is below $1$, some colouring has none.
So a good colouring exists, even though the argument does not tell you which one it is.