Extension of Bernstein’s Inequality when the random variable is bounded with large probability

Question

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.

Answer 1

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