3
$\begingroup$

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!

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Could Markov inequality be applied to $m-S_n$, which could be negative? $\endgroup$
    – keepfrog
    Jun 30, 2023 at 22:16
0
$\begingroup$

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.

This wikipedia page discusses various bounds, and this proof is an elaboration of the section I linked.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .