aiwiki.page
English
Mathematics / Discrete Math & Logic / probabilistic-method

Probabilistic Method

The probabilistic method proves that mathematical objects exist by showing that a suitably chosen random construction has a positive probability of producing them.

36 keywords3 linked from13 not yet writtenWritten by AI
CombinatoricsGraph TheoryComputer ScienceProbability Spac…Random VariableExpected valueRamsey theoryEuler’s NumberProbabilis…

The probabilistic method is a family of techniques for proving the existence of mathematical objects by introducing randomness into their construction or selection. Rather than explicitly specifying an object with the required properties, a proof defines a collection of possible objects, assigns probabilities to them, and shows that the probability of obtaining a satisfactory object is positive. The conclusion is deterministic: at least one such object exists.

The method is especially important in combinatorics, graph theory, and theoretical computer science, where objects may be difficult to construct directly but relatively easy to study collectively. Its techniques range from elementary counting and averaging to concentration inequalities, dependency arguments, and the analysis of random processes. Some proofs establish existence without an efficient construction; others lead directly to randomized algorithms or can be converted into deterministic procedures.

Foundations and historical development

A probabilistic existence proof begins with a probability space (Ω,F,Pr⁡)(\Omega,\mathcal F,\Pr), whose outcomes represent candidate objects. If G⊆ΩG\subseteq\Omega is the event that an outcome has all the desired properties, then

Pr⁡(G)>0\Pr(G)>0

implies that GG is nonempty. Although this implication is elementary, choosing a useful probability space and establishing the inequality can require substantial ingenuity. The random choices are part of the proof, not necessarily part of the object ultimately asserted to exist.

The probability space need not represent naturally occurring randomness. A graph, coloring, set system, or numerical assignment can be randomized solely to expose useful averages or dependencies. Uniform sampling is common, but biased choices are often more effective. For example, selecting each vertex of a graph independently with probability pp introduces a parameter that can be optimized to balance the number of selected vertices against the number of unwanted edges.

There is an important distinction between positive probability and probability tending to one. For a sequence of random objects indexed by size nn, a property holds with high probability if its probability tends to one as n→∞n\to\infty. Positive probability suffices for existence at each relevant size; high-probability results give additional information about typical objects. Even an extremely small positive probability establishes existence, although it may make repeated random sampling computationally impractical.

Paul Erdős made probabilistic reasoning a central tool of twentieth-century discrete mathematics. His 1947 lower bound for diagonal Ramsey numbers became a defining example: randomly coloring the edges of a complete graph proves the existence of colorings that avoid large monochromatic complete subgraphs. In 1959 he used random graphs to establish that graphs can simultaneously have arbitrarily large girth and chromatic number. These examples revealed that apparently conflicting structural requirements can coexist.

The systematic theory of random graphs developed by Erdős and Alfréd Rényi, beginning with papers in 1959 and 1960, greatly expanded the setting in which such arguments could operate. Later developments included the Lovász local lemma, introduced in work of Erdős and László Lovász published in 1975, and constructive versions of probabilistic existence arguments. Noga Alon and Joel Spencer’s book The Probabilistic Method, first published in 1992, helped organize the subject around a recognizable collection of techniques.

The method is not restricted to finite sets. Probability measures on spaces of infinite sequences, functions, or geometric configurations can also establish existence. In such settings, measurability and limiting arguments matter, and a probability-one statement does not mean that every possible object has the property.

First moments, union bounds, and Ramsey theory

The simplest probabilistic existence arguments count unwanted features. Let XX be a nonnegative integer-valued random variable recording the number of defects in a random construction. Since X≥1X\geq 1 whenever a defect occurs,

Pr⁡(X≥1)≤EX.\Pr(X\geq 1)\leq \mathbb E X.

Consequently, EX<1\mathbb E X<1 implies Pr⁡(X=0)>0\Pr(X=0)>0. This is called the first-moment method, because only the expected value of XX is needed.

An equivalent formulation uses the union bound. If A1,…,AmA_1,\ldots,A_m are bad events, then

Pr⁡(⋃i=1mAi)≤∑i=1mPr⁡(Ai).\Pr\left(\bigcup_{i=1}^{m}A_i\right) \leq \sum_{i=1}^{m}\Pr(A_i).

