What are the main inequalities used in statistical proofs? [closed]

Question

I know Jensen's is used everywhere. What other inequalities are used in statistical proofs (please state the inequality rigorously and formally)? As a bonus, you could cite a paper/theorem where the inequality is applied.

Answer 1

1. Markov/Chebychef inequality.

Let $X$ be a real valued random variable. Suppose that $p > 0$ and that $E[|X|^p]$ exists. Then $$P[|X| > R] \leq \frac{1}{R^p}E[|X|^p]$$ Suppose $X$ has a density $f$. As this inequality gives a bound on $P[|X| > R] = \int_{-\infty}^{-R} f(x) dx + \int_{R}^{\infty} f(x) dx$ we actually bound the behaviour of the 'tails', i.e. the "area under the integral" the density assigns to areas far away from zero. This can be useful if one knows that 'something' works on a compact interval $[-R, R]$ around zero and one wants to conclude that 'it' actually works for all of $\mathbb{R}$. For example: Suppose we want to approximize a density function $f$ of a random variable $X$ by more simple functions $f_n$ (decision trees, step functions, ...). This (density estimation) is a classical ML task and can be used for clustering. Let us assume that the $2$nd moment of $X$ exists, i.e. $E[|X|^2] < \infty$. Now we do something weird: We consider the random variables $f \circ X$ and $f_n \circ X$, i.e. we insert $X$ into its own density and consider this as a function! Motivation: See below. Our measure of 'coming close' is then $$E[|f_n \circ X - f \circ X|]$$ i.e. we want to show that this converges to zero. Let us assume that we can bound $f_n$ by $n$, i.e. $|f_n(x)| \leq n$ and $|f(x)| \leq C$ for some constant $C$ for all $x \in \mathbb{R}$. Let us further assume that we know that on a compact set $[-n, n]$ $f_n$ and $f$ come close quickly, i.e. for every $\epsilon > 0$ there exists an $N_0$ such that $|f_n(x) - f(x)| \leq \frac{\epsilon}{2Cn}$ for all $x \in [-n, n]$ (i.e. the process works on compact sets of increasing size but outside we do not know whether or not it works). Now for all $n \geq N_0$ \begin{align*} E[|f_n \circ X - f \circ X|] &= \int_\Omega |f_n - f|\circ X d\omega \\ &= \int_{\mathbb{R}} |f_n(x) - f(x)| f(x) dx \\ &\leq \int_{[-n, n]} |f_n(x) - f(x)| f(x) dx + (n + C)\left[\int_{(-\infty, -n)} f(x) dx + \int_{(n, \infty)} f(x) dx \right]\\ &= \frac{\epsilon}{2} + (n+C)P[|X| > n] \\ &\leq \frac{\epsilon}{2} + (n+C)\frac{1}{n^2} E(|X|^2) \\ &\leq \frac{\epsilon}{2} + \frac{\text{const}}{n} \end{align*} The latter part becomes smaller than $\epsilon/2$ for $n$ big enough. I.e. if the approximation works well on the compactum $[-n, n]$ then we do not have to worry about the tails given that moments exist with an exponential high enough to encope the increase behaviour of $f_n - f$ outside of the compactum.

Motivation: We see that our "measurement of distance" $E[|f_n \circ X - f \circ X|]$ actually translates into an integral $$\int_{\mathbb{R}} |f_n(x) - f(x)| f(x) dx$$ i.e. we measure the target distance $|f_n(x) - f(x)|$ weighted by $f$. This makes sense: When I do have only little data ($f$ small) then I cannot hope to get a good approximation. See here (https://math.stackexchange.com/questions/1185389/real-applications-of-markovs-inequality) for more (partially simpler) applications also in conjunction with Borel/Cantelli.

2. Borel/Cantelli

Let $\Omega$ be a probability space and let $A_1, A_2, ...$ be a sequence of subsets of $\Omega$. If $$\sum_{n=1}^\infty P(A_n) < \infty$$ then $$P\left( \cup_{n=1}^\infty \cap_{k=n}^\infty A_k \right) = 0$$

Unfortunately I was a little hasty with writing the comment and did not see that in order to prove the infinite monkey theorem (that monkeys typing random letters will eventually produce the complete work of Shakespeare) one needs the second, "extended" version which is much harder to prove (see https://math.stackexchange.com/questions/1249629/proof-of-infinite-monkey-theorem).

3. Fubini/Tonelli and Substitution

People always write integrals like this $$\int_{\mathbb{R}^2} f(x,y) d(x,y) = \int_{\mathbb{R}} \int_{\mathbb{R}} f(x,y) dx dy$$ This is in fact not true for all functions (see https://en.wikipedia.org/wiki/Fubini%27s_theorem#Failure_of_Fubini's_theorem_for_non-integrable_functions for a counterexample). We need to check first that either $\int_{\mathbb{R}} \int_{\mathbb{R}} |f(x,y)| dx dy < \infty$ or $\int_{\mathbb{R}^2} |f(x,y)| d(x,y) < \infty$. The fact that we can split the integral for checking is the little known Theorem of Tonelli. Fubini then asserts that we really may pull the integral apart in that case (without absolute values).

When one want to integrate stuff these theorems often work together with substitution. The simple version $$\int_{a}^b f \circ \phi(x) \cdot \phi'(x) dx = \int_{\phi(a)}^{\phi(b)} f(x) dx$$ carries over to multidimensional integrals. Often one has to apply a substitution first before it is posible to split the integral into senseful parts. For example, one can prove things about multivariate Gaussians in such a way (first make the multivariate Gaussian have $\Sigma = \text{Id}$ and $\mu=0$ and then pull the integral, i.e. apply substitution and then split the integral, see Linear subspace property of Gaussian integrals for one example but there are much more).