Limit Theorems and Markov Chains

1. Modes of convergence, WLLN, SLLN, CLT

Exam focus: Know the implication diagram and one counterexample per missing arrow. The typewriter sequence and the moving-bump are the two you need.

Lec-39 Modes of convergence

NPTEL · Measure and Integration

The implication diagram, done measure-theoretically.

Lec-40 Convergence in Measure

NPTEL · Measure and Integration

Lec-04 Problems in Sequences of Random Variables

NPTEL · Stochastic Processes

Worked problems on LLN and CLT-type limits.

Modes of convergence and the limit theorems free

The diagram

   L^p  ──────▶  probability  ──────▶  distribution
                     ▲
almost sure ─────────┘

No other arrows hold in general. Partial converses:

convergence in probability ⇒ an a.s. convergent subsequence;
convergence in distribution to a constant ⇒ convergence in probability;
probability + uniform integrability $\Rightarrow L^{1}$ ; $- \sum P ($ | $X_{n} - X$ | $> ε) < \infty \Rightarrow a . s . ($ Borel–Cantelli).

The counterexamples

Missing arrow	Example
probability ⇏ a.s.	typewriter: indicators of $[k / 2^{n}, (k + 1) / 2^{n}]$ sweeping [0,1]
a.s. ⇏ $L^{1}$	$X_{n} = n \cdot 1_{(0, 1/ n)}$ : $\to 0 a . s ., E [X_{n}] = 1$
probability ⇏ $L^{1}$	same
distribution ⇏ probability	X ~ $N (0, 1), X_{n} = - X$ for all n
$L^{1}$ ⇏ a.s.	typewriter again

Laws of large numbers

WLLN (in probability) needs finite mean; SLLN (a.s.) also holds with finite mean (Kolmogorov).
Fails without a mean: the Cauchy sample mean has the same Cauchy distribution for every n.

Central limit theorem

$n (\overset{ˉ}{X} - μ) / σ \to N (0, 1)$ whenever $σ^{2} < \infty$ . Consequences examined: $- P (S_{n} \leq n μ) \to$ ½, so intervals with the mean as an endpoint have limiting probability ½, while intervals containing $μ$ in the interior have probability → 1.