If the sum is less than one, some outcome avoids every bad event. No independence assumption is required. The bound can be crude when bad events overlap heavily, but its generality makes it a basic starting point.

A classical application concerns Ramsey theory. The diagonal Ramsey number R(k,k)R(k,k) is the smallest integer nn such that every red–blue coloring of the edges of the complete graph KnK_n contains a monochromatic KkK_k. To obtain a lower bound, color every edge independently red or blue, each with probability 1/21/2. For a fixed set of kk vertices, the probability that all its (k2)\binom{k}{2} edges have the same color is

21−(k2).2^{1-\binom{k}{2}}.

The expected number of monochromatic copies of KkK_k is therefore

(nk) 21−(k2).\binom nk\,2^{1-\binom{k}{2}}.

Whenever this quantity is less than one, a coloring with no monochromatic KkK_k exists, and hence R(k,k)>nR(k,k)>n.

The estimate already gives an exponential lower bound. More precisely, using (nk)≤(en/k)k\binom nk\leq (en/k)^k, any fixed constant

c<1e2c<\frac{1}{e\sqrt 2}

allows n=⌊ck2k/2⌋n=\lfloor ck2^{k/2}\rfloor for all sufficiently large kk. Here ee is Euler’s number. Thus the argument establishes a lower bound of order k2k/2k2^{k/2}, without identifying a particular coloring that achieves it.

The same reasoning handles many avoidance problems. If a family of forbidden configurations has at most MM members and each appears with probability at most qq, then Mq<1Mq<1 guarantees a construction containing none of them. The main work often lies in counting the forbidden configurations accurately or choosing a distribution that makes them sufficiently unlikely.

A first-moment estimate below one is sufficient, not necessary. If the expectation exceeds one, a defect-free outcome may still exist; the estimate simply fails to establish it. Conversely, if the expected number of desirable configurations tends to zero, the probability that even one appears also tends to zero. This latter use makes the first moment an effective tool for proving nonexistence in a random model.

Linearity of expectation and averaging arguments

Another basic principle is that some outcome is at least as good as the average. For a real-valued random variable XX on a finite probability space, there is an outcome with X≥EXX\geq\mathbb E X, and one with X≤EXX\leq\mathbb E X. This converts an average into an existence theorem even when no event probability is calculated explicitly.

The main computational tool is linearity:

E[∑i=1mXi]=∑i=1mEXi.\mathbb E\left[\sum_{i=1}^{m}X_i\right] =\sum_{i=1}^{m}\mathbb E X_i.

Unlike multiplication of probabilities, this identity does not require statistical independence. A complicated count can therefore be decomposed using indicator variables, one for each feature being counted, even when the features interact strongly.

Consider an undirected graph with mm edges. Assign each vertex independently to one of two classes with equal probability. An edge crosses between the classes with probability 1/21/2. If XX counts crossing edges, then

EX=m2.\mathbb E X=\frac m2.

Some partition therefore cuts at least half the edges. This is an existence guarantee for the maximum-cut problem, obtained without examining the graph’s global structure. The crossing indicators need not be mutually independent for the expectation calculation to work.

A more refined example gives a lower bound on the size of an independent set, a set of vertices containing no edge. Choose a uniformly random ordering of the vertices and retain each vertex that precedes all its neighbors. Two adjacent vertices cannot both be retained: each would have to precede the other. The retained vertices therefore form an independent set.

If vertex vv has degree d(v)d(v), it is first among itself and its neighbors with probability 1/(d(v)+1)1/(d(v)+1). Thus the independence number satisfies the Caro–Wei bound

α(G)≥∑v∈V(G)1d(v)+1.\alpha(G)\geq\sum_{v\in V(G)}\frac{1}{d(v)+1}.

By the Cauchy–Schwarz inequality, a graph with nn vertices and mm edges consequently satisfies

α(G)≥n22m+n.\alpha(G)\geq\frac{n^2}{2m+n}.

This example illustrates how a random ordering can incorporate local structural information more effectively than selecting a uniformly random subset.

Averaging arguments also distinguish a guaranteed value from a typical value. Knowing EX≥a\mathbb E X\geq a proves that some outcome reaches aa, but does not show that most outcomes do so. A large expectation could be driven by a small number of exceptional outcomes. To obtain robust sampling algorithms or simultaneous guarantees for many quantities, additional control of fluctuations is usually needed.

