<p>The generic Chernoff bound for a random variable <span class="math-container">$X$</span> is attained by applying Markov's inequality to <span class="math-container">$e^{t X}$</span>. For positive <span class="math-container">$t$</span> this gives a bound on the right tail of <span class="math-container">$X$</span> in terms of its moment-generating function <span class="math-container">$M(t)=\mathrm{E}\left(e^{t X}\right)$</span> :
<span class="math-container">$$
\mathrm{P}(X \geq nq)=\mathrm{P}\left(e^{t X} \geq e^{t nq}\right) \leq M(t) e^{-t nq} \quad(t&gt;0)
$$</span>
Since this bound holds for every positive <span class="math-container">$t$</span>, we may take the infimum:
<span class="math-container">$$
\mathrm{P}(X \geq nq) \leq \inf _{t&gt;0} M(t) e^{-t nq}
$$</span></p>
<p>When <span class="math-container">$X$</span> is the sum of <span class="math-container">$n$</span> independent random variables <span class="math-container">$X_1, \ldots, X_n$</span>, the moment generating function of <span class="math-container">$X$</span> is the product of the individual moment generating functions, giving that:
<span class="math-container">$$
\operatorname{Pr}(X \geq nq) \leq \inf _{t&gt;0} \frac{\mathrm{E}\left[\prod_{i=1}^n e^{t \cdot X_i}\right]}{e^{t \cdot nq}}=\inf _{t&gt;0} e^{-t \cdot nq} \prod_{i=1}^n \mathrm{E}\left[e^{t \cdot X_i}\right]
$$</span>
Now,
<span class="math-container">$$\mathrm{E}\left[e^{t \cdot X_i}\right]=\left(1-p_i\right) e^0+p_i e^t$$</span></p>
<p><span class="math-container">$$
\operatorname{Pr}(X \geq nq) \leq \inf _{t&gt;0} e^{-t \cdot nq} \prod_{i=1}^n \left( p_i e^t+(1-p_i)\right)
$$</span>
Let,
<span class="math-container">$$a= \prod_{i=1}^n \left( p_i e^t+(1-p_i)\right)\\b=(\bar{p}e^t+(1-\bar{p}))^n.$$</span> where <span class="math-container">$ \bar{p}=\frac{1}{n}\sum_{i=1}^np_i$</span>,<span class="math-container">$0\leq p_i\leq 1,t&gt;0,n\in \mathbb{Z^+}$</span></p>
<p><span class="math-container">\begin{align}
    \log(a) 
    &amp;= \log \left ( \prod_{i=1}^n (p_ie^t + (1-p_i)) \right ) \\
    &amp;= \sum_{i=1}^n \log (p_ie^t + 1 - p_i) \\
    &amp;= n \sum_{i=1}^n \frac{1}{n} \log(p_i e^t + 1 - p_i) \\
    &amp;\leq n \log \left ( \sum_{i=1}^n \frac{1}{n} (p_ie^t + 1-p_i) \right ) \\
    &amp;= n \log (\bar{p}e^t + 1 - \bar{p}) \\
    &amp;= \log \left ( (\bar{p}e^t + (1- \bar{p}))^n \right ) = \log(b)
