Markov's inequality#Proof

If {{mvar|X}} is a nonnegative random variable and {{math|a > 0}}, then the probability

that {{mvar|X}} is at least {{mvar|a}} is at most the expectation of {{mvar|X}} divided by {{mvar|a}}:

:$\backslash operatorname\{P\}(X\; \backslash geq\; a)\; \backslash leq\; \backslash frac\{\backslash operatorname\{E\}(X)\}\{a\}.$

When $\backslash operatorname\{E\}(X)\; >\; 0$, we can take $a\; =\; \backslash tilde\{a\}\; \backslash cdot\; \backslash operatorname\{E\}(X)$ for $\backslash tilde\{a\}\; >\; 0$ to rewrite the previous inequality as

:$\backslash operatorname\{P\}(X\; \backslash geq\; \backslash tilde\{a\}\; \backslash cdot\; \backslash operatorname\{E\}(X))\; \backslash leq\; \backslash frac\{1\}\{\backslash tilde\{a\}\}.$

In the language of measure theory, Markov's inequality states that if {{math|(X, Σ, μ)}} is a measure space, $f$ is a measurable extended real-valued function, and {{math|ε > 0}}, then

:$\backslash mu(\backslash \{x\backslash in\; X:|f(x)|\backslash geq\; \backslash varepsilon\; \backslash \})\; \backslash leq\; \backslash frac\; 1\; \backslash varepsilon\; \backslash int\_X\; |f|\backslash ,d\backslash mu.$

This measure-theoretic definition is sometimes referred to as Chebyshev's inequality.{{citation| author1-first= E. M. | author1-last= Stein| author2-first=R. | author2-last=Shakarchi | author1-link= Elias M. Stein | title=Real Analysis | series=Princeton Lectures in Analysis | volume=3 | edition= 1st | year= 2005| page= 91}}.

If {{mvar|φ}} is a nondecreasing nonnegative function, {{mvar|X}} is a (not necessarily nonnegative) random variable, and {{math|φ(a) > 0}}, then{{Cite book |last=Lin |first=Zhengyan |title=Probability inequalities |publisher=Springer |year=2010 |pages=52}}

:$\backslash operatorname\; P\; (X\; \backslash ge\; a)\; \backslash le\; \backslash frac\{\backslash operatorname\; E(\backslash varphi(X))\}\{\backslash varphi(a)\}.$

An immediate corollary, using higher moments of {{mvar|X}} supported on values larger than 0, is

:$\backslash operatorname\; P\; (|X|\; \backslash ge\; a)\; \backslash le\; \backslash frac\{\backslash operatorname\; E(|X|^n)\}\{a^n\}.$

