2018.Q5 — Random Walks, Stopping Times, and Invariance Principle
2018 Probability Prelim Exam (PDF)
Let ${B_t, t \ge 0}$ be standard Brownian motion.
Let $X_1, X_2, \ldots$ be i.i.d. random variables with
\(\mathbb E[X]=0, \qquad \mathbb E[X^2]<\infty.\) Define \(S_n = \sum_{k=1}^n X_k.\) Let $0<T_1<T_2<\cdots$ be a sequence of stopping times such that
- $S_n \overset{d}{=} B_{T_n}$, for all $n\ge1$.
- ${T_1,\; T_2-T_1,\; T_3-T_2,\ldots}$ are i.i.d.
- $\mathbb E[T_1] = \mathbb E[X^2]$.
(a) Show that $T_n/n \to \mathbb E[X^2]$ a.s.
(b) For $n\ge1$, let
\(W_n(t) = \frac{B(nt)}{\sqrt n},\qquad t\ge0.\) Prove $W_n$ is standard Brownian motion, and show
\(W_n\!\left(\frac{T_n}{n}\right) \overset{d}{=} \frac{S_n}{\sqrt n}.\)(c) Let ${H, Y_n, Z_n : n \ge 1}$ be random variables.
Prove: if $Y_n - Z_n \xrightarrow{p} 0$ and $Z_n \xrightarrow{d} H$, then
$Y_n \xrightarrow{d} H$.(d) Conclude that
\(\frac{S_n}{\sqrt n} \xrightarrow{d} N\bigl(0,\mathbb E[X^2]\bigr).\)
Part (a)
Claim
\(\frac{T_n}{n} \to \mathbb E[X^2] \qquad \text{a.s.}\)
Proof
Define
\(Y_1 = T_1,\qquad
Y_k = T_k - T_{k-1},\quad k\ge2.\)
By assumption (2), ${Y_k}$ are i.i.d.
Also,
\(\mathbb E[Y_k] = \mathbb E[T_1] = \mathbb E[X^2] < \infty.\)
Because \(T_n = Y_1 + \cdots + Y_n,\) we may rewrite \(\frac{T_n}{n} = \frac{1}{n}\sum_{k=1}^n Y_k.\)
Since ${Y_k}$ are i.i.d. with finite mean, the Strong Law of Large Numbers (SLLN) gives \(\frac{1}{n}\sum_{k=1}^n Y_k \;\xrightarrow{\text{a.s.}}\; \mathbb E[Y_1] = \mathbb E[T_1] = \mathbb E[X^2].\)
Conclusion
\(\boxed{\displaystyle \frac{T_n}{n} \to \mathbb E[X^2] \text{ a.s.}}\)
Key Ideas
- Representation $T_n=\sum Y_k$.
- Apply SLLN to the i.i.d. increments $T_k-T_{k-1}$.
- Use hypothesis $\mathbb E[T_1]=\mathbb E[X^2]$.
Part (b)
Claim 1
$W_n(t)=B(nt)/\sqrt n$ is standard Brownian motion.
Proof
Check the four defining properties:
-
Starts at zero
\(W_n(0)=\frac{B(0)}{\sqrt n}=0.\) -
Continuous paths
Brownian motion has continuous paths, and rescaling preserves continuity. -
Independent increments
\(W_n(t)-W_n(s)=\frac{B(nt)-B(ns)}{\sqrt n}.\) Since Brownian increments are independent, the difference above is independent of the past. -
Correct variance scaling
Using Brownian scaling: \(B(nt) - B(ns) \sim N(0,\, n(t-s)).\) Hence \(W_n(t)-W_n(s) \sim N\!\left(0,\frac{n(t-s)}{n}\right) = N(0,t-s).\)
Thus $W_n$ satisfies all defining properties of standard Brownian motion.
Claim 2
\(W_n\!\left(\frac{T_n}{n}\right) \overset{d}{=} \frac{S_n}{\sqrt n}.\)
Proof
Compute: \(W_n\!\left(\frac{T_n}{n}\right) = \frac{B\!\left(n\frac{T_n}{n}\right)}{\sqrt n} = \frac{B(T_n)}{\sqrt n}.\) By assumption (1), \(B(T_n) \overset{d}{=} S_n.\) Hence \(\frac{B(T_n)}{\sqrt n} \overset{d}{=} \frac{S_n}{\sqrt n}.\)
Conclusion
\(\boxed{ W_n\!\left(\frac{T_n}{n}\right) \overset{d}{=} \frac{S_n}{\sqrt n} }\)
Key Ideas
- Brownian scaling: $B(ct)\overset{d}{=}\sqrt c\,B(t)$.
- Time-change: evaluating Brownian motion at a random time.
- Given identity: $S_n \overset{d}{=} B_{T_n}$.
Part (c)
Claim
If $Y_n - Z_n \xrightarrow{p} 0$ and $Z_n \xrightarrow{d} H$, then $Y_n\xrightarrow{d}H$.
Proof
Let $f$ be any bounded continuous function. Then \(\mathbb E[f(Y_n)] - \mathbb E[f(Z_n)] = \mathbb E\!\big[f(Y_n)-f(Z_n)\big].\)
Write \(|f(Y_n)-f(Z_n)| = |f(Y_n)-f(Z_n)|\mathbf 1_{\{|Y_n-Z_n|<\delta\}} + |f(Y_n)-f(Z_n)|\mathbf 1_{\{|Y_n-Z_n|\ge\delta\}}.\)
Term (1): continuity.
If $|Y_n-Z_n|<\delta$, continuity of $f$ gives
$|f(Y_n)-f(Z_n)| < \varepsilon$.
Hence
\(\mathbb E[|f(Y_n)-f(Z_n)|\mathbf1_{\{|Y_n-Z_n|<\delta\}}]
\le \varepsilon.\)
Term (2): boundedness.
Since $f$ is bounded, $|f|\le M$. Then
\(|f(Y_n)-f(Z_n)|\le2M\)
and
\(\mathbb E[|f(Y_n)-f(Z_n)|\mathbf1_{\{|Y_n-Z_n|\ge\delta\}}]
\le
2M\,\mathbb P(|Y_n-Z_n|\ge\delta).\)
But $Y_n-Z_n\xrightarrow{p}0$, so this probability $\to0$.
Combining both terms:
\(\limsup_n |\mathbb E[f(Y_n)]-\mathbb E[f(Z_n)]|
\le\varepsilon.\)
Since $\varepsilon$ is arbitrary,
\(\mathbb E[f(Y_n)]-\mathbb E[f(Z_n)]\to0.\)
Given $Z_n\xrightarrow{d}H$, we have $\mathbb E[f(Z_n)]\to\mathbb E[f(H)]$.
Thus
\(\mathbb E[f(Y_n)]\to\mathbb E[f(H)].\)
By the Portmanteau theorem, this proves $Y_n\xrightarrow{d}H$.
Conclusion
\(\boxed{Y_n \xrightarrow{d} H.}\)
Key Ideas
- Standard “Slutsky-type” argument using bounded continuous test functions.
- Split expectation into “small difference” + “tail” terms.
- Boundedness controls the tail; continuity controls the small difference set.
Part (d)
Claim
\(\frac{S_n}{\sqrt n} \xrightarrow{d} N\bigl(0,\mathbb E[X^2]\bigr).\)
Proof
From part (b), \(\frac{S_n}{\sqrt n} \overset{d}{=} W_n\!\left(\frac{T_n}{n}\right).\)
From part (a), \(\frac{T_n}{n} \xrightarrow{\text{a.s.}} \mathbb E[X^2] =: t.\)
Brownian motion has continuous sample paths, so for each fixed $n$, \(W_n\!\left(\frac{T_n}{n}\right) - W_n(t) \to 0 \quad \text{a.s.}\) Hence also in probability.
But since $W_n$ is SBM, \(W_n(t) \sim N(0,t)=N\bigl(0,\mathbb E[X^2]\bigr).\)
Part (c) now applies:
- Let $Y_n = W_n(T_n/n)$.
- Let $Z_n = W_n(t)$.
- Let $H \sim N(0,\mathbb E[X^2])$.
We showed:
- $Y_n - Z_n \xrightarrow{p}0$.
- $Z_n \xrightarrow{d}H$.
Thus \(Y_n \xrightarrow{d}H.\)
Using the identity from part (b), \(\frac{S_n}{\sqrt n} \overset{d}{=} Y_n,\) so \(\frac{S_n}{\sqrt n} \xrightarrow{d} N(0,\mathbb E[X^2]).\)
Conclusion
\(\boxed{ \frac{S_n}{\sqrt n} \;\Longrightarrow\; N(0,\mathbb E[X^2]). }\)
Key Ideas
- Representing $S_n$ as a Brownian motion evaluated at a random time.
- Using the strong law for $T_n/n$.
- Continuity of Brownian paths.
- Applying part (c): convergence in distribution is stable under small-probability perturbations.
- Final form is a functional CLT–style argument using a time-change.
Full Summary
This problem cleverly replaces classical CLT machinery with:
- Time-change representation $S_n \overset{d}{=} B_{T_n}$.
- SLLN on stopping times to identify the limiting variance.
- Brownian scaling to interpret $\frac{S_n}{\sqrt n}$.
- A Slutsky-type lemma (part (c)) to transfer convergence.
- Continuity of Brownian motion, ensuring the time-change is well behaved.
Use this question as a template: whenever a problem expresses a discrete process as Brownian motion at random times, the entire convergence problem often reduces to showing that the time-change converges.
Comments