\end{align}</span>
where the inequality is a consequence of Jensen's inequality and the fact that <span class="math-container">$\log$</span> is concave. <a href="https://math.stackexchange.com/a/4783713/972242">relevant answer</a></p>
<p>Then
<span class="math-container">$$
\operatorname{Pr}(X \geq nq) \leq \inf _{t&gt;0} e^{-t \cdot nq} a\leq \inf _{t&gt;0} e^{-t \cdot nq} b= \inf _{t&gt;0} e^{-t \cdot nq}(\bar{p}e^t+(1-\bar{p}))^n
$$</span>
<span class="math-container">$$
\operatorname{Pr}(X \geq nq) \leq \inf _{t&gt;0}\left(\bar{p} e^{(1-q) t}+(1-\bar{p}) e^{-q t}\right)^n
$$</span></p>
<p>Therefore, we can easily compute the infimum, using calculus:
<span class="math-container">$$
\frac{d}{d t}\left(\bar{p} e^{(1-q) t}+(1-\bar{p}) e^{-q t}\right)=(1-q) \bar{p} e^{(1-q) t}-q(1-\bar{p}) e^{-q t}
$$</span>
Setting the equation to zero and solving, we have
<span class="math-container">$$
\begin{aligned}
(1-q) \bar{p} e^{(1-q) t} &amp; =q(1-\bar{p}) e^{-q t} \\
(1-q) \bar{p} e^t &amp; =q(1-\bar{p})
\end{aligned}
$$</span>
so that
<span class="math-container">$$
e^t=\frac{(1-\bar{p}) q}{(1-q) \bar{p}}
$$</span>
Thus,
<span class="math-container">$$
t=\log \left(\frac{(1-\bar{p}) q}{(1-q)\bar{p}}\right)
$$</span></p>
<p>Setting <span class="math-container">$q=\bar{p}+\varepsilon&gt;\bar{p}$</span>, we see that <span class="math-container">$t&gt;0$</span>, so our bound is satisfied on <span class="math-container">$t$</span>. Having solved for <span class="math-container">$t$</span>, we can plug back into the equations above to find that
<span class="math-container">$$
\begin{aligned}
\log \left(\bar{p} e^{(1-q) t}+(1-\bar{p}) e^{-q t}\right) &amp; =\log \left(e^{-q t}\left(1-\bar{p}+\bar{p} e^t\right)\right) \\
&amp; =\log \left(e^{-q \log \left(\frac{(1-\bar{p}) q}{(1-q) \bar{p}}\right)}\right)+\log \left(1-\bar{p}+\bar{p} e^{\log \left(\frac{1-\bar{p}}{1-q}\right)} e^{\log \frac{q}{\bar{p}}}\right) \\
&amp; =-q \log \frac{1-\bar{p}}{1-q}-q \log \frac{q}{\bar{p}}+\log \left(1-\bar{p}+\bar{p}\left(\frac{1-\bar{p}}{1-q}\right) \frac{q}{\bar{p}}\right) \\
&amp; =-q \log \frac{1-\bar{p}}{1-q}-q \log \frac{q}{\bar{p}}+\log \left(\frac{(1-\bar{p})(1-q)}{1-q}+\frac{(1-\bar{p}) q}{1-q}\right) \\
&amp; =-q \log \frac{q}{\bar{p}}+\left(-q \log \frac{1-\bar{p}}{1-q}+\log \frac{1-\bar{p}}{1-q}\right) \\
&amp; =-q \log \frac{q}{\bar{p}}+(1-q) \log \frac{1-\bar{p}}{1-q} \\
&amp; =-D(q \| \bar{p}) .
\end{aligned}
$$</span>
Finally,</p>
<p><span class="math-container">$$\operatorname{Pr}\left(\frac{1}{n} \sum X_i \geq \bar{p}+\varepsilon\right) \leq e^{-D(\bar{p}+\varepsilon \| \bar{p}) n}$$</span></p>

CC BY-SA 4.0
2023-10-10T21:42:37.917Z
2023-10-10T21:42:37.917Z
Dotman
<p>From wikipedia,</p>
<p><strong><a href="https://en.wikipedia.org/wiki/Chernoff_bound#Additive_form_(absolute_error)" rel="nofollow noreferrer">Additive form (absolute error)</a></strong></p>
<p>The following theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem.</p>
<p><em>Chernoff-Hoeffding theorem.</em></p>
<p>Suppose <span class="math-container">$X_1, \ldots, X_n$</span> are i.i.d. random variables, taking values in <span class="math-container">$\{0,1\}$</span>. Let <span class="math-container">$p=\mathrm{E}\left[X_i\right]$</span> and <span class="math-container">$\varepsilon&gt;0$</span>.</p>
<p><span class="math-container">$$
Pr\left(\frac{1}{n} \sum X_i \geq p+\varepsilon\right) \leq\left(\left(\frac{p}{p+\varepsilon}\right)^{p+\varepsilon}\left(\frac{1-p}{1-p-\varepsilon}\right)^{1-p-\varepsilon}\right)^n=e^{-D(p+\varepsilon \| p) n }
$$</span></p>
<p><span class="math-container">$$
Pr \left(\frac{1}{n} \sum X_i \leq p-\varepsilon\right) \leq\left(\left(\frac{p}{p-\varepsilon}\right)^{p-\varepsilon}\left(\frac{1-p}{1-p+\varepsilon}\right)^{1-p+\varepsilon}\right)^n=e^{-D(p-\varepsilon \| p) n}
$$</span></p>
<p>where
<span class="math-container">$$
D(x \| y)=x \ln \frac{x}{y}+(1-x) \ln \left(\frac{1-x}{1-y}\right)
$$</span></p>
<p><strong>Question</strong></p>
<p>As I understand, inorder to apply this specific form of the chernoff bound, the random variables should have the same expectation value. Is there a way to modify this bound to the case where the random variables don't necessarily have the same expectation value?</p>
<p>EDIT</p>
<p>I've written a  possible solution in the answers</p>
<p><strong>Is my answer correct? If its correct then what is the relevance of the <a href="https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_form_(relative_error)" rel="nofollow noreferrer">Multiplicative chernoff bound  variables</a>? Additive form do not use any approximations and is hence tighter than the multiplicative form. Why not just use the additive form for any independent variables?</strong></p>

