<p>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!).</p>
<p>Define <span class="math-container">$Y_i=\sum_{j=1}^i C_j$</span>. We claim that</p>
<p><span class="math-container">\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*}</span></p>
<p>For all <span class="math-container">$i$</span> and <span class="math-container">$\lambda$</span> we have</p>
<p><span class="math-container">\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*}</span></p>
<p>By assumption  <span class="math-container">$\mu _{C_i}=E[C_i|C_1=c_1,...,C_{i-1}=c_{i-1}]\leq \beta$</span> and <span class="math-container">$Pr[C_i \in [-\alpha,\alpha]]=1$</span>(<span class="math-container">$Pr[C_i \in [-\alpha,\alpha]]=1 \Longleftrightarrow -\alpha \leq C_i \leq \alpha$</span>) (Absolute value definition). By <a href="https://www.stat.cmu.edu/%7Elarry/=stat705/Lecture2.pdf" rel="nofollow noreferrer">Hoeffding Lemma </a>, where <span class="math-container">$a_i=-\alpha$</span> y <span class="math-container">$b_i=\alpha$</span>. We can get:</p>
<p><span class="math-container">\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*}</span></p>
<p>because <span class="math-container">$\mu _{C_i} \leq \beta$</span>,</p>
<p><span class="math-container">\begin{equation*}
\begin{aligned}
     E[e^{\lambda Y_i}] &amp;= E[e^{\lambda Y_{i-1}}\cdot E[e^{\lambda C_i}|C_1,...,C_{i-1}]] \\
     &amp;\leq E[e^{\lambda Y_{i-1}}\cdot e^{\lambda\beta +\frac18 \lambda^2(2\alpha)^2}]\\
     &amp;.\\
     &amp;. \ \text{(Iterating)} \\
     &amp;. \\
     &amp;\leq e^{\sum_{i=1}^k \lambda \beta + \frac18 \lambda^2(2\alpha)^2 }\\
     &amp;= e^{\lambda k \beta + k \frac18 \lambda^2(2\alpha)^2}\\
     &amp;= e^{\lambda k \beta + k \frac12 \lambda^2(\alpha)^2}\
\end{aligned}
\end{equation*}</span></p>
<p>In that way :</p>
<p><span class="math-container">\begin{equation*}
\begin{aligned}
    Pr \Big[ \sum_{i=1}^k C_i &gt; k\beta +z \sqrt{k}\cdot \alpha \Big] &amp;= Pr \Big[ \lambda Y_n &gt; \lambda (k\beta +z \sqrt{k}\cdot \alpha) \Big] \\
    &amp;= Pr \Big[ e^{ \lambda Y_n} &gt; e^{ \lambda (k\beta +z \sqrt{k}\cdot \alpha)} \Big] \ \ \ \text{(By Markov inequality)}\\
    &amp;\leq \frac{E[e^{Y_n}]}{e^{ \lambda(k\beta +z \sqrt{k}\cdot \alpha)}}\\
    &amp;= e^{- \lambda(k\beta +z \sqrt{k}\cdot \alpha)}E[e^{ \lambda Y_n}]\\
    &amp; \leq e^{- \lambda(k\beta +z \sqrt{k}\cdot \alpha)} e^{\lambda k \beta + k \frac12 \lambda^2(\alpha)^2}
\end{aligned}
\end{equation*}</span></p>
<p>When we minimize <span class="math-container">$\lambda $</span>, we get that <span class="math-container">$\lambda = \frac{z}{\sqrt{k}\alpha}$</span>, replacing it on the equation we have :</p>
<p><span class="math-container">\begin{equation*}
    Pr \Big[ \sum_{i=1}^k C_i &gt; k\beta +z \sqrt{k}\cdot \alpha \Big] \leq e^{\frac{-z^2}{2}}
\end{equation*}</span></p>

