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 first, your proof is correct.

For the second, we can get \begin{equation} \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} \end{equation} 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 \begin{equation} E[e^{\lambda (p_i - X_i) }] \leq e^{\frac{\lambda^2}{2} E[X_i^2]} = e^{\frac{\lambda^2}{2} p_i} \end{equation} for each $i$ and therefore \begin{equation} P[S_n \leq (1-\delta)m] \leq e^{-\lambda \delta m + \frac{\lambda^2}{2} m } \end{equation} Choose $\lambda = \delta$ to get the desired result.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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