Introduction to Tail and Concentration Bounds

SECTION 01Introduction to Tail and Concentration Bounds

In this chapter, we study how to bound the probability that a random variable takes an extreme value or deviates far from its mean.

Definition · Tail Probability

A tail probability measures how likely a random variable is to take an extreme value, for example:

P (X \geq t), P (X \leq - t)

A tail bound gives an upper bound on such a probability.

Definition · Concentration Inequality

A concentration inequality bounds the probability that a random variable deviates from its mean or median. A two-sided bound around the mean takes the form:

P (| X - E [X] | \geq t) \leq b (t)

Here, t is the deviation threshold and b(t) bounds the probability of a deviation of at least t.

SECTION 02Classical Bounds

Setting and Goal

Assume X ≥ 0, t > 0, and k is a positive integer with a finite kth moment. We want to bound the tail probability P(X ≥ t).

Claim 1 · Controlling Tails through Moments

One way to control a tail probability is by controlling the moments of the random variable.^[1] Controlling higher-order moments can give sharper tail bounds.^[2] Specifically,

P (X \geq t) \leq \frac{E [X^{k}]}{t^{k}}

Proof of Claim 1

If X ≥ t always holds, then Xᵏ ≥ tᵏ always holds, so E[Xᵏ] ≥ tᵏ. More generally, if X ≥ t holds with probability P(X ≥ t), then E[Xᵏ] ≥ tᵏ P(X ≥ t), because Xᵏ is at least tᵏ in those outcomes and is nonnegative in all other outcomes.

Example · Why This Contribution Is at Least tᵏ P(X ≥ t)

Imagine 100 observations, of which 10 satisfy X ≥ 5. Each of those 10 contributes at least 25 to the sum of squares, so their total contribution is at least 10 × 25 = 250. The other squares are nonnegative, so the average of all 100 squares is at least 250 / 100 = 2.5.

This illustrates the same rule: minimum contribution × proportion of outcomes. Here it is 25 × 0.1 = 2.5.

Applying this reasoning to the population expectation gives

E [X^{k}] \geq t^{k} P (X \geq t)

Dividing by tᵏ > 0 proves Claim 1:

P (X \geq t) \leq \frac{E [X^{k}]}{t^{k}}

This inequality holds deterministically under the stated assumptions; it bounds the probability of a random event.

Example · k = 2: Variance Controls Deviations

The second moment E[X²] equals the variance only when E[X] = 0. For a general X, the variance is E[(X − E[X])²]: the average squared deviation from the mean.

Apply Claim 1 to the nonnegative variable |X − E[X]| with k = 2. This gives Chebyshev’s inequality:

P (| X - E [X] | \geq t) \leq \frac{Var (X)}{t^{2}}