Edit this page on GitHub

2023-Q5 - Optional stopping for a simple symmetric random walk

2023 Probability Prelim Exam (PDF)

Problem statement

Let ${\varepsilon, \varepsilon_k: k = 1,2, \dots}$ be i.i.d. random variables with
\(P(\varepsilon = \pm 1) = \frac12.\)

Let \(S_n = \sum_{k=1}^n \varepsilon_k, \quad n = 1,2,\dots, \quad S_0 = 0\) (so ${S_n}$ is a simple symmetric random walk).

Let ${\mathcal{F}_n: n = 0,1,\dots}$ be the natural filtration of ${S_n}$.

Finally, let \(\tau = \min\{n : S_n = 1\}.\)

(a)

(i) Prove that $\tau$ is a stopping time with respect to ${\mathcal{F}_n}$.

(ii) Let ${H_n: n = 1,2,\dots}$ be a bounded sequence of random variables with
$H_n \in \mathcal{F}_{n-1}$ for all $n \ge 1$. Prove that \(M_n := \sum_{k=1}^n H_k \varepsilon_k\) is a martingale with respect to ${\mathcal{F}_n}$.

(b)

(i) Prove that ${S_{n \wedge \tau}, \mathcal{F}_n}$ is a martingale. Do this by using part (a)(ii) with an appropriate choice of ${H_n}$.

(ii) Prove that $S_{n \wedge \tau}$ converges a.s. as $n \to \infty$.

(c)

(i) Identify the distribution of the limit of $S_{n \wedge \tau}$ as $n \to \infty$.

(ii) Prove that ${S_{n \wedge \tau}}$ is not uniformly integrable.

Solution :contentReference[oaicite:1]{index=1}

I keep your structure and main ideas, but fill in details and clean up some logic.

(a)(i) $\tau$ is a stopping time

Claim.

$\tau = \min{n : S_n = 1}$ is a stopping time with respect to ${\mathcal{F}_n}$.

Proof.

We need to show that for each fixed $n$, \(\{\tau \le n\} \in \mathcal{F}_n.\)

By definition, \(\{\tau \le n\} = \{\omega : \tau(\omega) \le n\} = \{\exists\, k \le n : S_k = 1\} = \bigcup_{k=1}^n \{S_k = 1\}.\)

For each $k\le n$, $S_k$ is $\mathcal{F}_k$-measurable and $\mathcal{F}_k \subseteq \mathcal{F}_n$ (filtration is increasing), so \(\{S_k = 1\}\in \mathcal{F}_k\subseteq\mathcal{F}_n.\)

Therefore, the union \(\{\tau \le n\} = \bigcup_{k=1}^n \{S_k = 1\}\) is also in $\mathcal{F}_n$.

Conclusion.

$\tau$ is a stopping time with respect to ${\mathcal{F}_n}$.

(a)(ii) A general martingale of the form $\sum H_k \varepsilon_k$

Claim.

If ${H_n}$ is bounded and $H_n \in \mathcal{F}_{n-1}$, then \(M_n := \sum_{k=1}^n H_k \varepsilon_k\) is a martingale with respect to ${\mathcal{F}_n}$.

Proof.

We check the three martingale conditions.

  1. Adaptedness.
    For each $n$, \(M_n = \sum_{k=1}^n H_k \varepsilon_k.\) For each $k\le n$, $H_k \in \mathcal{F}_{k-1}\subseteq\mathcal{F}_k$ and $\varepsilon_k$ is $\mathcal{F}_k$-measurable, so $H_k\varepsilon_k\in\mathcal{F}_k\subseteq\mathcal{F}_n$.
    A finite sum of $\mathcal{F}_n$-measurable random variables is $\mathcal{F}_n$-measurable, hence $M_n$ is $\mathcal{F}_n$-measurable.

  2. Integrability.
    Since $H_k$ is bounded, say $|H_k|\le C$, and $|\varepsilon_k|=1$, \(|M_n| =\left|\sum_{k=1}^n H_k\varepsilon_k\right| \le \sum_{k=1}^n |H_k||\varepsilon_k| \le \sum_{k=1}^n C = nC.\) Thus $E|M_n| \le nC < \infty$.

  3. Martingale property.
    For $n\ge 0$, \(M_{n+1}=M_n + H_{n+1}\varepsilon_{n+1}.\) So \(E(M_{n+1} \mid \mathcal{F}_n) = E(M_n + H_{n+1}\varepsilon_{n+1} \mid \mathcal{F}_n) = M_n + E(H_{n+1}\varepsilon_{n+1} \mid \mathcal{F}_n).\)

    Since $H_{n+1}\in \mathcal{F}n$ is $\mathcal{F}_n$-measurable and $\varepsilon{n+1}$ is independent of $\mathcal{F}n$ with $E\varepsilon{n+1} = 0$, we get \(E(H_{n+1}\varepsilon_{n+1} \mid \mathcal{F}_n) = H_{n+1}E(\varepsilon_{n+1} \mid \mathcal{F}_n) = H_{n+1}E(\varepsilon_{n+1}) = 0.\) Hence \(E(M_{n+1} \mid \mathcal{F}_n) = M_n.\)