If {{mvar|X}} is a nonnegative random variable and {{math|a > 0}}, and {{mvar|U}} is a uniformly distributed random variable on $[0,1]$ that is independent of {{mvar|X}}, then{{citation| author1-first= Aaditya | author1-last= Ramdas| author2-first=Tudor | author2-last=Manole | title = Randomized and Exchangeable Improvements of Markov's, Chebyshev's and Chernoff's Inequalities | date= 2023| arxiv=2304.02611}}.

:$\backslash operatorname\{P\}(X\; \backslash geq\; Ua)\; \backslash leq\; \backslash frac\{\backslash operatorname\{E\}(X)\}\{a\}.$

Since {{mvar|U}} is almost surely smaller than one, this bound is strictly stronger than Markov's inequality. Remarkably, {{mvar|U}} cannot be replaced by any constant smaller than one, meaning that deterministic improvements to Markov's inequality cannot exist in general. While Markov's inequality holds with equality for distributions supported on $\backslash \{0,a\backslash \}$, the above randomized variant holds with equality for any distribution that is bounded on $[0,a]$.

We separate the case in which the measure space is a probability space from the more general case because the probability case is more accessible for the general reader.

Property 1:

Given a non-negative random variable $X$, the conditional expectation because $X\; \backslash geq\; 0$. Also, probabilities are always non-negative, i.e., . Thus, the product:

.

This is intuitive since conditioning on still results in non-negative values, ensuring the product remains non-negative.

Property 2: $\backslash operatorname\{P\}(X\; \backslash geq\; a)\; \backslash cdot\; \backslash operatorname\{E\}(X\; \backslash mid\; X\; \backslash geq\; a)\; \backslash geq\; a\; \backslash cdot\; \backslash operatorname\{P\}(X\; \backslash geq\; a)$

For $X\; \backslash geq\; a$, the expected value given $X\; \backslash geq\; a$ is at least $a.\; \backslash operatorname\{E\}(X\; \backslash mid\; X\; \backslash geq\; a)\; \backslash geq\; a$. Multiplying both sides by $\backslash operatorname\{P\}(X\; \backslash geq\; a)$, we get:

$\backslash operatorname\{P\}(X\; \backslash geq\; a)\; \backslash cdot\; \backslash operatorname\{E\}(X\; \backslash mid\; X\; \backslash geq\; a)\; \backslash geq\; a\; \backslash cdot\; \backslash operatorname\{P\}(X\; \backslash geq\; a)$.

This is intuitive since all values considered are at least $a$, making their average also greater than or equal to $a$.

Hence intuitively, $\backslash operatorname\{E\}(X)\backslash geq\; \backslash operatorname\{P\}(X\; \backslash geq\; a)\backslash cdot\; \backslash operatorname\{E\}(X|X\backslash geq\; a)\backslash geq\; a\; \backslash cdot\; \backslash operatorname\{P\}(X\backslash geq\; a)$, which directly leads to $\backslash operatorname\{P\}(X\backslash geq\; a)\backslash leq\; \backslash frac\{\backslash operatorname\{E\}(X)\}\{a\}$.

Method 1:

From the definition of expectation:

:$\backslash operatorname\{E\}(X)=\backslash int\_\{-\backslash infty\}^\{\backslash infty\}\; xf(x)\; \backslash ,\; dx$

However, X is a non-negative random variable thus,

:$\backslash operatorname\{E\}(X)=\backslash int\_\{-\backslash infty\}^\backslash infty\; xf(x)\; \backslash ,\; dx\; =\; \backslash int\_0^\backslash infty\; xf(x)\; \backslash ,\; dx$

From this we can derive,

:$\backslash operatorname\{E\}(X)=\backslash int\_0^a\; xf(x)\; \backslash ,\; dx\; +\; \backslash int\_a^\backslash infty\; xf(x)\; \backslash ,\; dx\; \backslash ge\; \backslash int\_a^\backslash infty\; xf(x)\; \backslash ,\; dx\; \backslash ge\backslash int\_a^\backslash infty\; af(x)\; \backslash ,\; dx\; =\; a\backslash int\_a^\backslash infty\; f(x)\; \backslash ,\; dx=\; a\; \backslash operatorname\{Pr\}(X\; \backslash ge\; a)$

From here, dividing through by $a$ allows us to see that

:$\backslash Pr(X\; \backslash ge\; a)\; \backslash le\; \backslash operatorname\{E\}(X)/a$

Method 2:

For any event $E$, let $I\_E$ be the indicator random variable of $E$, that is, $I\_E=1$ if $E$ occurs and $I\_E=0$ otherwise.

Using this notation, we have $I\_\{(X\backslash geq\; a)\}=1$ if the event $X\backslash geq\; a$ occurs, and $I\_\{(X\backslash geq\; a)\}=0$ if

:$aI\_\{(X\; \backslash geq\; a)\}\; \backslash leq\; X$

which is clear if we consider the two possible values of $X\backslash geq\; a$. If

Since $\backslash operatorname\{E\}$ is a monotonically increasing function, taking expectation of both sides of an inequality cannot reverse it. Therefore,

:$\backslash operatorname\{E\}(aI\_\{(X\; \backslash geq\; a)\})\; \backslash leq\; \backslash operatorname\{E\}(X).$

Now, using linearity of expectations, the left side of this inequality is the same as

:

Thus we have

:$a\backslash operatorname\{P\}(X\; \backslash geq\; a)\; \backslash leq\; \backslash operatorname\{E\}(X)$

and since a > 0, we can divide both sides by a.

We may assume that the function $f$ is non-negative, since only its absolute value enters in the equation. Now, consider the real-valued function s on X given by

:$$

s(x) =

\begin{cases}

\varepsilon, & \text{if } f(x) \geq \varepsilon \\

0, & \text{if } f(x) < \varepsilon

\end{cases}

Then $0\backslash leq\; s(x)\backslash leq\; f(x)$. By the definition of the Lebesgue integral

:$$

\int_X f(x) \, d\mu \geq \int_X s(x) \, d \mu = \varepsilon \mu( \{ x\in X : \, f(x) \geq \varepsilon \} )

and since $\backslash varepsilon\; >0$, both sides can be divided by $\backslash varepsilon$, obtaining

:$\backslash mu(\backslash \{x\backslash in\; X\; :\; \backslash ,\; f(x)\; \backslash geq\; \backslash varepsilon\; \backslash \})\; \backslash leq\; \{1\backslash over\; \backslash varepsilon\; \}\backslash int\_X\; f\; \backslash ,d\backslash mu.$

We now provide a proof for the special case when $X$ is a discrete random variable which only takes on non-negative integer values.

Let $a$ be a positive integer. By definition $a\backslash operatorname\{Pr\}(X\; >\; a)$

$=a\backslash operatorname\{Pr\}(X\; =\; a\; +\; 1)\; +\; a\backslash operatorname\{Pr\}(X\; =\; a\; +\; 2)\; +\; a\backslash operatorname\{Pr\}(X\; =\; a\; +\; 3)\; +\; ...$

$\backslash leq\; a\backslash operatorname\{Pr\}(X\; =\; a)\; +\; (a+1)\backslash operatorname\{Pr\}(X\; =\; a\; +\; 1)\; +\; (a+2)\backslash operatorname\{Pr\}(X\; =\; a\; +\; 2)\; +\; ...$

$\backslash leq\; \backslash operatorname\{Pr\}(X\; =\; 1)\; +\; 2\backslash operatorname\{Pr\}(X\; =\; 2)\; +\; 3\backslash operatorname\{Pr\}(X\; =\; 3)\; +\; ...$

$+a\backslash operatorname\{Pr\}(X\; =\; a\; )\; +\; (a+1)\backslash operatorname\{Pr\}(X\; =\; a\; +\; 1)\; +\; (a+2)\backslash operatorname\{Pr\}(X\; =\; a\; +\; 2)\; +\; ...$

$=\backslash operatorname\{E\}(X)$

Dividing by $a$ yields the desired result.

Chebyshev's inequality uses the variance to bound the probability that a random variable deviates far from the mean. Specifically,

:$\backslash operatorname\{P\}(|X-\backslash operatorname\{E\}(X)|\; \backslash geq\; a)\; \backslash leq\; \backslash frac\{\backslash operatorname\{Var\}(X)\}\{a^2\},$

for any {{math|a > 0}}. Here {{math|Var(X)}} is the variance of X, defined as:

:$\backslash operatorname\{Var\}(X)\; =\; \backslash operatorname\{E\}[(X\; -\; \backslash operatorname\{E\}(X)\; )^2].$

Chebyshev's inequality follows from Markov's inequality by considering the random variable

: $(X\; -\; \backslash operatorname\{E\}(X))^2$

and the constant $a^2,$ for which Markov's inequality reads

: $\backslash operatorname\{P\}(\; (X\; -\; \backslash operatorname\{E\}(X))^2\; \backslash ge\; a^2)\; \backslash le\; \backslash frac\{\backslash operatorname\{Var\}(X)\}\{a^2\}.$

This argument can be summarized (where "MI" indicates use of Markov's inequality):

:$\backslash operatorname\{P\}(|X-\backslash operatorname\{E\}(X)|\; \backslash geq\; a)\; =$

\operatorname{P}\left((X-\operatorname{E}(X))^2 \geq a^2\right) \,\overset{\underset{\mathrm{MI}}{}}{\leq}\,

\frac {\operatorname{E} \left( (X-\operatorname{E}(X))^2 \right)}{a^2} =

\frac{\operatorname{Var}(X)}{a^2}.

1. The "monotonic" result can be demonstrated by:
2. :$\backslash operatorname\; P\; (|X|\; \backslash ge\; a)\; =\; \backslash operatorname\; P\; \backslash big(\backslash varphi(|X|)\; \backslash ge\; \backslash varphi(a)\backslash big)\; \backslash ,\backslash overset\{\backslash underset\{\backslash mathrm\{MI\}\}\{\}\}\{\backslash leq\}\backslash ,$

\frac{\operatorname E(\varphi(|X|))}{\varphi(a)}

1. :
2. The result that, for a nonnegative random variable {{mvar|X}}, the quantile function of {{mvar|X}} satisfies:
3. :$Q\_X(1-p)\; \backslash leq\; \backslash frac\; \{\backslash operatorname\; E(X)\}\{p\},$
4. :the proof using
5. :$p\; \backslash leq\; \backslash operatorname\; P(X\; \backslash geq\; Q\_X(1-p))\; \backslash ,\backslash overset\{\backslash underset\{\backslash mathrm\{MI\}\}\{\}\}\{\backslash leq\}\backslash ,\; \backslash frac\; \{\backslash operatorname\; E(X)\}\{Q\_X(1-p)\}.$
6. :
7. Let $M\; \backslash succeq\; 0$ be a self-adjoint matrix-valued random variable and $A\; \backslash succ\; 0$. Then
8. :$$

\operatorname{P}(M \npreceq A) \leq \operatorname{tr}(\operatorname E (X) A^{-1})

1. :which can be proved similarly.{{cite web |url= https://stephentu.github.io/blog/probability-theory/matrix-analysis/2017/11/04/matrix-markovs-inequality.html |title= Markov's Inequality for Matrices |last=Tu |first=Stephen |date=2017-11-04 |website= |publisher= |access-date=May 27, 2024 |quote=}}

Assuming no income is negative, Markov's inequality shows that no more than 10% (1/10) of the population can have more than 10 times the average income.{{Cite book |last=Ross |first=Kevin |url=https://bookdown.org/kevin_davisross/probsim-book/probability-inequalitlies.html |title=5.4 Probability inequalitlies {{!}} An Introduction to Probability and Simulation}}

Another simple example is as follows: Andrew makes 4 mistakes on average on his Statistics course tests. The best upper bound on the probability that Andrew will do at least 10 mistakes is 0.4 as $\backslash operatorname\{P\}(X\; \backslash geq\; 10)\; \backslash leq\; \backslash frac\{\backslash operatorname\{E\}(X)\}\{\backslash alpha\}\; =\; \backslash frac\{4\}\{10\}.$ Note that Andrew might do exactly 10 mistakes with probability 0.4 and make no mistakes with probability 0.6; the expectation is exactly 4 mistakes.

• Paley–Zygmund inequality – a corresponding lower bound
• Concentration inequality – a summary of tail-bounds on random variables.

{{reflist}}

• [http://mws.cs.ru.nl/mwiki/random_1.html#T36 The formal proof of Markov's inequality] in the Mizar system.

{{Lp spaces}}

{{Refimprove|date=September 2010}}

{{DEFAULTSORT:Markov's Inequality}}

Category:Probabilistic inequalities

Category:Articles containing proofs