Skip to main content
7 of 8
I have added an addendum to address your question.
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

This inequality cannot be true. Let us rewrite it in the more common form $$P(R_n\ge x)\le e^{-x^2/2} \tag{1} $$ for $x\ge0$, where $R_n:=S_n/B_n$, $S_n:=\sum_1^n c_iB_i$, $B_n:=\sqrt{\sum_1^n c_i^2}$.

Let $n=2$, $c_1=1$, and $c_2=aI\{B_1=-1\}$, where $I\{\cdot\}$ denotes the indicator function, $a>0$ is large enough so that $\frac{-1+a}{\sqrt{1+a^2}}>x$, $x$ is less than $1$ but close enough to $1$ so that $e^{-x^2/2}<0.7$ (note that $e^{-1^2/2}=0.606\ldots<0.7$). Then $$P(R_2\ge x)=P(R_2\ge x,B_1=1)+P(R_2\ge x,B_1=-1)$$ $$=P(R_1\ge x,B_1=1)+P\Big(\frac{-1+aB_2}{\sqrt{1+a^2}}\ge x,B_1=-1\Big) $$ $$=P(B_1\ge x,B_1=1)+P(B_2=1,B_1=-1)$$ $$=P(B_1=1)+P(B_2=1,B_1=-1)$$ $$=\tfrac12+\tfrac14=0.75>0.7>e^{-x^2/2}, $$ so that $(1)$ fails to hold.

Letting now $c_3=\dots=c_n=0$, one disproves the inequality in question for any natural $n\ge2$.

(What is sometimes referred to as the Azuma (or Hoeffding--Azuma) inequality is due entirely to [Hoeffding 1963]; see the last paragraph of Section 2 there.)

Addendum: I doubt very much that any modification of the inequality in question can hold without preventing the sum of the conditional variances of the increments of the martingale from being too small; cf. e.g. inequalities (1.11) in [de la Peña]. That actually gave me the idea for the counterexample.

Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229