Inequalities, Convergence and Limit Theorems
CSIR NET probability: Markov, Chebyshev and Jensen inequalities, modes of convergence, Borel-Cantelli, weak and strong laws of large numbers, i.i.d. CLT.
- 19 min
On this page · 13 sections
Prerequisites
- Random Variables, Distribution Functions and Moments: expectation, existence of moments, MGFs.
- Joint, Marginal and Conditional Distributions; Characteristic Functions: independence of random variables, variance of sums, characteristic functions and Lévy’s continuity theorem.
- Sequences and Series of Functions and Riemann, Improper and Lebesgue Integration: pointwise versus uniform convergence, and the monotone and dominated convergence theorems. Almost-sure convergence is pointwise convergence off a null set; convergence in mean is \( L^p \) convergence.
The Hook: Why Averages Settle Down
Inequalities
Markov and Chebyshev
Markov’s inequality. If \( X \ge 0 \) and \( a > 0 \),
$$\boxed{P(X \ge a) \le \frac{E X}{a}}$$Proof in one line: \( a\,\mathbf{1}\{X \ge a\} \le X \); take expectations. More generally, for increasing \( g \ge 0 \), \( P(X \ge a) \le \frac{E\,g(X)}{g(a)} \).
Chebyshev’s inequality. If \( E X = \mu \) and \( \text{Var}\,X = \sigma^2 < \infty \), for \( k > 0 \),
$$\boxed{P(\lvert X - \mu \rvert \ge k\sigma) \le \frac{1}{k^2}}, \qquad \text{equivalently} \quad P(\lvert X - \mu \rvert < k\sigma) \ge 1 - \frac{1}{k^2}.$$Apply Markov to \( (X - \mu)^2 \).
One-sided (Cantelli) inequality. For \( \lambda > 0 \), \( P(X - \mu \ge \lambda) \le \frac{\sigma^2}{\sigma^2 + \lambda^2} \).
Chernoff bound. For every \( t > 0 \), \( P(X \ge a) \le e^{-ta}M_X(t) \); minimise over \( t \). For sums of i.i.d. bounded variables this gives exponentially small tails, far sharper than Chebyshev.
Jensen and its relatives
Jensen’s inequality. If \( g \) is convex on an interval containing the values of \( X \), and \( E\lvert X \rvert \), \( E\lvert g(X) \rvert < \infty \), then
$$\boxed{g(E X) \le E\,g(X)}$$with the reverse for concave \( g \). For strictly convex \( g \), equality holds iff \( X \) is almost surely constant.
| Choice of \( g \) | Consequence |
|---|---|
| \( x^2 \) | \( (E X)^2 \le E X^2 \), i.e. \( \text{Var} \ge 0 \) |
| \( \lvert x \rvert \) | \( \lvert E X \rvert \le E\lvert X \rvert \) |
| \( \frac{1}{x} \), \( x > 0 \) | \( E\frac{1}{X} \ge \frac{1}{E X} \) |
| \( \log x \) (concave) | \( E \log X \le \log E X \); this is AM \( \ge \) GM |
| \( e^{x} \) | \( e^{E X} \le E e^{X} = M_X(1) \) |
| \( x^{s/r} \), \( s > r > 0 \) | Lyapunov: \( (E\lvert X \rvert^r)^{1/r} \le (E\lvert X \rvert^s)^{1/s} \) |
Also in the toolkit:
- Cauchy–Schwarz: \( (E XY)^2 \le E X^2\,E Y^2 \) (gives \( \lvert \rho \rvert \le 1 \)).
- Hölder: \( E\lvert XY \rvert \le (E\lvert X \rvert^p)^{1/p}(E\lvert Y \rvert^q)^{1/q} \), \( \frac{1}{p} + \frac{1}{q} = 1 \).
- Minkowski: \( (E\lvert X + Y \rvert^p)^{1/p} \le (E\lvert X \rvert^p)^{1/p} + (E\lvert Y \rvert^p)^{1/p} \), \( p \ge 1 \).
- Conditional Jensen: \( g(E(X \mid Y)) \le E(g(X) \mid Y) \) for convex \( g \).
Modes of Convergence
Let \( X_n, X \) be random variables on one probability space (for convergence in distribution, they need not be).
| Mode | Notation | Definition |
|---|---|---|
| Almost surely | \( X_n \xrightarrow{a.s.} X \) | \( P(\lim X_n = X) = 1 \) |
| In probability | \( X_n \xrightarrow{P} X \) | \( P(\lvert X_n - X \rvert > \varepsilon) \to 0 \) for every \( \varepsilon > 0 \) |
| In \( r \)-th mean (\( r > 0 \)) | \( X_n \xrightarrow{L^r} X \) | \( E\lvert X_n - X \rvert^r \to 0 \) |
| In distribution (law) | \( X_n \xrightarrow{d} X \) | \( F_{X_n}(x) \to F_X(x) \) at every continuity point \( x \) of \( F_X \) |
graph LR
AS[Almost sure] --> P[In probability]
LS[In L^s] --> LR[In L^r, r less than s]
LR --> P
P --> D[In distribution]
D -.->|limit is a constant| P
P -.->|along a subsequence| AS
P -.->|plus domination or uniform integrability| LRSolid arrows always hold; dashed arrows need the extra condition shown.
Equivalent forms of \( \xrightarrow{d} \). \( E\,g(X_n) \to E\,g(X) \) for every bounded continuous \( g \); or (Lévy) \( \varphi_{X_n}(t) \to \varphi_X(t) \) for every \( t \).
Useful rules.
- Continuous mapping: if \( g \) is continuous, each mode (a.s., P, d) passes from \( X_n \) to \( g(X_n) \).
- Slutsky: if \( X_n \xrightarrow{d} X \) and \( Y_n \xrightarrow{P} c \) (a constant), then \( X_n + Y_n \xrightarrow{d} X + c \), \( Y_nX_n \xrightarrow{d} cX \), and \( \frac{X_n}{Y_n} \xrightarrow{d} \frac{X}{c} \) if \( c \ne 0 \).
- Sums: a.s. and in-probability limits add (\( X_n + Y_n \to X + Y \)); in-distribution limits do not in general.
Counter-examples on \( [0, 1] \) with Lebesgue measure
| Sequence | a.s. | P | \( L^1 \) | d |
|---|---|---|---|---|
| \( X_n = n\,\mathbf{1}_{(0, 1/n)} \) | yes, to 0 | yes | no (\( E X_n = 1 \)) | yes |
| \( X_n = \sqrt{n}\,\mathbf{1}_{(0, 1/n)} \) | yes | yes | yes (\( E X_n = n^{-1/2} \)); not \( L^2 \) | yes |
| “Typewriter”: indicators of \( [\frac{j}{2^k}, \frac{j+1}{2^k}] \), \( j = 0, \dots, 2^k - 1 \), \( k = 0, 1, \dots \) in order | no (every point is covered infinitely often) | yes | yes | yes |
| \( X \sim N(0, 1) \), \( X_n = -X \) | no | no | no | yes, to \( X \) |
The last row shows convergence in distribution is a statement about laws only: \( -X \) has the same law as \( X \), yet \( \lvert X_n - X \rvert = 2\lvert X \rvert \) does not shrink.
Borel–Cantelli lemmas
For events \( A_n \), \( \limsup A_n = \bigcap_{n}\bigcup_{k \ge n} A_k \) is the event “\( A_n \) occurs infinitely often”.
- First lemma. If \( \sum P(A_n) < \infty \), then \( P(A_n \text{ i.o.}) = 0 \). (No independence needed.)
- Second lemma. If the \( A_n \) are independent and \( \sum P(A_n) = \infty \), then \( P(A_n \text{ i.o.}) = 1 \).
Typical use: \( X_n \to 0 \) a.s. iff \( P(\lvert X_n \rvert > \varepsilon \text{ i.o.}) = 0 \) for every \( \varepsilon > 0 \). So for independent \( X_n \), \( X_n \to 0 \) a.s. iff \( \sum P(\lvert X_n \rvert > \varepsilon) < \infty \) for every \( \varepsilon > 0 \).
Laws of Large Numbers
Let \( S_n = X_1 + \dots + X_n \) and \( \bar{X}_n = \frac{S_n}{n} \).
| Theorem | Hypotheses | Conclusion |
|---|---|---|
| Chebyshev’s WLLN | uncorrelated, \( \text{Var}\,X_i \le C \) for all \( i \) | \( \bar{X}_n - E\bar{X}_n \xrightarrow{P} 0 \) |
| Markov’s WLLN | \( \frac{\text{Var}(S_n)}{n^2} \to 0 \) | \( \bar{X}_n - E\bar{X}_n \xrightarrow{P} 0 \) |
| Khintchine’s WLLN | i.i.d., \( E\lvert X_1 \rvert < \infty \) | \( \bar{X}_n \xrightarrow{P} \mu \) |
| Kolmogorov’s SLLN | i.i.d. | \( \bar{X}_n \xrightarrow{a.s.} \mu \) iff \( E\lvert X_1 \rvert < \infty \) (and then \( \mu = E X_1 \)) |
| Kolmogorov’s SLLN, non-identical | independent, \( \sum_n \frac{\text{Var}\,X_n}{n^2} < \infty \) | \( \bar{X}_n - E\bar{X}_n \xrightarrow{a.s.} 0 \) |
| Borel’s SLLN | i.i.d. Bernoulli(\( p \)) | \( \frac{S_n}{n} \xrightarrow{a.s.} p \) |
The proof of Chebyshev’s WLLN is one line: \( P(\lvert \bar{X}_n - E\bar{X}_n \rvert \ge \varepsilon) \le \frac{\text{Var}\,\bar{X}_n}{\varepsilon^2} \le \frac{C}{n\varepsilon^2} \to 0 \).
Using the SLLN with continuous maps. If \( X_i \) are i.i.d. and \( E\lvert g(X_1) \rvert < \infty \), then \( \frac{1}{n}\sum g(X_i) \to E\,g(X_1) \) a.s., and continuous functions of such averages converge to the function of the limits.
When the law fails. For i.i.d. standard Cauchy \( X_i \), \( \bar{X}_n \) is standard Cauchy for every \( n \) (CF: \( (e^{-\lvert t/n \rvert})^n = e^{-\lvert t \rvert} \)). It does not converge to a constant in any mode.
The Central Limit Theorem (i.i.d.)
Proof sketch (characteristic functions). Let \( Y_i = \frac{X_i - \mu}{\sigma} \), with CF \( \varphi(t) = 1 - \frac{t^2}{2} + o(t^2) \) because \( E Y = 0 \), \( E Y^2 = 1 \). The CF of \( \frac{1}{\sqrt{n}}\sum Y_i \) is
$$\varphi\left(\frac{t}{\sqrt{n}}\right)^n = \left(1 - \frac{t^2}{2n} + o\left(\frac{1}{n}\right)\right)^n \to e^{-t^2/2},$$the CF of \( N(0, 1) \). Lévy’s continuity theorem finishes the proof.
What the CLT does not say. It is a statement about distributions, not about \( S_n \) itself: \( \frac{S_n - n\mu}{\sigma\sqrt{n}} \) does not converge in probability. It needs a finite variance: for the Cauchy, no normal limit exists. For independent but non-identical summands, the Lindeberg (or Lyapunov) condition replaces “identically distributed”; the syllabus line asks only for the i.i.d. case.
De Moivre–Laplace. For \( S_n \sim \text{Binomial}(n, p) \), \( \frac{S_n - np}{\sqrt{npq}} \xrightarrow{d} N(0, 1) \). With a continuity correction for integer-valued \( S_n \):
$$P(S_n \le k) \approx \Phi\left(\frac{k + \frac{1}{2} - np}{\sqrt{npq}}\right), \qquad P(S_n \ge k) \approx 1 - \Phi\left(\frac{k - \frac{1}{2} - np}{\sqrt{npq}}\right).$$Delta method. If \( \sqrt{n}(\bar{X}_n - \mu) \xrightarrow{d} N(0, \sigma^2) \) and \( g \) is differentiable at \( \mu \) with \( g'(\mu) \ne 0 \), then \( \sqrt{n}(g(\bar{X}_n) - g(\mu)) \xrightarrow{d} N(0, g'(\mu)^2\sigma^2) \). (It is a Taylor expansion plus Slutsky; more on asymptotics belongs to the inference chapter of Unit 4.)
| \( z \) | 1 | 1.5 | 1.645 | 1.96 | 2 | 2.5 | 3 |
|---|---|---|---|---|---|---|---|
| \( \Phi(z) \) | 0.8413 | 0.9332 | 0.9500 | 0.9750 | 0.9772 | 0.9938 | 0.9987 |
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| WLLN: \( \bar{X}_n \xrightarrow{P} \mu \) | SLLN: \( \bar{X}_n \xrightarrow{a.s.} \mu \) | |
| LLN: \( \bar{X}_n - \mu \to 0 \) | CLT: \( \sqrt{n}(\bar{X}_n - \mu) \) has a normal limit law | |
| first Borel–Cantelli (any events) | second Borel–Cantelli (independent events) | |
| \( X_n \xrightarrow{d} X \) (laws only) | \( X_n \xrightarrow{P} X \) (same space, values close) | |
| Chebyshev bound \( \frac{1}{k^2} \) (any law) | normal probabilities (0.317, 0.046, 0.003 at \( k = 1, 2, 3 \)) | |
| Jensen for convex \( g \): \( g(E X) \le E g(X) \) | concave: reversed |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C of Mathematical Sciences, one or more options may be correct.
Level 1: Foundation
- \( X \ge 0 \) with \( E X = 2 \). What does Markov give for \( P(X \ge 10) \)?
- What is Chebyshev’s upper bound for \( P(\lvert X - \mu \rvert \ge 3\sigma) \)?
- Does convergence in probability imply almost-sure convergence?
Answers
- \( P(X \ge 10) \le \frac{2}{10} = 0.2 \).
- \( \frac{1}{9} \approx 0.111 \).
- No (typewriter sequence). It does along a subsequence.
Level 2: Part B Style
Practice Q1. \( X \) has mean 50 and standard deviation 5. Chebyshev’s inequality gives the best lower bound for \( P(40 < X < 60) \) as:
(a) 0.25 (b) 0.75 (c) 0.95 (d) 0.89
Answer: (b)
\( 40 < X < 60 \) is \( \lvert X - 50 \rvert < 10 = 2\sigma \). So \( P \ge 1 - \frac{1}{4} = 0.75 \). (c) is the normal value (about 0.954), not a bound valid for every distribution; (d) is the \( k = 3 \) bound.
Practice Q2. \( X_1, X_2, \dots \) are i.i.d. \( U(0, 1) \). Almost surely, \( (X_1X_2\cdots X_n)^{1/n} \) converges to:
(a) \( \frac{1}{2} \) (b) \( \frac{1}{e} \) (c) 0 (d) \( \frac{1}{\sqrt{e}} \)
Answer: (b)
SLLN on \( \log X_i \): \( \frac{1}{n}\sum\log X_i \to \int_0^1 \log x\,dx = -1 \). (a) wrongly treats the geometric mean as the arithmetic mean.
Practice Q3. A fair coin is tossed 100 times. Using the normal approximation with continuity correction, \( P(\text{at least 60 heads}) \) is closest to:
(a) 0.023 (b) 0.029 (c) 0.046 (d) 0.16
Answer: (b)
\( 1 - \Phi\left(\frac{59.5 - 50}{5}\right) = 1 - \Phi(1.9) \approx 0.0287 \). (a) omits the correction; (c) is the two-sided tail \( 2(1 - \Phi(2)) \); (d) is the one-sided tail at one standard deviation.
Practice Q4. \( X \) is a positive random variable with \( E X = 2 \) and \( E\frac{1}{X} < \infty \). Which must be true?
(a) \( E\frac{1}{X} = \frac{1}{2} \) (b) \( E\frac{1}{X} \ge \frac{1}{2} \) (c) \( E\frac{1}{X} \le \frac{1}{2} \) (d) \( E\log X \ge \log 2 \)
Answer: (b)
\( \frac{1}{x} \) is convex on \( (0, \infty) \), so Jensen gives \( E\frac{1}{X} \ge \frac{1}{E X} \). (d) has the inequality backwards: \( \log \) is concave, so \( E\log X \le \log 2 \).
Level 3: Part C Style
Practice Q5. Let \( X_n \) be independent with \( P(X_n = n) = \frac{1}{n} \) and \( P(X_n = 0) = 1 - \frac{1}{n} \). Which statements are true?
(a) \( X_n \to 0 \) in probability. (b) \( E X_n \to 0 \). (c) \( X_n \to 0 \) almost surely. (d) \( E\sqrt{X_n} \to 0 \).
Answer: (a) and (d)
- (a) True. \( P(X_n \ne 0) = \frac{1}{n} \to 0 \).
- (b) False. \( E X_n = 1 \) for every \( n \).
- (c) False. The events \( \{X_n = n\} \) are independent with \( \sum \frac{1}{n} = \infty \); by the second Borel–Cantelli lemma \( X_n = n \) infinitely often, almost surely.
- (d) True. \( E\sqrt{X_n} = \frac{\sqrt{n}}{n} = n^{-1/2} \to 0 \): convergence in \( L^{1/2} \).
Practice Q6. \( X_1, X_2, \dots \) are i.i.d. with mean 0 and variance 1; \( S_n = X_1 + \dots + X_n \). Which statements are true?
(a) \( \frac{S_n}{n} \to 0 \) almost surely. (b) \( \frac{S_n}{\sqrt{n}} \xrightarrow{d} N(0, 1) \). (c) \( \frac{S_n}{\sqrt{n}} \) converges in probability. (d) \( P(S_n > 0) \to \frac{1}{2} \).
Answer: (a), (b) and (d)
- (a) True. Kolmogorov’s SLLN (finite mean).
- (b) True. Lindeberg–Lévy CLT.
- (c) False. If \( \frac{S_n}{\sqrt{n}} \to Z \) in probability, then \( D_n = \frac{S_{2n}}{\sqrt{2n}} - \frac{S_n}{\sqrt{n}} \to 0 \) in probability. But \( D_n = \left(\frac{1}{\sqrt{2}} - 1\right)\frac{S_n}{\sqrt{n}} + \frac{S_{2n} - S_n}{\sqrt{2n}} \), a sum of two independent terms, which by the CLT converges in distribution to \( N\left(0, \left(\frac{1}{\sqrt{2}} - 1\right)^2 + \frac{1}{2}\right) = N(0, 2 - \sqrt{2}) \), not to 0.
- (d) True. \( P\left(\frac{S_n}{\sqrt{n}} > 0\right) \to 1 - \Phi(0) = \frac{1}{2} \), since 0 is a continuity point of the normal CDF.
Practice Q7. The number of defects on an item has mean 2 and variance 2. A batch of 200 items is inspected, items being independent; let \( T \) be the total number of defects. Which statements are true?
(a) Chebyshev’s inequality gives \( P(\lvert T - 400 \rvert \ge 40) \le \frac{1}{4} \). (b) The CLT approximation (without continuity correction) gives \( P(T > 440) \approx 0.023 \). (c) Markov’s inequality gives \( P(T \ge 800) \le \frac{1}{2} \). (d) Chebyshev’s inequality gives \( P(\lvert T - 400 \rvert \ge 40) \le 0.05 \).
Answer: (a), (b) and (c)
\( E T = 400 \), \( \text{Var}\,T = 400 \), \( \sigma_T = 20 \).
- (a) True. \( \frac{400}{40^2} = \frac{1}{4} \) (\( k = 2 \)).
- (b) True. \( 1 - \Phi\left(\frac{440 - 400}{20}\right) = 1 - \Phi(2) \approx 0.0228 \).
- (c) True. \( \frac{E T}{800} = \frac{1}{2} \).
- (d) False. 0.05 is roughly the normal two-sided tail at \( 2\sigma \) (about 0.046); Chebyshev, valid for every distribution, gives only 0.25.
Quick Revision Table
| Idea | Fact |
|---|---|
| Markov | \( P(X \ge a) \le \frac{E X}{a} \), \( X \ge 0 \) |
| Chebyshev | \( P(\lvert X - \mu \rvert \ge k\sigma) \le \frac{1}{k^2} \) |
| Cantelli | \( P(X - \mu \ge \lambda) \le \frac{\sigma^2}{\sigma^2 + \lambda^2} \) |
| Jensen | convex \( g \): \( g(E X) \le E g(X) \) |
| Lyapunov | \( (E\lvert X \rvert^r)^{1/r} \) non-decreasing in \( r \) |
| Modes | a.s. \( \Rightarrow \) P; \( L^r \Rightarrow \) P; P \( \Rightarrow \) d; d to a constant \( \Rightarrow \) P |
| Borel–Cantelli | \( \sum P(A_n) < \infty \Rightarrow \) finitely often; independent and \( = \infty \Rightarrow \) i.o. |
| Slutsky | \( X_n \xrightarrow{d} X \), \( Y_n \xrightarrow{P} c \Rightarrow X_n + Y_n \xrightarrow{d} X + c \), etc. |
| WLLN | i.i.d. finite mean (Khintchine); bounded variances (Chebyshev) |
| SLLN | i.i.d.: \( \bar{X}_n \to \mu \) a.s. iff \( E\lvert X_1 \rvert < \infty \) |
| CLT | i.i.d., \( \sigma^2 < \infty \): \( \frac{S_n - n\mu}{\sigma\sqrt{n}} \xrightarrow{d} N(0, 1) \) |
| Continuity correction | \( \pm\frac{1}{2} \) for integer-valued sums |
| Cauchy | \( \bar{X}_n \) is Cauchy for every \( n \): no LLN, no CLT |
Key Takeaways
What’s Next
- Probability Theory: Quick Revision: the whole chapter on one page.
- Back to the Probability Theory chapter overview for the official syllabus map.
- Joint, Marginal and Conditional Distributions; Characteristic Functions to revise Lévy’s continuity theorem, the key tool in the CLT proof.
- The Mathematical Sciences overview lists the other Unit 4 chapters (Markov chains, distributions and inference, linear models, sampling and design, reliability and operations research). Markov chains build directly on the conditional probability and limit ideas of this chapter.