# Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2$

Let $$X_1, X_2, \dots, X_n$$ be a martingale difference sequence such that $$X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2.$$ Question 1: Does the following hold? $$\mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] \leq \exp{\left(\frac{-x^2}{2B^2 + \frac{2}{3}xy}\right)}.$$

A similar bound (albeit for independent random variables) is given in Corollary 2 in Pinelis–Utev (1990) (DOI link). I have seen that exponential inequalities for sums of independent random variables can be extended to martingales generally.

Question 2: If the bound given in question 1 doesn't hold, does any other similar exponential inequality exist for the LHS? I have came across Freedman's inequality (Theorem 1.6 in Freedman (1975)) which deals with similar quantities but it contains $$\operatorname{Var}(X_i | \mathcal{F}_{i-1})$$. As seen from the above, I would rather have the bound in terms of $$\operatorname{Var}(X_i)$$.

Thank you for your time and consideration.

• Your bound will not hold even when the $X_i$'s are independent, because your bound does not involve $y$. Sep 23, 2020 at 17:12
• Under a stronger hypothesis you can get the conclusion you want from Azuma's inequality. Sep 23, 2020 at 18:34
• @IosifPinelis, thanks for your comment. I had misread Theorem 7 in epubs.siam.org/doi/abs/10.1137/1134032 earlier. I think it doesn't involve y (i.e. the bound on the value of individual $X_i$'s), because y is assumed to be 0. I see that you are the author of that paper. Could you please elaborate what Theorem 7 would look like if y is some positive number? I suppose the denominator in the RHS exponential will be something akin to 2(B^2 + yx).
– Siam
Sep 24, 2020 at 9:26
• @BillJohnson, thanks. Could you please elaborate on that? My main concern is having the bound in terms of $Var(X_i)$ and not $Var(X_i|\mathcal{F_{i-1}})$.
– Siam
Sep 24, 2020 at 9:35
• @Siam : For positive $y$, the right result would be Theorem 3 (or Corollary 2) in the paper you read. Sep 24, 2020 at 13:12

Theorem 1: In the known exponential bounds for martingales, the conditional variances cannot be replaced by the unconditional ones.

Proof: Otherwise, we would most likely have such bounds. $$\Box$$ :-)

This "proof" of "Theorem 1" is not so non-serious as it may look.

Perhaps more seriously, we have

Theorem 2: The following statement is false:

There is a real constant $$c>0$$ such that for all natural $$n$$, all real $$y>0$$, all real $$B>0$$, and all martingale difference sequences $$(X_1,\dots,X_n)$$ such that $$\begin{equation*} X_i\le y \ \forall i\quad\text{and}\quad\sum_{i=1}^n Var\,X_i\le B^2\label{0}\tag{0} \end{equation*}$$ we have $$\begin{equation*} P\Big(\sum_{i=1}^n X_i\ge x\Big)\le\exp\frac{-cx^2}{B^2+xy}\label{1}\tag{1} \end{equation*}$$ for all real $$x>0$$.

Proof: This proof would be a bit simpler if, instead of using Corollary 2 in the Pinelis--Utev paper, you used the better bound in Theorem 3 in that paper. Indeed, one can show that, at least in the case when the $$X_i$$'s are conditionally symmetric (given $$\mathcal F_{i-1}$$), that theorem implies the Rosenthal-type inequality $$\begin{equation*} ES_n^4\ll B^4+A^{(4)}_n, \end{equation*}$$ where $$S_n:=\sum_{i=1}^n X_i,$$ $$a\ll b$$ means $$a\le Cb$$ for some real $$C$$ depending only on $$c$$, and $$\begin{equation*} A^{(p)}_n:=\sum_{i=1}^n E|X_i|^p. \end{equation*}$$

Because the bound in \eqref{1} is suboptimal, it only implies an ugly version of the Rosenthal-type inequality:

