Markov's inequality
/ MAR-kof /
Suppose all you know about a non-negative quantity is its average. A charity tells you the average donation was $20. Could half the donors have given $1000 each? Common sense says no — if too many people gave huge amounts, the average could not stay so low. Markov's inequality turns that gut feeling into a precise, guaranteed bound on how often a non-negative random variable can be large.
The statement: if X is a non-negative random variable and a is any positive number, then P(X >= a) <= E[X] / a. In words, the chance that X reaches at least a is no more than its mean divided by a. The reasoning is almost embarrassingly simple. Whenever X >= a, that single outcome contributes at least a to the average; the worlds where X < a contribute at least 0. So E[X] is at least a times the probability of the big-value worlds: E[X] >= a P(X >= a). Divide by a and you are done. Notice it is a one-sided tail bound built from nothing but the mean and non-negativity.
The price of needing so little is that the bound is usually loose — it is the weakest of the concentration tools, and it can never beat 1 (if E[X]/a > 1 the bound says nothing). Its real power is as a building block: feed it X^2 and you get Chebyshev's inequality; feed it e^(tX) and you get the Chernoff bound. Almost every sharper tail bound in this field is Markov's inequality applied to a cleverly chosen function of X.
Test scores average E[X] = 60 out of 100 (so X >= 0). What fraction could have scored at least 90? Markov says P(X >= 90) <= 60/90 = 2/3. Loose, but ironclad: even knowing only the mean, no more than two-thirds can be that high.
From the mean alone, a guaranteed ceiling on how often a non-negative variable is large.
Markov requires X >= 0. Applied to a variable that can be negative, the inequality is simply false; you must first take absolute values or a non-negative function.