3
$\begingroup$

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.

$\endgroup$
14
  • $\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, 2020 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, 2020 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$ Sep 8, 2020 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$ Sep 10, 2020 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, 2020 at 20:58

1 Answer 1

3
$\begingroup$

$\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.

$\endgroup$
2
  • $\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, 2020 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$ Sep 14, 2020 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.