Return to Answer

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.

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.

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 \geq 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}[|X_i-X_{i-1}|\leq c_i]=1$), and then applying the above result.

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.

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}]=0$ and
2. $\mathbb{P}[X_i \in [a_i,b_i] | X_1=x_1, \cdots, X_{i-1}=x_{i-1}]=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 \in \mathbb{R} ~~~~~ \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+1}}\right] = \mathbb{E}\left[e^{\lambda Y_i}\cdot e^{\lambda X_{i+1}}\right] = \mathbb{E}\left[e^{\lambda Y_i}\cdot \mathbb{E}\left[e^{\lambda X_{i+1}}\middle|Y_i\right]\right].$$ By assumption, $\mathbb{E}[X_{i+1}|Y_i=y_i]=0$ and $\mathbb{P}[X_{i+1} \in [a_{i+1},b_{i+1}] | Y_i=y_i] =1$ for all $y_i$ in the support of $Y_i$. (Note that $Y_i=X_1+\cdots+X_i$.) Thus, by Hoeffding's lemma, $\mathbb{E}\left[e^{\lambda X_{i+1}}\middle|Y_i=y_i\right] \leq e^{\lambda^2(b_{i+1}-a_{i+1})^2/8}$ for all $y_i$ in the support of $Y_i$ and all $\lambda \in \mathbb{R}$. Hence $$\mathbb{E}\left[e^{\lambda Y_{i+1}}\right] \leq \mathbb{E}\left[e^{\lambda Y_i}\cdot e^{\lambda^2(b_{i+1}-a_{i+1})^2/8}\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 \geq 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]$.

Note that the $Y_i$ random variables in the proof are a Martingale. 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}[|X_i-X_{i-1}|\leq c_i]=1$), and then applying the above result.

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 \geq 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}[|X_i-X_{i-1}|\leq c_i]=1$), and then applying the above result.