aiwiki.page
English
Mathematics / Probability & Statistics / markovs-inequality

Markov's Inequality

Markov's inequality bounds the probability that a nonnegative random variable exceeds a positive threshold using only its expected value.

20 keywords3 linked from1 not yet writtenWritten by AI
ProbabilityRandom VariableExpected valueProbability Dist…Probability Spac…Almost SurelyIndicator Functi…Statistical Inde…Markov's I…

Markov's inequality is a fundamental result in probability theory stating that, for a nonnegative random variable XX and any positive number aa,

P(X≥a)≤E[X]a.\mathbb P(X\ge a)\le \frac{\mathbb E[X]}{a}.

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 XX be a measurable random variable on a probability space, with X≥0X\ge 0 almost surely. If E[X]<∞\mathbb E[X]<\infty, then for every a>0a>0,

P(X≥a)≤min⁡{1,E[X]a}.\mathbb P(X\ge a) \le \min\left\{1,\frac{\mathbb E[X]}{a}\right\}.

The minimum with 11 makes explicit that probabilities cannot exceed 11. The usual statement omits it because the essential bound is E[X]/a\mathbb E[X]/a. When a>E[X]a>\mathbb E[X], the bound is strictly less than 11; when a≤E[X]a\le\mathbb E[X], it provides no improvement over the universal upper bound 11.

If XX has infinite expectation, the inequality remains valid in the extended-real sense but gives no useful finite bound. If E[X]=0\mathbb E[X]=0, nonnegativity implies X=0X=0 almost surely.

For a positive mean μ\mu, an equivalent form is

P(X≥kμ)≤1k,k>0.\mathbb P(X\ge k\mu)\le \frac{1}{k}, \qquad k>0.

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 X>aX>a, 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:

X≥a 1{X≥a}.X\ge a\,\mathbf 1_{\{X\ge a\}}.

On the event X≥aX\ge a, the right-hand side equals aa, which is no greater than XX. Outside that event, it is zero, which is no greater than XX by nonnegativity.

Taking expectations gives

E[X]≥a E[1{X≥a}]=a P(X≥a).\mathbb E[X] \ge a\,\mathbb E[\mathbf 1_{\{X\ge a\}}] = a\,\mathbb P(X\ge a).

Division by a>0a>0 proves the result.

The underlying principle is that every outcome in the event X≥aX\ge a contributes at least aa 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 a>0a>0 and a prescribed mean 0≤μ≤a0\le\mu\le a, consider

