Concentration Inequalities Quantify How Random Sums Leave Their Typical Set

The law of large numbers tells us that an average of independent observations converges toward its expectation. The central limit theorem goes further and describes the scale and approximate shape of ordinary fluctuations around that expectation. Both results are foundational, but neither directly answers a common finite-sample question:

Given the sample size I actually have, how unlikely is a deviation of this size?

That question appears everywhere. How unlikely is it that a defect rate estimated from one thousand components exceeds its nominal value by two percentage points? How far can an empirical mean move from its expectation with probability at most one in a million? How large can the maximum of ten thousand noisy coordinates become? How much can a function of many independent inputs change because the inputs fluctuate? How confident can we be that a stochastic algorithm has not deviated substantially from its average behaviour?

Concentration inequalities answer questions of this form by providing non-asymptotic tail bounds. Instead of waiting for

they give inequalities valid at a specified finite $n$.

The price is that a bound is usually not an exact probability. It is a guarantee derived from limited structural information. If all we know is that the variables lie in an interval, Hoeffding's inequality gives a distribution-free exponential tail. If we also know the variance is small, Bernstein-type inequalities can be much sharper. If we know the exact Bernoulli distribution, the Chernoff method can exploit its full moment-generating function and produce a relative-entropy bound that is sharper again.

These are not competing formulas for the same information. They answer the same tail question from increasingly rich assumptions.

The distinction becomes dramatic in rare-event problems.

Exponential moments turn a tail probability into an optimization problem

Let

be a random variable whose upper tail we want to bound. For any

the event

is equivalent to

Markov's inequality therefore gives

Because this is true for every positive $\lambda$,

If $S$ is centred,

it is convenient to write the cumulant-generating function

Then

The exponent is the convex conjugate of the log moment-generating function.

This is the core Chernoff method. Many concentration inequalities differ only in how the moment-generating function is bounded before the optimization over $\lambda$ is performed.

If the exact mgf is known, one can optimize it directly.

If only boundedness is known, Hoeffding's lemma supplies a universal quadratic mgf bound.

If variance and boundedness are known, Bernstein's method keeps more information and obtains a quadratic-to-linear transition in the exponent.

The geometry of the tail bound is therefore already contained in the log mgf.

Hoeffding uses only the range

Suppose

are independent and

almost surely.

Hoeffding's lemma states that for any centred bounded variable,

Independence allows exponential moments to multiply. For

we obtain

Applying the Chernoff method and optimizing in $\lambda$ gives

For independent variables in

the empirical mean

therefore satisfies

The two-sided form is

The inequality is powerful because it requires no knowledge of the distribution inside the interval. Bernoulli variables, continuous uniforms, bimodal bounded distributions and highly irregular bounded laws all receive the same guarantee.

That universality is also why the bound can be loose.

Hoeffding only knows that each observation lies somewhere in a range of width one. It does not know whether almost all mass is concentrated near zero, whether the variance is tiny, whether the distribution is symmetric or whether the exact mgf is available.

A distribution-free guarantee cannot exploit information it was never given.

A rare Bernoulli event shows how much information Hoeffding discards

Let

independently, with

The true mean is

Suppose we observe an empirical rate of at least

Equivalently,

The exact probability is the upper tail of a binomial distribution:

This is a genuinely rare deviation.

Hoeffding sees only that each observation lies in

and that the empirical mean deviates upward by

Its one-sided bound is

The true probability is about

Hoeffding's valid upper bound is approximately

times larger than the actual probability.

Nothing is wrong with the theorem. It was asked to protect against every independent distribution on $[0,1]$ with the same mean, not to exploit the special low-variance structure of a Bernoulli variable with success probability 0.01.

This example is worth remembering because Hoeffding bounds are often reported numerically as though they were rough approximations to actual probabilities.

They are not.

A concentration inequality is a guarantee.

Its numerical tightness depends on how much information the theorem uses.

