Probabilistic method

A proof technique that establishes an object with a desired property exists by showing that a random choice has positive probability of satisfying it.

Linearity of expectation: The identity that the expectation of a sum equals the sum of the expectations, even when the variables are dependent. It lets proofs show that some outcome meets a target by estimating an average.
Ramsey theory: The study of conditions under which sufficiently large structures contain highly organized substructures. Random graphs give lower bounds on how large Ramsey numbers must be.
Paul Erdős: A Hungarian mathematician whose work shaped combinatorics, number theory, and graph theory. Erdős’s proofs established the method’s reach, especially in Ramsey theory.
Constructive proof: A proof that provides an explicit object, procedure, or algorithm witnessing the claim. A probabilistic existence proof may guarantee a witness without specifying how to produce it.
Expectation: The probability-weighted average value of a random variable. Existence arguments often compare an expected quantity with a threshold that some outcome must reach.
Random graph: A graph chosen according to a probability distribution over graphs, often by independently including each possible edge. Random graphs supply samples whose properties yield existence bounds for finite graphs.
Alfréd Rényi: A Hungarian mathematician known for foundational work in probability theory and information theory. His collaboration with Erdős helped develop the theory of random graphs used in existence proofs.
Probabilistic analysis of algorithms: The analysis of an algorithm’s expected behavior under a probability distribution on inputs or internal choices. It uses probability to estimate performance rather than primarily to prove that an object exists.
Markov's inequality: For a nonnegative random variable, the probability of reaching a positive threshold is at most its expectation divided by that threshold. It converts an expectation bound into a probability bound on undesirable outcomes.
Erdős–Ko–Rado theorem: A theorem bounding the size of an intersecting family of fixed-size subsets under specified conditions. Probabilistic arguments illuminate extremal bounds on families of combinatorial objects.

Linked from 12 pages