Bernstein’s Inequality can be stated as follows : Let $x_1, x_2, \dots, x_n$ be independent bounded random variables such that $\mathbb{E}[x_i] = 0$ and $|x_i| \leq \zeta$ with probability $1$ and let $\sigma^2 = \tfrac{1}{n}\sum_{1}^{n} Var\{x_i\}$. Then for any $\epsilon > 0$, we have $$ \mathbb{P} \left[ \frac{1}{n} \sum_{i=1}^{n} x_i \geq \epsilon \right] \leq \exp{\left\{ \frac{-n \epsilon^2}{ 2 \sigma^2 + 2\zeta \epsilon/3} \right\}} $$

If instead of $|x_i| \leq \zeta$ with probability $1$, it is the case that $ \sum_{i=1}^{n} \mathbb{P}\left\{ |x_i| > \zeta \right\} \leq \delta$, then is the following applicable?

$$ \mathbb{P} \left[ \frac{1}{n} \sum_{i=1}^{n} x_i \geq \epsilon \right] \leq \exp{\left\{ \frac{-n \epsilon^2}{ 2 \sigma^2 + 2\zeta \epsilon/3} \right\}} + \delta \qquad \qquad \qquad \qquad (1) $$

I think, the above extension is similar to the extension of the Azuma-Hoeffding inequality proved in Theorem 32 of Chung and Lu(2006). The question concerning the extension of the Azuma-Hoeffding inequality was also asked here.

Is it possible to extend Bernstein’s Inequality as eq. $(1)$ following the lines of the proof of Theorem 32 in Chung and Lu(2006)?

Addendum : The Freedman inequality for martingales is a result like the Bernstein inequality but where the random variables can be dependent. Is an extension like the above possible for Freedman inequality?

For reference Freedman inequality (Theorem 1.6 in Freedman (1975)] ) can be stated as follows: let $x_1, x_2, \dots $ be a martingale difference sequence and $|x_i| \leq \zeta$ for all $i$. Then $$ \mathbb{P} \left[ \sum_{i=1}^{n} x_i \geq \epsilon, \sum_{i=1}^{n} var(x_i | \mathcal{F}_{i-1}) \leq \eta \right] \leq \exp{\left\{ \frac{-\epsilon^2}{2\eta + 2 \zeta \epsilon/3 } \right\}}. $$

If instead of $|x_i| \leq \zeta$ with probability $1$, it is the case that $ \sum_{i=1}^{n} \mathbb{P}\left\{ |x_i| > \zeta \right\} \leq \delta$, then is the following applicable? $$ \mathbb{P} \left[ \sum_{i=1}^{n} x_i \geq \epsilon, \sum_{i=1}^{n} var(x_i | \mathcal{F}_{i-1}) \leq \eta \right] \leq \exp{\left\{ \frac{-\epsilon^2}{2\eta + 2 \zeta \epsilon/3 } \right\}} + \delta \qquad \qquad (2) $$ Thank you.

  • $\begingroup$ For $\delta=1$, it looks like your eq. (1) doesn't recover Bernstein's inequality -- is there maybe a typo somewhere? $\endgroup$ – gmvh Sep 8 '20 at 18:21
  • $\begingroup$ @gmvh It, obviously, should be $1-\delta$ in the assumption but I agree that it would be nice to fix it. $\endgroup$ – fedja Sep 8 '20 at 18:30
  • $\begingroup$ By "$|x_i| \leq \zeta$ with probability $\delta$", do you mean "$P(\max_i|x_i| \leq \zeta)=1-\delta$ or "$P(|x_i| \leq \zeta)=1-\delta$ for all $i$" or ...? $\endgroup$ – Iosif Pinelis Sep 8 '20 at 20:23
  • 1
    $\begingroup$ @Komkom : Also, you are citing Freedman's Theorem 1.6 incorrectly: instead of $x_i^2$, you need $Var(x_i|\mathcal F_{i-1})$. $\endgroup$ – Iosif Pinelis Sep 10 '20 at 16:46
  • 1
    $\begingroup$ Doesn't your (1) follow from using Freedman (the correct version, as Iosif Pinelis points out) instead of Azuma in the Chung-Lu argument, and noting $\delta$ is an upper bound (union) for $Pr(B)$ in their paper? As a cheap justification, note that you can couple $x_i$ to $y_i$ defined to be equal to $x_i$ if $|x_i|\le\zeta$ and $0$ otherwise. If the $y_i$ have mean zero, then they are by Bernstein concentrated as you desire, and the failure probability of the coupling is at most $\delta$, so you get (1). $\endgroup$ – user36212 Sep 10 '20 at 20:58

