2
$\begingroup$

From wikipedia,

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? 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?

$\endgroup$
12
  • 1
    $\begingroup$ 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) $\endgroup$ Oct 9, 2023 at 23:17
  • $\begingroup$ Sorry, this should be $2e^{-{\bf 2}\Delta^2/n}$. $\endgroup$ Oct 9, 2023 at 23:25
  • 2
    $\begingroup$ @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). $\endgroup$
    – Clement C.
    Oct 10, 2023 at 12:03
  • 1
    $\begingroup$ Please see my edit @Bruno $\endgroup$
    – Dotman
    Oct 10, 2023 at 12:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aryeh
    Oct 10, 2023 at 20:27

1 Answer 1

1
$\begingroup$

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

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.