Markov, Chebyshev, and Chernoff Bounds

SECTION 01Markov, Chebyshev, and Chernoff Bounds

In the previous section, we introduced basic tail and concentration bounds to build an initial understanding. We now start with Markov’s inequality and develop several commonly used bounds, all based on the idea of controlling tails through moments that we derived earlier.

Setting

We want to bound the probability of a large value or a large deviation from the mean. The information available—such as a mean, variance, or moment generating function—determines which bound we can use.

Formulation · Markov’s Inequality

For a nonnegative random variable X with a finite mean, and any t > 0,

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

A small mean limits how often X can be large. This is the moment bound with k = 1.

Formulation · Chebyshev’s Inequality

For a random variable X with mean μ = E[X] and finite variance, and any t > 0,

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

A small variance limits the probability of a large deviation from the mean.

Claim · Both Bounds Are Sharp^[1]

Neither bound can be improved uniformly over all distributions satisfying its assumptions.

Example · A Distribution That Attains Equality

Let t > 0 and 0 < p ≤ 1. Let X equal −t, 0, and t with probabilities p/2, 1 − p, and p/2, respectively. Its mean is 0 and its variance is pt², so

P (| X | \geq t) = p = \frac{Var (X)}{t^{2}}

Chebyshev’s bound is exactly the true probability p. Any smaller bound at this same mean, variance, and threshold would fail for this distribution. Markov’s bound also attains equality: take a nonnegative variable equal to t with probability p and 0 otherwise.

SECTION 02Extensions of Markov’s Inequality

Higher-Order Moment Bounds

Chebyshev’s inequality can be extended to higher-order moments by applying Markov’s inequality to higher powers of the deviation from the mean.

Formulation · Centered Moments

For any positive integer k with E[|X − μ|ᵏ] finite, and any t > 0,

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

From Exponential Moments to the Chernoff Bound

We can also apply Markov’s inequality to functions other than polynomials.

Formulation · Chernoff Bound

Suppose X has mean μ = E[X] and a moment generating function in a neighborhood of zero: there is a b > 0 such that $ϕ (λ) = E [e^{λ (X - μ)}]$ is finite for every |λ| ≤ b.

For any t > 0 and 0 < λ ≤ b, applying Markov’s inequality to the nonnegative random variable $Y = e^{λ (X - μ)}$ gives

P (X - μ \geq t) = P (e^{λ (X - μ)} \geq e^{λ t}) \leq \frac{E [e^{λ (X - μ)}]}{e^{λ t}}

Optimizing λ to obtain the tightest bound yields the Chernoff bound:

\log P (X - μ \geq t) \leq inf_{0 < λ \leq b} {\log ϕ (λ) - λ t}

SUPPLEMENTARYMoments and Moment Generating Functions

1. Why Is It Called Moment Generating?

Start with the exponential expansion:

e^{λ X} = 1 + λ X + \frac{λ^{2} X^{2}}{2!} + \frac{λ^{3} X^{3}}{3!} + \dots

Taking expectations gives

M_{X} (λ) = 1 + λ E [X] + \frac{λ^{2}}{2!} E [X^{2}] + \frac{λ^{3}}{3!} E [X^{3}] + \dots

The moments E[X], E[X²], E[X³], … appear as coefficients in this expansion. The MGF therefore puts all these moments into one function.

2. How Do We Extract a Moment?

Differentiate the MGF and evaluate at λ = 0. For example,

M_{X}' (0) = E [X], M_{X} ″ (0) = E [X^{2}]

More generally,

{M_{X}}^{(k)} (0) = E [X^{k}]

3. Why Can It Control a Tail?

We previously used powers to amplify large values. An exponential does the same: for λ > 0, a large X produces a large $e^{λ X}$ . If $E [e^{λ X}]$ is bounded, these large values cannot occur too often. Applying Markov’s inequality to the exponential gives a tail bound, and choosing λ lets us adjust the amplification.