Bernstein adds variance and becomes dramatically sharper

Suppose independent centred variables satisfy

almost surely, and let

A standard Bernstein inequality gives

For the empirical mean of independent identically distributed variables with variance

and centred deviations bounded by $M$,

The exponent has two regimes.

For small deviations,

the variance term dominates and the exponent behaves like

This is Gaussian-like concentration.

For large deviations, the linear term in $\varepsilon$ matters and the exponent behaves more like

The tail transitions from quadratic to approximately linear exponential decay.

Return to

The variance is

For the centred Bernoulli deviation, we may use

At

Bernstein gives

Numerically,

Compare the three numbers:

Quantity	Probability / upper bound
Exact binomial probability	$2.06\times10^{-7}$
Bernstein	$5.71\times10^{-6}$
Hoeffding	$4.49\times10^{-1}$

Using one additional piece of information, the variance, improves the bound by almost five orders of magnitude.

The true probability is still smaller than Bernstein's guarantee by a factor of about 28.

There is more distributional information left to use.

The Bernoulli Chernoff bound recovers the correct large-deviation geometry

For Bernoulli variables, the exact moment-generating function is known.

If

then

For

independence gives

The Chernoff bound for

with

is

Optimizing yields

where

is the Bernoulli Kullback-Leibler divergence.

For

we have

Therefore,

The comparison is now:

Quantity	Probability / upper bound
Exact binomial probability	$2.06\times10^{-7}$
KL-Chernoff	$1.92\times10^{-6}$
Bernstein	$5.71\times10^{-6}$
Hoeffding	$4.49\times10^{-1}$

The Chernoff exponent is still not exact at finite $n$, but it has the correct large-deviation rate.

For fixed

the binomial tail behaves exponentially like

up to subexponential factors under standard large-deviation asymptotics.

The relative entropy

is not an arbitrary algebraic artifact. It is the natural cost of forcing the empirical Bernoulli rate away from its true value.

This is the bridge between concentration inequalities and large-deviation theory.

Hoeffding, Bernstein and Chernoff use different information

The rare-Bernoulli example can be summarized conceptually.

Hoeffding uses:

Bernstein uses:

and

The Bernoulli Chernoff bound uses the exact mgf,

The bounds improve because the assumptions become more informative.

This gives a general rule for concentration arguments:

Use the weakest inequality that still exploits the strongest information you can justify.

A variance-sensitive bound is preferable to a range-only bound when the variance is known or estimable reliably.

An exact Chernoff calculation is preferable when the distributional form is credible.

A distribution-free bound remains valuable when those stronger assumptions would be questionable.

Sharpness is not free.

It comes from assumptions.

Sub-Gaussian variables generalize Gaussian-type concentration

A centred random variable $X$ is called sub-Gaussian if there exists a scale parameter

such that

for every

Applying the Chernoff method gives

A standard normal variable has this form exactly with

Bounded centred random variables are sub-Gaussian with an appropriate proxy variance because of Hoeffding's lemma.

If independent centred variables

are sub-Gaussian with parameters

then their sum is sub-Gaussian with parameter

Indeed,

and therefore

This closure under sums explains why sub-Gaussian variables are so central in high-dimensional probability.

They behave like Gaussian variables at the level of tails even when their exact distributions are not Gaussian.

The terminology should still be used carefully. The parameter

is often a variance proxy rather than the actual variance.

A random variable can have

while the mgf requires the larger scale for a valid global bound.

Sub-exponential variables explain the Bernstein shape

Some variables have tails heavier than Gaussian but still possess exponential moments near zero.

A centred variable is commonly called sub-exponential if its mgf satisfies a bound of the form

for

The restriction on $\lambda$ changes the optimized tail.

One obtains a bound of the schematic form

For moderate deviations, the quadratic term dominates and the behaviour is Gaussian-like.

For large deviations, the linear term dominates.

This is the same two-regime geometry visible in Bernstein's inequality.

