Laws of Large Numbers

Throughout, $S_n = \sum_{j=1}^{n} X_j$.

Tail Equivalence

Two sequences $(X_n), (X'_n)$ are tail-equivalent if

$$\sum_n P(X_n \ne X'_n) < \infty$$

By Borel-Cantelli, a.s. $X_n = X'_n$ for all large $n$. If $(X_n), (X'_n)$ are tail-equivalent, then

1. $\sum_n (X_n - X'_n)$ converges a.s.,
2. $\sum_n X_n$ converges a.s. iff $\sum_n X'_n$ converges a.s.,
3. if $a_n \uparrow \infty$ and $\frac{1}{a_n} \sum_{j=1}^{n} X_j \to X$ a.s., then $\frac{1}{a_n} \sum_{j=1}^{n} X'_j \to X$ a.s.

Weak Law of Large Numbers (WLLN)

Let $X_1, X_2, \ldots$ be independent. If

$$\sum_{j=1}^{n} P(|X_j| > n) \to 0 \quad \text{and} \quad \frac{1}{n^2} \sum_{j=1}^{n} E\big[X_j^2 \mathbf{1}\{|X_j| \le n\}\big] \to 0$$

then

$$\frac{S_n - a_n}{n} \xrightarrow{P} 0, \qquad a_n = \sum_{j=1}^{n} E\big[X_j \mathbf{1}\{|X_j| \le n\}\big]$$

IID Case

For the rest, $X_1, X_2, \ldots$ are iid and $\mu = E X_1$.

Chebyshev If $E X_1^2 < \infty$, then $S_n/n \xrightarrow{P} \mu$, i.e. for all $\varepsilon > 0$

$$\lim_{n \to \infty} P\Big(\Big|\frac{1}{n} \sum_{i=1}^{n} X_i - \mu\Big| > \varepsilon\Big) = 0$$

Khinchin If $E|X_1| < \infty$, then $S_n/n \xrightarrow{P} \mu$.

Feller If $x P(|X_1| > x) \to 0$, then

$$\frac{S_n}{n} - E\big[X_1 \mathbf{1}\{|X_1| \le n\}\big] \xrightarrow{P} 0$$

The conditions get weaker,

$$E X_1^2 < \infty \Rightarrow E|X_1| < \infty \Rightarrow x P(|X_1| > x) \to 0$$

and the converses don't hold. If $x P(|X_1| > x) \not\to 0$, no WLLN of this form holds.

$X$ is symmetric if $X$ and $-X$ have the same distribution. If $X_1$ is symmetric and Feller applies, then $E[X_1 \mathbf{1}\{|X_1| \le n\}] = 0$, so $S_n/n \xrightarrow{P} 0$.

Example: let $X_n$ be iid, symmetric, with

$$1 - F(x) = \frac{e}{2x \log x}, \quad x > e$$

Then $E X_1$ is undefined, but $x P(|X_1| > x) = \frac{e}{\log x} \to 0$, so $S_n/n \xrightarrow{P} 0$.

Bernstein Polynomials

$f : \mathbb{R} \to \mathbb{R}$ is uniformly continuous if for all $\varepsilon > 0$ there is $\delta > 0$ such that $|x - y| < \delta \Rightarrow |f(x) - f(y)| < \varepsilon$ for all $x, y$, using the same $\delta$ for all points. A continuous function on $[a,b]$ is uniformly continuous.

If $f : [0,1] \to \mathbb{R}$ is continuous and

$$B_n(x) = \sum_{k=0}^{n} f\Big(\frac{k}{n}\Big) \binom{n}{k} x^k (1-x)^{n-k}$$

then

$$\sup_{x \in [0,1]} |B_n(x) - f(x)| \to 0$$

Quantiles

For a df $F$ and $0 < p < 1$, the $p$th quantile of $F$ is

$$F^{\leftarrow}(p) = \inf\{y \in \mathbb{R} : F(y) \ge p\}$$

Let $X_1, X_2, \ldots$ be iid with df $F$. The empirical distribution function is

$$F_n(x) = \frac{1}{n} \sum_{k=1}^{n} \mathbf{1}\{X_k \le x\}$$

and by the WLLN, $F_n(x) \xrightarrow{P} F(x)$ for each $x$.

For RVs $X_1, \ldots, X_n$, the order statistics $X_n^{(1)} \le \cdots \le X_n^{(n)}$ are $X_1, \ldots, X_n$ arranged in increasing order. For $0 < p < 1$,

$$F_n^{\leftarrow}(p) = X_n^{(\lceil np \rceil)}$$

Let $q = F^{\leftarrow}(p)$. If $F(q - \varepsilon) < p < F(q + \varepsilon)$ for all $\varepsilon > 0$, then

$$F_n^{\leftarrow}(p) \xrightarrow{P} F^{\leftarrow}(p)$$