Markov's inequality

Theorem

Markov's inequality

T-037Home MU-106Threads chance

Statement

Let \( (\Omega, \mathcal{F}, \mathbb{P}) \) be a probability space and let \( X : \Omega \to \mathbb{R} \) be a random variable (i.e. \( \mathcal{F} \)-measurable) with \( X \geq 0 \) almost surely. Then for every real \( a \gt 0 \), \[ \mathbb{P}(X \geq a) \;\leq\; \frac{\mathbb{E}[X]}{a}. \] Here \( \mathbb{E}[X] \in [0, \infty] \) is the (always defined) expectation of the non-negative random variable \( X \); the inequality is read as trivially true when \( \mathbb{E}[X] = \infty \). No integrability, independence, or distributional assumption is required beyond non-negativity and measurability.

Why it matters

Markov's inequality is the primal tail bound: it converts knowledge of a single number, the mean, into control of the entire upper tail of a non-negative random variable. It is the weakest inequality in the concentration hierarchy, but every stronger one — Chebyshev, Chernoff, Hoeffding, Bernstein — is obtained by applying Markov's inequality to a cleverly transformed variable. Learning where the transformation enters is learning how concentration of measure works.

It is also the engine of the first moment method in probabilistic combinatorics and the workhorse behind convergence-in-measure arguments in analysis: statements of the form "if the integral is small, the function cannot be large on a large set" are all Markov's inequality in disguise.

Hypotheses

Hypothesis.\( X \geq 0 \) almost surely. Without it the inequality fails outright: take \( X = -10 \) with probability \( \tfrac{1}{2} \) and \( X = 2 \) with probability \( \tfrac{1}{2} \). Then \( \mathbb{E}[X] = -4 \), so the claimed bound for \( a = 2 \) would be \( \mathbb{P}(X \geq 2) \leq -2 \), yet \( \mathbb{P}(X \geq 2) = \tfrac{1}{2} \). Negative mass below zero subsidises the mean without shrinking the upper tail.

Hypothesis.\( a \gt 0 \). For \( a = 0 \) the right-hand side is undefined (division by zero), and the natural candidate statement \( \mathbb{P}(X \geq 0) \leq \) anything below \( 1 \) is false since \( \mathbb{P}(X \geq 0) = 1 \). For \( a \lt 0 \) the left side is \( 1 \) while the right side \( \mathbb{E}[X]/a \leq 0 \) whenever \( \mathbb{E}[X] \geq 0 \): the inequality reverses.

Hypothesis.\( X \) is \( \mathcal{F} \)-measurable. Measurability is what makes both sides meaningful: the event \( \{X \geq a\} = X^{-1}([a,\infty)) \) must lie in \( \mathcal{F} \) for \( \mathbb{P}(X \geq a) \) to be defined, and \( \mathbb{E}[X] \) is the Lebesgue integral of \( X \), defined only for measurable functions. If one works with a non-measurable function on \( ([0,1], \mathcal{B}, \lambda) \) — e.g. the indicator of a Vitali set — neither side of the inequality exists. Note that integrability is not assumed: for non-negative measurable \( X \) the integral always exists in \( [0,\infty] \), and if \( \mathbb{E}[X] = \infty \) the inequality holds vacuously.

Proof

Fix \( a \gt 0 \) and set \( A := \{ \omega \in \Omega : X(\omega) \geq a \} \). Then \( A \in \mathcal{F} \), so the indicator \( \mathbf{1}_A \) is a random variable.

\( A = X^{-1}([a, \infty)) \) is the preimage of a Borel set under the measurable map \( X \), hence lies in \( \mathcal{F} \) by the definition of measurability. Indicators of measurable sets are measurable. A

Pointwise (for \( \mathbb{P} \)-almost every \( \omega \)): \[ a \, \mathbf{1}_A(\omega) \;\leq\; X(\omega). \]

Case split — this is the key idea of the whole proof. If \( \omega \in A \), the left side is \( a \) and the right side is \( X(\omega) \geq a \) by definition of \( A \). If \( \omega \notin A \), the left side is \( 0 \) and the right side is \( X(\omega) \geq 0 \), using the hypothesis \( X \geq 0 \) a.s. (this is the only place non-negativity is used; the exceptional null set where \( X \lt 0 \) is absorbed into "almost every"). B