The terminology can be confusing because "sub-exponential" does not mean slower than every exponential tail. It refers to a class whose tails are controlled by exponential-type decay and whose sums satisfy Bernstein-style concentration.

Products of sub-Gaussian variables often become sub-exponential.

This matters in covariance estimation. Even when coordinates are sub-Gaussian, products such as

have heavier tails, so concentration of sample covariances naturally uses sub-exponential tools rather than the same sub-Gaussian inequality applied blindly.

Maxima introduce logarithms through the union bound

Suppose

are centred sub-Gaussian variables with common parameter

For any

the union bound gives

Therefore,

To make this probability at most

choose

The maximum therefore grows on the scale

rather than linearly with the number of coordinates.

This simple calculation appears throughout high-dimensional statistics.

If we inspect ten thousand noisy features, some large-looking feature is expected purely because there are many opportunities for fluctuation.

The logarithm enters because the tail probability for one coordinate decays exponentially while the number of opportunities grows multiplicatively.

The union bound can be loose when variables are strongly dependent.

Its value is that it requires no dependence assumptions at all.

More refined tools, including Gaussian comparison inequalities, chaining and entropy methods, exploit dependence and metric structure to obtain sharper bounds for suprema.

The elementary union-bound calculation already reveals the basic trade-off between tail decay and multiplicity.

Bounded differences control functions, not only sums

Concentration is not limited to averages.

Let

be independent, and consider a function

Suppose changing only coordinate $i$ can alter the function by at most

Formally, for input vectors differing only in coordinate $i$,

McDiarmid's bounded-difference inequality gives

This looks like Hoeffding because it is a functional extension of the same bounded-difference geometry.

For the sample mean of $[0,1]$ variables,

changing one observation can change the mean by at most

Then

and McDiarmid recovers the Hoeffding-type bound

The functional form is much broader.

If one observation changes a statistic only slightly, the statistic can concentrate even when its exact distribution is difficult to compute.

This idea underlies algorithmic stability arguments, random graph functionals, bounded-loss empirical processes and many randomized combinatorial quantities.

Again, the sensitivity constants

are part of the model.

A statistic dominated by one observation has weak bounded-difference concentration.

A statistic averaging many small influences can concentrate strongly.

Independence can be weakened through martingale concentration

Real data are often sequential or dependent.

The simplest concentration inequalities assume independence because exponential moments factor cleanly. Dependence does not make concentration impossible, but the structure has to be replaced by something else.

Let

be a martingale with bounded increments,

almost surely.

Azuma-Hoeffding gives

The role formerly played by independent summands is now played by martingale differences.

This is useful when observations arrive adaptively but conditional expectations remain controlled.

Freedman's inequality adds a variance process and is the martingale analogue of Bernstein-style concentration. Roughly, if increments are bounded and predictable quadratic variation is small, deviations can be bounded more sharply than Azuma's range-only inequality.

The pattern is the same as before:

• bounded increments give a distribution-free guarantee;
• conditional variance gives a sharper guarantee;
• richer process information can sharpen it further.

Sequential dependence therefore changes the technical machinery without changing the underlying logic.

Concentration and the central limit theorem answer different questions

The central limit theorem says that for iid variables with finite variance,

This gives an asymptotic approximation to the distribution of fluctuations on the scale

Concentration inequalities provide finite-sample upper bounds, often valid uniformly over classes of distributions.

Neither dominates the other.

For moderate sample sizes and ordinary deviations, a normal approximation can be far sharper numerically than Hoeffding.

For a bounded variable with unknown distribution, Hoeffding gives a rigorous guarantee where a Gaussian approximation may not be justified.

For rare deviations that move farther from the mean as $n$ grows, large-deviation theory becomes more natural than the ordinary CLT.

The scales differ.

A fixed standardized deviation,

belongs to the CLT regime.

A fixed absolute deviation,

for constant

becomes exponentially rare in $n$ and belongs naturally to concentration and large-deviation analysis.