Delta method: $n (g (\overset{ˉ}{X}) - g (μ)) \to N (0, σ^{2} g^{'} (μ)^{2})$ .
Slutsky: $X_{n} \Rightarrow X$ and $Y_{n} \to c$ in probability $\Rightarrow X_{n} + Y_{n} \Rightarrow X + c, X_{n} Y_{n} \Rightarrow$ cX.

Key takeaways

a.s. and L^p both imply probability, which implies distribution; nothing else.
Typewriter kills "probability ⇒ a.s."; n· $1_{(0, 1/ n)}$ kills " $a . s . \Rightarrow L^{1}$ ".
CLT at the boundary gives ½ — a favourite Part-C trick.

Part B2023 Decembershow ▾

Let

X_{1}, X_{2}, \dots

be i.i.d. with CDF F(x) = 0 for x < 5 and 1 −

e^{5 - x}

for x ≥ 5. Define

Y_{n} = min

{

X_{1}, \dots, X_{n}

} and

Z_{n} = n (Y_{n} - 5)

, and let Z be standard normal. Which one of the following statements is true?

A. $lim P (1/2 < Y_{n} < 3/2) = 1$
B. $Y_{n} \to 5$ in probability as $n \to \infty$ ✓
C. $Z_{n} \to Z$ in distribution as $n \to \infty$
D. $lim P (1 < Z_{n} < 2) = Φ (2) - Φ (1)$

Solution

$Y_{n} - 5$ ~ Exp(n), so $Y_{n} \to 5$ in probability while $n (Y_{n} - 5) \to 0$ in probability (the right scaling is n, not $n)$ .

Save for spaced revision (free account)

Part C2023 Juneshow ▾

Suppose

X_{1}, X_{2}, \dots

are independent and identically distributed N(0,1) random variables and

Y_{n} = X_{1}^{4} + X_{2}^{4} + \dots + X_{n}^{4}

. Which of the following probabilities converge to 1/2 as

n \to \infty

A.P{ $Y_{n} \in [0, 2 n]$ }
B.P{ $Y_{n} \in [n, 3 n]$ }✓
C.P{ $Y_{n} \in [2 n, 4 n]$ }
D.P{ $Y_{n} \in [3 n, 5 n]$ }✓

Solution

$E [X^{4}] = 3$ , so $Y_{n} / n \to 3 ($ LLN) and $(Y_{n} - 3 n) / n$ is asymptotically normal (CLT). Intervals with 3n as an endpoint have probability → 1/2; [2n, 4n] contains 3n in its interior (→ 1); [0, 2n] excludes it (→ 0).

Save for spaced revision (free account)

Part Bshow ▾

X_{n} \to X

in probability, then necessarily

A. $X_{n} \to X$ almost surely
B. $X_{n} \to X$ in distribution✓
C.E| $X_{n} - X$ | → 0
D. $X_{n} \to X$ in $L^{2}$

Solution

Convergence in probability implies convergence in distribution; the other implications fail in general.

Save for spaced revision (free account)

Part Cshow ▾

Let

X_{1}, X_{2}, \dots

and X be random variables on a common probability space. Which of the following implications hold in general?

A. $X_{n} \to X$ almost surely ⟹ $X_{n} \to X$ in probability.✓
B. $X_{n} \to X$ in probability ⟹ $X_{n} \to X$ almost surely.
C. $X_{n} \to X$ in probability ⟹ $X_{n} \to X$ in distribution.✓
D. $X_{n} \to X$ in distribution ⟹ $X_{n} \to X$ in probability.

Solution

The standard hierarchy is: almost sure ⟹ in probability ⟹ in distribution, and no arrow reverses in general. (2) Fails for the sliding-block ('typewriter') sequence of indicators on [0,1], which tends to 0 in probability while diverging at every point. (4) Fails whenever the limit is not degenerate: take X ~ N(0,1) and $X_{n} = - X$ for all n. Then $X_{n}$ has the same distribution as X for every n, so $X_{n} \to X$ in distribution, yet | $X_{n} - X$ | = 2|X| does not tend to 0 in probability. Convergence in distribution does imply convergence in probability when the limit is a constant.

Save for spaced revision (free account)

Part Cshow ▾

Let

X_{1}, X_{2}, \dots

be i.i.d. with E|

X_{1}

< \infty, E X_{1} = μ

, and

\overset{ˉ}{S}_{n} = (X_{1} + \dots + X_{n}) / n

. Which of the following are true?

A. $\overset{ˉ}{S}_{n} \to μ$ almost surely.✓
B.If additionally $0 < V a r X_{1} = σ^{2} < \infty$ , then $n (\overset{ˉ}{S}_{n} - μ) / σ$ converges in distribution to N(0, 1).✓
C.Under the assumptions of option $2, \overset{ˉ}{S}_{n} - μ = O_{p} (n^{- 1/2})$ , so $\overset{ˉ}{S}_{n} \to μ$ in probability.✓
D.The strong law of large numbers requires finite variance.

Solution

(1) Kolmogorov's strong law needs only a finite first moment. (2) is the classical CLT. (3) tightness of $n (\overset{ˉ}{S}_{n} - μ)$ forces $\overset{ˉ}{S}_{n} - μ \to 0$ in probability. (4) fails — finite mean suffices for the SLLN; finite variance is a hypothesis of the CLT, not of the strong law.

Save for spaced revision (free account)

2. Markov chains: classification of states, stationary distributions

Exam focus: Classify states (recurrent/transient, periodicity), then use irreducible + aperiodic + positive recurrent ⇒ unique stationary distribution with πⱼ = 1/mⱼⱼ.

Lec-01 Introduction, Definition and Transition Probability Matrix

NPTEL · Stochastic Processes

Lec-03 Classification of States and Limiting Distributions

NPTEL · Stochastic Processes

Recurrence, transience and periodicity as class properties.

Lec-04 Limiting and Stationary Distributions

NPTEL · Stochastic Processes

Where aperiodicity is needed for convergence.

Limit Theorems and Markov Chains

1. Modes of convergence, WLLN, SLLN, CLT

The Central Limit Theorem, watchedinteractivefree

Modes of convergence and the limit theorems free

The diagram

The counterexamples

Laws of large numbers

Central limit theorem

Key takeaways

2. Markov chains: classification of states, stationary distributions

Why periodic chains never settleinteractive

Markov chains: classification and stationary behaviour

Classification