CC BY-SA 4.0
2023-10-09T23:17:46.363Z
The following variant is also known: Let $p_i \in (0, 1)$ and let $\mu=\sum_{i=1}^n p_i$. If $p_i = \mathbb{E}(X_i)$, then letting $S=\sum_i X_i$, we have $\Pr[|S - \mu|\geq \Delta ] \leq 2e^{-\Delta^2/n}$ for any $\Delta\geq 0$. Is this tight enough? (I believe there are tighter versions)
user3508551
CC BY-SA 4.0
2023-10-09T23:25:42.813Z
Sorry, this should be $2e^{-{\bf 2}\Delta^2/n}$.
user3508551
CC BY-SA 4.0
2023-10-10T06:04:38.293Z
I don't get your question: Wikipedia entry for [Hoeffding's inequality](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality) does not assume the same expectation for the variables…
Bruno
CC BY-SA 4.0
2023-10-10T12:03:36.030Z
@Bruno the OP is asking for the specific form of the bound given in terms of relative entropy. This is not the same as what is listed on Wikipedia (the "usual" form of the bound).
Clement C.
CC BY-SA 4.0
2023-10-10T12:40:03.450Z
Please see my edit @Bruno
Dotman
CC BY-SA 4.0
2023-10-10T18:18:12.950Z
Looks correct to me. Well done! It's what I tried to do in my original answer but messed up.
Aryeh
CC BY-SA 4.0
2023-10-10T19:28:01.037Z
Thanks! Could you please comment on my last question? Doesnt this mean that the additive form is superior to the multiplicative form?
Dotman
CC BY-SA 4.0
2023-10-10T20:27:25.320Z
I don't know if one easily follows from the other -- che choices of t are different, for example. Also, I don't think either one is uniformly superior to the other over all parameter regimes.
Aryeh
CC BY-SA 4.0
2023-10-10T20:41:52.250Z
Also, simplicity is useful. The KL-based bound is not always the nicest to work with to get easy-to-state or manipulate results, and if the other one is tight enough...
Clement C.
CC BY-SA 4.0
2023-10-10T21:46:59.910Z
Hmm not so good news to me!  My next order of business was to get a (easy to solve) lower bound for the KL divergence. Wikipedia has some approximations but not tight enough.
Dotman
CC BY-SA 4.0
2023-10-10T21:52:20.780Z
@Aryeh Im not so sure about it but If my answer is correct then the additive form should always give a bound as good as the multiplicative form, for a given $n, \mu=n\bar{p}$. The derivation of multiplicative form involves two approximations ( including the choice of t, which is not minimised), whereas the additive form makes no approximations and the choice of t is minimised
Dotman
CC BY-SA 4.0
2023-10-10T22:25:01.233Z
See e.g. https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_form_(relative_error) for a standard multiplicative Chernoff bound that does not require the variables to be identically distributed.  This variant also implies the standard additive bound by an appropriate change of variables.
Neal Young
<pr.probability><st.statistics><chernoff-bound>
Additive chernoff bound
Dotman
# Additive chernoff bound

(Asked by: username_0 on 2023-10-09)

From wikipedia,

**[Additive form (absolute error)](https://en.wikipedia.org/wiki/Chernoff_bound#Additive_form_(absolute_error))**

The following theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem.

*Chernoff-Hoeffding theorem.*

Suppose $X\_1, \ldots, X\_n$ are i.i.d. random variables, taking values in $\{0,1\}$. Let $p=\mathrm{E}\left[X\_i\right]$ and $\varepsilon>0$.

$$
Pr\left(\frac{1}{n} \sum X\_i \geq p+\varepsilon\right) \leq\left(\left(\frac{p}{p+\varepsilon}\right)^{p+\varepsilon}\left(\frac{1-p}{1-p-\varepsilon}\right)^{1-p-\varepsilon}\right)^n=e^{-D(p+\varepsilon \| p) n }
$$

$$
Pr \left(\frac{1}{n} \sum X\_i \leq p-\varepsilon\right) \leq\left(\left(\frac{p}{p-\varepsilon}\right)^{p-\varepsilon}\left(\frac{1-p}{1-p+\varepsilon}\right)^{1-p+\varepsilon}\right)^n=e^{-D(p-\varepsilon \| p) n}
$$

where
$$
D(x \| y)=x \ln \frac{x}{y}+(1-x) \ln \left(\frac{1-x}{1-y}\right)
$$

**Question**

As I understand, inorder to apply this specific form of the chernoff bound, the random variables should have the same expectation value. Is there a way to modify this bound to the case where the random variables don't necessarily have the same expectation value?

EDIT

I've written a possible solution in the answers

**Is my answer correct? If its correct then what is the relevance of the [Multiplicative chernoff bound variables](https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_form_(relative_error))? Additive form do not use any approximations and is hence tighter than the multiplicative form. Why not just use the additive form for any independent variables?**

**Tags:** pr.probability, st.statistics, chernoff-bound
> **Comments:**
> **username_1**: The following variant is also known: Let $p_i \in (0, 1)$ and let $\mu=\sum_{i=1}^n p_i$. If $p_i = \mathbb{E}(X_i)$, then letting $S=\sum_i X_i$, we have $\Pr[|S - \mu|\geq \Delta ] \leq 2e^{-\Delta^2/n}$ for any $\Delta\geq 0$. Is this tight enough? (I believe there are tighter versions)  
> **username_1**: Sorry, this should be $2e^{-{\bf 2}\Delta^2/n}$.  
> **username_2**: I don't get your question: Wikipedia entry for [Hoeffding's inequality](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality) does not assume the same expectation for the variables…  
> **username_3**: @Bruno the OP is asking for the specific form of the bound given in terms of relative entropy. This is not the same as what is listed on Wikipedia (the "usual" form of the bound).  
> **username_0**: Please see my edit @Bruno  
> **username_4**: Looks correct to me. Well done! It's what I tried to do in my original answer but messed up.  
> **username_0**: Thanks! Could you please comment on my last question? Doesnt this mean that the additive form is superior to the multiplicative form?  
> **username_4**: I don't know if one easily follows from the other -- che choices of t are different, for example. Also, I don't think either one is uniformly superior to the other over all parameter regimes.  
> **username_3**: Also, simplicity is useful. The KL-based bound is not always the nicest to work with to get easy-to-state or manipulate results, and if the other one is tight enough...  
> **username_0**: Hmm not so good news to me!  My next order of business was to get a (easy to solve) lower bound for the KL divergence. Wikipedia has some approximations but not tight enough.  
> **username_0**: @Aryeh Im not so sure about it but If my answer is correct then the additive form should always give a bound as good as the multiplicative form, for a given $n, \mu=n\bar{p}$. The derivation of multiplicative form involves two approximations ( including the choice of t, which is not minimised), whereas the additive form makes no approximations and the choice of t is minimised  
> **username_5**: See e.g. https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_form_(relative_error) for a standard multiplicative Chernoff bound that does not require the variables to be identically distributed.  This variant also implies the standard additive bound by an appropriate change of variables.  

---

## 1 answers

### Answer by username_0 on 2023-10-10. Score: 1 | Accepted answer

The generic Chernoff bound for a random variable $X$ is attained by applying Markov's inequality to $e^{t X}$. For positive $t$ this gives a bound on the right tail of $X$ in terms of its moment-generating function $M(t)=\mathrm{E}\left(e^{t X}\right)$ :
$$
\mathrm{P}(X \geq nq)=\mathrm{P}\left(e^{t X} \geq e^{t nq}\right) \leq M(t) e^{-t nq} \quad(t>0)
$$
Since this bound holds for every positive $t$, we may take the infimum:
$$
\mathrm{P}(X \geq nq) \leq \inf \_{t>0} M(t) e^{-t nq}
$$

When $X$ is the sum of $n$ independent random variables $X\_1, \ldots, X\_n$, the moment generating function of $X$ is the product of the individual moment generating functions, giving that:
$$
\operatorname{Pr}(X \geq nq) \leq \inf \_{t>0} \frac{\mathrm{E}\left[\prod\_{i=1}^n e^{t \cdot X\_i}\right]}{e^{t \cdot nq}}=\inf \_{t>0} e^{-t \cdot nq} \prod\_{i=1}^n \mathrm{E}\left[e^{t \cdot X\_i}\right]
$$
Now,
$$\mathrm{E}\left[e^{t \cdot X\_i}\right]=\left(1-p\_i\right) e^0+p\_i e^t$$

