# Prove an anti-concentration inequality for a martingale

My problem can be described easily: I have a sequence $(X_l)_{l \in \mathbb{N}}$ of r.v. adapted to some filtration $(\mathcal{F}_l)_{l \in \mathbb{N}}$, such that

1. $\left|X_{l+1}-X_l\right|\le R$ a. s.
2. $\mathbb{E}[X_{l+1}-X_l| \mathcal{F}_l]\le \delta$ a. s.
3. $X_0 = x_0$ a.s. where $x_0 \in \mathbb{R}$ is fixed
4. $\operatorname{Var}[X_{l+1}-X_l |\mathcal{F}_l] \ge v$ where $v>0$.

I want to prove $\mathbb{P}[X_l \le x_0-c\sqrt{vl}+\delta l]\ge p$ for some $p>0$ and some constant $c>0$.

By using 2) one can easily reduce the problem to a martingale $$\bar{X}_l:= \left(\sum_{k=1}^l D_k - \mathbb{E}[D_k| \mathcal{F}_{k-1}]\right)+x_0$$ where $D_k:=X_k-X_{k-1}$. The martingale again has bounded increments, $\bar{X}_l=x_0$ and $\operatorname{Var}[\bar{X}_l]\ge vl$. The task then is to prove $\mathbb{P}[\bar{X}_l \le x_0-c\sqrt{vl}]\ge p$.

Sadly, the proof in the original paper (Lemma 6.5) was wrong and as I've found out one can't adapt it after having corrected the wrong inequality (Jensen's inequality used in the wrong direction).

The only possibility I see so far is using the Martingale Central limit theorem and then try to control the speed of convergence for my original process using the inequalities described in the beginning of this paper. This seems pretty hard to check for my concrete considered process.

May I miss any obvious proof using simple martingale theory? Can anybody prove this result using only the above assumptions (or maybe some small additional assumptions, e.g. $L^{2+\delta}$ moments) ?

Basically, the proof goes along the following lines:

(1) Take a small $\varepsilon>0$ and show that the expected exit time from the interval $[-\varepsilon\sqrt{vl},\varepsilon\sqrt{vl}]$ is less than $\varphi l$ (this is standard, using the fact that your martingale squared becomes a submartingale with uniformly positive drift, see e.g. Example 7.1 of Section 4.7 of Durrett/Probability) with small $\varphi$. Chebyshev's inequality then will show that you martingale will go out of that interval with probability close to 1 until time $l$.

(2) By the Optional Stopping Theorem, with probability bounded away from 0 (in fact, even close to $1/2$) it will exit the above interval through $(-\varepsilon\sqrt{vl})$.

(3) now, you only need to show that the walker will remain to the left of (say) $(-\frac{1}{2}\varepsilon\sqrt{vl})$ till time $l$.

(4) For this, first note that the Optional Stopping Theorem implies that, starting at $(-\varepsilon\sqrt{vl})$, the probability that the walker exits the interval $[-M\sqrt{vl},-\frac{1}{2}\varepsilon\sqrt{vl}]$ through the left side is at least constant (depending on $M$).

(5) Using the Doob's inequality, we then observe that the process is unlikely to reach $(-\frac{1}{2}\varepsilon\sqrt{vl})$ in time $l$.

You may find it interesting to look at the proof of Lemma 2.1 in https://arxiv.org/abs/1201.6089, it contains all these ideas.

• Thanks for your helpful answer, Serguei. I get the idea of the proof and I'm able to comprehend each of the steps formally, but I do not understand how you make sure that the probability of staying left of $-1/2\epsilon\sqrt(vl)$ conditioned on having hit $- \epsilon\sqrt(vl)$ before time $l$ is strictly positive (so how you combine steps (3)-(5)). It seems to me that you want to use some Markov-like property in step 4 (without assuming a Markov process?).
– T.T
Nov 3, 2017 at 14:46
• No, on step (4) you only use the Optional Stopping Theorem and the boundedness of jumps. Just think how would you solve the Gambler's Ruin Problem for equally strong players using the fact that the one-dimensional SRW is a martingale; that argument easily generalizes to any martingale with bounded jumps (you'll obtain 2 inequalities instead of 1 equality, but that's still OK). Nov 3, 2017 at 16:37
• My question wasn't really precise. I knew how to compute the probability, but I didn't know how to combine it with Doob's inequality. But that's fine now, too. One just has to define $\tau_M := \inf \{t \ge \tau^-:\dots \}$ where $\tau^-$ is the first hitting time of $-\epsilon \sqrt{vl}$. Then one can can combine these results to get a lower bound on the probability of $X_l$ smaller than $-\epsilon/2 \sqrt{vl}$ conditioned on $\tau \le l$ and $X_{\tau} \le -\epsilon \sqrt{vl}$ and get the wanted result.
– T.T
Nov 4, 2017 at 12:02