MathIsimple

Limit Theorems Formulas

Essential formulas for convergence and asymptotic behavior

5
Categories
31
Formulas
Advanced
Level
Theory
Focus
Convergence in Distribution
Fundamental formulas for weak convergence of distribution functions
6 formulas

Weak Convergence Definition

Formula 1
Fn→wF  ⟺  lim⁡n→∞Fn(x)=F(x)F_n \stackrel{w}{\to} F \iff \lim_{n\to\infty} F_n(x) = F(x)

For all continuity points x of F(x)

Convergence in Distribution

Formula 2
ξn→dξ  ⟺  Fξn→wFξ\xi_n \stackrel{d}{\to} \xi \iff F_{\xi_n} \stackrel{w}{\to} F_{\xi}

Random variable convergence through distribution function convergence

Lévy Continuity Theorem

Formula 3
ξn→dξ  ⟺  fn(t)→f(t) for all t∈R\xi_n \stackrel{d}{\to} \xi \iff f_n(t) \to f(t) \text{ for all } t \in \mathbb{R}

Equivalence between distribution convergence and characteristic function convergence

Poisson Approximation to Binomial

Formula 4
If ξn∼B(n,pn) and lim⁡n→∞npn=λ, then ξn→dP(λ)\text{If } \xi_n \sim B(n, p_n) \text{ and } \lim_{n\to\infty} np_n = \lambda, \text{ then } \xi_n \stackrel{d}{\to} P(\lambda)

Binomial distribution converges to Poisson when n is large and p is small

Normal Approximation to Poisson

Formula 5
If ξn∼P(λn) and λn→∞, then ξn−λnλn→dN(0,1)\text{If } \xi_n \sim P(\lambda_n) \text{ and } \lambda_n \to \infty, \text{ then } \frac{\xi_n - \lambda_n}{\sqrt{\lambda_n}} \stackrel{d}{\to} N(0,1)

Poisson distribution becomes approximately normal for large parameter

Helly's Second Theorem

Formula 6
If Fn→wF and g bounded continuous, then ∫g(x)dFn(x)→∫g(x)dF(x)\text{If } F_n \stackrel{w}{\to} F \text{ and } g \text{ bounded continuous, then } \int g(x) dF_n(x) \to \int g(x) dF(x)

Integral convergence for bounded continuous functions

Convergence in Probability
Formulas for probability convergence and related theorems
6 formulas

Convergence in Probability Definition

Formula 1
ξn→Pξ  ⟺  lim⁡n→∞P(∣ξn−ξ∣≥ε)=0 for all ε>0\xi_n \stackrel{P}{\to} \xi \iff \lim_{n\to\infty} P(|\xi_n - \xi| \geq \varepsilon) = 0 \text{ for all } \varepsilon > 0

Probability of large deviations goes to zero

Convergence to Constant

Formula 2
ξn→dc  ⟺  ξn→Pc\xi_n \stackrel{d}{\to} c \iff \xi_n \stackrel{P}{\to} c

For constants, distribution convergence equals probability convergence

Slutsky's Lemma - Addition

Formula 3
If ξn→dξ and ηn→Pc, then ξn+ηn→dξ+c\text{If } \xi_n \stackrel{d}{\to} \xi \text{ and } \eta_n \stackrel{P}{\to} c, \text{ then } \xi_n + \eta_n \stackrel{d}{\to} \xi + c

Sum rule for combining convergence types

Slutsky's Lemma - Multiplication

Formula 4
If ξn→dξ and ηn→Pc, then ξnηn→dcξ\text{If } \xi_n \stackrel{d}{\to} \xi \text{ and } \eta_n \stackrel{P}{\to} c, \text{ then } \xi_n \eta_n \stackrel{d}{\to} c\xi

Product rule for combining convergence types

Continuous Mapping Theorem

Formula 5
If ξn→Pξ and g continuous, then g(ξn)→Pg(ξ)\text{If } \xi_n \stackrel{P}{\to} \xi \text{ and } g \text{ continuous, then } g(\xi_n) \stackrel{P}{\to} g(\xi)

Continuous functions preserve probability convergence

Markov Inequality for Convergence