This is why the binomial probability

with true

has an exponent involving

The deviation is not shrinking with

It is a large-deviation event.

Using a CLT formula outside its natural scale can be inaccurate even when $n$ is large.

Sample complexity formulas are guarantees, not forecasts

Hoeffding's inequality can be inverted.

For independent

we want

It is sufficient that

Solving for

gives

This looks like a sample-size formula.

It is a worst-case sufficient sample size over all distributions supported on

It should not be interpreted as the actual sample size required for a particular low-variance distribution.

Suppose

and

Hoeffding requires

If the underlying Bernoulli probability is only 0.01, variance-sensitive calculations can require substantially fewer observations for some one-sided questions.

The distinction is the same one that appeared in the rare-event example.

Distribution-free robustness costs sharpness.

When a sample-size argument is based on a concentration inequality, the assumptions and worst-case nature of the guarantee should be stated.

Otherwise a conservative theorem can be mistaken for a data-generating prediction.

Heavy tails can break the usual concentration picture

Exponential concentration depends on exponential moments or comparable tail control.

If the data are heavy-tailed enough, the mgf may not exist for any positive

Then the Chernoff machinery cannot even begin.

A Pareto-distributed variable can have a finite mean and infinite variance.

For such variables, the ordinary sample mean can be dominated by rare extreme observations, and sub-Gaussian confidence widths are unjustified.

This does not mean finite-sample inference is impossible.

Robust estimators can restore concentration under weaker moment assumptions.

Median-of-means procedures split observations into groups, compute the mean within each group, and take the median of those means.

Under finite variance, such estimators can achieve sub-Gaussian-type deviation guarantees up to constants without requiring the original observations themselves to be sub-Gaussian.

Catoni-type estimators use robust influence functions to control the effect of extremes.

Truncation and winsorization can also produce concentration at the cost of bias.

The lesson is broader than the specific methods.

Concentration belongs to an estimator-plus-assumption pair.

If ordinary averages do not concentrate under the available tail assumptions, one can sometimes redesign the estimator rather than pretending the assumptions are stronger.

A probability bound should be matched to the information actually available

The rare-Bernoulli example provides a compact hierarchy.

The exact probability was

Hoeffding knew only the range and returned

Bernstein also knew the variance and returned

The Bernoulli Chernoff bound knew the exact mgf and returned

Every bound was correct.

Their usefulness differed by more than five orders of magnitude.

This is the central practical lesson of concentration inequalities.

A theorem is not useful merely because it is valid.

It should exploit the information one can justify and no more.

If only boundedness is credible, Hoeffding is powerful because it makes almost no distributional assumptions.

If variance is reliably known or estimable, Bernstein can be far better.

If the exact model is justified, a distribution-specific Chernoff bound or exact calculation can be sharper again.

If tails are heavy, redesigning the estimator can be more honest than invoking an exponential bound that does not apply.

If data are dependent, martingale, mixing or process-specific concentration should replace iid arguments.

The same discipline applies when concentration is used inside more elaborate mathematics. Generalization bounds, random matrix theory, compressed sensing, online learning and high-dimensional statistics all rely on concentration. Their final guarantees are only as meaningful as the assumptions behind the tail bounds they inherit.

The law of large numbers tells us that randomness averages out.

Concentration inequalities quantify how quickly that happens and how unlikely it is to fail by a specified amount.

The answer depends on what we know about the randomness.

References

Bernstein, S. N. (1924). On a modification of Chebyshev's inequality and of the error formula of Laplace. Annals of the Scientific Institute Sav. Ukraine, Sect. Math., 1, 38–49.

Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press.

Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4), 493–507.

Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30.

McDiarmid, C. (1989). On the method of bounded differences. In Surveys in Combinatorics. Cambridge University Press.

Petrov, V. V. (1995). Limit Theorems of Probability Theory. Oxford University Press.

Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.

Wainwright, M. J. (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press.