Expected time for a submartingale increasing from A to B

Question

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?

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