Concept

Union bound

The inequality that the chance of at least one of several events is at most the sum of their separate chances. It needs nothing about how the events overlap, which is why it is the first estimate reached for when many different things could go wrong.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The expected number of monochromatic sets, and where it drops below one. The logarithm of the expected number of single-coloured 4, 5, 6-point sets in a random two-colouring, plotted against the number of points, with the crossing of one marked for each.

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

discrete · Ramsey theory

A 6-sided die rolled 6 to 40 times: some face missing, and the sum stopped early. Curves of the chance that some face of a die has not yet appeared against the number of rolls, with the inclusion–exclusion sum stopped after one, two and three terms drawn around the exact curve.

A sum stopped early still says something

Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.

probability · Inclusion exclusion

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argument Alternating series Approximation Binomial coefficient Complementary counting Complete graph Derangement Existence proof Expectation Independence Nonconstructive Probabilistic method

All concepts