This blog, we still talk about randomized algorithms. Today we will focus on a technique known as the Chernoff bound.

Poisson Trials

Let ${0\leq p_1 , \cdots , p_n \leq 1}$, let ${X_1,\cdots,X_n}$ be independent indicator variables with ${\Pr[X_i = 1]= p_i}$ and let ${X = \sum_{i=1}^n X_i}$.

We call ${X_1,\cdots,X_n}$ as Poisson Trials and say that ${X}$ has the Poisson Binomial Distribution.

First Chernoff Bound

Let ${X_1,\cdots,X_n}$ be independent Poisson Trials such that, for ${1\leq i \leq n}$, ${\Pr[X_i = 1]=p_i}$, where ${0 < p_i < 1}$. Then, for ${X = \sum_{i=1}^n X_i}$, ${\mu = \mathbb{E}[X] = \sum_{i=1}^n p_i}$ and ${\delta>0}$, we have

\[\begin{aligned} \Pr[X > (1+ \delta) \mu] < \left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu} \end{aligned}\]

Note: Main Ideas of proof

• Analyze ${e^{tX}}$ (for some ${t > 0}$) rather than ${X}$.
• Use independence to turn expectation of a product into a product of expectations.
• Pick ${t}$ to get best possible bound.

Proof. For any $t \geq 0$: \(\begin{aligned} \Pr[X > (1 + \delta)\mu] & = \Pr[e^{tX} > e^{t(1+\delta)\mu}] \\ & < \frac{\mathbb{E}[e^{tX}]}{e^{t(1+\delta)\mu}} & (\text{By Markov's inequality}) \\ & = \frac{\prod_{i=1}^n \mathbb{E}[e^{tX_i}]}{e^{t(1+\delta)\mu}} & (\text{By Independence}) \\ & = \frac{\prod_{i=1}^n (e^{t\cdot 0} (1-p_i) + e^{t \cdot 1}p_i )}{e^{t(1+\delta)\mu}} & (\text{By def of } \mathbb{E}) \\ & =\frac{\prod_{i=1}^n (1 + p_i(e^t -1)) }{e^{t(1+\delta)\mu}} & (\text{By def of } \mathbb{E}) \\ & \leq \frac{\prod_{i=1}^n e^{p_i(e^{t}-1)}}{e^{t(1+\delta)\mu}} & (\text{By } 1 + x \leq e^x) \\ & = \frac{e^{(\sum_{i=1}^n p_i(e^{t}-1))}}{e^{t(1+\delta)\mu}} \\ & = \frac{e^{\mu(e^{t}-1)}}{e^{t(1+\delta)\mu}} & (\text{By } \mu = \sum_{i=1}^n p_i)\\ & = \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right)^\mu \end{aligned}\)

Denote ${f(t) = \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right)^\mu}$, now we find ${t}$ to minimize ${f(t)}$. First, we solve derivative of ${f(t)}$

\[\begin{aligned} f'(t) &= \mu \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right) \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right)'\\ & = \mu \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right) \left(e^{(e^t-1)-t(1+\delta)}\right)((e^t-1)-t(1+\delta))'\\ & = \mu \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right) \left(e^{(e^t-1)-t(1+\delta)}\right) (e^t -1 - \delta) \end{aligned}\]

we know ${\mu \left( \frac{e^{(e^{t}-1)}}{e^{t(1+\delta)}} \right) \left(e^{(e^t-1)-t(1+\delta)}\right) > 0}$. Hence, ${f’(t)=0}$ means ${t = \ln (1+\delta)}$. Thus, the ${\min f(t) = f(\ln (1+ \delta)) =\left( \frac{e^{\delta}}{(1+\delta)^{(1+\delta)}} \right)^\mu }$. We have

\[\Pr[X > (1 + \delta)\mu] < \left( \frac{e^{\delta}}{(1+\delta)^{(1+\delta)}} \right)^\mu \quad \quad \quad \square\]

Second Chernoff Bound

Let ${X_1,\cdots,X_n}$ be independent Poisson Trials such that, for ${1\leq i \leq n}$, ${\Pr[X_i = 1]=p_i}$, where ${0 < p_i < 1}$. Then, for ${X = \sum_{i=1}^n X_i}$, ${\mu = \mathbb{E}[X] = \sum_{i=1}^n p_i}$ and ${0< \delta < 0}$ , we have

\(\begin{aligned} \Pr[X < (1- \delta) \mu] < \left(\frac{e^{\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu} < e^{\frac{-\delta^2 \mu}{2}} \end{aligned}\) Proof. For any $t > 0$:

\[\begin{aligned} \Pr[X < (1 - \delta)\mu] & = \Pr[e^{-tX} > e^{-t(1-\delta)\mu}] \\ & < \frac{\mathbb{E}[e^{-tX}]}{e^{-t(1-\delta)\mu}} & (\text{By Markov}) \\ & = \frac{\prod_{i=1}^n \mathbb{E}[e^{-tX_i}]}{e^{-t(1-\delta)\mu}} & (\text{By Independence}) \\ & = \frac{\prod_{i=1}^n (1 + p_i(e^{-t} - 1))}{e^{-t(1-\delta)\mu}} & (\text{By def of } \mathbb{E}) \\ & \leq \frac{\prod_{i=1}^n e^{p_i(e^{-t}-1)}}{e^{-t(1-\delta)\mu}} & (\text{By } 1 + x \leq e^x) \\ & = \frac{e^{\sum_{i=1}^n p_i(e^{-t}-1)}}{e^{-t(1-\delta)\mu}} \\ & = \frac{e^{\mu(e^{-t}-1)}}{e^{-t(1-\delta)\mu}} \\ & = \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right)^\mu \end{aligned}\]

Denote ${f(t) = \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right)^\mu}$, now we find ${t}$ to minimize ${f(t)}$. First, we solve derivative of ${f(t)}$

\[\begin{aligned} f'(t) &= \mu \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right) \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right)'\\ & = \mu \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right) \left(e^{(e^{-t}-1)+t(1-\delta)}\right)((e^{-t}-1)+t(1-\delta))'\\ & = \mu \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right) \left(e^{(e^{-t}-1)+t(1-\delta)}\right) (-e^{-t} +1 - \delta) \end{aligned}\]

we know ${\mu \left( \frac{e^{(e^{-t}-1)}}{e^{-t(1-\delta)}} \right) \left(e^{(e^{-t}-1)+t(1-\delta)}\right)>0}$. Hence, ${f’(t)=0}$ means ${t = -\ln (1-\delta)}$. Thus, the ${\min f(t) = f(-\ln (1- \delta)) =\left( \frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}} \right)^\mu }$. We have

