Distribution-free probability bound
Markov's Inequality
For any nonnegative random variable, the probability of exceeding a positive threshold cannot be greater than the mean divided by that threshold.
P(X >= a) <= E[X] / a, for X >= 0 and a > 0
The bound requires only nonnegativity and a finite mean. That generality makes it robust but often loose; additional information about variance, shape, dependence, or support can produce tighter bounds.
The sampler changes distribution shape while holding the mean fixed. The actual tail changes, but every displayed distribution remains below the same Markov ceiling.
(%)
The plot, diagram, and calculated result share the same state. Animation runs only when it adds explanatory value.
- CHANGE
- Threshold as multiple of mean
- WATCH
- actual tail + guaranteed ceiling
- MEANING
- The sampler changes distribution shape while holding the mean fixed. The actual tail changes, but every displayed distribution remains below the same Markov ceiling.
The mean buys a ceiling, not a forecast.
A threshold cuts through several equal-mean distributions, exposing the gap between actual tail mass and the distribution-free bound.
What it actually says
Markov's inequality converts one piece of information, the mean, into a guaranteed upper bound on a tail probability. If the threshold is four times the mean, no more than one quarter of probability mass can lie at or above it.
The inequality can be tight: a variable that is zero most of the time and exactly a with probability E[X]/a reaches equality. For smoother real distributions the bound may be much larger than the actual tail, which is the price of making almost no distributional assumptions.
"A useful law compresses a pattern. It does not erase the conditions that make the pattern true."
How the idea developed
The modern form emerged through observation, argument, and later refinement. The timeline separates the first insight from the version now used in textbooks and practice.[1]
Andrey Markov develops inequalities and dependence theory in probability.
Chebyshev and Markov bounds become foundational tools in probability proofs.
Concentration inequalities extend the approach using moments and transforms.
Algorithms, learning theory, queueing, reliability, and randomized analysis use tail bounds.
How the pattern works
The relation becomes useful only when its mechanism, measurement process, and operating range are visible.
Values below the threshold cannot cancel tail contribution to the mean.
Each outcome at or above a contributes at least a to expectation.
Only the first moment is used.
Two-point distributions can spend the entire mean budget at the threshold.
The bound requires only nonnegativity and a finite mean. That generality makes it robust but often loose; additional information about variance, shape, dependence, or support can produce tighter bounds.
Where it earns its keep
Applications are strongest when the law changes a decision, measurement, model, or experiment rather than merely providing an analogy.
Bound bad-event probability
ApplicationExpected cost can yield a quick failure-probability ceiling.
Seek sharper concentration when variance or independence is known.
Screen extreme exposure
ApplicationA nonnegative loss mean limits the maximum tail probability.
Do not treat the ceiling as a calibrated risk estimate.
Build stronger inequalities
ApplicationApply Markov to squared deviations or exponential transforms.
Verify the transformed variable remains nonnegative.
Where it stops working
The variable must be nonnegative, the threshold positive, and the expectation finite. Shifting a variable changes both the condition and interpretation.
The bound can be arbitrarily loose for a specific distribution; it provides assurance under ignorance, not a substitute for modeling available structure.
"The probability is E[X]/a"
Better: That quantity is an upper bound, not usually the actual probability."It works unchanged for signed variables"
Better: Negative values can invalidate the proof."A loose bound is mathematically wrong"
Better: Looseness and validity are different."The inequality assumes a normal distribution"
Better: It is distribution-free under its stated conditions.Sources and further reading
Original publications and serious secondary scholarship are prioritized over summaries.
- MIT - Mathematics for Computer ScienceOpen treatment of Markov and related bounds.https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
- Stanford CS109 - Probability for Computer ScientistsCourse materials applying tail inequalities.https://web.stanford.edu/class/cs109/
- Durrett - Probability: Theory and ExamplesGraduate probability reference.https://services.math.duke.edu/~rtd/PTE/PTE5_011119.pdf
- NIST - Probability DistributionsAuthoritative statistical context for distributions and tails.https://www.itl.nist.gov/div898/handbook/eda/section3/eda36.htm