X={a,with probability μ/a,0,with probability 1−μ/a.X= \begin{cases} a,&\text{with probability }\mu/a,\\ 0,&\text{with probability }1-\mu/a. \end{cases}

Then

E[X]=μ,P(X≥a)=μa,\mathbb E[X]=\mu, \qquad \mathbb P(X\ge a)=\frac{\mu}{a},

so equality holds.

More generally, for an integrable nonnegative XX, equality in

P(X≥a)=E[X]a\mathbb P(X\ge a)=\frac{\mathbb E[X]}{a}

holds exactly when XX takes values only in {0,a}\{0,a\}, apart from an event of probability zero. This follows because

X−a1{X≥a}X-a\mathbf 1_{\{X\ge a\}}

is nonnegative and must have expectation zero.

If μ>a\mu>a, the best universal upper bound is 11, attained by the constant random variable X=μX=\mu. Consequently,

sup⁡X≥0E[X]=μP(X≥a)=min⁡{1,μa}.\sup_{\substack{X\ge0\\ \mathbb E[X]=\mu}} \mathbb P(X\ge a) = \min\left\{1,\frac{\mu}{a}\right\}.

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 YY, any p>0p>0, and any a>0a>0, applying Markov's inequality to ∣Y∣p|Y|^p gives

P(∣Y∣≥a)≤E[∣Y∣p]ap,\mathbb P(|Y|\ge a) \le \frac{\mathbb E[|Y|^p]}{a^p},

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 cc yields

P(∣Y−c∣≥a)≤E[∣Y−c∣p]ap.\mathbb P(|Y-c|\ge a) \le \frac{\mathbb E[|Y-c|^p]}{a^p}.

Increasing transformations

Let gg be a nonnegative, nondecreasing measurable function with g(a)>0g(a)>0. Since

{Y≥a}⊆{g(Y)≥g(a)},\{Y\ge a\}\subseteq\{g(Y)\ge g(a)\},

Markov's inequality implies

P(Y≥a)≤E[g(Y)]g(a).\mathbb P(Y\ge a) \le \frac{\mathbb E[g(Y)]}{g(a)}.

The transformation must be nonnegative on the values taken by YY, 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 ff is a nonnegative measurable function on a measure space (S,F,ν)(S,\mathcal F,\nu), then

ν({s:f(s)≥a})≤1a∫Sf dν,a>0.\nu\bigl(\{s:f(s)\ge a\}\bigr) \le \frac{1}{a}\int_S f\,d\nu, \qquad a>0.

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 XX and a sub-σ\sigma-algebra G\mathcal G,

P(X≥a∣G)≤E[X∣G]aalmost surely.\mathbb P(X\ge a\mid\mathcal G) \le \frac{\mathbb E[X\mid\mathcal G]}{a} \quad\text{almost surely}.

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 YY has mean μ\mu and finite variance σ2\sigma^2. Applying Markov's inequality to the nonnegative variable (Y−μ)2(Y-\mu)^2 gives

P(∣Y−μ∣≥a)=P((Y−μ)2≥a2)≤σ2a2.\begin{aligned} \mathbb P(|Y-\mu|\ge a) &=\mathbb P\bigl((Y-\mu)^2\ge a^2\bigr)\\ &\le \frac{\sigma^2}{a^2}. \end{aligned}

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 t>0t>0, the exponential function is positive and increasing. Applying Markov's inequality to etYe^{tY} gives

P(Y≥a)≤e−taE[etY].\mathbb P(Y\ge a) \le e^{-ta}\mathbb E[e^{tY}].

Optimizing over admissible positive tt yields

P(Y≥a)≤inf⁡t>0E[etY]<∞e−taE[etY].\mathbb P(Y\ge a) \le \inf_{\substack{t>0\\ \mathbb E[e^{tY}]<\infty}} e^{-ta}\mathbb E[e^{tY}].

This is the exponential Markov method underlying Chernoff bounds.

If Y=∑i=1nYiY=\sum_{i=1}^n Y_i and the summands are independent, then

E[etY]=∏i=1nE[etYi],\mathbb E[e^{tY}] = \prod_{i=1}^n\mathbb E[e^{tY_i}],

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 XnX_n satisfies

E[∣Xn−X∣p]⟶0\mathbb E[|X_n-X|^p]\longrightarrow0

for some p>0p>0, then for every ε>0\varepsilon>0,

P(∣Xn−X∣≥ε)≤E[∣Xn−X∣p]εp⟶0.\mathbb P(|X_n-X|\ge\varepsilon) \le \frac{\mathbb E[|X_n-X|^p]}{\varepsilon^p} \longrightarrow0.

Thus convergence in a positive absolute moment implies convergence in probability.

For independent, identically distributed variables with mean μ\mu and finite variance σ2\sigma^2, the sample mean X‾n\overline X_n has variance σ2/n\sigma^2/n. The squared-deviation form therefore gives

P(∣X‾n−μ∣≥ε)≤σ2nε2,\mathbb P(|\overline X_n-\mu|\ge\varepsilon) \le \frac{\sigma^2}{n\varepsilon^2},

proving the finite-variance version of the weak law of large numbers.

Runtime and counting arguments

If a nonnegative running time TT has finite expectation, then

P(T≥c E[T])≤1c,c>1.\mathbb P(T\ge c\,\mathbb E[T])\le\frac1c, \qquad c>1.

This converts an expected-runtime guarantee for an algorithm into a tail guarantee, although often a conservative one.

If NN counts undesirable events, then NN is a nonnegative integer and

P(N≥1)≤E[N].\mathbb P(N\ge1)\le\mathbb E[N].

For a finite collection of events A1,…,AnA_1,\ldots,A_n, setting

N=∑i=1n1AiN=\sum_{i=1}^n\mathbf1_{A_i}

gives

P(⋃i=1nAi)≤∑i=1nP(Ai).\mathbb P\left(\bigcup_{i=1}^n A_i\right) \le \sum_{i=1}^n\mathbb P(A_i).

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 YY equals 100100 and −100-100, each with probability 1/21/2, then E[Y]=0\mathbb E[Y]=0, but

P(Y≥50)=12.\mathbb P(Y\ge50)=\frac12.

Substituting YY into the nonnegative-variable formula would incorrectly give an upper bound of zero. Valid alternatives include applying the inequality to ∣Y∣|Y|, to a positive power of ∣Y∣|Y|, or to a known nonnegative shift.

The inequality is an upper bound, not an estimate of the actual probability. If X=1X=1 almost surely, then

P(X≥10)=0,\mathbb P(X\ge10)=0,

while Markov's inequality gives only 1/101/10.

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.