\[\Pr[X < (1 - \delta)\mu] < \left( \frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}} \right)^\mu\]

Now use the fact that for $-1 < x < 1$

\[\begin{align*} \ln(1 + x) & = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} + \ldots & (\text{By Maclaurin series}) \\ \ln(1 - x) & = -x - \frac{x^2}{2} - \frac{x^3}{3} - \frac{x^4}{4} - \ldots \\ -\ln(1 - x) & = x + \frac{x^2}{2} + \frac{x^3}{3} + \ldots > x + \frac{x^2}{2} \end{align*}\]

so

\[\begin{aligned} (1 - \delta)^{1-\delta} & = e^{(1-\delta)\ln(1-\delta)} \\ & = e^{(-(1-\delta))(-\ln(1-\delta))} \\ & > e^{(\delta-1)(\delta + \frac{\delta^2}{2})} \\ & = e^{-\delta+\frac{\delta^2}{2} + \frac{\delta^3}{2}} \\ & > e^{-\delta+\frac{\delta^2}{2}} \end{aligned}\]

We have shown that

\[\begin{aligned} \Pr[X < (1 - \delta)\mu] < \left( \frac{e^{-\delta}}{(1 - \delta)^{1-\delta}} \right)^\mu \leq \left( e^{-\frac{\delta^2}{2}} \right)^\mu = e^{-\mu\frac{\delta^2}{2}} \end{aligned} \quad \quad \quad\square\]