# Proof of the Bernstein–Chernov bound

This is Exercise 5.2.1 from Achim Klenke: »Probability Theory — A Comprehensive Course«.

Exercise (Bernstein–Chernov bound): Let $n \in \mathbb{N}$ and $p_1,\ldots, p_n \in [0,1]$. Let $X_1,\ldots, X_n$ be independent random variables with $X_i = \mathrm{Ber}_{p_i}$ (this means Bernoulli-distributed: $\mathbf{P}[X_i = 1] = p_i, \mathbf{P}[X_i = 0] = 1-p_i$) for any $i = 1,\ldots, n$. Define $S_n = X_1 +\cdots+X_n$ and $m:= \mathbf{E}[S_n]$. Show that, for any $\delta > 0$, the following two estimates hold: \begin{align*} \mathbf{P}[S_n\geq (1+\delta)m] &\leq \biggl(\frac{e^\delta}{(1+\delta)^{1+\delta}}\biggr)^m \\ \mathbf{P}[S_n\leq (1-\delta)m] &\leq \exp\biggl(-\frac{\delta^2 m}{2}\biggr)\, . \end{align*} Hint: For $S_n$, use Markov’s inequality with $f(x) = e^{\lambda x}$ for some $\lambda > 0$ and then find the $\lambda$ that optimizes the bound.

Solution: We prove the first inequality. The Markov inequality says that for a real random variable $X$ and $f\colon [0,\infty) \rightarrow [0,\infty)$ monotone increasing, for any $\varepsilon > 0$ with $f(\varepsilon) > 0$ the following holds: \begin{equation*} \mathbf{P}\bigl[|X| \geq \varepsilon\bigr] \leq \frac{\mathbf{E}\bigl[f(|X|)]}{f(\varepsilon)}\, . \end{equation*}

Using the Markov inequality with $X = S_n$, $\varepsilon = (1+\delta) m$ and $f(x) = e^{\lambda x}$ (which is monotone increasing) we get: \begin{align*} \mathbf{P}\bigl[S_n \geq (1+\delta)m\bigr] & \leq \frac{1}{e^{\lambda(1+\delta)m}} \mathbf{E}\bigl[e^{\lambda S_n}\bigr] \, . \end{align*} Using the definition of $S_n = X_1 + \cdots + X_n$ and the independence of the $X_1, X_2, \ldots, X_n$, we obtain: \begin{align*} \mathbf{E}\bigl[e^{\lambda S_n}\bigr] = \mathbf{E}\Bigl[\prod_{j=1}^n e^{\lambda X_j} \Bigr] = \prod_{j=1}^n \mathbf{E}\bigl[e^{\lambda X_j}\bigr] = \prod_{j=1}^n \bigl(e^{\lambda} p_j + (1-p_j)\bigr) \, . \end{align*} We now use $\lambda = \ln(1+\delta)$. All derivatives of $e^{\delta x}$ are positive for $\delta > 0$, so a Taylor expansion around $x=0$ gives us that $e^{\delta x} \geq 1 + \delta x$. `\begin{align*} \mathbf{P}\bigl[S_n \geq (1+\delta)m\bigr] & \leq \frac{1}{e^{\ln(1 + \delta) (1+\delta)m}} \prod_{j=1}^n \Bigl(e^{\ln(1 + \delta)} p_j + (1-p_j)\Bigr) \\ & = \frac{1}{(1+\delta)^{(1+\delta)m}} \prod_{j=1}^n (\delta p_j + 1) \\ & \leq \frac{1}{(1+\delta)^{(1+\delta)m}}\prod_{j=1}^n e^{\delta p_j} \\ & = \frac{e^{\sum_{j=1}^n \delta p_j}}{(1+\delta)^{(1+\delta)m}} = \frac{e^{\delta m}}{(1+\delta)^{(1+\delta)m}} = \biggl(\frac{e^\delta}{(1+\delta)^{1+\delta}}\biggr)^m \, . \end{align*}

Could you please check if my proof of the first inequality is correct?

I don't know how to prove the second inequality, can you help me?

Thank you!

For the second, we can get $$\begin{split} P[S_n \leq (1-\delta)m]=P[m-S_n\geq \delta m] &\leq\frac{E[e^{\lambda (m-S_n)}]}{e^{\lambda \delta m}} \\ &= e^{-\lambda \delta m} \prod_{i=1}^{n} E[e^{\lambda (p_i - X_i) }] \\ \end{split}$$ Since $-X_i \leq 0$ a.s. you can use a one-sided Bernstein bound (e.g. proposition 2.4 here) applied to $-X_i$ to find that $$E[e^{\lambda (p_i - X_i) }] \leq e^{\frac{\lambda^2}{2} E[X_i^2]} = e^{\frac{\lambda^2}{2} p_i}$$ for each $i$ and therefore $$P[S_n \leq (1-\delta)m] \leq e^{-\lambda \delta m + \frac{\lambda^2}{2} m }$$ Choose $\lambda = \delta$ to get the desired result.
• Could Markov inequality be applied to $m-S_n$, which could be negative? Jun 30, 2023 at 22:16
For the second inequality, Markov inequality can be applie on $$n-S_n\ge 0$$: $$\mathbb{P}(S_n \le (1-\delta)m)=\mathbb{P}(n-S_n\ge n - (1-\delta)m).$$ You can do the same computation that you did for the first inequality to get $$\mathbb{P}(S_n \le (1-\delta)m) \le \left[\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right]^{m}.$$ Take the log of the RHS to get $$m(-\delta-(1-\delta)\log(1-\delta))$$. Now use the following inequality: $$\log (1+x)\ge \frac{x}{2}\frac{2+x}{1+x},\quad x\in (-1,0)$$ to get $$m(-\delta-(1-\delta)\log(1-\delta)) \le -\delta^2 m /2$$. Since $$x=\exp(\log(x))$$, the desired inequality is obtained.