10 Inequalities
10.0.1 Jensen’s inequality
For a convex function f: \mathbb R \to \mathbb R and random variable X:
f(\mathbb EX) \leq \mathbb E f(X)
Any norm on \mathbb R^n is convex so:
\|\mathbb E X \| \leq \mathbb E \| X\|
10.0.2 Minkowski’s inequality
Any L^p norm satisifies the triangle inequality for p\geq 1 and X, y \in L^p:
\|X + Y \|_{L_p} \leq \|X \|_{L_p} + \| Y \|_{L_p}
10.0.3 Cauchy-Scharz inequality
\|X Y \|_{L_1} \leq \|X \|_{L_2} \| Y \|_{L_2}
10.0.4 Hölder’s inequality
If pp' = p + p': \|X Y \|_{L_1} \leq \|X \|_{L_p} \| Y \|_{L_{p'}}
10.0.5 Boole’s inequality
Also known as the union bound, it is just countable subadditivity: \mathbb P(\cup_n A_n ) \leq \sum_n \mathbb P(A_n)
10.1 Generalised Markov inequalities
For any non-decreasing non-negative integrable function f, non-negative random variable X and t>0: \mathbb P(X \geq t) \leq \frac{1}{f(t)} \mathbb E[f(X)]
10.1.1 Proof
\begin{align*} \mathbb 1 (y \geq 1) &\leq y\\ \mathbb 1 \left(\frac{f(X)}{f(t)} \geq 1 \right) &\leq \frac{f(X)}{f(t)}\\ \mathbb E \mathbb 1 \left(\frac{f(X)}{f(t)} \geq 1 \right) &\leq \mathbb E\left[ \frac{f(X)}{f(t)}\right] \\ \mathbb P \left(f(X) \geq f(t) \right) &\leq \frac{1}{f(t)} \mathbb E\left[ f(X) \right]\\ \end{align*}
Now, because f is non decreasing:
\begin{align*} X \geq t &\implies f(X) \geq f(t)\\ \{\omega \in \Omega: X(\omega) \geq t \} &\subset \{\omega \in \Omega: f(X(\omega)) \geq f(t) \} \\ \mathbb P \{\omega \in \Omega: X(\omega) \geq t \} &\leq \mathbb P \{\omega \in \Omega: f(X(\omega)) \geq f(t) \} \\ \mathbb P (X \geq t) &\leq \mathbb P (f(X) \geq f(t)) \end{align*}
Combining the two we get the result.
10.1.2 Markov’s inequality
\mathbb P (X \geq t) \leq \frac{\mathbb E X}{t}
10.1.3 Chebyshev’s inequality
Letting X = |Y - \mathbb EY| f(x) = t^2:
P( |Y- \mathbb E Y | \geq t) \leq \frac{\text{Var}[Y]}{t^2}
10.1.4 Chernoff’s bound
Let f(x)= \exp sx for s \geq 0: \mathbb P (X \geq t) \leq e^{-st} \mathbb E[e^{sX}]
Thus,
\mathbb P (X \geq t) \leq \inf_{s\geq 0} e^{-st} \mathbb E[e^{sX}]