# What is the proof of this nonstandard version of Azuma's inequality?

In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:

Let $C_1, \dots, C_k$ be real-valued random variables such that for every $i \in [k]$,

1. $\Pr[|C_i| \leq \alpha] = 1$, and
2. for every $(c_1, \dots, c_{i - 1}) \in \text{Supp}(C_1, \dots, C_{i - 1})$, we have $\text{E}[C_i \mid C_1 = c_1, \dots, C_{i - 1} = c_{i - 1}] \leq \beta$.

Then for every $z > 0$, we have $\Pr[\sum_{i = 1}^k C_i > k\beta + z \sqrt{k} \cdot \alpha] \leq e^{-z^2/2}$.

I'm having trouble proving this. The standard version of Azuma's inequality says:

Suppose $\{X_0, X_1, \dots, X_k\}$ is a martingale, and $|X_i - X_{i - 1}| \leq \gamma_i$ almost surely. Then for all $t > 0$, we have $\Pr[X_k \geq t] \leq \exp(-t^2/(2 \sum_{i = 1}^k \gamma_i^2))$.

To prove the version of Azuma's inequality stated by Dwork et al., I figured we should take $X_0 = 0$ and $X_i = X_{i - 1} + C_i - \text{E}[C_i \mid C_1, C_2, \dots, C_{i - 1}]$. That way, I think $\{X_0, \dots, X_k\}$ is a martingale. But all we can say is that $|X_i - X_{i - 1}| \leq 2\alpha$ almost surely, right? That factor of two causes trouble, because it means that after substituting, we merely find that $\Pr[\sum_{i = 1}^k C_i > k\beta + z\sqrt{k} \cdot 2\alpha] \leq e^{-z^2/2}$, which is weaker than the conclusion stated by Dwork et al.

Is there a simple trick I'm missing? Is the statement by Dwork et al. missing a factor of two?

• The statement in the paper is true, but does not follow from the "usual" version of Azuma's inequality. The issue is that the usual statement assumes $X_i-X_{i-1}\in[-a,a]$ but any interval of the same length will do; there is no reason to assume a symmetric interval. – Thomas Sep 25 '17 at 23:44

I can't find a reference, so I'll just sketch the proof here.

Theorem. Let $$X_1, \cdots, X_n$$ be real random variables. Let $$a_1, \cdots, a_n, b_1, \cdots, b_n$$ be constants. Suppose that, for all $$i \in \{1,\cdots,n\}$$ and all $$(x_1,\cdots,x_{i-1})$$ in the support of $$(X_1, \cdots, X_{i-1})$$, we have

1. $$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \leq 0$$ and
2. $$\mathbb{P}[X_i \in [a_i,b_i]]=1$$.

Then, for all $$t\geq0$$, $$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right] \leq \exp\left(\frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right).$$

Proof. Define $$Y_i = \sum_{j=1}^i X_j$$. We claim that $$\forall i \in \{1,\cdots,n\}~\forall \lambda \geq 0 ~~~~~ \mathbb{E}\left[e^{\lambda Y_i}\right] \leq e^{\frac18 \lambda^2 \sum_{j=1}^i (b_j-a_j)^2}.\tag*{(*)}$$ For all $$i$$ and $$\lambda$$, we have $$\mathbb{E}\left[e^{\lambda Y_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{\lambda X_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot \mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}\right]\right].$$ By assumption, $$\mu(y_{i-1}):=\mathbb{E}[X_i|Y_{i-1}=y_{i-1}]\leq 0$$ and $$\mathbb{P}[X_i \in [a_i,b_i]] =1$$ for all $$y_{i-1}$$ in the support of $$Y_{i-1}$$. (Note that $$Y_{i-1}=X_1+\cdots+X_{i-1}$$.) Thus, by Hoeffding's lemma, $$\mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}=y_{i-1}\right] \leq e^{\lambda\mu(y_{i-1})+\frac18 \lambda^2(b_i-a_i)^2}$$ for all $$y_{i-1}$$ in the support of $$Y_{i-1}$$ and all $$\lambda \in \mathbb{R}$$. Since $$\mu(y_{i-1})\leq 0$$, we have, for all $$\lambda \geq 0$$, $$\mathbb{E}\left[e^{\lambda Y_i}\right] \leq \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{0+\frac18 \lambda^2(b_i-a_i)^2}\right].$$ Now induction yields the claim (*) above.

Now we apply Markov's inequality to $$e^{\lambda Y_n}$$ and use our claim (*). For all $$t, \lambda > 0$$, $$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right]=\mathbb{P}[Y_n \geq t] = \mathbb{P}\left[e^{\lambda Y_n} \geq e^{\lambda t}\right] \leq \frac{\mathbb{E}\left[e^{\lambda Y_n}\right]}{e^{\lambda t}} \leq \frac{e^{\frac18 \lambda^2 \sum_{i=1}^n (b_i-a_i)^2}}{e^{\lambda t}}.$$ Finally, set $$\lambda=\frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}$$ to minimize the right hand expression and obtain the result. $$\tag*{\blacksquare}$$