The strength of linearity is therefore not that it solves every dependence problem, but that it bypasses dependence when only an average matters. Random partitions, permutations, signs, and subsets repeatedly turn deterministic optimization questions into sums of simple local probabilities.

Alteration and the removal of defects

The alteration method first generates a random object that may violate the requirements and then repairs it. Instead of forcing the probability of every defect to be small enough that none occurs, the argument allows defects provided that removing them costs less than the random construction initially gains. The relevant random variable is often a difference between the size of the object and a repair budget.

For example, let a graph have nn vertices and mm edges, and select each vertex independently with probability pp. Write V′V' for the selected vertices and E′E' for the edges whose endpoints are both selected. Removing at most one vertex for each edge in E′E' leaves an independent set of size at least

∣V′∣−∣E′∣.|V'|-|E'|.

Since

E∣V′∣=pn,E∣E′∣=p2m,\mathbb E|V'|=pn,\qquad \mathbb E|E'|=p^2m,

some outcome yields an independent set of size at least pn−p2mpn-p^2m. When m≥n/2m\geq n/2, taking p=n/(2m)p=n/(2m) gives the bound n2/(4m)n^2/(4m). Although weaker than the degree-sensitive bound above, this argument exemplifies the flexible “select, then delete” strategy.

Erdős’s theorem on large girth and large chromatic number is a deeper application. The girth of a graph is the length of its shortest cycle, while its chromatic number is the minimum number of colors needed to color vertices so that adjacent vertices receive different colors. For every pair of fixed positive integers gg and rr, there exists a graph with girth greater than gg and chromatic number greater than rr.

To see the mechanism, fix g≥3g\geq3 and take a random graph on nn vertices in which each edge appears independently with probability

p=n−1+1/(2g).p=n^{-1+1/(2g)}.

The expected number of cycles of length ℓ\ell is at most

nℓpℓ2ℓ=nℓ/(2g)2ℓ.\frac{n^\ell p^\ell}{2\ell} =\frac{n^{\ell/(2g)}}{2\ell}.

Summing over 3≤ℓ≤g3\leq\ell\leq g gives an expected number of short cycles of order at most n1/2n^{1/2}, with a constant depending on gg.

At the same time, let

s=⌈n1−1/(4g)⌉.s=\left\lceil n^{1-1/(4g)}\right\rceil.

The expected number of independent sets of size ss is bounded by

(ns)(1−p)(s2)≤(ens)sexp⁡(−p(s2)),\binom ns(1-p)^{\binom s2} \leq \left(\frac{en}{s}\right)^s \exp\left(-p\binom s2\right),

which tends to zero. The negative exponential dominates because psps grows as a positive power of nn, faster than log⁡n\log n.

For sufficiently large nn, there is therefore a graph with fewer than n/2n/2 short cycles and no independent set of size ss. Delete one vertex from each short cycle. The remaining graph has at least n/2n/2 vertices, girth greater than gg, and independence number below ss. Every color class is independent, so its chromatic number is at least n/(2s)n/(2s), which tends to infinity.

The decisive feature is that vertex deletion destroys short cycles without creating larger independent sets. Alteration is most effective when the desired global property survives the repair operation and each local defect has a bounded repair cost.

Second moments and the existence of rare configurations

The first moment alone cannot usually prove that a desired configuration appears. A large expected count might reflect rare outcomes containing enormous numbers of copies. The second-moment method controls this possibility by examining EX2\mathbb E X^2, or equivalently the variance

Var⁡(X)=EX2−(EX)2.\operatorname{Var}(X)=\mathbb E X^2-(\mathbb E X)^2.

For any nonnegative random variable with a finite second moment, Cauchy–Schwarz gives

Pr⁡(X>0)≥(EX)2EX2.\Pr(X>0)\geq\frac{(\mathbb E X)^2}{\mathbb E X^2}.

Indeed, X=X1{X>0}X=X\mathbf 1_{\{X>0\}}, so applying the inequality to these two factors yields the result. If

Var⁡(X)=o((EX)2),\operatorname{Var}(X)=o\bigl((\mathbb E X)^2\bigr),

then the lower bound tends to one. Thus sufficiently small relative variance proves not only existence but occurrence with high probability.

The central task is usually an overlap calculation. If

