Markov's Inequality

The inequality

For any non-negative random variable X with E[X] < ∞, and any a > 0:

P(X ≥ a) ≤ E[X] / a

That's it. No assumption about the shape of X's distribution. No moments above the first. Just non-negativity and a finite mean. The bound is universal but typically loose — the price of asking so little.

Three-line proof

The standard proof uses the indicator-function trick:

For X ≥ 0 and a > 0:
  a · 1[X ≥ a] ≤ X      (case split: 1[X≥a] is 0 or 1; both cases ≤ X)

Take expectations:
  a · P(X ≥ a) ≤ E[X]

Divide by a:
  P(X ≥ a) ≤ E[X] / a   ∎

The key observation: the indicator function a · 1[X ≥ a] is a step function that equals a when X ≥ a and 0 otherwise. Since X ≥ 0 always, and X ≥ a in the "step up" region, the indicator never exceeds X itself. Expectations preserve inequalities, and division by a positive a finishes it.

Worked example — Markov is loose

Suppose X is exponential with rate 1, so E[X] = 1. Ask for P(X ≥ 10):

Markov: P(X ≥ 10) ≤ E[X]/10 = 1/10 = 10%

True value: P(X ≥ 10) = e^(-10) ≈ 0.0045%

Looseness factor: 10% / 0.0045% ≈ 2200×

Markov gives 10% but the truth is 0.0045%. That's how loose Markov can be. Why use it? Because it's the only bound that needs nothing more than the mean — distribution-free, three-line proof, every other concentration bound is built from it.

When is Markov tight?

Markov is tight when X is binary — either 0 or exactly a. Let X = a with probability p and X = 0 with probability 1 − p:

E[X] = pa
P(X ≥ a) = p

Markov says P(X ≥ a) ≤ E[X]/a = pa/a = p ✓  (equality)

So Markov's worst case is a Bernoulli scaled to {0, a}. Any spread of probability mass between 0 and a, or any mass above a, makes Markov strictly loose. The lesson: Markov only "knows" about mean, so its tightness adversary uses mass entirely at 0 or at the threshold.

Deriving Chebyshev from Markov

This is the trick that makes Markov so powerful — apply it to a clever transformation.

Want: P(|X − μ| ≥ kσ) ≤ 1/k²

Let Y = (X − μ)², which is non-negative. Apply Markov at a = k²σ²:

  P(Y ≥ k²σ²) ≤ E[Y] / (k²σ²) = σ² / (k²σ²) = 1/k²

The event {Y ≥ k²σ²} is exactly {|X − μ| ≥ kσ}. Done.

Same recipe gives Chernoff bounds: apply Markov to e^{tX} for a parameter t > 0 to be optimized. The MGF M(t) = E[e^{tX}] becomes the numerator and you get exponential decay in a.

Markov vs Chebyshev vs Chernoff vs Hoeffding

Bound	Form	Requires	Tail decay	Use when
Markov	P(X ≥ a) ≤ E[X]/a	X ≥ 0, finite mean	1/a (linear)	only mean known, X non-negative
Reverse Markov	P(X ≤ a) ≤ (b − E[X])/(b − a)	X ≤ b, a < E[X]	linear in (b − a)	bounded above, lower tail
Chebyshev	P(|X−μ| ≥ kσ) ≤ 1/k²	finite variance	1/k² (polynomial)	variance known
Cantelli	P(X−μ ≥ kσ) ≤ 1/(1+k²)	finite variance	1/k² (one-sided)	one-tail question
Chernoff	P(X ≥ a) ≤ e^{−ta}M(t)	MGF exists	e^{−Ω(a)} (exponential)	sums of indep RVs
Hoeffding	P(X̄−μ ≥ ε) ≤ e^{−2nε²/(b−a)²}	bounded i.i.d.	e^{−Ω(nε²)} (exponential)	bounded sums
Bernstein	P(X̄−μ ≥ ε) ≤ e^{−nε²/(2σ²+2bε/3)}	bounded + variance	between Chebyshev & Hoeffding	small variance, large support

The progression: each row uses one more moment or property than the row above. Markov is the foundation; everything else is Markov applied to a cleverly chosen non-negative function of X.

Reverse Markov

If X ≤ b almost surely, then for a < E[X]:

P(X ≤ a) ≤ (b − E[X]) / (b − a)

Proof: apply Markov to b − X (non-negative, mean b − E[X]) at threshold b − a. This is rarely seen in textbooks but useful when bounding lower tails of bounded variables — e.g., guaranteeing a value isn't too small.

Where Markov shows up

• Randomized algorithm analysis. If E[runtime] = T, then P(runtime > cT) ≤ 1/c. Repeat the algorithm log₂(1/δ) times and take the fastest run — failure probability ≤ δ. This is how Las Vegas algorithms get high-probability guarantees.
• Probabilistic method. To prove an object with property P exists, define X = number of objects with property P, show E[X] > 0. Markov implies P(X > 0) > 0 (in the contrapositive direction). Erdős used this to revolutionize combinatorics.
• Streaming algorithms. Median-of-means estimators bound the failure probability via Markov on individual estimates, then amplify with the median trick to exponentially small failure.
• Concentration of measure. All higher-moment bounds (Chebyshev, Chernoff, Bernstein) factor through Markov applied to (X − μ)^k, e^{tX}, or other clever transforms.
• PageRank stability. Bounding the deviation of empirical PageRank from the limit measure uses Markov on the mixing time of the Markov chain.
• Queueing theory. Little's law involves expected queue length; Markov bounds the probability of long queues even without distributional assumptions.
• Markov vs Markov chains. Markov's inequality and Markov chains are due to the same Andrey Markov, but they're separate concepts. Same man, two famous contributions.

The polynomial generalization

For any non-decreasing, non-negative function φ and any a in its range:

P(X ≥ a) ≤ E[φ(X)] / φ(a)

Set φ(x) = x → standard Markov. Set φ(x) = x² → Chebyshev for non-negative X. Set φ(x) = e^{tx} → Chernoff. Set φ(x) = (1 + x)^k → kth-moment bound. Every concentration inequality is this template with a chosen φ; the art is picking the right φ to optimize the bound.

Common pitfalls

• Forgetting non-negativity. Markov fails for variables that can be negative. Always check or shift the variable: apply Markov to X − min(X) if X is bounded below.
• Using Markov when you have more information. If you know variance, use Chebyshev; if you know the MGF, use Chernoff. Markov ignores everything past the mean.
• Tightness expectations. Markov is often 100×–10000× looser than the truth. Use only when you genuinely have no other information.
• Confusing with Markov chains. Markov's inequality is a tail bound for a single random variable. Markov chains are stochastic processes. Same name, different topic.
• Applying to a-values below the mean. Markov is vacuous when a ≤ E[X] (the bound says ≤ 1, which is always true). Useful only when a > E[X].
• Not optimizing parameters. When using Markov inside a derivation (e.g., Chernoff's e^{tX} trick), the parameter t is yours to choose — optimize it.

Historical note

Andrey Markov (1856–1922) published the inequality in 1884 as part of his probability lectures at St. Petersburg. He was a student of Pafnuty Chebyshev, who had proved the related variance inequality in 1867. So pedagogically Markov is the "simpler" foundational step, but historically Chebyshev came first; Markov extracted the simpler statement underneath. Markov went on to invent Markov chains in 1906 by analyzing letter sequences in Pushkin's "Eugene Onegin" — same name, separate fame.