Markov's inequality is a fundamental result in probability theory stating that, for a nonnegative random variable and any positive number ,
It bounds an upper-tail probability using only the expected value, without requiring a particular probability distribution or a finite variance. Named after Andrey Markov, the inequality is a basic tool for deriving more refined probability bounds and proving convergence results.
Statement and assumptions
Let be a measurable random variable on a probability space, with almost surely. If , then for every ,
The minimum with makes explicit that probabilities cannot exceed . The usual statement omits it because the essential bound is . When , the bound is strictly less than ; when , it provides no improvement over the universal upper bound .
If has infinite expectation, the inequality remains valid in the extended-real sense but gives no useful finite bound. If , nonnegativity implies almost surely.
For a positive mean , an equivalent form is
Thus a nonnegative quantity can be at least ten times its mean with probability no greater than one tenth.
The inequality also holds with the strict event , although the distinction between strict and non-strict thresholds matters when discussing equality.
Proof and interpretation
The proof follows from a pointwise comparison with an indicator function:
On the event , the right-hand side equals , which is no greater than . Outside that event, it is zero, which is no greater than by nonnegativity.
Taking expectations gives
Division by proves the result.
The underlying principle is that every outcome in the event contributes at least to the expectation. The total probability of such outcomes is therefore limited by the available mean.
No independence assumption is involved. The proof applies equally to discrete, continuous, and mixed distributions.
Sharpness and equality
Markov's inequality is sharp: without additional information about the distribution, its bound cannot generally be improved.
For a fixed threshold and a prescribed mean , consider
Then
so equality holds.
More generally, for an integrable nonnegative , equality in
holds exactly when takes values only in , apart from an event of probability zero. This follows because
is nonnegative and must have expectation zero.
If , the best universal upper bound is , attained by the constant random variable . Consequently,
Sharpness does not mean the bound is close to the actual probability for every distribution. It means that some admissible distribution attains it.
Generalizations
Absolute moments
For any real-valued random variable , any , and any , applying Markov's inequality to gives
provided the moment on the right is finite.
This converts control of an absolute moment into control of a tail probability. Centering at a constant yields
Increasing transformations
Let be a nonnegative, nondecreasing measurable function with . Since
Markov's inequality implies
The transformation must be nonnegative on the values taken by , and its expectation must be finite for the bound to be informative. Power functions and exponential functions give particularly useful instances.
Measure-theoretic form
In measure theory, if is a nonnegative measurable function on a measure space , then
The underlying measure need not be a probability measure. This version is also commonly called a Chebyshev inequality in mathematical analysis.
Conditional form
For a nonnegative integrable and a sub--algebra ,
Here conditional probability is the conditional expectation of the event indicator. The proof uses the same pointwise comparison and the monotonicity of conditional expectation.
Relations to other probability inequalities
Chebyshev's inequality
Suppose has mean and finite variance . Applying Markov's inequality to the nonnegative variable gives
This is Chebyshev's inequality. It controls deviations from the mean through the second centered moment, whereas the basic Markov bound controls a nonnegative variable through its first moment.
Exponential bounds
For , the exponential function is positive and increasing. Applying Markov's inequality to gives
Optimizing over admissible positive yields
This is the exponential Markov method underlying Chernoff bounds.
If and the summands are independent, then
when these expectations are finite. The factorization often makes exponential bounds much stronger than applying the original inequality directly to the sum.
Applications
Convergence from moment bounds
If a sequence satisfies
for some , then for every ,
Thus convergence in a positive absolute moment implies convergence in probability.
For independent, identically distributed variables with mean and finite variance , the sample mean has variance . The squared-deviation form therefore gives
proving the finite-variance version of the weak law of large numbers.
Runtime and counting arguments
If a nonnegative running time has finite expectation, then
This converts an expected-runtime guarantee for an algorithm into a tail guarantee, although often a conservative one.
If counts undesirable events, then is a nonnegative integer and
For a finite collection of events , setting
gives
Thus the union bound is an immediate consequence of Markov's inequality and linearity of expectation, without requiring independence.
Limitations and common misapplications
Nonnegativity is essential. A signed random variable can have a small mean because large positive and negative values cancel. For example, if equals and , each with probability , then , but
Substituting into the nonnegative-variable formula would incorrectly give an upper bound of zero. Valid alternatives include applying the inequality to , to a positive power of , or to a known nonnegative shift.
The inequality is an upper bound, not an estimate of the actual probability. If almost surely, then
while Markov's inequality gives only .
Finally, a finite first moment alone provides no universal exponentially decreasing tail bound and does not imply a finite second moment. Stronger bounds require additional information, such as bounded support, higher moments, finite exponential moments, or structural assumptions about sums of random variables.