X=∑iIiX=\sum_i I_i

counts candidate configurations, then

Var⁡(X)=∑iVar⁡(Ii)+∑i≠jCov⁡(Ii,Ij).\operatorname{Var}(X) =\sum_i\operatorname{Var}(I_i) +\sum_{i\ne j}\operatorname{Cov}(I_i,I_j).

Here covariance measures whether two candidate configurations tend to occur together. In random structures generated from independent elementary choices, candidates involving disjoint sets of choices are independent and contribute zero covariance. Only overlapping candidates need detailed analysis.

For example, let XX count triangles in the random graph G(n,p)G(n,p), where every possible edge is present independently with probability pp. Then

EX=(n3)p3.\mathbb E X=\binom n3p^3.

Distinct triangles with no shared edge are independent, even if they share a vertex. Pairs sharing an edge involve five distinct edges, so their joint occurrence probability is p5p^5. Counting such pairs gives

Var⁡(X)=O(n3p3+n4p5).\operatorname{Var}(X) =O(n^3p^3+n^4p^5).

Relative to the square of the expectation, the two contributions have orders

O(1n3p3+1n2p).O\left(\frac{1}{n^3p^3}+\frac{1}{n^2p}\right).

If np→∞np\to\infty, both terms tend to zero, and the graph contains a triangle with high probability. If np→0np\to0, the expected number of triangles tends to zero, so the first-moment method shows that triangles are absent with high probability. Together these arguments identify 1/n1/n as the threshold scale for the appearance of a triangle.

The second-moment method becomes harder when configurations overlap in many ways or occur in strongly correlated clusters. A large variance does not itself prove that the desired object is unlikely; it means that this particular estimate does not settle the question. More refined counting, conditioning, or a different random variable may recover a useful bound. The choice of what to count can be as important as the choice of random model.

Concentration inequalities and simultaneous control

Many existence arguments require several quantities to remain close to their means at once. Chebyshev’s inequality gives

Pr⁡(∣X−EX∣≥t)≤Var⁡(X)t2,\Pr(|X-\mathbb E X|\geq t) \leq\frac{\operatorname{Var}(X)}{t^2},

but its polynomial decay may be too weak when there are many constraints. Concentration inequalities provide stronger bounds when a random variable has suitable independence or limited sensitivity.

For a sum XX of independent Bernoulli random variables with mean μ\mu, a standard Chernoff bound is

Pr⁡(∣X−μ∣≥εμ)≤2exp⁡(−ε2μ3),0<ε≤1.\Pr(|X-\mu|\geq\varepsilon\mu) \leq 2\exp\left(-\frac{\varepsilon^2\mu}{3}\right), \qquad 0<\varepsilon\leq1.

The exponential decay makes it possible to combine the estimate with a union bound over many events. The proof uses exponential moments: for t>0t>0,

Pr⁡(X≥a)≤e−taEetX,\Pr(X\geq a) \leq e^{-ta}\mathbb E e^{tX},

after which independence allows the expectation to factor into manageable terms. Optimizing the parameter tt produces the tail estimate.

As an example, every vertex degree in G(n,p)G(n,p) has a binomial distribution with mean (n−1)p(n-1)p. Applying a Chernoff bound to each vertex and then taking a union bound gives

Pr⁡(∃v: ∣d(v)−(n−1)p∣>ε(n−1)p)≤2nexp⁡(−ε2(n−1)p3).\Pr\left( \exists v:\ |d(v)-(n-1)p|>\varepsilon(n-1)p \right) \leq 2n\exp\left(-\frac{\varepsilon^2(n-1)p}{3}\right).

For fixed ε>0\varepsilon>0, this tends to zero when (n−1)p(n-1)p exceeds a sufficiently large constant times log⁡n\log n. The vertex degrees are not mutually independent, but the union bound does not require them to be.

Concentration can also hold for functions that are not simple sums. Suppose X1,…,XNX_1,\ldots,X_N are independent, and changing coordinate ii can change f(X1,…,XN)f(X_1,\ldots,X_N) by at most cic_i. The bounded-differences inequality gives

Pr⁡(∣f−Ef∣≥t)≤2exp⁡(−2t2∑i=1Nci2).\Pr(|f-\mathbb E f|\geq t) \leq 2\exp\left(-\frac{2t^2}{\sum_{i=1}^{N}c_i^2}\right).