Conclusion.

${M_n,\mathcal{F}_n}$ is a martingale.

(b)(i) $S_{n\wedge\tau}$ is a martingale

Claim.

${S_{n\wedge\tau},\mathcal{F}_n}$ is a martingale.

Proof.

Observe that \(S_{n\wedge\tau} = \sum_{k=1}^{n\wedge\tau}\varepsilon_k = \sum_{k=1}^n \mathbf{1}_{\{\tau \ge k\}}\varepsilon_k.\)

Set \(H_k = \mathbf{1}_{\{\tau \ge k\}}, \quad k\ge1.\)

  • Since $\tau$ is a stopping time, ${\tau \ge k}\in\mathcal{F}{k-1}$, so $H_k \in \mathcal{F}{k-1}$.
  • Also $H_k$ is bounded by $1$.

So by part (a)(ii), the process \(M_n := \sum_{k=1}^n H_k \varepsilon_k = \sum_{k=1}^n \mathbf{1}_{\{\tau\ge k\}}\varepsilon_k = S_{n\wedge\tau}\) is a martingale with respect to ${\mathcal{F}_n}$.

Conclusion.

${S_{n\wedge\tau},\mathcal{F}_n}$ is a martingale.

(b)(ii) Almost sure convergence of $S_{n\wedge\tau}$

Claim.

$S_{n\wedge\tau} \to S_\tau$ a.s. as $n\to\infty$, and $\tau < \infty$ a.s.

Proof.

  1. Show $\tau < \infty$ a.s.

    Consider the “two-barrier” stopping time \(\tau_M := \min\{n\ge 0 : S_n = 1 \text{ or } S_n = -M\},\) where $M$ is a positive integer.

    The stopped process $S_{\tau_M}$ is bounded between $-M$ and $1$. Since ${S_n}$ is a martingale and $\tau_M$ is a bounded (in the sense of values) hitting time, the optional stopping theorem gives \(E(S_{\tau_M}) = E(S_0) = 0.\) But \(S_{\tau_M} = \begin{cases} 1, & \text{if we hit } 1 \text{ before } -M,\\ -M, & \text{if we hit } -M \text{ before } 1. \end{cases}\) Denote $p_M = P(S_{\tau_M}=1)$. Then \(0 = E(S_{\tau_M}) = 1\cdot p_M + (-M)\cdot (1-p_M) = p_M - M(1-p_M).\) Solving, \(p_M - M + M p_M = 0 \quad\Rightarrow\quad p_M (1+M) = M \quad\Rightarrow\quad p_M = \frac{M}{M+1}.\)

    Thus \(P(\text{hit } 1 \text{ before } -M) = \frac{M}{M+1} \to 1 \quad\text{as } M\to\infty.\)

    The event “never hit 1” implies “for every $M$ we eventually hit -M before 1,” so \(P(\tau = \infty) \le \lim_{M\to\infty} P(\text{hit } -M \text{ before } 1) = \lim_{M\to\infty} \frac{1}{M+1} = 0.\) Hence $P(\tau < \infty) = 1$.

  2. Convergence of $S_{n\wedge\tau}$.

    Since $\tau < \infty$ a.s., for each $\omega$ there is some finite $\tau(\omega)$ such that \(S_{n\wedge\tau(\omega)}(\omega) = \begin{cases} S_n(\omega), & n < \tau(\omega),\\ S_{\tau(\omega)}(\omega), & n \ge \tau(\omega). \end{cases}\) So $S_{n\wedge\tau}(\omega)$ stabilizes at $S_\tau(\omega)$ once $n\ge\tau(\omega)$. Thus \(S_{n\wedge\tau} \to S_\tau \quad\text{a.s.}\)

    Since $\tau$ is the first time $S_n=1$, we have $S_\tau = 1$ a.s.

