2023-Q6 - Kolmogorov-type inequality via stopped square martingale
2023 Probability Prelim Exam (PDF)
Problem statement
Let ${\varepsilon_k}$ be an independent sequence of random variables, with
\(E(\varepsilon_k)=0,\qquad E(\varepsilon_k^2)<\infty,\quad k=1,2,\dots\)
Let \(S_n = \sum_{k=1}^n \varepsilon_k,\qquad n=1,2,\dots\) and let ${\mathcal{F}_n}$ be the natural filtration of ${S_n}$, $n=1,2,\dots$
Let \(A = \left\{ \max_{1\le n\le m} |S_n|>x\right\},\) where $x>0$ and the integer $m\ge1$ are fixed. Let \(\tau = \min\{n\le m : |S_n|>x \text{ or } n=m\}.\)
(a)
(i) Prove $(S_n^2 - \sigma_n^2, \mathcal{F}_n)$ is a martingale, where $\sigma_n^2 = E(S_n^2)$.
(ii) Prove $E(S_\tau^2 - \sigma_\tau^2) = 0$.
(b) Assume from now on that, in addition to the above, there exists a finite $C>0$ so that \(|\varepsilon_k| \le C,\quad k=1,2,\dots\)
(i) Prove \(S_\tau^2 \le (x+C)^2.\)
(ii) On the event \(A^c = \left\{\max_{1\le n\le m}|S_n| \le x\right\}\) we have \(S_\tau^2 - \sigma_\tau^2 \le x^2 - \sigma_m^2.\)
(c)
(i) Prove \(0 = E(S_\tau^2 - \sigma_\tau^2) \le (x+C)^2 P(A) + (x^2 - \sigma_m^2)P(A^c).\)
(ii) Prove \(P\!\left(\max_{1\le n\le m}|S_n|\le x\right) \le \frac{(x+C)^2}{\sigma_m^2}.\)
Solution :contentReference[oaicite:1]{index=1}
I keep your structure and steps, but clean up the arguments and fill gaps while preserving your style.
(a)(i) The square-minus-variance martingale
Claim.
Let $\sigma_n^2 = E(S_n^2)$. Then \(M_n := S_n^2 - \sigma_n^2\) is a martingale with respect to $(\mathcal{F}_n)$.
Proof.
We check the three martingale conditions.
-
Integrability.
Since $E(\varepsilon_k^2)<\infty$, we have \(E(S_n^2) = \sum_{k=1}^n E(\varepsilon_k^2) < \infty\) (independence and mean zero).
Hence $E|M_n| \le E(S_n^2) + \sigma_n^2 < \infty$. -
Adaptedness.
$S_n$ is $\mathcal{F}_n$-measurable, so $S_n^2$ is $\mathcal{F}_n$-measurable.
$\sigma_n^2$ is a constant. Thus $M_n$ is $\mathcal{F}_n$-measurable. -
Martingale property.
We compute $E(M_{n+1} \mid \mathcal{F}_n)$.
First, \(S_{n+1} = S_n + \varepsilon_{n+1},\) so \(S_{n+1}^2 = S_n^2 + 2S_n \varepsilon_{n+1}+\varepsilon_{n+1}^2.\) Take conditional expectations: $$ E(S_{n+1}^2 \mid \mathcal{F}n) = S_n^2 + 2S_n E(\varepsilon{n+1} \mid \mathcal{F}_n)
- E(\varepsilon_{n+1}^2 \mid \mathcal{F}n). \(Since $\varepsilon_{n+1}$ is independent of $\mathcal{F}_n$ and has mean zero,\) E(\varepsilon{n+1} \mid \mathcal{F}n) = E(\varepsilon{n+1}) = 0, \qquad E(\varepsilon_{n+1}^2 \mid \mathcal{F}n) = E(\varepsilon{n+1}^2). \(Thus\) E(S_{n+1}^2 \mid \mathcal{F}n) = S_n^2 + E(\varepsilon{n+1}^2). $$
On the other hand, \(\sigma_{n+1}^2 = E(S_{n+1}^2) = E(S_n^2) + E(\varepsilon_{n+1}^2) = \sigma_n^2 + E(\varepsilon_{n+1}^2).\)
Therefore \(E(M_{n+1} \mid \mathcal{F}_n) = E(S_{n+1}^2 - \sigma_{n+1}^2 \mid \mathcal{F}_n) = \big(S_n^2 + E(\varepsilon_{n+1}^2)\big) - \big(\sigma_n^2 + E(\varepsilon_{n+1}^2)\big) = S_n^2 - \sigma_n^2 = M_n.\)
Conclusion.
$(M_n) = (S_n^2 - \sigma_n^2)$ is a martingale.
(a)(ii) Expected value at the bounded stopping time
Claim.
For $\tau = \min{n\le m : |S_n|>x \text{ or } n=m}$,
\(E(S_\tau^2 - \sigma_\tau^2) = 0.\)
Proof.
By construction, $\tau \le m$ almost surely, so $\tau$ is a bounded stopping time.
From part (a)(i), $(M_n)$ is a martingale, and $\tau$ is a stopping time bounded by $m$, so we may apply the optional stopping theorem: \(E(M_\tau) = E(M_0).\)
Now \(M_\tau = S_\tau^2 - \sigma_\tau^2, \qquad M_0 = S_0^2 - \sigma_0^2 = 0 - 0 = 0.\)
Hence \(E(S_\tau^2 - \sigma_\tau^2) = E(M_\tau) = E(M_0) = 0.\)
Conclusion.
The stopped square-minus-variance martingale has expectation zero at $\tau$.
(b)(i) Bounding $S_\tau$ using bounded increments
Claim.
Under $|\varepsilon_k|\le C$, we have \(S_\tau^2 \le (x+C)^2.\)
Proof.
By definition of $\tau$, \(\tau = \min\{n\le m : |S_n|>x \text{ or } n=m\}.\)
At time $\tau$ we are in one of two cases:
-
Case 1: $\tau < m$ and $|S_\tau|>x$ (first exit before $m$).
Then by minimality of $\tau$, for all $n<\tau$ we must have $|S_n|\le x$. In particular, \(|S_{\tau-1}|\le x.\) Also \(S_\tau = S_{\tau-1} + \varepsilon_\tau.\) Hence \(|S_\tau| \le |S_{\tau-1}| + |\varepsilon_\tau| \le x + C.\) -
Case 2: $\tau = m$ and never exited before $m$.
Then by definition we must have $|S_n|\le x$ for all $n < m$, and in particular $|S_m|\le x$. So \(|S_\tau| = |S_m| \le x \le x+C.\)
In both cases, $|S_\tau|\le x+C$, hence \(S_\tau^2 \le (x+C)^2.\)
Conclusion.
The stopped walk’s squared position is uniformly bounded by $(x+C)^2$.
(b)(ii) Behavior on the “good” event $A^c$
Recall \(A^c = \left\{\max_{1\le n\le m}|S_n| \le x\right\}.\)
Claim.
On $A^c$ we have \(S_\tau^2 - \sigma_\tau^2 \le x^2 - \sigma_m^2.\)
Proof.
On $A^c$, the maximum absolute value over $1,\dots,m$ is at most $x$. In particular, \(|S_n|\le x \quad\text{for all } 1\le n\le m.\) Since we never have $|S_n|>x$ for $n\le m$, the stopping time \(\tau = \min\{n\le m : |S_n|>x \text{ or } n=m\}\) must be $\tau = m$ (the “or $n=m$” part triggers).
Thus on $A^c$, \(S_\tau = S_m, \qquad \sigma_\tau^2 = \sigma_m^2.\) Since $|S_m|\le x$, it follows that \(S_\tau^2 = S_m^2 \le x^2,\) and therefore \(S_\tau^2 - \sigma_\tau^2 = S_m^2 - \sigma_m^2 \le x^2 - \sigma_m^2.\)
Conclusion.
On the event that the walk always stays within $[-x,x]$ up to time $m$, $S_\tau^2-\sigma_\tau^2$ is bounded above by $x^2-\sigma_m^2$.
(c)(i) Splitting the expectation over $A$ and $A^c$
Claim.
We have \(0 = E(S_\tau^2 - \sigma_\tau^2) \le (x+C)^2 P(A) + (x^2 - \sigma_m^2)P(A^c).\)
Proof.
From part (a)(ii), \(0 = E(S_\tau^2 - \sigma_\tau^2).\)
Split this expectation over $A$ and $A^c$: $$ 0 = E[(S_\tau^2 - \sigma_\tau^2)\mathbf{1}_A]
-
E[(S_\tau^2 - \sigma_\tau^2)\mathbf{1}_{A^c}]. $$
-
On $A$, we know $S_\tau^2 \le (x+C)^2$ (from (b)(i)), but we do not have a precise lower bound on $\sigma_\tau^2$, except that it is nonnegative. Thus \(S_\tau^2 - \sigma_\tau^2 \le S_\tau^2 \le (x+C)^2,\) so \(E[(S_\tau^2 - \sigma_\tau^2)\mathbf{1}_A] \le (x+C)^2 P(A).\)
-
On $A^c$, we have from (b)(ii) \(S_\tau^2 - \sigma_\tau^2 \le x^2 - \sigma_m^2,\) so \(E[(S_\tau^2 - \sigma_\tau^2)\mathbf{1}_{A^c}] \le (x^2 - \sigma_m^2) P(A^c).\)
Combining, $$ 0 = E[(S_\tau^2 - \sigma_\tau^2)\mathbf{1}_A]
- E[(S_\tau^2 - \sigma_\tau^2)\mathbf{1}_{A^c}] \le (x+C)^2P(A) + (x^2-\sigma_m^2)P(A^c). $$
Conclusion.
We obtain the key inequality for $E(S_\tau^2-\sigma_\tau^2)$ split over $A$ and $A^c$.
(c)(ii) Bounding the probability that the maximum stays small
Claim.
We have \(P\!\left(\max_{1\le n\le m}|S_n|\le x\right) = P(A^c) \le \frac{(x+C)^2}{\sigma_m^2}.\)
Proof.
Start from the inequality in (c)(i): \(0 \le (x+C)^2 P(A) + (x^2 - \sigma_m^2)P(A^c).\)
Recall that $P(A^c) = 1-P(A)$. Let $p = P(A^c)$. Then $P(A) = 1-p$, and \(0 \le (x+C)^2(1-p) + (x^2 - \sigma_m^2)p.\)
Rewrite: \(0 \le (x+C)^2 + p\big[(x^2 - \sigma_m^2) - (x+C)^2\big].\)
Observe \((x^2 - \sigma_m^2) - (x+C)^2 = x^2 - \sigma_m^2 - (x^2 + 2Cx + C^2) = -\sigma_m^2 - 2Cx - C^2 \le -\sigma_m^2.\)
Thus \(0 \le (x+C)^2 + p\big[-\sigma_m^2 - 2Cx - C^2\big] \le (x+C)^2 - p\sigma_m^2.\)
Hence \(p\sigma_m^2 \le (x+C)^2 \quad\Rightarrow\quad p = P(A^c) \le \frac{(x+C)^2}{\sigma_m^2}.\)
Therefore \(P\!\left(\max_{1\le n\le m}|S_n|\le x\right) \le \frac{(x+C)^2}{\sigma_m^2}.\)
Conclusion.
We obtained a Kolmogorov-type inequality for the maximum of the partial sums with bounded increments.
Key Takeaways
-
Square-minus-variance martingale:
For independent mean-zero increments, \(M_n = S_n^2 - E(S_n^2)\) is a martingale. This is a standard construction for variance and maximal inequalities. -
Bounded stopping time + OST:
If $\tau\le m$ a.s., then for any martingale $(M_n)$, \(E(M_\tau) = E(M_0),\) with no uniform integrability issues. This is the “safe” version of optional stopping. -
Bounding stopped paths via bounded increments:
Knowing $|\varepsilon_k|\le C$ lets you control how far $S_n$ can jump at the stopping time: \(|S_\tau| \le |S_{\tau-1}| + |\varepsilon_\tau| \le x + C,\) which drives the $(x+C)^2$ factor in the maximal inequality. -
Splitting expectations on good vs bad events:
A standard technique: \(E(Z) = E(Z\mathbf{1}_A) + E(Z\mathbf{1}_{A^c}),\) then bound each part using different information on $A$ and $A^c$. Here, $A$ is the “bad” event where the maximum exceeds $x$. -
Kolmogorov-type inequality:
The final inequality \(P\!\left(\max_{1\le n\le m}|S_n|\le x\right) \le \frac{(x+C)^2}{\sigma_m^2}\) is a maximal inequality for partial sums with bounded increments, derived purely from martingale methods.
This problem is a good template for using stopped square martingales and bounded increments to derive maximal inequalities.
Comments