Common Inequalities

For $p, q \geq 1$ with $\frac{1}{p} + \frac{1}{q} = 1$ (conjugate exponents):

$\sum_i |a_i b_i| \leq \left(\sum_i |a_i|^p\right)^{1/p} \left(\sum_i |b_i|^q\right)^{1/q}$

Or in integral form: $\int |fg| \leq \|f\|_p \|g\|_q$.

Special case: $p = q = 2$ gives Cauchy-Schwarz.

When it arises: Bounding mixed-norm expressions, dual norm computations ($\|x\|_p^* = \|x\|_q$), and proving interpolation inequalities. The duality between $\ell_p$ and $\ell_q$ norms underpins convex analysis.

For $p \geq 1$:

$\left(\sum_i |a_i + b_i|^p\right)^{1/p} \leq \left(\sum_i |a_i|^p\right)^{1/p} + \left(\sum_i |b_i|^p\right)^{1/p}$

In short: $\|a + b\|_p \leq \|a\|_p + \|b\|_p$.

This is the triangle inequality for $\ell_p$ norms, proven using Holder. It confirms that $\|\cdot\|_p$ is a valid norm for $p \geq 1$. (For $p < 1$, the triangle inequality fails and $\|\cdot\|_p$ is not a norm.)

For non-negative reals $a_1, \ldots, a_n$:

$\frac{a_1 + a_2 + \cdots + a_n}{n} \geq (a_1 a_2 \cdots a_n)^{1/n}$

Equality holds if and only if all $a_i$ are equal.

Two-variable form: $\frac{a + b}{2} \geq \sqrt{ab}$, or equivalently $ab \leq \frac{(a + b)^2}{4}$.

Proof from Jensen: Apply Jensen to the concave function $f(x) = \log x$: $\log\!\left(\frac{1}{n}\sum a_i\right) \geq \frac{1}{n}\sum \log a_i = \log\!\left(\prod a_i\right)^{1/n}$.

When it arises: Bounding products by sums (which are easier to handle), optimizing expressions involving products, proving convergence rates.

For $a, b \geq 0$ and conjugate exponents $p, q > 1$ with $\frac{1}{p} + \frac{1}{q} = 1$:

$ab \leq \frac{a^p}{p} + \frac{b^q}{q}$

Special case ($p = q = 2$): $ab \leq \frac{a^2}{2} + \frac{b^2}{2}$, which is AM-GM for squares.

Parametric form: For any $\epsilon > 0$: $ab \leq \frac{\epsilon a^2}{2} + \frac{b^2}{2\epsilon}$. This is extremely useful in proofs where you need to "split" a product into two terms with different scaling.

When it arises: Splitting cross-terms in energy estimates, proving Holder from Young, absorbing error terms in convergence proofs. The parametric form lets you trade off how much of the bound goes into each term.

If $X \geq 0$, then for any $t > 0$:

$\mathbb{P}(X \geq t) \leq \frac{\mathbb{E}[X]}{t}$

Proof: $\mathbb{E}[X] \geq \mathbb{E}[X \cdot \mathbf{1}_{X \geq t}] \geq t \cdot \mathbb{P}(X \geq t)$.

When it arises: Markov is the foundation of all tail bounds. Chebyshev applies Markov to $(X - \mu)^2$. The Chernoff method applies Markov to $e^{\lambda X}$. Every concentration inequality starts with Markov.

Limitation: The bound decays as $1/t$. far too slow for most applications. You almost always want Hoeffding or Bernstein instead.

For any random variable $X$ with mean $\mu$ and finite variance $\sigma^2$:

$\mathbb{P}(|X - \mu| \geq t) \leq \frac{\sigma^2}{t^2}$

Proof: Apply Markov to $(X - \mu)^2$: $\mathbb{P}(|X - \mu| \geq t) = \mathbb{P}((X-\mu)^2 \geq t^2) \leq \sigma^2/t^2$.

When it arises: Proving weak laws of large numbers, giving initial sample complexity bounds ($n = O(1/\epsilon^2\delta)$ to estimate a mean within $\epsilon$ at confidence $1 - \delta$). The polynomial tail $1/t^2$ is worse than the exponential tails from Hoeffding, but Chebyshev requires only finite variance. no boundedness assumption.