Bounds and Inequalities
Recommended Prerequesites
- Probability
Probability inequalities provide bounds on probabilities and expectations, allowing us to make precise statements about random variables without knowing their exact distributions. Additionally, sometimes a quantity may not have a closed form expression. Inequalities can help provide loose estimates and also bounds for computational techniques.
General Inequalities
These inequalities broadly apply to many families of distributions, although there may be conditions for application.
McKay's Inequality
For any real-valued random variable X with finite mean \(\mu\), finite variance \(\sigma^2\), and median \(m\):
$$|\mu-m|\leq \sigma$$
Higher Moment Analogue
A similar statement can be done with respect to the skewness \(\gamma\) (provided it is finite):
$$|\mu-m|\leq \frac{\gamma \sigma}{3}$$
Markov's Inequality
Let \(X\) be a non-negative random variable with finite expected value \(\mathbb{E}[X]\). Then, for any \(a\gt 0\):
$$P(X\geq a)\leq \frac{\mathbb{E}[X]}{a}$$
Extended Markov's Inequality
Let \(\phi\) be a non-decreasing non-negative function with \(\phi(a)\gt 0\):
$$P(X\geq a)\leq \frac{\mathbb{E}[\phi(X)]}{\phi(a)}$$
Chebyshev's Inequality
Chebyshev's inequality provides a bound on the probability that a random variable deviates from its mean by more than a certain number of standard deviations, with mild conditions.
Let \(X\) be a random variable with finite mean \(\mu\) and finite variance \(\sigma^2\). Then for \(k\gt 0\):
$$P(|X-\mu|\geq k\sigma)\leq \frac{1}{k^2}$$
Vysochanskij-Petunin
If X is unimodal, we can get tigheter bounds for a given distance away:
$$P(|X-\mu|\geq \lambda\sigma)\leq \frac{4}{9\lambda^2}$$
for \(\lambda \gt \sqrt{\frac{8}{3}}\)
Cantelli's Inequality
Cantelli's Inequality is a one-sided analogue:
$$P(X-\mu\geq k\sigma)\leq \frac{1}{1+k^2}$$
Jensen's Inequality
Let \(X\) be a random variable, and let \(\phi\) be a convex function. Then:
$$\phi(\mathbb{E}[X])\leq \mathbb{E}[\phi(X)]$$
Distribution-Specific
Convergence of Random Variables
Sure Convergergence
Also known as pointwise convergence.
Let \(\left\{X_n\right\}\) be a sequence of random variables.
Let \(\Omega\) be the sample space of \(X_i\). \(X_n\) converges pointwise (surely) if
$$\forall \omega\in\Omega: \lim_{n\rightarrow\infty}X_n(\omega)=X(\omega)$$
Almost Sure Convergence
A sequence of random variables \(\left\{X_n\right\}\) converges almost surely (a.s.) to \(X\) if:
$$P(\lim_{n\rightarrow \infty}X_n=X)=1$$
We can denote this as \(X_n\overset{\text{a.s.}}{{\to}X}\).
How is this different from sure convergence? The notation of "almost sure" refers to allowing \(X_n\) and X to disagree on sets of probability (measure) 0.
Strong Law of Large Numbers
An example of almost sure convergence is the Strong Law of Large Numbers.
$$P(\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^nX_i=\mu)=1$$
Converges in Probability
\(\left\{X_n\right\}\) converges in probability to X if, for every \(\varepsilon\gt0\):
$$\lim_{n\rightarrow\infty}P(|X_n-X|\geq \varepsilon)=0$$
Almost sure convergence implies convergence in probability, but the converse is not necessarily true. It only requires that the probability of large deviations goes to zero.
Weak Law of Large Numbers
An example of convergence in probability is the weak law of large numbers.
$$\lim_{n\rightarrow\infty}P(|\frac{1}{n}\sum_{i=1}^nX_i-\mu|\geq\varepsilon)=0$$
Example of Convergence in Probability but not Almost Surely
Convergence in Distribution
\(\left\{X_n\right\}\) converges in distribution to \(X\) if, for all continuity points x of \(F_X(x)\):
$$\lim_{n\rightarrow\infty}F_{X_n}(x)=F_X(x)$$
We can denote this as
$$F_n(x)\overset{d}{\rightarrow}F(x)$$
Convergence in distribution does not imply convergence in probability. However, convergence in probability does imply convergence in distribution.
Central Limit Theorem
Let \(\{X_i\}\) be iid random variables with finite mean \(\mu\) and finite variance \(\sigma^2\). Then as \(n\rightarrow\infty\):
$$\frac{\sum_{i=1}^nX_i-n\mu}{\sigma\sqrt{n}}\overset{d}{\rightarrow}N(0,1)$$
or equivalently
$$\frac{\bar{X}-\mu}{\frac{\sigma}{\sqrt{n}}}\overset{d}{\rightarrow}N(0,1)$$
Continuous Mapping Theorem
If \(X_n\overset{d}{\rightarrow}X\) and g is a continuous function, then:
$$g(X_n)\overset{d}{\rightarrow}g(X)$$
Borel-Cantelli Lemma
First Borel-Cantelli Lemma
If \(\sum_{n=1}^\infty P(A_n)\lt \infty\):
$$P(\limsup_{n\rightarrow\infty}A_n)=0$$
Second Borel-Cantelli Lemma
If \(\left\{A_n\right\}\) are independent events and \(\sum_{n=1}^\infty P(A_n)=\infty\):
$$P(\limsup_{n\rightarrow\infty}A_n)=1$$
Example of Using Borel-Cantelli
Let \(\left\{X_n\right\}\) be a sequence of independent Bernouilli random variables defined on a probability space where \(X_n\) takes values:
$$X_n=\begin{cases}1 & \text{with probability }p_n=\frac{1}{n}\\
0 & \text{with probability }1-p_n=1-\frac{1}{n}\end{cases}$$
Showing Convergence in Probability
$$X_n\to 0$$
For any \(\varepsilon\gt 0\):
$$P(|X_n-0|\geq \varepsilon)=P(X_n=1)=\frac{1}{n}\to 0\text{ as n }\to\infty$$
Therefore, \(X_n\) to 0.
Showing No Almost Sure Convergence
Let \(A_n=\left\{X_n=1\right\}\). These are the events where \(X_n\) deviates from the limiting distribution of 0.
$$\sum_{n=1}^\infty P(A_n)=\sum_{n=1}^\infty\frac{1}{n}=\infty$$
From the second Borel-Cantelli Lemma, if \(\{A_n\}\) are independent events and \(\sum P(A_n)=\infty\) then:
$$P(\limsup_{n\to\infty}A_n)=1$$
Thus, \(X_n\) does not converge almost surely to 0.