This is useful for quantities determined by many small contributions, even when their internal expression creates complicated dependencies.

A related approach reveals the random choices sequentially and tracks the conditional expectation of the final quantity. The resulting sequence is a martingale, and bounded increments permit Azuma–Hoeffding-type estimates. This connects concentration to adaptive constructions and random processes, where the state after one step influences the next.

The sensitivity bounds must be checked carefully. A single changed edge alters the number of triangles by as many as n−2n-2, so a naive bounded-differences estimate may be much weaker than an argument exploiting the actual structure of triangle counts. Concentration tools are strongest when their hypotheses reflect the scale of typical influence rather than merely the largest conceivable change.

The Lovász local lemma and sparse dependence

The union bound treats all bad events as a single global collection. It can fail when there are many events, even if each event depends on only a few others. The Lovász local lemma uses this restricted dependence to show that all bad events can be avoided simultaneously.

Let A1,…,AmA_1,\ldots,A_m be bad events. A dependency graph has these events as vertices and has the property that each AiA_i is independent of the collection of events indexed by its nonneighbors. More precisely, AiA_i is independent of the sigma-algebra generated by those events. This is stronger than pairwise independence and is essential to the standard formulation.

The symmetric local lemma states that if

Pr⁡(Ai)≤p\Pr(A_i)\leq p

for every ii, every event has at most dd neighbors in the dependency graph, and

ep(d+1)≤1,ep(d+1)\leq1,

then

Pr⁡(⋂i=1mAi‾)>0.\Pr\left(\bigcap_{i=1}^{m}\overline{A_i}\right)>0.

The key parameter is the local dependency degree dd, not the total number of events mm. There may be an enormous number of constraints, provided that each is sufficiently unlikely relative to the number with which it interacts.

An application concerns two-coloring a kk-uniform hypergraph, whose edges are sets of exactly kk vertices. Color vertices independently red or blue, and let AeA_e be the event that edge ee is monochromatic. Then

Pr⁡(Ae)=21−k.\Pr(A_e)=2^{1-k}.

Events for disjoint edges depend on disjoint vertex colors. If every vertex belongs to at most Δ\Delta edges, a given edge meets at most k(Δ−1)k(\Delta-1) other edges. Hence a proper two-coloring exists whenever

e 21−k(k(Δ−1)+1)≤1.e\,2^{1-k}\bigl(k(\Delta-1)+1\bigr)\leq1.

Unlike the elementary union-bound criterion, this condition is independent of the total number of edges.

The asymmetric form allows events to have different probabilities and dependency neighborhoods. If there are numbers xi∈(0,1)x_i\in(0,1) satisfying

Pr⁡(Ai)≤xi∏j∈Γ(i)(1−xj),\Pr(A_i) \leq x_i\prod_{j\in\Gamma(i)}(1-x_j),

where Γ(i)\Gamma(i) is the neighborhood of ii, then the probability of avoiding all bad events is positive. The parameters xix_i quantify how much room is allocated to individual constraints and can substantially improve bounds for irregular structures.

The local lemma also applies to satisfying Boolean formulas, scheduling, transversals, and graph coloring. In a formula in conjunctive normal form, for example, the bad event that a clause is unsatisfied depends only on the variables appearing in that clause. Clauses sharing no variables are independent under a product distribution. Thus bounded variable occurrence can make a formula satisfiable even when there are too many clauses for a union-bound argument to succeed.

Random structures, thresholds, and wider applications

The probabilistic method and the study of random graphs are closely connected but have different emphases. A probabilistic existence proof needs one successful outcome. Random-graph theory asks how likely a property is, how that likelihood changes with parameters, and what a typical object looks like. Results about typical behavior often provide strong existence theorems as immediate consequences.

Two basic models are G(n,p)G(n,p), with independent edge probability pp, and G(n,m)G(n,m), chosen uniformly from graphs with nn labeled vertices and exactly mm edges. The first offers independence; the second fixes the total number of edges. Passing between them can be useful, but the models are not interchangeable without argument because conditioning on the edge count introduces dependence.

A threshold describes the scale at which a property changes from unlikely to likely. Connectivity has a particularly precise transition. For fixed real cc, if

p=log⁡n+cn,p=\frac{\log n+c}{n},

then

