Probabilistic Inequalities
Markov’s Inequality
Theorem: If $X$ is a random variable, $X>0$ and $a>0$ is a positive real number, then
\begin{eqnarray}
\mathrm{P}(X>a) \leqslant \frac{\mathrm{E}(X)}{a}
\end{eqnarray}
{\bf Proof:}
\begin{eqnarray}
E(X)=\int_0^{\infty}xf_X(x)dx > \int_a^{\infty}xf_X(x)dx > a \int_a^{\infty}f_X(x)dx = a P(X>a)
\end{eqnarray}
which gives us the markov inequality. $\Box$
Markov inequality gives us some power of estimation if the random variable is positive and if we know nothing but the mean. For example, assume that a population has a mean weight of 50 kg. What is the probability of seeing an individual with weight 200kg? For an exact answer, we must know the exact shape of the pdf. But we can immediately say that the probability is less than 0.25, whatever the pdf is..
Chebyshev’s Inequality
Theorem: If $X$ is a random variable and $a$ is a real number, then
\begin{eqnarray}
\mathrm{P}[|X-\mathrm{E}(x)|>a] \leqslant \frac{\mathrm{Var}(X)}{a^2}
\end{eqnarray}
{\bf Proof:} We will use Markov’s inequality to prove Chebyshev’s inequality. Note that
\begin{eqnarray}
\mathrm{P}[|X-\mathrm{E}(x)|>a]=\mathrm{P}[(X-\mathrm{E}(x))^2>a^2]
\end{eqnarray}
Hence, by using Markov’s inequality
\begin{eqnarray}
\mathrm{P}[|X-\mathrm{E}(x)|>a] < \frac{E(X-\mathrm{E}(x))^2}{a^2} = \frac{\mathrm{Var}(X)}{a^2}
\end{eqnarray}
$\Box$
Unlike Markov Inequality, Chebyshev inequality does not require that our random variable be positive. It gives us some power to estimate the distribution if the only things we know are mean and variance. For example, if we know that $\mathrm{E}(x)=\mu$, $\mathrm{Var}(X)=\sigma^2$, then
we can immediately say that
\begin{eqnarray}
\mathrm{P}[|X-\mu|> n\sigma] < \frac{1}{n^2}
\end{eqnarray}
which means: the probability of our random variable to be away from the mean by more than $n$ standard deviations is $1/n^2$. This is valid for
all pdf’s.
Chernoff Bound
An another consequence of Markov’s inequality is Chernoff bound: \\\\
{\bf Theorem:} If $X$ is a random variable and $M_X(s)$ is its moment generating function. Then, for all $t>0$
\begin{eqnarray}
P(X \geq t) \leq
\end{eqnarray}
Hoeffding Inequality
Hoeffding Bound helps us establish the Upper Confidence Bound (UCB) on random variables.