CC BY-SA 4.0
2020-07-09T02:13:20.350Z
2020-07-09T02:42:04.237Z
2020-07-09T02:42:04.237Z
Miguel Gutierrez
<p>I can't find a reference, so I'll just sketch the proof here.</p>
<blockquote>
<p><strong>Theorem.</strong> Let <span class="math-container">$X_1, \cdots, X_n$</span> be real random variables. Let <span class="math-container">$a_1, \cdots, a_n, b_1, \cdots, b_n$</span> be constants. Suppose that, for all <span class="math-container">$i \in \{1,\cdots,n\}$</span> and all <span class="math-container">$(x_1,\cdots,x_{i-1})$</span> in the support of <span class="math-container">$(X_1, \cdots, X_{i-1})$</span>, we have</p>
<ol>
<li><span class="math-container">$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \leq 0$</span> and</li>
<li><span class="math-container">$\mathbb{P}[X_i \in [a_i,b_i]]=1$</span>.</li>
</ol>
<p>Then, for all <span class="math-container">$t\geq0$</span>, <span class="math-container">$$\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).$$</span></p>
</blockquote>
<p><em>Proof.</em> Define <span class="math-container">$Y_i = \sum_{j=1}^i X_j$</span>. We claim that <span class="math-container">$$\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*{(*)}$$</span> For all <span class="math-container">$i$</span> and <span class="math-container">$\lambda$</span>, we have <span class="math-container">$$\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].$$</span>
By assumption, <span class="math-container">$\mu(y_{i-1}):=\mathbb{E}[X_i|Y_{i-1}=y_{i-1}]\leq 0$</span> and <span class="math-container">$\mathbb{P}[X_i \in [a_i,b_i]] =1$</span> for all <span class="math-container">$y_{i-1}$</span> in the support of <span class="math-container">$Y_{i-1}$</span>. (Note that <span class="math-container">$Y_{i-1}=X_1+\cdots+X_{i-1}$</span>.) Thus, by <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_lemma" rel="noreferrer">Hoeffding's lemma</a>, <span class="math-container">$$\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}$$</span> for all <span class="math-container">$y_{i-1}$</span> in the support of <span class="math-container">$Y_{i-1}$</span> and all <span class="math-container">$\lambda \in \mathbb{R}$</span>. Since <span class="math-container">$\mu(y_{i-1})\leq 0$</span>, we have, for all <span class="math-container">$\lambda \geq 0$</span>, <span class="math-container">$$\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].$$</span>
Now induction yields the claim (*) above.</p>
<p>Now we apply <a href="https://en.wikipedia.org/wiki/Markov%27s_inequality" rel="noreferrer">Markov's inequality</a> to <span class="math-container">$e^{\lambda Y_n}$</span> and use our claim (*). For all <span class="math-container">$t, \lambda &gt; 0$</span>, <span class="math-container">$$\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}}.$$</span>
Finally, set <span class="math-container">$\lambda=\frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}$</span> to minimize the right hand expression and obtain the result. <span class="math-container">$\tag*{$\blacksquare$}$</span></p>
<p>As I mentioned in my comment, the key difference between this and the &quot;usual&quot; statement of Azuma's inequality is requiring <span class="math-container">$X_i \in [a_i,b_i]$</span>, rather than <span class="math-container">$X_i \in [-a,a]$</span>. The former allows more flexibility and this saves a factor of 2 in some cases.</p>
<p>Note that the <span class="math-container">$Y_i$</span> random variables in the proof are a supermartingale. You can obtain the usual version of Azuma's inequality by taking a Martingale <span class="math-container">$Y_1, \cdots, Y_n$</span>, setting <span class="math-container">$X_i=Y_i-Y_{i-1}$</span> and <span class="math-container">$[a_i,b_i]=[-c_i,c_i]$</span> (where <span class="math-container">$\mathbb{P}[|Y_i-Y_{i-1}|\leq c_i]=1$</span>), and then applying the above result.</p>

CC BY-SA 3.0
2017-09-26T02:12:52.647Z
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
CC BY-SA 3.0
2017-09-27T08:01:42.920Z
The proof is also given in the monograph by Dubhashi and Panconesi.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-09-27T18:17:27.050Z
@KristofferArnsfeltHansen: Great. Do you have a link?
Thomas Steinke
CC BY-SA 4.0
2017-09-26T00:24:04.807Z
2018-07-19T17:10:38.710Z
2020-06-17T09:38:08.363Z
Thomas Steinke
<p>In Appendix B of <a href="https://guyrothblum.files.wordpress.com/2014/11/drv10.pdf" rel="noreferrer">Boosting and Differential Privacy</a> by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:</p>

<blockquote>
  <p>Let $C_1, \dots, C_k$ be real-valued random variables such that for every $i \in [k]$,</p>
  
  <ol>
  <li>$\Pr[|C_i| \leq \alpha] = 1$, and</li>
  <li>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$.</li>
  </ol>
  
  <p>Then for every $z &gt; 0$, we have $\Pr[\sum_{i = 1}^k C_i &gt; k\beta + z \sqrt{k} \cdot \alpha] \leq e^{-z^2/2}$.</p>
</blockquote>

<p>I'm having trouble proving this. The <a href="https://en.wikipedia.org/wiki/Azuma%27s_inequality" rel="noreferrer">standard version of Azuma's inequality</a> says:</p>

<blockquote>
  <p>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 &gt; 0$, we have $\Pr[X_k \geq t] \leq \exp(-t^2/(2 \sum_{i = 1}^k \gamma_i^2))$.</p>
</blockquote>

<p>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 &gt; k\beta + z\sqrt{k} \cdot 2\alpha] \leq e^{-z^2/2}$, which is weaker than the conclusion stated by Dwork et al.</p>

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

CC BY-SA 3.0
2017-09-25T23:44:29.217Z
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 Steinke
<pr.probability><randomized-algorithms><upper-bounds><privacy>
What is the proof of this nonstandard version of Azuma's inequality?
William Hoza
# What is the proof of this nonstandard version of Azuma's inequality?

(Asked by: username_0 on 2017-09-25)

In Appendix B of [Boosting and Differential Privacy](https://guyrothblum.files.wordpress.com/2014/11/drv10.pdf) 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](https://en.wikipedia.org/wiki/Azuma%27s_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?

**Tags:** pr.probability, randomized-algorithms, upper-bounds, privacy
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_1 on 2017-09-26. Score: 15 | Accepted 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](https://en.wikipedia.org/wiki/Hoeffding%27s_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](https://en.wikipedia.org/wiki/Markov%27s_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.

> **Comments:**
> **username_3**: 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$)....  
> **username_4**: The proof is also given in the monograph by Dubhashi and Panconesi.  
> **username_1**: @KristofferArnsfeltHansen: Great. Do you have a link?  

---

### Answer by username_2 on 2020-07-09. Score: 0

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](https://www.stat.cmu.edu/%7Elarry/=stat705/Lecture2.pdf) , 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\*}


---

