The problem:
Let $(X_n, \mathcal{F}_n)$ be a martingale such that $|X_n-X_{n-1}| \leq c$, $\mathbb{E}(|X_n-X_{n-1}|^2|\mathcal{F}_{n-1}) \geq \delta > 0$, $\sup X_n = -\inf X_n = \infty$ and $X_0 = 0$.
Let $b>0$ and define the stopping time $\tau = \inf\{n : X_n \not\in (-b,b)\}$, we want to show that exists $C = C(\delta, c)$ such that for all $b\geq 10c$,
$$\forall k\in\mathbb{N}: \mathbb{P}(\tau \geq kCb^2) \leq e^{-k}.$$
My partial solution:
Let $Y_n = X^2_{n} – \delta n$, then $Y_n$ is a submartingale and so is $Y_{n\wedge \tau}$. It is true that $\sup \mathbb{E}Y_{n\wedge\tau}^+ \leq \sup \mathbb{E}X_{n\wedge\tau}^2 \leq (b+c)^2$, then $Y_{n\wedge \tau} \to Y_\tau$ a.s and $EY_\tau < \infty$ and by the dominated convergence theorem
\begin{align}
\mathbb{E}( X_{n\wedge \tau}^2 – (n\wedge \tau)\delta ) \geq 0 \Rightarrow \mathbb{E}( X_\tau^2) \geq \delta \mathbb{E}(\tau)
\end{align}
Using Markov:
\begin{equation}
\mathbb{P}( \tau \geq k C b^2 ) \leq \frac{\mathbb{E}\tau}{ kCb^2 } \leq \frac{\mathbb{E}X_\tau^2}{ \delta kCb^2 } \leq \frac{(b+c)^2}{ \delta kCb^2 } \approx \frac{1}{k}.
\end{equation}
Giving a bound of order $\frac{1}{k}$, but far way from the goal that is a bound of order $e^{-k}$, how to improve it?
Best Answer
Here is a solution sketch. Given $m\in\mathbb{N}$, define $$\tau_m:=\inf\{n\in\mathbb{N}\,:\,n\geq m,\,X_n\not\in (-b,b)\}.$$
We will argue later that there is a $K_0>0$ depending only on $\delta$ and $b$ such that: $$(\star)\,\mathbb{E}[\tau_m - m\mid \mathcal{F}_m]\leq K_0.$$ and therefore $$\mathbb{E}[{\bf 1}_{\{\tau_m - m>K\}}\mid \mathcal{F}_m]\leq \frac{1}{2}$$ for $K=2K_0$, by the conditional form of Markov's inequality.
Let us see how the above gives us the desired result. Notice the equality of events, for $i\in\mathbb{N}$. $$\{\tau>i\,K\} = \{\tau>(i-1)K\}\cap \{\tau_{(i-1)K}-(i-1)K>K\}.$$ Since $\{\tau>(i-1)K\}\in\mathcal{F}_{(i-1)K}$, $$\mathbb{P}\{\tau>i\,K\} = \mathbb{E}[{\bf 1}_{\{\tau>(i-1)K\}}\,{\bf 1}_{\{\tau_{(i-1)K}-(i-1)K>K\}}] = \mathbb{E}[{\bf 1}_{\{\tau>(i-1)K\}}\,\mathbb{E}[{\bf 1}_{\{\tau_{(i-1)K}-(i-1)K>K\}}\mid \mathcal{F}_{(i-1)K}]]$$ and applying $(\star)$ with $m=(i-1)K$ gives: $$\mathbb{P}\{\tau>i\,K\} \leq \frac{\mathbb{E}[{\bf 1}_{\{\tau>(i-1)K\}}]}{2} = \frac{\mathbb{P}\{\tau>(i-1)\,K\}}{2}.$$ If this is true, then the prob. of $\tau\geq iK$ decays exponentially in $i.$ Since the events $\tau> t$ are decreasing, we obtain: $$\mathbb{P}\{\tau>t\}\leq 2^{-\left\lfloor\frac{t}{K}\right\rfloor}.$$
It remains to prove $(\star)$. This uses the same submartingale you defined, in a different way (notice that the conditional expectation is a r.v.). Since $\tau_m\geq m$ is a stopping time, optional stopping gives: $$\mathbb{E}[Y_{\tau_m\wedge j} - Y_{m}\mid \mathcal{F}_m]\geq 0\mbox{ a.s.}$$ and so, for $j\geq m$: $$\delta\mathbb{E}[\tau_m\wedge j -m\mid \mathcal{F}_m]\leq \limsup_j\mathbb{E}[X^2_{\tau_m\wedge j} - X^2_m\mid \mathcal{F}_m]\leq (b+c)^2.$$ Indeed, $X^2_{\tau_m\wedge j} - X^2_m$ equals $0$ when $X_m\not\in(-b,b)$ (as in that case $\tau_m=m$) and is at most $(b+c)^2$ otherwise. So the same argument you gave of taking limits shows
$$\mathbb{E}[[\tau_m -m\mid \mathcal{F}_m]\leq K_0:=\frac{(b+c)^2}{\delta}.$$