4.8. Optional stopping theorem
In this section, we generalize the bounded version of optional stopping. After that as an example we will cover theorem regarding assymetric random walk.
Optional stopping theorem
Our first theorem will be the extension of theorem 4.2.9.
Let $(X_n)$ be a uniformly integrable submartingale and $N$ be a stopping time. Then $(X_{n\wedge N})$ is a uniformly integrable submartingale.
It is shown that $(X_{n\wedge N})$ is a submartingale in theorem 4.2.9. By Vitali's lemma $X_n$ converges almost surely and in $L^1$ to some $X_\infty.$ Since $x \mapsto x^+$ is convex and increasing, $X_n^+, X_{n\wedge N}^+$ are submartingales. Let $\tau=n, \sigma=n\wedge N$ then $\tau,\sigma$ are bounded stopping times. By Doob's inequality, $EX_{n\wedge N}^+ \le EX_n^+$ and $$\sup_n EX_{n\wedge N}^+ \le \sup_n EX_n^+ \le \sup_n E|X_n| < \infty.$$ By Submartingale convergence, $X_{n\wedge N} \to X_N$ a.s. and $E|X_N| < \infty.$ $$\begin{aligned} &E|X_{n\wedge N}| \mathbf{1}_{|X_{n\wedge N}| \ge a} \\ &\le E|X_{n\wedge N}| \mathbf{1}_{|X_{n\wedge N}| \ge a, N \le n} + E|X_{n\wedge N}| \mathbf{1}_{|X_{n\wedge N}| \ge a, N>n} \\ &= E|X_N| \mathbf{1}_{|X_N| \ge a} + E|X_n| \mathbf{1}_{|X_n| \ge a}. \end{aligned}$$ Since both terms on the right-hand side goes to 0 as $a\to\infty,$ $X_{n\wedge N}$ is uniformly integrable.
Next theorem is the unbounded version of Doob’s inequality.
Let $(X_n)$ be a uniformly integrable submartingale, $N$ be a stopping time. Then
$$EX_0 \le EX_N \le EX_\infty$$
where $X_\infty = \lim_n X_n$ a.s.
By the previous theorem $X_{n\wedge N}$ is a uniformly integrable submartingale. By Doob's inequality $$EX_0 \le EX_{n\wedge N} \le EX_n.$$ By Vitali's lemma, $EX_n \to EX_\infty$ and $$\begin{aligned} \lim_n X_{n\wedge N} = \begin{cases} X_N &,~ N<\infty \\ X_\infty = X_N &,~ N=\infty \end{cases} \end{aligned}$$ Thus $X_{n\wedge N} \to X_N$ a.s. with $E|X_N| < \infty$ by Vitali's lemma and the desired result follows.
Finally we state and prove the main theorem.
Let $L \le M$ be stopping times and $(Y_{n\wedge M})$ be a uniformly integrable submartingale. Then $EY_L \le EY_M$ and $Y_L \le E(Y_M | \mathcal{F}_L)$ a.s.
Let $X_n = Y_{n\wedge M}$ then it directly follows that $EY_L \le EY_M.$ The rest of the proof is the same as the first proof of bounded stopping theorem.
Note that we do not need uniform integrability of $Y_n.$ The next theorem guarantees uniform integrability of stopped martingale of submartingale with uniformly bounded conditional increment.
Let $X_n$ be a submartingale with $E\left(\left|X_{n+1}-X_n\right| | \mathcal{F}_n\right) \le B$ a.s. and $N$ be a stopping time with $EN < \infty.$ Then $X_{n\wedge N}$ is uniformly integrable and $EX_0 \le EX_N.$
$$X_{n\wedge N} = X_0 + \sum\limits_{m=1}^n (X_m - X_{m-1}) \mathbf{1}_{m \le N}\\ |X_{n\wedge N}| \le |X_0| + \sum\limits_{m=1}^n |X_m - X_{m-1}| \mathbf{1}_{m \le N}$$ Let $Z$ be the right-hand side of the inequality. $$\begin{aligned} E|Z| &\le E|X_0| + \sum_m |X_m - X_{m-1}| \mathbf{1}_{m \le N} \\ &\le E|X_0| + \sum_m E\left( \mathbf{1}_{m\le N} E(\left|X_m - X_{m-1}\right| | \mathcal{F}_{m-1}) \right) \\ &\le E|X_0| + B \cdot \sum_m P(m \le N) \\ &= E|X_0| + B\cdot EN < \infty. \end{aligned}$$ Thus $Z$ is integrable and $X_{n\wedge N}$ is uniformly integrable. $EX_0 \le EX_N$ follows directly.
Assymetric random walk
As an application of optional stopping, we look into properties of assymetric random walk. We define assymetric random walk $S_n = \xi_1 + \cdots + \xi_n,$ $S_0 = 0$ where $\xi_i$’s are i.i.d. with $P(\xi_1=1)=p,$ $P(\xi_1=-1)=q,$ $p+q=1.$ Let $\text{Var}(\xi_1) = \sigma^2 < \infty$ and $\mathcal{F}_n = \sigma(\xi_1,\cdots,\xi_n)$ for $n\ge 1,$ $\mathcal{F}_0$ be a trivial $\sigma$-field. Let $\varphi(x) = (\frac{1-p}{p})^x.$
(a) $0 < p < 1 \implies \varphi(S_n)$ is a martingale.
(b) $T_x := \inf\{n: S_n=x\},$ $x\in\mathbb{Z}$ is a stopping time and $P(T_a < T_b) = \frac{\varphi(b)-\varphi(0)}{\varphi(b)-\varphi(a)}$ for $a<0<b.$
(c) $1/2<p<1$ and $a<0<b \implies$ $T_b < \infty$ a.s. and $P(T_a < \infty) < 1.$
(d) $1/2<p<1 \implies$ $ET_b = \frac{b}{2p-1},$ $b>0.$
(b) $T_x := \inf\{n: S_n=x\},$ $x\in\mathbb{Z}$ is a stopping time and $P(T_a < T_b) = \frac{\varphi(b)-\varphi(0)}{\varphi(b)-\varphi(a)}$ for $a<0<b.$
(c) $1/2<p<1$ and $a<0<b \implies$ $T_b < \infty$ a.s. and $P(T_a < \infty) < 1.$
(d) $1/2<p<1 \implies$ $ET_b = \frac{b}{2p-1},$ $b>0.$
expand proof
(b) Let $T_a \wedge T_b$ be a stopping time. By law of iterated logarithm,
$$\begin{aligned}
\limsup_n \frac{S_n - n(p-q)}{\sigma \sqrt{2n\log\log n}} &= 1 \text{ a.s.} \\
\liminf_n \frac{S_n - n(p-q)}{\sigma \sqrt{2n\log\log n}} &= -1 \text{ a.s.}
\end{aligned}$$
thus $S_n \approx n(p-q) \pm \sigma\sqrt{2n\log\log n}.$ If $p>q,$ $\lim_n S_n = \infty$ a.s. and $T_b < \infty$ a.s. Similarly $T_a$ or $T_b$ is almost surely finite in any cases, so $N < \infty$ a.s. If $N \ge n,$ $a \le S_{n\wedge N} = S_n \le b.$ If $N < n,$ $S_{n\wedge N} = S_N = a$ or $b.$ $\varphi(S_{n\wedge N})$ is a bounded, thus uniformly integrable and closable martingale. Note that $S_N = a\mathbf{1}_{T_a < T_b} + b\mathbb{1}_{T_a > T_b}.$ Also note that $E\varphi(S_N) = 1$ since $1 = E\varphi(S_0) = E\varphi(S_{n\wedge N}) \to E\varphi(S_N).$
$$\begin{aligned}
1 = E\varphi(S_N)
&= \varphi(a) P(T_a < T_b) + \varphi(b) P(T_a > T_b) \\
&= (\varphi(a) - \varphi(b)) P(T_a < T_b) + \varphi(b).
\end{aligned}$$
Organizing both sides gives the result.
Observe that $T_\alpha < T_\beta$ for all $\beta<\alpha<0.$ Thus $\lim_{a\to-\infty} T_a = \infty.$
$$\begin{aligned}
P(T_b < \infty)
&= \lim_{a\to-\infty} P(T_b<T_a) \\
&= \lim_{a\to-\infty} \left(1 - \frac{\varphi(b) - 1}{\varphi(b) - \varphi(a)}\right) \\
&= \lim_{a\to-\infty} \frac{1-\varphi(a)}{\varphi(b) - \varphi(a)} = 1.
\end{aligned}$$
Similarly, $P(T_a < \infty) = 1/\varphi(a) < 1.$
Observe that if $a<0,$ $(\inf_n S_n \le a) = (T_a < \infty).$
Since
$$P(\inf_n S_n \le a) = P(T_a < \infty) = \begin{cases}
\left(\frac{1-p}{p}\right)^{-a} &,~ a<0 \\
1 &,~ a\ge 0
\end{cases}$$
we get
$$\begin{aligned}
E|\inf_n S_n|
&= \sum_{a=-\infty}^\infty |a| P(\inf_n S_n = a) \\
&= \sum_{a=-\infty}^\infty |a| \left( \left(\frac{1-p}{p}\right)^{-a} - \left(\frac{1-p}{p}\right)^{-(a-1)} \right) \\
&= \sum_{a=-\infty}^\infty |a| \left(\frac{1-p}{p}\right)^{-a} \left(1 - \frac{1-p}{p}\right) < \infty.
\end{aligned}$$
Thus $\inf_n S_n$ is integrable. Let $X_n = S_n - n(p-q)$ then $X_n$ is a martingale. Since $T_b < \infty$ a.s., $X_{n\wedge T_b}$ is also a martingale.
$$\begin{aligned}
ES_{n\wedge T_b}
&= EX_{n\wedge T_b} + (p-q)E(T_b\wedge n) \\
&= \cancel{EX_0} + (p-q)E(T_b\wedge n).
\end{aligned}$$
Note that $\inf_n S_n \le S_{n\wedge T_b} \le b$ and $|S_{n\wedge T_b}| \le |\inf_n S_n| + b$ for all $n.$ By DCT, $ES_{n\wedge T_b} \to ES_{T_b} = b.$ By MCT, $E(T_b \wedge n) \uparrow ET_b.$ Thus the desired result follows.
Acknowledgement
This post series is based on the textbook Probability: Theory and Examples, 5th edition (Durrett, 2019) and the lecture at Seoul National University, Republic of Korea (instructor: Prof. Sangyeol Lee).