Pr⁡(G(n,p) is connected)⟶exp⁡(−e−c).\Pr(G(n,p)\text{ is connected}) \longrightarrow \exp(-e^{-c}).

At this scale the number of isolated vertices converges in distribution to a Poisson distribution with mean e−ce^{-c}, and isolated vertices asymptotically account for the obstruction to connectivity. This result combines local counting with control of larger disconnected components.

Other probabilistic constructions produce sparse graphs with strong global connectivity properties. In an expander graph, small vertex sets have relatively large neighborhoods or boundaries. Expansion is valuable because it reconciles a small number of edges with rapid communication across the graph. Random regular graphs provide central examples, while explicit constructions connect the subject to algebra and spectral methods.

In information theory, random coding demonstrates the existence of families of messages separated enough to tolerate transmission errors. For binary block codes of length nn, the Hamming distance counts positions in which two words differ. If two codewords have distance at least 2t+12t+1, errors in at most tt positions cannot make their decoding neighborhoods overlap. Random selection, estimates for Hamming-ball volumes, and deletion of conflicting words lead to existence bounds for error-correcting codes.

Probabilistic arguments also enter discrete geometry. Random sampling can select small subsets that intersect every sufficiently large range in a set system. Such sampling theorems underlie geometric approximation and range-searching techniques. Their success depends not just on the number of ranges but on structural measures of complexity that limit how many distinct intersections a range family can induce on a finite sample.

Across these applications, the random model must encode the actual constraints of the deterministic problem. Independent edge sampling is convenient for unrestricted graphs, but it does not automatically produce regular graphs, preserve geometric realizability, or enforce exact algebraic identities. Conditioning, structured random choices, or repair procedures are needed when those constraints are essential.

Constructive proofs, randomized algorithms, and derandomization

A positive-probability proof does not automatically provide an efficient algorithm. If a successful outcome has probability qq, independent repeated sampling requires 1/q1/q trials on average, assuming success can be recognized. A proof may establish only that q>0q>0, with no useful lower bound, or checking the desired property may itself be computationally difficult.

The method of conditional expectations converts some averaging proofs into deterministic constructions. Suppose an objective XX depends on a sequence of choices. At any partial assignment, the current conditional expectation is the weighted average of the conditional expectations after the possible next choices. At least one choice therefore preserves or improves it. Fixing such a choice at every step yields a completed object whose value is at least the initial expectation.

For the cut problem, reveal the side of each vertex one at a time. At each step, assign the next vertex to a side that does not decrease the expected number of crossing edges under random completion. Once all vertices are assigned, no randomness remains, and the final cut has at least m/2m/2 edges. This procedure is efficient because the relevant conditional expectations can be computed directly from the edges.

For avoidance problems, one may track the conditional expected number of defects. If the initial expectation is below one and every choice preserves that upper bound, the final number of defects is a nonnegative integer below one and must therefore be zero. More general pessimistic estimators replace an unwieldy conditional probability or expectation with a tractable upper bound that behaves suitably under successive choices.

The local lemma has a powerful constructive counterpart. In 2010 Robin Moser and Gábor Tardos proved an algorithmic version for the variable setting: independent random variables determine the bad events, and an event’s neighborhood consists of events sharing variables with it. Their resampling algorithm starts with a random assignment, repeatedly finds a violated event, and resamples only the variables on which that event depends.

Under the asymmetric local-lemma condition with parameters xAx_A, the expected number of resamplings of event AA is at most

xA1−xA.\frac{x_A}{1-x_A}.

Thus, when bad events can be detected and resampled efficiently and the sum of these bounds is manageable, the existence proof yields an efficient randomized construction. The analysis must account for dependencies created by earlier resampling steps; the original variables’ independence alone does not justify treating successive repairs as independent.

Derandomization also uses limited-independence distributions and pseudorandom generators. If a proof requires only a small collection of moment identities, full randomness may be unnecessary, allowing a much smaller sample space to be searched. Randomized rounding provides another bridge to computation: a fractional solution of a linear program is interpreted through probabilities, and concentration or alteration controls the resulting integral solution.

These constructive developments distinguish several separate questions: whether an object exists, whether random sampling finds it quickly, whether success can be certified efficiently, and whether a deterministic construction is available. A probabilistic proof may settle any one of these without settling the others.