Markov's Inequality

P(X ≥ a) ≤ E[X]/a for X ≥ 0 — the simplest tail bound.

The idea

Theorem (Markov's inequality).

If $X$ is a nonnegative random variable and $a > 0$, then $\mathbb{P}(X \geq a) \leq \frac{\mathbb{E}[X]}{a}.$

Knowing only the average of $X$ already limits how often $X$ can be large. If a quantity averages $10$, it cannot reach $100$ more than a tenth of the time: those occasions by themselves would already contribute $10$ to the average.

Nonnegativity is essential to this argument. With no negative values available to pull the average back down, every large value must be paid for by the mean.

Because the bound uses nothing but the mean, it holds for every nonnegative distribution; for the same reason it is usually far from tight, and it decays only like $1/a$ as the threshold grows.

Its main use is as a building block. Applied not to $X$ itself but to a well-chosen function of $X$, it produces most of the stronger tail bounds.

Ways to work on it

• Walkthrough. Bound the tail of X given its mean.
• Proof. See why it holds — the mean as a balance point on a seesaw.
• Practice. Apply Markov's bound with small, clean numbers.
• Hardest. Reverse Markov — bound E[X] from a known tail probability — and a tightness check.

Not sure where to start? Take the ten-question placement test.