2022.Q6: Random Walk Exit Times and Exponential Martingales
(Random Walks, Exponential Martingales, Optional Stopping)
2022 Probability Prelim Exam (PDF)
Problem Statement (verbatim from Prob_F22)
Let ${X, X_k}_{k\ge1}$ be an i.i.d. sequence of real-valued random variables. Define \(S_n = \sum_{k=1}^n X_k, \quad n=1,2,\ldots, \qquad S_0=0,\) and assume \(d = \mathbb E(e^X), \qquad 1<d<\infty.\) Let $a,b$ be constants such that \(-\infty < a < 0 < b < \infty,\) and define the stopping time \(T=\inf\{n\ge1 : S_n\le a \text{ or } S_n\ge b\}.\)
(a) Prove that $T<\infty$ almost surely. (Prove by theorem quote.)
Let $\mathcal F_n=\sigma(X_1,\dots,X_n)$ and define \(Y_n = d^{-n}e^{S_n}, \qquad n=1,2,\dots\)
(b)
(i) Show that ${Y_n,\mathcal F_n}$ is a martingale and that $\lim_{n\to\infty}Y_n<\infty$ a.s.
(ii) Show that $T$ is a stopping time and that ${Y_{n\wedge T},\mathcal F_n}$ is a martingale.
| Now assume additionally that $ | X | <C$ a.s. for some finite constant $C$. |
(c)
(i) Show that
\(|S_{n\wedge T}|\le C+\max\{|a|,b\}, \qquad n=1,2,\dots\)
(ii) Compute $\mathbb E(Y_T)$.
Part (a)
Claim
\(T<\infty \quad \text{almost surely}.\)
Proof
For a random walk $S_n=\sum_{k=1}^n X_k$, exactly one of the following four possibilities occurs almost surely:
- $S_n=0$ for all $n$,
- $S_n\to\infty$,
- $S_n\to-\infty$,
- $-\infty=\liminf S_n < \limsup S_n=\infty$.
Since we assume $d=\mathbb E(e^X)>1$, the increments cannot satisfy $X\equiv 0$ a.s. Indeed, if $X\equiv0$, then $e^X=1$ a.s. and hence $\mathbb E(e^X)=1$, contradicting $d>1$. Thus case (1) is ruled out.
- In case (2), $S_n\to\infty$, so the event ${S_n\ge b}$ must occur for some finite $n$.
- In case (3), $S_n\to-\infty$, so the event ${S_n\le a}$ must occur for some finite $n$.
- In case (4), $\limsup S_n=\infty$ and $\liminf S_n=-\infty$, so the walk attains arbitrarily large positive and negative values. Hence it must hit either ${S_n\ge b}$ or ${S_n\le a}$ in finite time.
In all remaining cases, the defining event of $T$ occurs in finite time. Therefore, \(T<\infty \quad \text{a.s.}\)
Conclusion
\(T<\infty \quad \text{almost surely}.\)
Key Takeaways
- Random walk trichotomy / oscillation theorem (Durrett, Chapter 4).
- The assumption $\mathbb E(e^X)>1$ is used only to rule out the degenerate case $X\equiv0$.
- Once oscillation or drift is established, exiting any bounded interval is automatic.
Part (b)(i)
Claim
${Y_n,\mathcal F_n}$ is a martingale and $\lim_{n\to\infty}Y_n<\infty$ almost surely.
Proof
Step 1: Adaptedness
\(Y_n = d^{-n}e^{S_n},\) where $d$ is a constant and $S_n=\sum_{k=1}^n X_k$ is $\mathcal F_n$-measurable. Hence $Y_n$ is $\mathcal F_n$-measurable.
Step 2: Integrability
Since $Y_n\ge0$, \(\mathbb E|Y_n|=\mathbb E(Y_n) = d^{-n}\mathbb E(e^{S_n}) = d^{-n}\prod_{k=1}^n\mathbb E(e^{X_k}) = d^{-n}d^n =1<\infty.\)
Step 3: Martingale property
Using independence of $X_n$ from $\mathcal F_{n-1}$, \(\begin{aligned} \mathbb E(Y_n\mid\mathcal F_{n-1}) &= d^{-n}\mathbb E(e^{S_{n-1}+X_n}\mid\mathcal F_{n-1}) \\ &= d^{-n}e^{S_{n-1}}\mathbb E(e^{X_n}) \\ &= d^{-(n-1)}e^{S_{n-1}} =Y_{n-1}. \end{aligned}\) Thus ${Y_n,\mathcal F_n}$ is a martingale.
Step 4: Almost sure convergence
Since $Y_n\ge0$ and $\mathbb E(Y_n)=1$ for all $n$, $(Y_n)$ is a nonnegative $L^1$-bounded martingale. By the martingale convergence theorem for nonnegative martingales, \(Y_n\to Y_\infty<\infty \quad \text{a.s.}\)
Conclusion
\(\{Y_n,\mathcal F_n\} \text{ is a martingale and } Y_n\to Y_\infty<\infty \text{ a.s.}\)
Key Takeaways
- Exponential martingale construction: $d^{-n}e^{S_n}$.
- Independence allows conditional expectations to factor cleanly.
- Nonnegativity + bounded expectation gives a.s. convergence (no UI needed).
Part (b)(ii)
Claim
$T$ is a stopping time and ${Y_{n\wedge T},\mathcal F_n}$ is a martingale.
Proof
Step 1: $T$ is a stopping time
For each $n$, \(\{T\le n\} =\bigcup_{k=1}^n\{S_k\le a \text{ or } S_k\ge b\} =\bigcup_{k=1}^n(\{S_k\le a\}\cup\{S_k\ge b\}).\) Since $S_k$ is $\mathcal F_k$-measurable and $\mathcal F_k\subseteq\mathcal F_n$ for $k\le n$, each event belongs to $\mathcal F_n$. Hence ${T\le n}\in\mathcal F_n$ and $T$ is a stopping time.
Step 2: Stopped process is a martingale
Since constants are stopping times and the minimum of stopping times is a stopping time, $n\wedge T$ is a stopping time. Because $Y_n$ is a martingale, the stopped process ${Y_{n\wedge T},\mathcal F_n}$ is also a martingale.
Conclusion
\(T \text{ is a stopping time and } \{Y_{n\wedge T},\mathcal F_n\} \text{ is a martingale}.\)
Key Takeaways
- Hitting times of adapted processes are stopping times.
- Closure properties of stopping times are essential.
- Stopped martingales remain martingales.
Part (c)(i)
Claim
If $|X|<C$ a.s., then \(|S_{n\wedge T}|\le C+\max\{|a|,b\} \quad \text{a.s.}\)
Proof
Consider two cases.
Case 1: $n<T$.
By definition of $T$, $a<S_n<b$. Hence
\(|S_n|\le\max\{|a|,b\}\le C+\max\{|a|,b\}.\)
Case 2: $n\ge T$.
Then $S_{n\wedge T}=S_T$. Since $a<S_{T-1}<b$ and
\(S_T=S_{T-1}+X_T, \quad |X_T|<C,\)
we have
\(a-C\le S_T\le b+C.\)
Thus
\(|S_T|\le C+\max\{|a|,b\}.\)
Combining both cases yields the result.
Conclusion
\(|S_{n\wedge T}|\le C+\max\{|a|,b\} \quad \text{a.s.}\)
Key Takeaways
- Bounded increments imply bounded overshoot.
- Splitting into $n<T$ and $n\ge T$ is standard for stopped processes.
Part (c)(ii)
Claim
\(\mathbb E(Y_T)=1.\)
Proof
From part (c)(i), \(0\le Y_{n\wedge T} = d^{-(n\wedge T)}e^{S_{n\wedge T}} \le e^{S_{n\wedge T}} \le \exp\!\big(C+\max\{|a|,b\}\big),\) a finite constant. Thus $(Y_{n\wedge T})$ is uniformly bounded.
Since $T<\infty$ a.s., $Y_{n\wedge T}\to Y_T$ a.s. By dominated convergence, \(\mathbb E(Y_T)=\lim_{n\to\infty}\mathbb E(Y_{n\wedge T}).\) But ${Y_{n\wedge T}}$ is a martingale, so \(\mathbb E(Y_{n\wedge T})=\mathbb E(Y_0)=1.\) Hence $\mathbb E(Y_T)=1$.
Conclusion
\(\boxed{\mathbb E(Y_T)=1}.\)
Key Takeaways
- Optional stopping via dominated convergence, not Wald.
- Bounded overshoot is the technical condition enabling the limit.
- Exponential martingales + stopping times are a recurring prelim pattern.
Final Meta-Takeaway
This problem is a complete template for:
- random walk exit times,
- exponential martingales,
- stopping times,
- and safe optional stopping.
If you see $d^{-n}e^{S_n}$, think:
“Nonnegative martingale → stop → dominate → pass limit.”
Comments