Conclusion.

$S_{n\wedge\tau}$ converges almost surely to $S_\tau = 1$.

(c)(i) Distribution of the limit

Claim.

The limit of $S_{n\wedge\tau}$ as $n\to\infty$ has the degenerate distribution at $1$.

Proof.

From (b)(ii), \(S_{n\wedge\tau} \to S_\tau \quad\text{a.s., and} \quad S_\tau = 1 \quad\text{a.s.}\) Hence \(\lim_{n\to\infty} S_{n\wedge\tau} \overset{d}{=} 1.\)

Conclusion.

The limit distribution is a point mass at $1$ (degenerate at $1$).

(c)(ii) Non-uniform integrability of ${S_{n\wedge\tau}}$

Claim.

The family ${S_{n\wedge\tau}}_{n\ge 0}$ is not uniformly integrable.

Proof.

We already know:

  • $S_{n\wedge\tau} \to S_\tau = 1$ a.s.
  • For each $n$, \(E(S_{n\wedge\tau}) = E(S_0) = 0,\) because ${S_{n\wedge\tau}}$ is a martingale (from part (b)(i)).

Suppose, for contradiction, that ${S_{n\wedge\tau}}$ is uniformly integrable. Then:

  1. Since $S_{n\wedge\tau} \to S_\tau$ a.s. and the sequence is uniformly integrable, we would have convergence in $L^1$: \(E|S_{n\wedge\tau} - S_\tau| \to 0.\)

  2. In particular, \(E(S_\tau) = \lim_{n\to\infty} E(S_{n\wedge\tau}).\)

But $S_{n\wedge\tau}$ is a martingale, so \(E(S_{n\wedge\tau}) = E(S_0) = 0 \quad\text{for all } n.\)

Hence \(E(S_\tau) = \lim_{n\to\infty} E(S_{n\wedge\tau}) = 0.\)

On the other hand, $S_\tau = 1$ a.s., so \(E(S_\tau) = 1,\) a contradiction.

Therefore our assumption that ${S_{n\wedge\tau}}$ is uniformly integrable must be false.

Conclusion.

${S_{n\wedge\tau}}$ is not uniformly integrable. This is exactly why optional stopping cannot be applied at $\tau$ (only at each finite $n\wedge\tau$).

Key Takeaways

  • Stopping time check: For hitting times, always rewrite \(\{\tau \le n\} = \bigcup_{k=1}^n \{S_k = \text{target}\}\) and use that each ${S_k = \cdot}$ is measurable with respect to $\mathcal{F}_k \subseteq \mathcal{F}_n$.

  • Predictable integrand martingale:
    If $H_n$ is bounded and $\mathcal{F}_{n-1}$-measurable, and $\varepsilon_n$ is independent with mean zero, then \(M_n = \sum_{k=1}^n H_k\varepsilon_k\) is a martingale. This “stochastic integral” form is worth remembering.

  • Stopped random walk as a martingale:
    Writing $S_{n\wedge\tau}$ as \(S_{n\wedge\tau} = \sum_{k=1}^n \mathbf{1}_{\{\tau \ge k\}}\varepsilon_k\) is the standard trick to apply the previous result and show it is a martingale.

  • Using auxiliary barriers to show $\tau<\infty$ a.s.:
    Introducing $\tau_M$ with barriers at $1$ and $-M$ and applying OST gives explicit hitting probabilities. Letting $M\to\infty$ shows the walk hits $1$ with probability 1.

  • Uniform integrability vs. optional stopping:
    A key meta-fact:
    • If a martingale $(M_n)$ is uniformly integrable and $M_n \to M$ a.s., then $E(M) = \lim E(M_n)$.
    • In this problem, $E(S_{n\wedge\tau})=0$ for all $n$, but $S_{n\wedge\tau}\to 1$ a.s., so if they were UI we would get $E(S_\tau)=0$ contradicting $E(S_\tau)=1$.
    • This is a standard way to show a stopped martingale is not uniformly integrable.
  • Big picture:
    This problem is a template for:
    • Recognizing stopping times,
    • Constructing martingales from predictable integrands,
    • Using optional stopping to compute hitting probabilities,
    • Understanding how uniform integrability controls when we can “pass OST to the limit.”
Edit this page on GitHub

Comments