\[ \mathbb{E}\!\left[ a \, \mathbf{1}_A \right] \;\leq\; \mathbb{E}[X]. \]

Monotonicity of the Lebesgue integral for non-negative measurable functions: if \( 0 \leq f \leq g \) a.e., then \( \int f \, d\mathbb{P} \leq \int g \, d\mathbb{P} \). This is a lemma proved directly from the definition of the integral as \( \int g \, d\mathbb{P} = \sup \{ \int s \, d\mathbb{P} : s \text{ simple}, \ 0 \leq s \leq g \} \): every simple function below \( f \) is also below \( g \), so the supremum defining \( \int f \) ranges over a subset of the one defining \( \int g \). Both sides may equal \( +\infty \); the inequality is valid in \( [0, \infty] \). C

\[ \mathbb{E}\!\left[ a \, \mathbf{1}_A \right] \;=\; a \, \mathbb{E}[\mathbf{1}_A] \;=\; a \, \mathbb{P}(A) \;=\; a \, \mathbb{P}(X \geq a). \]

The first equality is positive homogeneity of the integral (\( \int c f \, d\mathbb{P} = c \int f \, d\mathbb{P} \) for constants \( c \geq 0 \), immediate for simple functions and preserved under the supremum). The second is the defining computation \( \mathbb{E}[\mathbf{1}_A] = \mathbb{P}(A) \) for the integral of an indicator. A

Combining Steps 3 and 4: \( a \, \mathbb{P}(X \geq a) \leq \mathbb{E}[X] \). Since \( a \gt 0 \), divide by \( a \): \[ \mathbb{P}(X \geq a) \;\leq\; \frac{\mathbb{E}[X]}{a}. \qquad \blacksquare \]

Division of an inequality by a strictly positive real preserves its direction. If \( \mathbb{E}[X] = \infty \) the conclusion is trivially true and no division is needed. A

Result

\[ X \geq 0 \ \text{a.s.}, \quad a \gt 0 \;\implies\; \mathbb{P}(X \geq a) \;\leq\; \frac{\mathbb{E}[X]}{a} \]

Reading. A non-negative quantity cannot be large too often: the chance that \( X \) is at least \( a \) times its mean is at most \( 1/a \). If average income is £30{,}000, at most one third of the population can earn £90{,}000 or more — no matter how the income is distributed.

Scope. Applies to every non-negative random variable on every probability space, with no moment, independence, or continuity assumptions; the expectation may be infinite (bound then vacuous). More generally the identical proof gives \( \mu(f \geq a) \leq \frac{1}{a} \int f \, d\mu \) for any measure \( \mu \) (not necessarily finite) and any non-negative measurable \( f \) — this is Chebyshev's inequality in the analysts' sense. The bound is informative only when \( a \gt \mathbb{E}[X] \); for \( a \leq \mathbb{E}[X] \) it says \( \mathbb{P}(X \geq a) \leq \) something \( \geq 1 \), which is vacuous.

Corollaries & converses