Lemma 1: If the highlighted statement is true, then for conditionally symmetric martingale difference sequences $$(X_1,\dots,X_n)$$ such that $$\sum_{i=1}^n Var\,X_i\le B^2$$ we have $$\begin{equation*} ES_n^4\ll B^4+A^{(6)}_n/B^2. \label{2}\tag{2} \end{equation*}$$

This lemma will be proved at the end of this answer.

Now consider the following construction of a conditionally symmetric martingale difference sequence $$(X_1,\dots,X_n)$$: Let $$V_1:=R_1$$, where $$R_1$$ is a Rademacher random variable, so that $$P(R_1=\pm1)=1/2$$. For natural $$k\ge2$$, let $$\begin{equation*} V_k:=a_k R_k,\quad a_k:=\frac1{\sqrt{k\ln k}}, \end{equation*}$$ where $$R_2,R_3,\dots$$ are independent copies of $$R_1$$. Let then $$X_1:=V_1$$, and for natural $$k\ge2$$ let $$\begin{equation*} X_k:=S_{k-1}V_k, \end{equation*}$$ where $$S_j:=\sum_{i=1}^j X_i$$, as before. So, for natural $$k\ge2$$, $$\begin{equation*} S_k=S_{k-1}(1+V_k). \end{equation*}$$ So, for any even natural $$p$$ and any natural $$k\ge2$$, we have $$M_k^{(p)}:=ES_k^p=M_{k-1}^{(p)} E(1+V_k)^p$$ and hence $$\begin{equation*} M_k^{(p)}=\prod_{j=2}^k E(1+V_j)^p. \end{equation*}$$ In particular, $$\begin{equation*} M_k^{(2)}=\prod_{j=2}^k (1+a_k^2)=\prod_{j=2}^k \Big(1+\frac1{k\ln k}\Big) =\exp\Big\{(1+o(1))\int_2^k\frac{dx}{x\ln x}\Big\} =(\ln k)^{1+o(1)} \end{equation*}$$ (as $$k\to\infty$$). Similarly, $$\begin{equation*} M_k^{(4)}=\prod_{j=2}^k (1+6a_k^2+a_k^4)=(\ln k)^{6+o(1)}, \end{equation*}$$ $$\begin{equation*} M_k^{(6)}=\prod_{j=2}^k (1+15a_k^2+15a_k^4+a_k^6)=(\ln k)^{15+o(1)}. \end{equation*}$$ Hence, $$\begin{equation*} A^{(6)}_n=1+\sum_{k=2}^n M_{k-1}^{(6)}a_k^6\ll1+\sum_{k=2}^n (\ln k)^{15+o(1)}\frac1{k^3\ln^3k}\ll1. \end{equation*}$$ Also, we may take $$\begin{equation*} B^2=\sum_{i=1}^n Var\,X_i=ES_n^2=M_n^{(2)}=(\ln n)^{1+o(1)}. \end{equation*}$$ So, for $$n\to\infty$$ the right-hand side of \eqref{2} is $$\begin{equation*} B^4+A^{(6)}_n/B^2=(\ln n)^{2+o(1)}+O(1)/(\ln n)^{1+o(1)}=(\ln n)^{2+o(1)}, \end{equation*}$$ whereas the left-hand side of \eqref{2} is $$\begin{equation*} ES_n^4=M_n^{(4)}=(\ln n)^{6+o(1)}. \end{equation*}$$ Thus, \eqref{2} fails to hold for large enough $$n$$.

It remains to give