Formula 6
If E∣ξn−ξ∣r<∞, then P(∣ξn−ξ∣≥ε)≤E∣ξn−ξ∣rεr\text{If } E|\xi_n - \xi|^r < \infty, \text{ then } P(|\xi_n - \xi| \geq \varepsilon) \leq \frac{E|\xi_n - \xi|^r}{\varepsilon^r}

Tool for verifying probability convergence using moments

Law of Large Numbers
Weak and strong law formulations and conditions
7 formulas

Bernoulli WLLN

Formula 1
If ξn∼Bernoulli(p) i.i.d., then 1n∑k=1nξk→Pp\text{If } \xi_n \sim \text{Bernoulli}(p) \text{ i.i.d., then } \frac{1}{n}\sum_{k=1}^n \xi_k \stackrel{P}{\to} p

Sample proportion converges to population proportion

Khintchine WLLN

Formula 2
If {ξn} i.i.d. with E∣ξ1∣<∞, then 1n∑k=1nξk→PEξ1\text{If } \{\xi_n\} \text{ i.i.d. with } E|\xi_1| < \infty, \text{ then } \frac{1}{n}\sum_{k=1}^n \xi_k \stackrel{P}{\to} E\xi_1

Sample mean converges in probability to population mean

Chebyshev WLLN Condition

Formula 3
If independent and 1n2∑k=1nVar(ξk)→0, then 1n∑k=1n(ξk−Eξk)→P0\text{If independent and } \frac{1}{n^2}\sum_{k=1}^n \text{Var}(\xi_k) \to 0, \text{ then } \frac{1}{n}\sum_{k=1}^n (\xi_k - E\xi_k) \stackrel{P}{\to} 0

Variance condition for weak law of large numbers

Almost Sure Convergence Definition

Formula 4
ξn→a.s.ξ  ⟺  P({ω:lim⁡n→∞ξn(ω)=ξ(ω)})=1\xi_n \stackrel{a.s.}{\to} \xi \iff P(\{\omega: \lim_{n\to\infty} \xi_n(\omega) = \xi(\omega)\}) = 1

Sample path convergence for almost all outcomes

Borel SLLN

Formula 5
If ξn∼Bernoulli(p) i.i.d., then 1n∑k=1nξk→a.s.p\text{If } \xi_n \sim \text{Bernoulli}(p) \text{ i.i.d., then } \frac{1}{n}\sum_{k=1}^n \xi_k \stackrel{a.s.}{\to} p

Strong law for Bernoulli trials

Kolmogorov SLLN

Formula 6
For i.i.d. {ξn}:1n∑k=1nξk→a.s.μ  ⟺  E∣ξ1∣<∞ and μ=Eξ1\text{For i.i.d. } \{\xi_n\}: \frac{1}{n}\sum_{k=1}^n \xi_k \stackrel{a.s.}{\to} \mu \iff E|\xi_1| < \infty \text{ and } \mu = E\xi_1

Necessary and sufficient condition for strong law

Convergence Hierarchy

Formula 7
Almost sure convergence⇒Convergence in probability⇒Convergence in distribution\text{Almost sure convergence} \Rightarrow \text{Convergence in probability} \Rightarrow \text{Convergence in distribution}

Strength ordering of different convergence types

Central Limit Theorem
Normal approximation formulas and conditions
6 formulas

de Moivre-Laplace Theorem

Formula 1
If Sn∼B(n,p), then Sn−npnpq→dN(0,1) where q=1−p\text{If } S_n \sim B(n,p), \text{ then } \frac{S_n - np}{\sqrt{npq}} \stackrel{d}{\to} N(0,1) \text{ where } q = 1-p

Normal approximation to binomial distribution

Lindeberg-Lévy CLT

Formula 2
If {ξn} i.i.d. with Eξ1=μ,Var(ξ1)=σ2<∞, then ∑k=1nξk−nμnσ→dN(0,1)\text{If } \{\xi_n\} \text{ i.i.d. with } E\xi_1 = \mu, \text{Var}(\xi_1) = \sigma^2 < \infty, \text{ then } \frac{\sum_{k=1}^n \xi_k - n\mu}{\sqrt{n}\sigma} \stackrel{d}{\to} N(0,1)

Classical central limit theorem for identical distributions

Sample Mean CLT

Formula 3
Xˉn−μσ/n→dN(0,1) where Xˉn=1n∑k=1nξk\frac{\bar{X}_n - \mu}{\sigma/\sqrt{n}} \stackrel{d}{\to} N(0,1) \text{ where } \bar{X}_n = \frac{1}{n}\sum_{k=1}^n \xi_k

