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.
Thank you in advance.

  • 1
    $\begingroup$ 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 $\endgroup$
    – Masacroso
    Commented Jun 23 at 17:29
  • 1
    $\begingroup$ @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 $\endgroup$
    – Allure
    Commented Jun 23 at 17:35

2 Answers 2


"$\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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .