Engineering / Mathematics — Discrete Probability
Markov's and Chebyshev's Inequalities
Markov's and Chebyshev's inequalities, their proofs, and how they bound deviation from the mean.
Executive summary
Markov's inequality bounds the probability that a non-negative variable greatly exceeds its mean, using only the mean. Chebyshev's inequality sharpens this using the variance.
Both are weak compared with exponential bounds but require far less: Markov needs only non-negativity, Chebyshev only a finite variance and pairwise independence within sums.
Learning objectives
- State and prove both inequalities.
- Choose between them based on available information.
- Apply Chebyshev to a sum of pairwise independent variables.
01Markov's inequality
Markov's inequality
For a non-negative random variable X and any t > 0:
P(X ≥ t) ≤ E[X] / t.
Proof. E[X] ≥ E[X · 1_{X ≥ t}] ≥ t · P(X ≥ t).
The bound is tight in the worst case — a variable equal to t with probability E[X]/t and 0 otherwise achieves it — so no improvement is possible from the mean alone.
02Chebyshev's inequality
Chebyshev's inequality
For any random variable X with finite variance and any t > 0:
P(|X − E[X]| ≥ t) ≤ Var[X] / t².
Proof. Apply Markov to the non-negative variable (X − E[X])² at threshold t².
Expressed in standard deviations, the bound says the probability of being k deviations from the mean is at most 1/k². That is weak — the true figure for well-behaved distributions is exponentially small — but it holds universally.
P(|X − μ| ≥ kσ) ≤ 1/k²03Choosing between them
| Bound | Requires | Decay in t | Typical use |
|---|---|---|---|
| Markov | X ≥ 0, finite mean | 1/t | Quick crude bound; proving Chebyshev |
| Chebyshev | Finite variance | 1/t² | Sums of pairwise independent variables |
| Exponential bounds | Mutual independence, bounded terms | e^{−ct²} | Repeated-trial amplification |
The decisive practical point is the independence requirement. For a sum of n pairwise independent variables the variance is the sum of variances, so Chebyshev gives concentration within O(√n) — enough for most sampling arguments, and available from a hash family needing only logarithmic randomness.
Exponential bounds give concentration within O(√(n log n)) with far better probability, but they need mutual independence, which is expensive to supply.
04Frequently asked questions
Why is Chebyshev only quadratic in decay?
Because it uses only the second moment. Bounding higher moments gives faster decay, and taking all moments through the moment generating function gives exponential decay — which is precisely how the sharper bounds are derived.
Can Chebyshev be applied to a one-sided deviation?
Directly it bounds two-sided deviation, so a one-sided bound follows by halving only when the distribution is symmetric. Cantelli's inequality gives a sharper one-sided version without a symmetry assumption.
When is Markov alone sufficient?
When the conclusion needs only that a quantity is rarely a large constant factor above its mean — for instance, showing a randomised algorithm exceeds twice its expected running time with probability at most one half, which is enough to justify restarting.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 117-121.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.