Central limit theorem expressed in terms of sample mean

Lindeberg Condition

Formula 4
1Bn2∑k=1n∫∣x−Eξk∣≥τBn(x−Eξk)2dFk(x)→0 for all τ>0\frac{1}{B_n^2}\sum_{k=1}^n \int_{|x-E\xi_k| \geq \tau B_n} (x-E\xi_k)^2 dF_k(x) \to 0 \text{ for all } \tau > 0

General condition for CLT, where B_n² = ∑Var(ξₖ)

Lyapunov Condition

Formula 5
1Bn2+δ∑k=1nE∣ξk−Eξk∣2+δ→0 for some δ>0\frac{1}{B_n^{2+\delta}}\sum_{k=1}^n E|\xi_k - E\xi_k|^{2+\delta} \to 0 \text{ for some } \delta > 0

Sufficient condition for CLT (easier to verify than Lindeberg)

Binomial Probability Approximation

Formula 6
P(a≤Sn≤b)≈Φ(b−npnpq)−Φ(a−npnpq)P(a \leq S_n \leq b) \approx \Phi\left(\frac{b - np}{\sqrt{npq}}\right) - \Phi\left(\frac{a - np}{\sqrt{npq}}\right)

Normal approximation formula for binomial probabilities

Supporting Inequalities and Theorems
Important auxiliary results for limit theorems
6 formulas

Borel-Cantelli Lemma (First)

Formula 1
If ∑n=1∞P(An)<∞, then P(lim sup⁡n→∞An)=0\text{If } \sum_{n=1}^{\infty} P(A_n) < \infty, \text{ then } P(\limsup_{n\to\infty} A_n) = 0

Finite sum of probabilities implies only finitely many events occur

Borel-Cantelli Lemma (Second)

Formula 2
If {An} independent and ∑n=1∞P(An)=∞, then P(lim sup⁡n→∞An)=1\text{If } \{A_n\} \text{ independent and } \sum_{n=1}^{\infty} P(A_n) = \infty, \text{ then } P(\limsup_{n\to\infty} A_n) = 1

Infinite sum with independence implies infinitely many events occur

Kolmogorov's Inequality

Formula 3
P(max⁡1≤j≤n∣∑k=1j(ξk−Eξk)∣≥ε)≤1ε2∑k=1nVar(ξk)P\left(\max_{1\leq j\leq n}\left|\sum_{k=1}^j (\xi_k - E\xi_k)\right| \geq \varepsilon\right) \leq \frac{1}{\varepsilon^2}\sum_{k=1}^n \text{Var}(\xi_k)

Maximum inequality for independent random variables

Hájek-Rényi Inequality

Formula 4
P(max⁡m≤j≤nCj∣∑k=1j(ξk−Eξk)∣≥ε)≤1ε2(Cm2∑j=1mVar(ξj)+∑j=m+1nCj2Var(ξj))P\left(\max_{m\leq j\leq n} C_j\left|\sum_{k=1}^j (\xi_k - E\xi_k)\right| \geq \varepsilon\right) \leq \frac{1}{\varepsilon^2}\left(C_m^2\sum_{j=1}^m \text{Var}(\xi_j) + \sum_{j=m+1}^n C_j^2 \text{Var}(\xi_j)\right)

Weighted version of Kolmogorov's inequality

Kolmogorov Three-Series Conditions

Formula 5
∑n=1∞P(∣ξn∣>c)<∞,∑n=1∞Eξn′ converges,∑n=1∞Var(ξn′)<∞\sum_{n=1}^{\infty} P(|\xi_n| > c) < \infty, \quad \sum_{n=1}^{\infty} E\xi_n' \text{ converges}, \quad \sum_{n=1}^{\infty} \text{Var}(\xi_n') < \infty

Necessary and sufficient conditions for a.s. convergence of ∑(ξₙ - Eξₙ), where ξₙ' = ξₙI(|ξₙ|≤c)

Chebyshev's Inequality

Formula 6
P(∣ξ−Eξ∣≥ε)≤Var(ξ)ε2P(|\xi - E\xi| \geq \varepsilon) \leq \frac{\text{Var}(\xi)}{\varepsilon^2}

Fundamental probability bound using variance