Proof of Lemma 1: Suppose the highlighted statement is true. Take any conditionally symmetric martingale difference sequence $$(X_1,\dots,X_n)$$ such that $$\sum_{i=1}^n Var\,X_i\le B^2$$. Take any real $$y>0$$. Let $$X_{i,y}:=X_i\,1(|X_i|\le y)$$ for all $$i$$. Then $$(X_{1,y},\dots,X_{n,y})$$ is a martingale difference sequence with $$|X_{i,y}|\le y$$ and $$Var\,X_{i,y}\le Var\,X_i$$ for all $$i$$. So, \begin{align*} P(|S_n|\ge x)&\le\sum_{i=1}^n P(|X_i|>y)+P\Big(\Big|\sum_{i=1}^nX_{i,y}\Big|\ge x\Big) \\ &\le \sum_{i=1}^n P(|X_i|>y)+2\exp\frac{-cx^2}{B^2+xy} \end{align*} by the highlighted statement, for all real $$x>0$$. Using this inequality with $$y=B(x/B)^{2/3}$$, integrating in $$x>0$$, and using the substitutions $$z=B(x/B)^{2/3}$$ and $$x/B=t$$, we have \begin{align*} ES_n^4&=\int_0^\infty dx\,4x^3P(|S_n|\ge x) \\ &\le\sum_{i=1}^n \int_0^\infty dx\,4x^3 P(|X_i|>B(x/B)^{2/3}) \\ & +\int_0^\infty dx\,4x^3 2\exp\frac{-cx^2}{B^2+xB(x/B)^{2/3}} \\ &\ll A^{(6)}_n/B^2+B^4. \end{align*} This completes the proof of Lemma 1 and thus the proof of Theorem 2. $$\Box$$

Whereas, as has just been shown, the highlighted statement is false even for conditionally symmetric martingale difference sequences $$(X_1,\dots,X_n)$$, note Theorem 3.6, which implies that for any conditionally symmetric martingale difference sequences $$(X_1,\dots,X_n)$$ such that $$\sum_{i=1}^n X_i^2\le B^2$$ for some real $$B>0$$, we have $$\begin{equation*} P\Big(\Big|\sum_{i=1}^n X_i\Big|\ge x\Big)\le2\exp\frac{-x^2}{2B^2} \end{equation*}$$ for all real $$x>0$$.

• thank you very much for such a comprehensive answer. I went through the paper that you have cited, but I couldn't find Theorem 3.6. Perhaps you meant Theorem 3? I have a couple of more questions :) 1. Is $B^2$ here equal to $A_1^2$ (and $A_2=0$) according to the notation of paper? 2. And isn’t the inequality you wrote at the end the same as Azuma’s inequality or am I missing something?
– Siam
Sep 25, 2020 at 15:37
• @Siam : Oops! I had given a wrong link. This is now corrected. Also, the last displayed inequality in the answer differs from Azuma's in that the inequality in the answer assumes a bound on the sum of the squares of the $X_i$'s, whereas Azuma's assumes bounds on the each of the squares of the $X_i$i's. When the $X_i$'s are independent, these two assumptions are equivalent, but not so in general. (On the other hand, Azuma's inequality does not assume the conditional symmetry). Also, Azuma's inequality is due entirely to Hoeffding '63 (see the last paragraph of Section 2 of Hoeffding's paper). Sep 25, 2020 at 21:33

Here is a simple counter example to the original question with $$B=y=1$$, which also gives an alternative proof of Theorem 2 from Iosif Pinelis' answer. Let $$\{R_i\}_{1 \le i \ge n}$$ be independent Rademacher random variables, so that $$\mathbb{P}(R_i=\pm 1)=1/2$$. Let $$J$$ be an indicator variable (independent of all the $$R_i$$) so that $$\mathbb{P}(J=1)=1/n=1-\mathbb{P}(J=0)$$, and define $$X_i:=JR_i$$ for $$1 \le i \le n$$. Then $$\{X_i\}_{1 \le i \ge n}$$ is a martingale difference sequence satisfying $${\rm Var}(X_i)=1/n$$. However, for $$x=\sqrt{n}$$ we have $$\mathbb{P}\left[ \sum_{i=1}^{n}X_i \geq x \right] =\frac{1}{n} \mathbb{P}\left[ \sum_{i=1}^{n}R_i \geq x \right] \ge c/n=c/x^2$$ for an absolute constant $$c$$. Indeed, by the Central limit Theorem, this will hold for any $$c< \mathbb{P}(Z\ge 1)$$ if $$n$$ is large enough, where $$Z$$ is standard normal.