Inequalities

info

Reference textbook High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Martin J. Wainwright

Integral identity: For X to be a non-negative R.V.

$$EX=E\int_0^{\infty}1_{t<x}dt=\int_0^{\infty}E1_{t<x}dt=\int_0^{\infty}P(X>t) dt$$

Markov's Inequality:For non-negative R.V. and $t>0$

$$EX=EX 1_{X\geq t} + EX 1_{x\leq t} \geq Et 1_{X\geq t}=t P(X \geq t)$$

Chebyshev's inequality: $X:=|X-\mu|^2$

Generalization: $X:=|X-\mu|^k$

$$P[|X-\mu|\geq t] \leq \frac{E[|X-\mu|^k]}{t^k}$$

Chernoff Bound

Chernoff bound: $X:=e^{\lambda (X-\mu)}$

$$\begin{aligned} &P[(X-\mu)\geq t] =P[e^{\lambda (X-\mu)}\geq e^{\lambda t}] \leq \frac{E[e^{\lambda (X-\mu)}]}{e^{\lambda t}}\\ &\log \mathbb{P}[(X-\mu) \geq t] \leq \inf _{\lambda \in[0, b]}\left\{\log \mathbb{E}\left[e^{\lambda(X-\mu)}\right]-\lambda t\right\} \end{aligned}$$

$\inf \limits_{k=0,1,2, . .} \frac{\mathbb{E}\left[|X|^{k}\right]}{\delta^{k}} \leq \inf\limits _{\lambda>0} \frac{\mathbb{E}\left[e^{\lambda X}\right]}{e^{\lambda \delta}}$.

Hoeffding's inequality of Rademacher RV

Hoeffding's inequality for n independent Rademacher R.V.s, vector $a \in R^n$ and $t \geq 0$:

$$P \left\{ \sum_{ i = 1 } ^ { n } a_{ i } X_{ i } \geq t \right\} \leq \exp \left( - \frac { t ^ { 2 } } { 2 \| a \|_{ 2 } ^ { 2 } } \right)$$

Proof:

$$\begin{aligned} \mathbb { P } \left\{ \sum_{ i = 1 } ^ { N } a_{ i } X_{ i } \geq t \right\} & = \mathbb { P } \left\{ \exp \left( \lambda \sum_{ i = 1 } ^ { N } a_{ i } X_{ i } \right) \geq \exp ( \lambda t ) \right\} \\ & \leq e ^ { - \lambda t } \mathbb { E } \exp \left( \lambda \sum_{ i = 1 } ^ { N } a_{ i } X_{ i } \right)\\ & = e ^ { - \lambda t } \prod_{ i = 1 } ^ { N } \mathbb { E } \exp \left( \lambda a_{ i } X_{ i } \right) \end{aligned}$$

For $\mathbb { E } \exp \left( \lambda a_{ i } X_{ i } \right) = \frac { \exp \left( \lambda a_{ i } \right) + \exp \left( - \lambda a_{ i } \right) } { 2 } = \cosh \left( \lambda a_{ i } \right)$ and $\cosh ( x ) \leq \exp \left( x ^ { 2 } / 2 \right) \quad \text { for all } x \in \mathbb { R }$

$$\begin{aligned} \mathbb { P } \left\{ \sum_{ i = 1 } ^ { N } a_{ i } X_{ i } \geq t \right\} \leq e ^ { - \lambda t } \prod_{ i = 1 } ^ { N } \exp \left( \lambda ^ { 2 } a_{ i } ^ { 2 } / 2 \right) & = \exp \left( - \lambda t + \frac { \lambda ^ { 2 } } { 2 } \sum_{ i = 1 } ^ { N } a_{ i } ^ { 2 } \right) \\ & = \exp \left( - \lambda t + \frac { \lambda ^ { 2 } } { 2 } \right) (\text{ make }\lambda = t) \end{aligned}$$

Chernoff's inequality for sum of Bernoulli rv

$\mathbb { P } \left\{ S _ { N } \geq t \right\} \leq e ^ { - \mu } \left( \frac { e \mu } { t } \right) ^ { t }$