As I mentioned in my comment, the key difference between this and the "usual" statement of Azuma's inequality is requiring $$X_i \in [a_i,b_i]$$, rather than $$X_i \in [-a,a]$$. The former allows more flexibility and this saves a factor of 2 in some cases.

Note that the $$Y_i$$ random variables in the proof are a supermartingale. You can obtain the usual version of Azuma's inequality by taking a Martingale $$Y_1, \cdots, Y_n$$, setting $$X_i=Y_i-Y_{i-1}$$ and $$[a_i,b_i]=[-c_i,c_i]$$ (where $$\mathbb{P}[|Y_i-Y_{i-1}|\leq c_i]=1$$), and then applying the above result.

• In the first line of the proof, it should presumably be $Y_i = \sum_{j=1}^i X_j$ (upper bound of the sum as $i$ rather than $n$).... – Danica Sep 26 '17 at 2:12
• The proof is also given in the monograph by Dubhashi and Panconesi. – Kristoffer Arnsfelt Hansen Sep 27 '17 at 8:01
• @KristofferArnsfeltHansen: Great. Do you have a link? – Thomas Sep 27 '17 at 18:17

I think, I just made it! basing me on the proof of @Thomas and something of my knowledge. Because @Thomas is not using the same hypothesis, but very similar ones (Thanks Thomas!).

Define $$Y_i=\sum_{j=1}^i C_j$$. We claim that

$$\begin{equation*} E[e^{\lambda Y_i}] \leq e^{\frac{1}{8} \lambda^2 \sum_{j=1}^i(b_j-a_j)^2} \end{equation*}$$

For all $$i$$ and $$\lambda$$ we have

$$\begin{equation*} E[e^{\lambda Y_i}] = E[e^{\lambda Y_{i-1}}\cdot e^{\lambda C_i}] = E[e^{\lambda Y_{i-1}}\cdot E[e^{\lambda C_i}|C_1,...,C_{i-1}]] \end{equation*}$$

By assumption $$\mu _{C_i}=E[C_i|C_1=c_1,...,C_{i-1}=c_{i-1}]\leq \beta$$ and $$Pr[C_i \in [-\alpha,\alpha]]=1$$($$Pr[C_i \in [-\alpha,\alpha]]=1 \Longleftrightarrow -\alpha \leq C_i \leq \alpha$$) (Absolute value definition). By Hoeffding Lemma , where $$a_i=-\alpha$$ y $$b_i=\alpha$$. We can get:

$$\begin{equation*} E \left[e^{\lambda C_i}\middle|C_1=c_1,...,C_{i-1}=c_{i-1}\right] \leq e^{\lambda\mu _{C_i}+\frac18 \lambda^2(2\alpha)^2} \end{equation*}$$

because $$\mu _{C_i} \leq \beta$$,

\begin{equation*} \begin{aligned} E[e^{\lambda Y_i}] &= E[e^{\lambda Y_{i-1}}\cdot E[e^{\lambda C_i}|C_1,...,C_{i-1}]] \\ &\leq E[e^{\lambda Y_{i-1}}\cdot e^{\lambda\beta +\frac18 \lambda^2(2\alpha)^2}]\\ &.\\ &. \ \text{(Iterating)} \\ &. \\ &\leq e^{\sum_{i=1}^k \lambda \beta + \frac18 \lambda^2(2\alpha)^2 }\\ &= e^{\lambda k \beta + k \frac18 \lambda^2(2\alpha)^2}\\ &= e^{\lambda k \beta + k \frac12 \lambda^2(\alpha)^2}\ \end{aligned} \end{equation*}

In that way :

\begin{equation*} \begin{aligned} Pr \Big[ \sum_{i=1}^k C_i > k\beta +z \sqrt{k}\cdot \alpha \Big] &= Pr \Big[ \lambda Y_n > \lambda (k\beta +z \sqrt{k}\cdot \alpha) \Big] \\ &= Pr \Big[ e^{ \lambda Y_n} > e^{ \lambda (k\beta +z \sqrt{k}\cdot \alpha)} \Big] \ \ \ \text{(By Markov inequality)}\\ &\leq \frac{E[e^{Y_n}]}{e^{ \lambda(k\beta +z \sqrt{k}\cdot \alpha)}}\\ &= e^{- \lambda(k\beta +z \sqrt{k}\cdot \alpha)}E[e^{ \lambda Y_n}]\\ & \leq e^{- \lambda(k\beta +z \sqrt{k}\cdot \alpha)} e^{\lambda k \beta + k \frac12 \lambda^2(\alpha)^2} \end{aligned} \end{equation*}

When we minimize $$\lambda$$, we get that $$\lambda = \frac{z}{\sqrt{k}\alpha}$$, replacing it on the equation we have :

$$\begin{equation*} Pr \Big[ \sum_{i=1}^k C_i > k\beta +z \sqrt{k}\cdot \alpha \Big] \leq e^{\frac{-z^2}{2}} \end{equation*}$$