Strict-inequality version. \( \mathbb{P}(X \gt a) \leq \mathbb{P}(X \geq a) \leq \mathbb{E}[X]/a \) — the same bound covers the open tail for free, by monotonicity of \( \mathbb{P} \).
Chebyshev's inequality. Apply Markov to \( (Y - \mathbb{E}[Y])^2 \geq 0 \): for \( Y \) with finite variance and \( k \gt 0 \), \( \mathbb{P}(|Y - \mathbb{E}[Y]| \geq k) = \mathbb{P}((Y - \mathbb{E}[Y])^2 \geq k^2) \leq \mathrm{Var}(Y)/k^2 \).
Generalised Markov. If \( \varphi : [0,\infty) \to [0,\infty) \) is non-decreasing and \( \varphi(a) \gt 0 \), then \( \mathbb{P}(X \geq a) \leq \mathbb{E}[\varphi(X)] / \varphi(a) \), since \( \{X \geq a\} \subseteq \{\varphi(X) \geq \varphi(a)\} \). Taking \( \varphi(x) = e^{\lambda x} \) yields the Chernoff bound \( \mathbb{P}(X \geq a) \leq e^{-\lambda a} \, \mathbb{E}[e^{\lambda X}] \) for every \( \lambda \gt 0 \).
First moment method. If \( N \) is a non-negative integer-valued variable, \( \mathbb{P}(N \geq 1) \leq \mathbb{E}[N] \) — the standard tool for showing a random structure a.s. contains no copies of some object when the expected count tends to \( 0 \).
Almost-sure vanishing. If \( X \geq 0 \) and \( \mathbb{E}[X] = 0 \), then \( \mathbb{P}(X \geq 1/n) = 0 \) for all \( n \in \mathbb{N} \), so \( \mathbb{P}(X \gt 0) = \mathbb{P}\!\left( \bigcup_{n} \{X \geq 1/n\} \right) = 0 \): a non-negative variable with zero mean is zero a.s.
Converse fails. Knowing \( \mathbb{P}(X \geq a) \leq C/a \) for all \( a \gt 0 \) does not imply \( \mathbb{E}[X] \leq C \), nor even \( \mathbb{E}[X] \lt \infty \). Counterexample: the Pareto variable with \( \mathbb{P}(X \geq a) = 1/a \) for \( a \geq 1 \) satisfies the tail bound with \( C = 1 \), yet \( \mathbb{E}[X] = 1 + \int_1^\infty \frac{da}{a} = \infty \). (See Problem 5.)
Equality case. For fixed \( a \gt 0 \) and \( \mathbb{E}[X] \lt \infty \), equality holds iff \( X \in \{0, a\} \) almost surely — the two-point distribution is extremal, which is why Markov cannot be improved without further information. (See Problem 3.)

Fails without

Drop \( X \geq 0 \): let \( X = -10 \) or \( 2 \), each with probability \( \tfrac{1}{2} \). Then \( \mathbb{E}[X] = -4 \) and \( \mathbb{E}[X]/2 = -2 \), but \( \mathbb{P}(X \geq 2) = \tfrac{1}{2} \gt -2 \) — the "bound" is negative while the probability is not. Even a mean-zero example breaks it: \( X = \pm 1 \) equiprobable gives \( \mathbb{P}(X \geq 1) = \tfrac{1}{2} \) while \( \mathbb{E}[X]/1 = 0 \).
Drop \( a \gt 0 \): take any \( X \geq 0 \) with \( \mathbb{E}[X] = 1 \) and \( a = -1 \). Then \( \mathbb{P}(X \geq -1) = 1 \) but \( \mathbb{E}[X]/a = -1 \), so the inequality \( 1 \leq -1 \) is false. At \( a = 0 \) the statement is not even well-formed.
Replace mean by median (mis-generalisation): the analogous claim \( \mathbb{P}(X \geq a) \leq m/a \) with \( m \) the median is false: \( X = 0 \) w.p. \( 0.6 \), \( X = 100 \) w.p. \( 0.4 \) has median \( 0 \), yet \( \mathbb{P}(X \geq 100) = 0.4 \gt 0 \). Only the mean carries this tail information.

Common errors

Applying it to signed variables. Writing \( \mathbb{P}(Y \geq a) \leq \mathbb{E}[Y]/a \) for a \( Y \) that can be negative. The correct move is \( \mathbb{P}(|Y| \geq a) \leq \mathbb{E}[|Y|]/a \), and note this bounds the two-sided tail, not \( \mathbb{P}(Y \geq a) \) alone.
Using it below the mean. Quoting \( \mathbb{P}(X \geq a) \leq \mathbb{E}[X]/a \) when \( a \leq \mathbb{E}[X] \) and then "concluding" something: the bound exceeds \( 1 \) there and carries no information.
Expecting a lower bound. Markov only bounds tails from above; it says nothing about how small \( \mathbb{P}(X \geq a) \) can be. Lower bounds need different tools (e.g. the Paley–Zygmund inequality).
Believing the bound is tight for nice distributions. For \( X \sim \mathrm{Exp}(1) \), Markov gives \( \mathbb{P}(X \geq a) \leq 1/a \) while the truth is \( e^{-a} \) — exponentially smaller. Tightness holds only for the two-point extremal distribution.
Confusing \( \mathbb{P}(X \geq a) \) with \( \mathbb{P}(X \geq a\,\mathbb{E}[X]) \). The scale-free form is \( \mathbb{P}(X \geq a\,\mathbb{E}[X]) \leq 1/a \) (for \( 0 \lt \mathbb{E}[X] \lt \infty \)); mixing up the two forms produces bounds off by a factor of the mean.
Forgetting the a.s. in the hypothesis. \( X \geq 0 \) is only needed almost surely; conversely, verifying \( X(\omega) \geq 0 \) for "typical" \( \omega \) while a set of positive probability goes negative invalidates the proof at Step 2.

