Markov's inequality

If φ is a nondecreasing nonnegative function, X is a (not necessarily nonnegative) random variable, and φ(a) > 0, then[3]

${\displaystyle \operatorname {P} (X\geq a)\leq {\frac {\operatorname {E} (\varphi (X))}{\varphi (a)}}.}$

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

${\displaystyle \operatorname {P} (|X|\geq a)\leq {\frac {\operatorname {E} (|X|^{n})}{a^{n}}}.}$

${\displaystyle \operatorname {E} (X)=\operatorname {P} (X<a)\cdot \operatorname {E} (X|X<a)+\operatorname {P} (X\geq a)\cdot \operatorname {E} (X|X\geq a)}$ where ${\displaystyle \operatorname {E} (X|X<a)}$ is larger than or equal to 0 as the random variable ${\displaystyle X}$ is non-negative and ${\displaystyle \operatorname {E} (X|X\geq a)}$ is larger than or equal to ${\displaystyle a}$ because the conditional expectation only takes into account of values larger than or equal to ${\displaystyle a}$ which r.v. ${\displaystyle X}$ can take.

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

Method 1: From the definition of expectation:

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

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

${\displaystyle \operatorname {E} (X)=\int _{-\infty }^{\infty }xf(x)\,dx=\int _{0}^{\infty }xf(x)\,dx}$

From this we can derive,

${\displaystyle \operatorname {E} (X)=\int _{0}^{a}xf(x)\,dx+\int _{a}^{\infty }xf(x)\,dx\geq \int _{a}^{\infty }xf(x)\,dx\geq \int _{a}^{\infty }af(x)\,dx=a\int _{a}^{\infty }f(x)\,dx=a\operatorname {Pr} (X\geq a)}$

From here, dividing through by ${\displaystyle a}$ allows us to see that

${\displaystyle \Pr(X\geq a)\leq \operatorname {E} (X)/a}$

Method 2: For any event ${\displaystyle E}$, let ${\displaystyle I_{E}}$ be the indicator random variable of ${\displaystyle E}$, that is, ${\displaystyle I_{E}=1}$ if ${\displaystyle E}$ occurs and ${\displaystyle I_{E}=0}$ otherwise.

Using this notation, we have ${\displaystyle I_{(X\geq a)}=1}$ if the event ${\displaystyle X\geq a}$ occurs, and ${\displaystyle I_{(X\geq a)}=0}$ if ${\displaystyle X<a}$. Then, given ${\displaystyle a>0}$,

${\displaystyle aI_{(X\geq a)}\leq X}$

which is clear if we consider the two possible values of ${\displaystyle X\geq a}$. If ${\displaystyle X<a}$, then ${\displaystyle I_{(X\geq a)}=0}$, and so ${\displaystyle aI_{(X\geq a)}=0\leq X}$. Otherwise, we have ${\displaystyle X\geq a}$, for which ${\displaystyle I_{X\geq a}=1}$ and so ${\displaystyle aI_{X\geq a}=a\leq X}$.

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

${\displaystyle \operatorname {E} (aI_{(X\geq a)})\leq \operatorname {E} (X).}$

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

${\displaystyle a\operatorname {E} (I_{(X\geq a)})=a(1\cdot \operatorname {P} (X\geq a)+0\cdot \operatorname {P} (X<a))=a\operatorname {P} (X\geq a).}$

Thus we have

${\displaystyle a\operatorname {P} (X\geq a)\leq \operatorname {E} (X)}$

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

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

${\displaystyle s(x)={\begin{cases}\varepsilon ,&{\text{if }}f(x)\geq \varepsilon \\0,&{\text{if }}f(x)<\varepsilon \end{cases}}}$

Then ${\displaystyle 0\leq s(x)\leq f(x)}$. By the definition of the Lebesgue integral

${\displaystyle \int _{X}f(x)\,d\mu \geq \int _{X}s(x)\,d\mu =\varepsilon \mu (\{x\in X:\,f(x)\geq \varepsilon \})}$

and since ${\displaystyle \varepsilon >0}$, both sides can be divided by ${\displaystyle \varepsilon }$, obtaining

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

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

Let ${\displaystyle a}$ be a positive integer. By definition ${\displaystyle a\operatorname {Pr} (X>a)}$ ${\displaystyle =a\operatorname {Pr} (X=a+1)+a\operatorname {Pr} (X=a+2)+a\operatorname {Pr} (X=a+3)+...}$ ${\displaystyle \leq a\operatorname {Pr} (X=a)+(a+1)\operatorname {Pr} (X=a+1)+(a+2)\operatorname {Pr} (X=a+2)+...}$ ${\displaystyle \leq \operatorname {Pr} (X=1)+2\operatorname {Pr} (X=2)+3\operatorname {Pr} (X=3)+...}$ ${\displaystyle +a\operatorname {Pr} (X=a)+(a+1)\operatorname {Pr} (X=a+1)+(a+2)\operatorname {Pr} (X=a+2)+...}$ ${\displaystyle =\operatorname {E} (X)}$

Dividing by ${\displaystyle 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,

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

for any a > 0.[3] Here Var(X) is the variance of X, defined as:

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

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

${\displaystyle (X-\operatorname {E} (X))^{2}}$

and the constant ${\displaystyle a^{2},}$ for which Markov's inequality reads

${\displaystyle \operatorname {P} ((X-\operatorname {E} (X))^{2}\geq a^{2})\leq {\frac {\operatorname {Var} (X)}{a^{2}}}.}$

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

${\displaystyle \operatorname {P} (|X-\operatorname {E} (X)|\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:

   ${\displaystyle \operatorname {P} (|X|\geq a)=\operatorname {P} {\big (}\varphi (|X|)\geq \varphi (a){\big )}\,{\overset {\underset {\mathrm {MI} }{}}{\leq }}\,{\frac {\operatorname {E} (\varphi (|X|))}{\varphi (a)}}}$

2. The result that, for a nonnegative random variable X, the quantile function of X satisfies:

   ${\displaystyle Q_{X}(1-p)\leq {\frac {\operatorname {E} (X)}{p}},}$

   the proof using

   ${\displaystyle p\leq \operatorname {P} (X\geq Q_{X}(1-p))\,{\overset {\underset {\mathrm {MI} }{}}{\leq }}\,{\frac {\operatorname {E} (X)}{Q_{X}(1-p)}}.}$

3. Let ${\displaystyle M\succeq 0}$ be a self-adjoint matrix-valued random variable and a > 0. Then

   ${\displaystyle \operatorname {P} (M\npreceq a\cdot I)\leq {\frac {\operatorname {tr} \left(E(M)\right)}{na}}.}$

   can be shown in a similar manner.