Why Tail-Bound Arguments Need an Audit
A tail bound is a chain of implications, not just a formula. The event must be contained in the event being bounded; the random variable to which an inequality is applied must satisfy that inequality’s assumptions; and any moment or MGF used in the calculation must exist at the value required. Even when all these conditions hold, the resulting bound may be so large that it says little.
This tutorial develops a practical audit for arguments based on Markov’s inequality, Chebyshev’s inequality, and Chernoff’s method. The aim is to separate three different diagnoses: invalid (a condition fails or a probability comparison is reversed), valid but loose (the reasoning is correct but the bound is weak), and valid and informative (the bound is correct and gives a useful numerical restriction).
The Basic Checks Behind Common Bounds
Begin with event inclusion. If \(A\subseteq B\), then every outcome in \(A\) is also in \(B\), so \(P(A)\leq P(B)\). The direction matters: a bound on \(P(B)\) can be used to bound \(P(A)\) only when \(A\subseteq B\). Reversing the inclusion reverses which probability is controlled.
Markov’s inequality requires a nonnegative random variable and a finite expectation. In its standard form, if \(Z\geq 0\) almost surely, \(E[Z]<\infty\), and \(c>0\), then \(P(Z\geq c)\leq E[Z]/c\). Chebyshev’s inequality is an application to \(Z=(X-E[X])^2\); it requires \(E[X]\) to be finite and \(\operatorname{Var}(X)<\infty\). Chernoff’s method also uses Markov’s inequality, now on an exponential transformation, so the MGF must be finite at the selected parameter.
Proof. Pointwise, \(c\,\mathbf{1}_{\{Z\geq c\}}\leq Z\), where \(\mathbf{1}_{\{Z\geq c\}}\) equals \(1\) on the event and \(0\) elsewhere. Taking expectations gives \(cP(Z\geq c)\leq E[Z]\), which proves the first inequality. For the second, \(t>0\) makes the exponential function increasing, so \(X\geq a\) implies \(e^{tX}\geq e^{ta}\). Apply the first inequality to the nonnegative random variable \(e^{tX}\) with threshold \(e^{ta}>0\). Its expectation is finite by assumption, yielding \(P(X\geq a)\leq E[e^{tX}]/e^{ta}\). This is the stated bound. \(\square\)
These results suggest an audit sequence: identify the exact event; write down the event inclusion or transformation used; check every required condition; evaluate the bound; and only then decide whether it is useful. The examples below apply that sequence to typical errors.
Worked Diagnostics
Worked Example: A Reversed Event Comparison
Let \(X\) take the value \(-2\) with probability \(0.99\) and \(2\) with probability \(0.01\). Compare the events \(\{X\geq 1\}\) and \(\{X^2\geq 1\}\). A proposed argument claims that \(P(X^2\geq 1)\leq P(X\geq 1)\).
At \(X=-2\), the event \(\{X^2\geq 1\}\) occurs, but \(\{X\geq 1\}\) does not. At \(X=2\), both events occur. Thus \(\{X\geq 1\}\subseteq\{X^2\geq 1\}\), not the reverse. Directly, $$ P(X\geq 1)=0.01,\qquad P(X^2\geq 1)=0.99+0.01=1. $$
The proposed inequality would say \(1\leq 0.01\), so it is false. The valid comparison is \(P(X\geq 1)\leq P(X^2\geq 1)\). Replacing a one-sided event by a two-sided event can support an upper bound, but it may enlarge the event substantially. In this example, the enlarged event has probability \(1\), so the comparison alone gives no useful tail estimate.
Worked Example: Applying Markov to a Negative Variable
Let \(X\sim\operatorname{Bernoulli}(1/2)\), and put \(Y=X-E[X]=X-1/2\). A proposed argument applies Markov directly to \(Y\) and claims $$ P(Y\geq 0.4)\leq \frac{E[Y]}{0.4}=0. $$
Here \(Y=1/2\) with probability \(1/2\) and \(Y=-1/2\) with probability \(1/2\). Therefore \(E[Y]=0\), but \(Y\) is not nonnegative almost surely, and $$ P(Y\geq 0.4)=P(Y=1/2)=\frac12. $$ The claimed zero upper bound is false. The failed step is not an arithmetic error: Markov’s inequality does not apply to a variable that can be negative.
A valid transformation for a one-sided upper tail is \(Y_+=\max(Y,0)\), which is nonnegative. Since \(Y\geq 0.4\) implies \(Y_+\geq 0.4\), Markov gives $$ P(Y\geq 0.4)\leq \frac{E[Y_+]}{0.4} =\frac{(1/2)(1/2)}{0.4} =\frac{0.25}{0.4}=0.625. $$ This is valid but loose relative to the exact probability \(0.5\). The transformation repairs the assumption; it does not guarantee a sharp result.
Worked Example: Chebyshev When the Variance Is Infinite
Consider a Pareto random variable with density \(f(x)=\frac{3}{2}x^{-5/2}\) for \(x\geq 1\), and density \(0\) otherwise. A proposed calculation uses Chebyshev’s inequality around its mean.
First check the moments. Its mean is finite: $$ E[X]=\frac{3}{2}\int_1^\infty x^{-3/2}\,dx =\frac{3}{2}\left[-2x^{-1/2}\right]_1^\infty=3. $$ But its second moment diverges: $$ E[X^2]=\frac{3}{2}\int_1^\infty x^{-1/2}\,dx=\infty. $$ Consequently, \(\operatorname{Var}(X)=\infty\). Chebyshev’s inequality cannot produce a finite variance-based bound here. Substituting “infinity” into \(\operatorname{Var}(X)/t^2\) does not yield a useful upper bound; it gives no restriction beyond a quantity exceeding \(1\).
A different valid bound is available from Markov, since \(X\geq 0\) and \(E[X]=3\). For \(u\geq 1\), $$ P(X\geq u)\leq \frac{3}{u}. $$ For comparison, direct integration gives the exact tail $$ P(X\geq u)=\frac{3}{2}\int_u^\infty x^{-5/2}\,dx=u^{-3/2}. $$ At \(u=8\), Markov gives \(P(X\geq 8)\leq 3/8=0.375\), whereas the exact probability is \(8^{-3/2}=1/(16\sqrt{2})\approx 0.0442\). The Markov bound is valid but loose; Chebyshev’s inequality is unavailable because the variance is not finite.
Worked Example: A Valid but Poor Chernoff Parameter
Let \(X\) have an exponential distribution with rate \(1\), so \(M_X(t)=1/(1-t)\) for \(t<1\), and \(M_X(t)=\infty\) for \(t\geq 1\). We want to bound \(P(X\geq 2)\).
For any \(0<t<1\), the Chernoff bound is $$ P(X\geq 2)\leq g(t),\qquad g(t)=\frac{e^{-2t}}{1-t}. $$ At \(t=0.1\), $$ g(0.1)=\frac{e^{-0.2}}{0.9} \approx\frac{0.8187308}{0.9} \approx 0.9097. $$ This is a valid bound, but it is weak. Direct integration gives \(P(X\geq 2)=e^{-2}\approx 0.1353\).
The MGF domain is essential: \(t=1\) is not an admissible choice because \(M_X(1)=\infty\). To see the effect of choosing a better admissible value, minimize \(g(t)\) over \(0<t<1\). Differentiating its logarithm gives $$ \frac{d}{dt}\log g(t)=-2+\frac{1}{1-t}. $$ Setting this derivative to zero gives \(1/(1-t)=2\), hence \(t=1/2\). The derivative is negative for \(0<t<1/2\) and positive for \(1/2<t<1\), so this is the minimum. Its value is $$ g(1/2)=\frac{e^{-1}}{1/2}=\frac{2}{e}\approx 0.7358. $$ Optimization improves the bound from about \(0.9097\) to about \(0.7358\), but it remains above the exact tail. A valid domain and a valid calculation do not by themselves ensure a sharp bound.
A Compact Audit for a Tail Calculation
When reviewing a derivation, follow the dependency of each inequality rather than checking only its final line. A displayed expression can look familiar while depending on an invalid event inclusion or an unavailable expectation. The following checklist makes those dependencies explicit.
Write the event in the probability being bounded, such as \(\{X\geq a\}\) or \(\{|X-E[X]|\geq t\}\). Do not silently replace a one-sided event by a two-sided one or vice versa.
If the argument replaces the target event by another event, check the set inclusion on every outcome. An upper bound requires an event at least as large as the target event.
Markov requires a nonnegative variable with finite expectation; Chebyshev requires finite variance; a Chernoff step requires a finite MGF at the selected parameter.
Compute the numerical bound accurately. A value at least \(1\) is valid in some arguments but cannot improve on the trivial probability bound \(P(A)\leq 1\).
Two additional checks help prevent false confidence. First, an algebraic expression for an MGF may only be valid on a restricted domain; its formula must not be extended beyond that domain. Second, parameter optimization only compares admissible choices. A formal minimizer at a point where the MGF is infinite is not a valid Chernoff parameter.
Common Mistakes and Why the Distinctions Matter
- Reversing event inclusion. If \(A\subseteq B\), then \(P(A)\leq P(B)\). A bound on the larger event may control the smaller one, but not the other way around.
- Using Markov on a centered variable. A centered variable has mean zero but need not be nonnegative. Apply Markov only after choosing a nonnegative transformation and verifying its expectation.
- Assuming finite moments without checking. A finite mean does not imply a finite variance. Chebyshev’s inequality needs the latter.
- Choosing an MGF parameter outside its domain. If \(M_X(t)=\infty\), the Chernoff expression is not a finite bound, even if substitution into a formula appears to give a number.
- Calling every valid bound useful. A correct upper bound larger than \(1\), or one close to \(1\) when the tail is small, may provide little information. This is a weakness of the bound, not a logical error.
Check Your Understanding
For each question, identify the assumption or comparison that needs to be checked before accepting the claimed bound.
- If \(A\subseteq B\), which probability is larger or equal, \(P(A)\) or \(P(B)\)? Which one can a known upper bound on \(P(B)\) control?
- A centered random variable \(Y=X-E[X]\) has \(E[Y]=0\). What additional condition is needed before Markov’s inequality can be applied directly to \(Y\)?
- A random variable has finite mean but infinite variance. Which of Markov’s and Chebyshev’s inequalities can still be applied directly, assuming the variable is nonnegative?
- If an MGF is finite only for \(t<1\), why is a Chernoff calculation at \(t=1\) invalid even when the MGF formula has a simple algebraic expression?
- Explain how a Chernoff bound can be both mathematically valid and uninformative. Give one way to improve it, if possible.