Discussion

The name is a historical accident of the best kind. The inequality appears in the work of Pafnuty Chebyshev (and, earlier still, in Irénée-Jules Bienaymé's 1853 memoir), while Andrei Markov — Chebyshev's student — stated and used the first-moment form systematically in his 1884 doctoral work and his textbook. Russian literature often calls the first-moment bound Chebyshev's first inequality and the variance bound his second; Western usage settled on "Markov" for the mean version and "Chebyshev" for the variance version. The mathematics is indifferent to the labels: Chebyshev's inequality is Markov's inequality applied to \( (Y - \mathbb{E}[Y])^2 \).

Conceptually, Markov's inequality is a statement about the impossibility of hiding mass. The mean is an integral, and an integral is a mass budget: if \( X \geq a \) on a set of probability \( p \), that set alone contributes at least \( ap \) to \( \mathbb{E}[X] \), and non-negativity guarantees the rest of the space cannot contribute negatively to cancel it. This "budget" reading explains both why non-negativity is essential and why the extremal distribution puts all its mass at \( 0 \) and \( a \): any mass strictly between \( 0 \) and \( a \), or above \( a \), wastes budget without helping the tail.

Its true power is as a transfer principle. Markov is weak on any fixed variable, but it is an equality-shaped funnel through which every moment or exponential-moment estimate becomes a tail estimate: apply it to \( |X|^p \) to get \( \mathbb{P}(|X| \geq a) \leq \mathbb{E}|X|^p / a^p \), optimise over \( p \); apply it to \( e^{\lambda X} \) and optimise over \( \lambda \gt 0 \) to get Chernoff bounds and, at scale, the whole large-deviations machinery (Cramér's theorem is Chernoff plus a matching lower bound). In probabilistic combinatorics the case \( a = 1 \) for counting variables — the first moment method — is the standard way to prove thresholds: Erdős-style non-existence arguments are Markov's inequality plus a computation of an expected count.

In its measure-theoretic form \( \mu(\{f \geq a\}) \leq a^{-1} \int f \, d\mu \), valid for arbitrary measures, the inequality is a pillar of real analysis. It shows that an \( L^1 \) function is finite a.e. (let \( a \to \infty \)), that \( L^p \) convergence implies convergence in measure (\( \mu(|f_n - f| \geq \varepsilon) \leq \varepsilon^{-p} \| f_n - f \|_p^p \)), and it defines the weak \( L^p \) spaces \( L^{p,\infty} \) via the tail condition \( \mu(|f| \geq a) \leq C^p a^{-p} \), the natural home of the Hardy–Littlewood maximal function through weak-type \( (1,1) \) bounds. The Pareto counterexample above is precisely the statement that \( L^{1,\infty} \supsetneq L^1 \): the inclusion given by Markov's inequality is strict. Even the Borel–Cantelli lemma's quantitative cousin — \( \sum_n \mathbb{P}(X_n \geq a) \lt \infty \) whenever \( \sum_n \mathbb{E}[X_n] \lt \infty \) — is Markov summed over \( n \).

Common misconceptions. Markov's inequality is not "crude because it ignores the distribution" — it is exactly as strong as possible given only the mean, since the two-point distribution attains it. It does not require independence of anything, does not require a density, and does not require finite variance. And it is one-directional: small mean forces small upper tail, but a small upper tail at every level does not force a small (or even finite) mean.

Worked examples

Example 1 (direct tail bound, and how far from the truth it can be). Server response time \( T \sim \mathrm{Exp}(1) \) (density \( e^{-t} \) for \( t \geq 0 \)), so \( \mathbb{E}[T] = 1 \). Bound \( \mathbb{P}(T \geq 10) \) by Markov and compare with the exact value.

\( T \geq 0 \) a.s. and \( \mathbb{E}[T] = \int_0^\infty t e^{-t} \, dt = 1 \lt \infty \).

Hypotheses of Markov's inequality verified: non-negativity from the support of the exponential distribution, and the mean computed by integration by parts. A

\[ \mathbb{P}(T \geq 10) \;\leq\; \frac{\mathbb{E}[T]}{10} \;=\; \frac{1}{10}. \]

Markov's inequality with \( a = 10 \gt 0 \). A

Exact value: \( \mathbb{P}(T \geq 10) = \int_{10}^\infty e^{-t} \, dt = e^{-10} \approx 4.5 \times 10^{-5} \).

Direct integration of the exponential density; shows the Markov bound \( 0.1 \) is valid but loose by a factor of roughly \( 2200 \) — Markov uses only the mean, and the exponential tail decays far faster than any distribution-free bound can certify. B

\[ \mathbb{P}(T \geq 10) \;\leq\; \tfrac{1}{10}, \qquad \text{exact value } e^{-10} \approx 4.5 \times 10^{-5} \]

Reading. With no knowledge beyond the mean, one-in-ten is the best guarantee available; the gap to \( e^{-10} \) is the price of using only one moment.

Scope. The bound \( 1/10 \) holds for every non-negative variable of mean \( 1 \), and is attained by the variable taking value \( 10 \) w.p. \( \tfrac{1}{10} \) and \( 0 \) otherwise.

Example 2 (bootstrapping: deriving and using Chebyshev). Let \( Y \) be a random variable with \( \mathbb{E}[Y] = 10 \) and \( \mathrm{Var}(Y) = 4 \). Bound \( \mathbb{P}(|Y - 10| \geq 5) \) — note Markov cannot be applied to \( Y \) directly, since \( Y \) may take negative values and the event is two-sided.

Set \( Z := (Y - 10)^2 \). Then \( Z \geq 0 \) everywhere and \( \mathbb{E}[Z] = \mathrm{Var}(Y) = 4 \).

A square is non-negative, and \( \mathbb{E}[(Y - \mathbb{E}Y)^2] \) is the definition of variance. This transformation is the standard trick for converting a two-sided deviation event into a one-sided event for a non-negative variable. B

\[ \{ |Y - 10| \geq 5 \} \;=\; \{ (Y-10)^2 \geq 25 \} \;=\; \{ Z \geq 25 \}. \]

The map \( t \mapsto t^2 \) is strictly increasing on \( [0, \infty) \), so for \( t, c \geq 0 \): \( t \geq c \iff t^2 \geq c^2 \). Applied with \( t = |Y - 10| \), \( c = 5 \). Equality of events, not just inclusion. A

\[ \mathbb{P}(|Y - 10| \geq 5) \;=\; \mathbb{P}(Z \geq 25) \;\leq\; \frac{\mathbb{E}[Z]}{25} \;=\; \frac{4}{25}. \]

Markov's inequality applied to the non-negative variable \( Z \) with \( a = 25 \gt 0 \). This is Chebyshev's inequality, derived on the spot. B

\[ \mathbb{P}(|Y - 10| \geq 5) \;\leq\; \frac{4}{25} = 0.16 \]

Reading. A variable with standard deviation \( 2 \) strays \( 2.5 \) standard deviations from its mean at most \( 16\% \) of the time — regardless of its distribution.

Scope. Needs only finite variance; no shape, symmetry, or support assumptions on \( Y \). The route Markov \( \to \) Chebyshev shown here is fully general.

Problems

Let \( X \geq 0 \) with \( \mathbb{E}[X] = 3 \). Give the best distribution-free upper bound on \( \mathbb{P}(X \geq 12) \), and exhibit a distribution attaining it.
Solution
By Markov's inequality with \( a = 12 \): \( \mathbb{P}(X \geq 12) \leq \frac{3}{12} = \frac{1}{4} \). Attained by the two-point distribution \( \mathbb{P}(X = 12) = \tfrac{1}{4} \), \( \mathbb{P}(X = 0) = \tfrac{3}{4} \): indeed \( \mathbb{E}[X] = 12 \cdot \tfrac{1}{4} = 3 \) and \( \mathbb{P}(X \geq 12) = \tfrac{1}{4} \) exactly. Hence \( \tfrac{1}{4} \) is the best bound obtainable from the mean alone: no smaller constant works for every distribution with mean \( 3 \).
Let \( X \geq 0 \) a.s. and \( a \gt 0 \). (i) Prove the strict-tail version \( \mathbb{P}(X \gt a) \leq \mathbb{E}[X]/a \). (ii) Show that for \( 0 \lt a \leq \mathbb{E}[X] \lt \infty \) Markov's inequality carries no information, i.e. the bound is \( \geq 1 \) and is met with slack by some distribution.
Solution
(i) \( \{X \gt a\} \subseteq \{X \geq a\} \), so by monotonicity of measures \( \mathbb{P}(X \gt a) \leq \mathbb{P}(X \geq a) \leq \mathbb{E}[X]/a \), the last step being Markov. (Alternatively, run the original proof with \( A' = \{X \gt a\} \): the pointwise bound \( a \mathbf{1}_{A'} \leq X \) still holds, since on \( A' \) we have \( X \gt a \), which implies \( X \geq a \).) (ii) If \( a \leq \mathbb{E}[X] \) then \( \mathbb{E}[X]/a \geq 1 \geq \mathbb{P}(X \geq a) \) holds for trivial reasons — every probability is at most \( 1 \) — so the inequality adds nothing. For slack, take \( X \) constant equal to \( \mathbb{E}[X] = m \) and \( a = m/2 \): the bound reads \( \mathbb{P}(X \geq m/2) \leq 2 \), while the truth is \( 1 \).
(Equality case.) Let \( X \geq 0 \) a.s., \( a \gt 0 \), and \( \mathbb{E}[X] \lt \infty \). Prove that \( \mathbb{P}(X \geq a) = \mathbb{E}[X]/a \) if and only if \( \mathbb{P}(X \in \{0, a\}) = 1 \).
Solution
Write \( A = \{X \geq a\} \). The proof of Markov shows \( \mathbb{E}[X] - a\mathbb{P}(A) = \mathbb{E}[X - a\mathbf{1}_A] \), and \( D := X - a\mathbf{1}_A \geq 0 \) a.s. (Step 2). Equality in Markov means \( \mathbb{E}[D] = 0 \) with \( D \geq 0 \) a.s., which forces \( D = 0 \) a.s. (a non-negative variable with zero mean vanishes a.s. — itself a corollary of Markov: \( \mathbb{P}(D \geq 1/n) \leq n\,\mathbb{E}[D] = 0 \) for every \( n \in \mathbb{N} \), and \( \{D \gt 0\} = \bigcup_n \{D \geq 1/n\} \) has probability \( 0 \) by countable subadditivity). Now \( D = 0 \) a.s. says: on \( A \), \( X = a \) a.s.; off \( A \), \( X = 0 \) a.s. Hence \( X \in \{0, a\} \) a.s. Conversely, if \( \mathbb{P}(X = a) = p \) and \( \mathbb{P}(X = 0) = 1 - p \), then \( \mathbb{E}[X] = ap \) and \( \mathbb{P}(X \geq a) = p = \mathbb{E}[X]/a \). \( \blacksquare \)
(Chernoff via Markov.) Let \( X \) be any random variable and \( a \in \mathbb{R} \). (i) Show that for every \( \lambda \gt 0 \), \( \mathbb{P}(X \geq a) \leq e^{-\lambda a} \, \mathbb{E}[e^{\lambda X}] \). (ii) For \( X \sim \mathrm{Exp}(1) \) and \( a \gt 1 \), optimise the bound over \( \lambda \in (0, 1) \) and compare with the exact tail \( e^{-a} \).
Solution
(i) Fix \( \lambda \gt 0 \). Since \( t \mapsto e^{\lambda t} \) is strictly increasing, \( \{X \geq a\} = \{ e^{\lambda X} \geq e^{\lambda a} \} \). The variable \( e^{\lambda X} \) is non-negative (an exponential of a real is positive), so Markov applies with threshold \( e^{\lambda a} \gt 0 \): \( \mathbb{P}(X \geq a) = \mathbb{P}(e^{\lambda X} \geq e^{\lambda a}) \leq e^{-\lambda a} \, \mathbb{E}[e^{\lambda X}] \). Note \( X \) itself need not be non-negative — the transformation manufactures non-negativity. (ii) For \( X \sim \mathrm{Exp}(1) \) and \( 0 \lt \lambda \lt 1 \), \( \mathbb{E}[e^{\lambda X}] = \int_0^\infty e^{\lambda t} e^{-t} dt = \frac{1}{1 - \lambda} \). The bound is \( g(\lambda) = \frac{e^{-\lambda a}}{1 - \lambda} \). Minimise \( \log g(\lambda) = -\lambda a - \log(1 - \lambda) \): derivative \( -a + \frac{1}{1-\lambda} = 0 \) gives \( \lambda^\ast = 1 - \frac{1}{a} \in (0,1) \) since \( a \gt 1 \); the second derivative \( \frac{1}{(1-\lambda)^2} \gt 0 \) confirms a minimum. Then \( g(\lambda^\ast) = \frac{e^{-(1 - 1/a) a}}{1/a} = a\, e^{1 - a} = ea \cdot e^{-a} \). So the optimised Chernoff bound is \( \mathbb{P}(X \geq a) \leq e a \, e^{-a} \): it captures the exact exponential rate \( e^{-a} \), losing only the polynomial factor \( ea \) — vastly sharper than plain Markov's \( 1/a \).
(Failure of the converse.) Let \( X \) have the Pareto distribution \( \mathbb{P}(X \geq a) = \frac{1}{a} \) for \( a \geq 1 \) (so \( \mathbb{P}(X \geq a) = 1 \) for \( a \lt 1 \); density \( f(x) = x^{-2} \) on \( [1, \infty) \)). (i) Verify that \( X \) satisfies the Markov-type tail bound \( \mathbb{P}(X \geq a) \leq \frac{1}{a} \) for all \( a \gt 0 \). (ii) Show \( \mathbb{E}[X] = \infty \). (iii) Conclude that no converse to Markov's inequality holds: uniform \( C/a \) tail decay does not imply a finite mean.
Solution
(i) For \( a \geq 1 \), \( \mathbb{P}(X \geq a) = 1/a \leq 1/a \) with equality. For \( 0 \lt a \lt 1 \), \( \mathbb{P}(X \geq a) = 1 \leq 1/a \) since \( 1/a \gt 1 \). So the bound holds with \( C = 1 \) at every level \( a \gt 0 \). (ii) Using the tail formula for non-negative variables, \( \mathbb{E}[X] = \int_0^\infty \mathbb{P}(X \gt t) \, dt \) (valid in \( [0, \infty] \) by Tonelli's theorem applied to \( \mathbf{1}_{\{t \lt X\}} \)): \( \mathbb{E}[X] = \int_0^1 1 \, dt + \int_1^\infty \frac{dt}{t} = 1 + \lim_{T \to \infty} \log T = \infty \). (Equivalently, \( \int_1^\infty x \cdot x^{-2} dx = \int_1^\infty \frac{dx}{x} \) diverges.) (iii) If a converse held — say "\( \mathbb{P}(X \geq a) \leq C/a \) for all \( a \gt 0 \) implies \( \mathbb{E}[X] \leq \psi(C) \) for some finite function \( \psi \)" — this \( X \) with \( C = 1 \) would have finite mean, contradicting (ii). Markov's funnel is strictly one-way: means control tails; tails of order exactly \( 1/a \) sit on the boundary and control nothing. In analysts' language, \( X \in L^{1, \infty} \setminus L^1 \).