Given $B>A>0$ and $C>0$. Let $\{X_t\}_{t=0}^{\infty}$ be a submartingale with $X_0=A$ and \begin{equation} \mathbb{E}[X_{t+1} | \mathcal{F}_t] \geq X_t + C. \end{equation}

Let $ \tau := \min\{t:X_t>B\}$. Under what condition can we upper bound $\mathbb{E}[\tau]$ roughly $\frac{B-A}{C}$?

For instance, define $$\eta_t:=\frac{X_t}{C}-t.$$ We see that $\eta_t$ is a submartingale as well and $\eta_{t\wedge \tau} \leq \frac{B}{C}$ almost surely for all $t\geq0$. Therefore, by the optional stopping theorem, \begin{equation} \begin{aligned} \frac{A}{C}=\eta_0 \leq \mathbb{E}[ \eta_{\tau}] &= \mathbb{E}[\eta_{\tau-1}] + \mathbb{E}[\eta_{\tau}-\eta_{\tau-1}]\\ &\leq \frac{B}{C}-\mathbb{E}[\tau]+1+\mathbb{E}[\eta_{\tau}-\eta_{\tau-1}]. \end{aligned} \end{equation} Hence, $$ \mathbb{E}[\tau] \leq \frac{B-A}{C} +2+\frac{\mathbb{E}[X_t-X_{t-1}]}{C} $$

So if we have conditions like $X_t-X_{t-1} \leq K $ or $\mathbb{E}[X_t-X_{t-1} \mid \mathcal{F}_{t-1} ] \leq K, $

we have $$ \mathbb{E}[\tau] \leq \frac{B-A}{C} +2+\frac{K}{C}. $$

However, the condition appears weird to me. Intuitively the larger $\mathbb{E}[X_t-X_{t-1}]$ is, the faster $X_t$ shall reach or cross $B$. But the proof above requires an upper-bound on $\mathbb{E}[X_t-X_{t-1}]$, limiting its speed of increment.

Is there other proof technique for getting $\mathbb{E}[\tau]$ upper bound roughly $\frac{B-A}{C}$, or this "weird" condition $\mathbb{E}[X_t-X_{t-1}] \leq K$ is actually necessary?


1 Answer 1


I don't think your argument works as stated. You don't have $\eta_{t \wedge \tau} \le B/C$ because $X_\tau$ could be a lot larger than $B$. That is, maybe when $X_t$ first exceeds $B$, it jumps a long way past it. An almost sure upper bound on the increment $|X_t - X_{t-1}|$ can fix it, but a bound on the expectation of the increment cannot.

To see what can go wrong, let $0 < p_1, p_2, \dots < 1$ be a sequence to be chosen later, and let $\{\xi_i\}$ be independent where $P(\xi_i = 0) = 1 - p_i$, $P(\xi_i = 1/p_i) = p_i$, so that $E[\xi_i] = 1$ for all $i$. Setting $X_n = \xi_1 + \dots + \xi_n$, we have the desired conditions with $A=0$, $C=1$. Also note that $E[|X_{n+1} - X_n|] = 1$ for all $n$.

Now taking $B=1$ we see that $P(\tau < \infty) = P(\bigcup_i \{\xi_i > 0\}) \le \sum_i p_i$ by union bound. So choosing $p_i$ with $\sum_i p_i < 1$ we have $\tau = \infty$ with positive probability and in particular $E[\tau] = \infty$.

  • $\begingroup$ A followed up question: If we know that $$E[\tau]<\infty$$, can we remove the boundedness condition? $\endgroup$ Commented Apr 6, 2018 at 22:28
  • $\begingroup$ @Sung-EnChiu: No. Repeat the same construction with $p_i = \epsilon$ for all $i$, where $\epsilon \ll 1/B$. Then $\tau$ has a geometric distribution and $E [\tau] = 1/\epsilon$ which is finite but much larger than $B$. $\endgroup$ Commented Apr 7, 2018 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.