$$
\operatorname{Pr}(X \geq nq) \leq \inf \_{t>0} e^{-t \cdot nq} \prod\_{i=1}^n \left( p\_i e^t+(1-p\_i)\right)
$$
Let,
$$a= \prod\_{i=1}^n \left( p\_i e^t+(1-p\_i)\right)\\b=(\bar{p}e^t+(1-\bar{p}))^n.$$ where $ \bar{p}=\frac{1}{n}\sum\_{i=1}^np\_i$,$0\leq p\_i\leq 1,t>0,n\in \mathbb{Z^+}$

\begin{align}
\log(a)
&= \log \left ( \prod\_{i=1}^n (p\_ie^t + (1-p\_i)) \right ) \\
&= \sum\_{i=1}^n \log (p\_ie^t + 1 - p\_i) \\
&= n \sum\_{i=1}^n \frac{1}{n} \log(p\_i e^t + 1 - p\_i) \\
&\leq n \log \left ( \sum\_{i=1}^n \frac{1}{n} (p\_ie^t + 1-p\_i) \right ) \\
&= n \log (\bar{p}e^t + 1 - \bar{p}) \\
&= \log \left ( (\bar{p}e^t + (1- \bar{p}))^n \right ) = \log(b)
\end{align}
where the inequality is a consequence of Jensen's inequality and the fact that $\log$ is concave. [relevant answer](https://math.stackexchange.com/a/4783713/972242)

Then
$$
\operatorname{Pr}(X \geq nq) \leq \inf \_{t>0} e^{-t \cdot nq} a\leq \inf \_{t>0} e^{-t \cdot nq} b= \inf \_{t>0} e^{-t \cdot nq}(\bar{p}e^t+(1-\bar{p}))^n
$$
$$
\operatorname{Pr}(X \geq nq) \leq \inf \_{t>0}\left(\bar{p} e^{(1-q) t}+(1-\bar{p}) e^{-q t}\right)^n
$$

Therefore, we can easily compute the infimum, using calculus:
$$
\frac{d}{d t}\left(\bar{p} e^{(1-q) t}+(1-\bar{p}) e^{-q t}\right)=(1-q) \bar{p} e^{(1-q) t}-q(1-\bar{p}) e^{-q t}
$$
Setting the equation to zero and solving, we have
$$
\begin{aligned}
(1-q) \bar{p} e^{(1-q) t} & =q(1-\bar{p}) e^{-q t} \\
(1-q) \bar{p} e^t & =q(1-\bar{p})
\end{aligned}
$$
so that
$$
e^t=\frac{(1-\bar{p}) q}{(1-q) \bar{p}}
$$
Thus,
$$
t=\log \left(\frac{(1-\bar{p}) q}{(1-q)\bar{p}}\right)
$$

Setting $q=\bar{p}+\varepsilon>\bar{p}$, we see that $t>0$, so our bound is satisfied on $t$. Having solved for $t$, we can plug back into the equations above to find that
$$
\begin{aligned}
\log \left(\bar{p} e^{(1-q) t}+(1-\bar{p}) e^{-q t}\right) & =\log \left(e^{-q t}\left(1-\bar{p}+\bar{p} e^t\right)\right) \\
& =\log \left(e^{-q \log \left(\frac{(1-\bar{p}) q}{(1-q) \bar{p}}\right)}\right)+\log \left(1-\bar{p}+\bar{p} e^{\log \left(\frac{1-\bar{p}}{1-q}\right)} e^{\log \frac{q}{\bar{p}}}\right) \\
& =-q \log \frac{1-\bar{p}}{1-q}-q \log \frac{q}{\bar{p}}+\log \left(1-\bar{p}+\bar{p}\left(\frac{1-\bar{p}}{1-q}\right) \frac{q}{\bar{p}}\right) \\
& =-q \log \frac{1-\bar{p}}{1-q}-q \log \frac{q}{\bar{p}}+\log \left(\frac{(1-\bar{p})(1-q)}{1-q}+\frac{(1-\bar{p}) q}{1-q}\right) \\
& =-q \log \frac{q}{\bar{p}}+\left(-q \log \frac{1-\bar{p}}{1-q}+\log \frac{1-\bar{p}}{1-q}\right) \\
& =-q \log \frac{q}{\bar{p}}+(1-q) \log \frac{1-\bar{p}}{1-q} \\
& =-D(q \| \bar{p}) .
\end{aligned}
$$
Finally,

$$\operatorname{Pr}\left(\frac{1}{n} \sum X\_i \geq \bar{p}+\varepsilon\right) \leq e^{-D(\bar{p}+\varepsilon \| \bar{p}) n}$$


---