$\newcommand{\de}{\delta}$Your inequality (2) does hold. Actually, a better and more general bound holds. First here, let us standardize and simplify notations. Let us use $X_i$ instead of $x_i$, $x$ instead of $\epsilon$, $y>0$ instead of $\zeta$, $B^2>0$ instead of $\eta$, $Var_{i-1}\,\cdot$ instead of $var(\cdot|\mathcal{F}_{i-1})$, and $E_{i-1}\,\cdot$ instead of $E(\cdot|\mathcal{F}_{i-1})$.

Instead of the conditions that the $x_i$'s are martingale differences and $\sum_{i=1}^n P(|x_i|>\zeta)\le\de$, let us use the more general conditions that the $X_i$'s are supermartingale differences and \begin{equation} P(\max_{i=1}^n X_i>y)\le\de.\tag{1} \end{equation}

Let also $Y_i:=X_i\,1(X_i\le y)$ and $Z_i:=Y_i\,1(V_i\le B^2)=X_i\,1(X_i\le y,V_i\le B^2)$, where $$V_i:=\sum_{j=1}^i E_{j-1}\,Y_j^2.$$ Note that $V_i$ is no greater than $\sum_{j=1}^i E_{j-1}\,X_j^2$, which latter coincides with $\sum_{j=1}^i Var_{j-1}\,X_j$ in the special case when the $X_i$'s are martingale differences.

By (1), $$P\Big(\sum_{i=1}^n X_i\ge x,V_n\le B^2\Big)\le P\Big(\sum_{i=1}^n Y_i\ge x,V_n\le B^2\Big)+\de.$$ Obviously, $V_i\le V_n$ for $i\le n$. So, $$P\Big(\sum_{i=1}^n Y_i\ge x,V_n\le B^2\Big)\le P\Big(\sum_{i=1}^n Z_i\ge x\Big).$$

Next, $E_{i-1}Z_i=1(V_i\le B^2)E_{i-1}Y_i\le 1(V_i\le B^2)E_{i-1}X_i\le0$, so that the $Z_i$'s are supermartingale differences. Also, $E_{i-1}Z_i^2\le E_{i-1}X_i^2$. So, by Theorem 8.2 on page 1702, we have the Hoeffding-type inequality \begin{equation*} P\Big(\sum_{i=1}^n Z_i\ge x\Big)\le\exp\Big\{\frac{B^2}{y^2}\psi\Big(\frac{xy}{B^2}\Big)\Big\}, \end{equation*} where $\psi(u):=u-(1+u)\ln(1+u)$. Collecting the pieces, we get \begin{equation*} P\Big(\sum_{i=1}^n X_i\ge x,V_n\le B^2\Big)\le\exp\Big\{\frac{B^2}{y^2}\psi\Big(\frac{xy}{B^2}\Big)\Big\}+\de. \tag{2} \end{equation*} The latter bound is better than the Bernstein-type bound \begin{equation*} \exp\Big\{-\frac{x^2}{2B^2+2xy/3}\Big\}+\de, \tag{3} \end{equation*} because, as shown in Theorem 3, the Hoeffding-type bound is the best exponential bound in its terms. Another, direct way to see that the bound in (2) is better than (3) is to use the inequality $\psi(u)\le-u^2/(2+2u/3)$ for real $u\ge0$.

Thus, the bound in (2) is better and more general than what you wanted.

  • $\begingroup$ Thank you very much for the detailed answer. I read Theorem 3 but I don't understand how it shows that the obtained bound is the best exponential bound. Could you please elaborate? $\endgroup$ – Kom kom Sep 14 '20 at 17:11
  • 1
    $\begingroup$ @Komkom : The inequality sign in Theorem 3 (and in other results in that paper) is, not $\leqq$, but $\overset{(T)}\leqq$, which means that the bounds are exact (best possible), in the sense defined on the first page of that paper. The letter T is the first letter of the Russian word "точный", meaning "exact". $\endgroup$ – Iosif Pinelis Sep 14 '20 at 21:23

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.