# Proof of Doob's inequality

I was reading probability theory script by our professors and saw this proof for Doob's inequality. here is the proof:

Doob's Inequality. Let $$(X_n)$$ be a non-negative submartingale. Then for all $$t > 0$$, we have $$\mathbb{P}\left( \max_{i \leq n} X_i > t \right) \leq \frac{1}{t} \mathbb{E}[X_n].$$

Proof. Let $$\tau = \min \{ n \geq 0 : X_n > t \}$$. It follows that $$\{ \max_{i \leq n} X_i > t \} = \{ X_{\tau \land n} > t \}$$. We use Markov's inequality and obtain $$\mathbb{P}\left( \max_{i \leq n} X_i > t \right) \leq \frac{1}{t} \mathbb{E}[X_{\tau \land n}].$$

Since $$\tau$$ is a stopping time and $$(X_n)$$ is a submartingale, it follows that $$\mathbb{E}[X_{\tau \land n}] \leq \mathbb{E}[X_n].$$ This proves the statement. $$\square$$

I understand the most of it, however one point in the proof is beyond my comprehension.

Why is this true?

$$\{ \max_{i \leq n} X_i > t \} = \{ X_{\tau \land n} > t \}$$

I couldn't find anything, since the most of the proofs in the internet use different methods.

• the equality $\{ \max_{i \leq n} X_i > t \} = \{ X_{\tau \land n} > t \}$ is true by definition of $\tau$. The hard part on the proof is knowing that $X_{\tau \,\land\, n}$ is a well-defined random variable, so we can apply Markov inequality Commented Jun 23 at 17:29
• @Masacroso definition of τ is minimal n so that $X_{n} > t$ so the right side of the equation means basically the first time X is greater than t, however the left side of the equation is maximim of X greater than t, my question is rather why maximum and the right side of the equation are the same Commented Jun 23 at 17:35

"$$\subseteq$$" Let $$\omega\in \{\max_{i\le n} X_i > t\}$$.

Since $$\max_{i\le n} X_i(\omega) > t$$, you find $$\tau(\omega)\le n$$, by definition of $$\tau$$. Therefore $$X_{\tau(\omega)\wedge n}(\omega)=X_{\tau(\omega)}(\omega)>t,$$ such that $$\omega\in \{X_{\tau\wedge n} > t\}$$.

"$$\supseteq$$" Let $$\omega\in \{X_{\tau\wedge n} > t\}$$.

Since $$\tau(\omega)\wedge n\le n$$, you find $$\max_{i\le n} X_i(\omega)\ge X_{\tau(\omega)\wedge n}(\omega) > t,$$ such that $$\omega\in \{\max_{i\le n} X_i > t\}$$.

$$\mathbb{E}[\max\{M_{n + 1}, 0\} | F] \ \geq \max\{\mathbb{E}[M_{n + 1}|F], 0\} \geq \max\{M_n, 0\}$$ By submartingale property, the max inequality follows from Jensen's inequality since max is convex. $$F$$ is the trajectory of the adaptation. This implies $$(M_n^+)_{n \geq 0}$$, $$M_n^+ := \max\{M_n, 0\}$$ is also a submartingale. Thus, assume that $$(M_n)_{n \geq 0}$$ is nonnegative. Let $$T := \inf\{n \geq 0 | M_n \geq \alpha\}$$.

$$P\{\max_iM_i \geq t \} = P\{M_{\min\{T, n\}} \geq t\} \le \frac{\mathbb{E}[M_{\min\{T, n\}}]}{t} \le \frac{\mathbb{E}[M_n]}{t}$$

The first equality follows from optional stopping theorem, first inequality follows from markov's inequality, but the last inequality require further analysis. $$\mathbb{E}[M_0] = \mathbb{E}[M_{\min\{T, 0\}}] \le \mathbb{E}[M_{\min\{T, n\}}]$$ We'll now show that $$M_n^* := M_n - M_{\min\{T, n\}}$$ adapted to $$F$$ is a martingale. $$\mathbb{E}[M_{n + 1}^{*}|F] = M_n^{*} + \mathbb{E}[\mathbb{1}_{\{T \le n\}}(M_{n + 1} - M_n)| F]$$ $$= M_n^{*} + \mathbb{1}_{\{T \le n\}}\mathbb{E}[M_{n + 1} - M_n|F] \geq M_n^{*}$$

This implies that using the monotonicity of expectations and the submartingale property, we can conclude: $$\mathbb{E}[M_n] - \mathbb{E}[M_{min\{T, n\}}] = \mathbb{E}[M_n^{*}] \geq \mathbb{E}[M_0^{*}] = 0$$ This concludes the proof that $$P\{\max_{i}M_i \geq t\} \le \frac{\mathbb{E}[M_n]}{t}$$. Courtesy of Spring 2024 EE 226A, Berkeley.