Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences

Question

A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:

Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$. Then, for all positive $t$,

$\mathbb{P} \left (\sum_{i=1}^n X_i > t \right ) \leq \exp \left ( -\frac{\tfrac{1}{2} t^2}{\sum \mathbb{E} \left[X_j^2 \right ]+\frac{1}{3} Mt} \right ).$

Question 1: Can the assumption $|X_i|\leq M$ be transformed into $|X_i|\leq M_i$ where now the bound can be different for each random variable. I would expect then the term $Mt$ in the bound to turn into $\frac{1}{n}\sum_{i=1}^n M_it$. Is there a reference of a paper with such a result? Or is there any reason why such a result does not exist? For instance the Hoeffding bound is always presented with a result depending on the individual bounds $M_i$.

Question 2: The Freedman concentration inequality for martingales is a result like the Bernstein bound but where the random variable can be dependent. Can we also have a result for the Freedman inequality with $\frac{1}{n}\sum_i M_i$ appearing instead of $\max_{i} M_i$? Do you know a paper proving that?

Question 3: For my research I would actually be happy already if a martingale concentration inequality exists in the special case where the random variable $X_i$ are Bernoulli with parameter $p_i$, $\beta(p_i)$, and then scaled by $\frac{1}{p_i}$, $X_i=\frac{1}{p_i}\beta(p_i)$ (this random variable has a variance and a range of order $\frac{1}{p_i}$ when $p_i$ is small). In my case the value of $p_i$ depend on the previous realizations $X_{i-1},\ldots,X_{i}$. I would hope the following is true then $\mathbb{P} \left (\sum_{i=1}^n X_i > t \right ) \leq \exp \left ( -\frac{\tfrac{1}{2} t^2}{\sum_i 1/p_i} \right ).$

I am aware of a result by Maurer (see reference below) but there the range $M_i$ appears in the bound as $\sum_{i}M^2_i$.

Maurer, Andreas, A bound on the deviation probability for sums of non-negative random variables, JIPAM, J. Inequal. Pure Appl. Math. 4, No.1, Paper No.15, 6 p. (2003). ZBL1021.60036.

Thanks for your help!

Answer 1

It appears you want to have the following:

Let $X_1,\dots,X_n$ be independent zero-mean random variables (r.v.'s ) (or, more generally, martingale-differences) with $S_n:=X_1+\dots+X_n$, $B^2:=EX_1^2+\dots+EX_n^2$, and $M:=\frac1n\sum_1^n M_i$, where $M_i:=\text{ess sup}|X_i|$. Then \begin{equation*} P(S_n\ge x)\overset{\text{(?)}}\le\exp-\frac{x^2}{C(B^2+nM^2)} \tag{1} \end{equation*} for some universal real constant $C>0$ and all real $x\ge0$.

Such an inequality cannot be true in general. E.g., for $n\ge2$, let $X_1,\dots,X_n$ be independent centered Bernoulli r.v.'s such that $P(X_i=\pm1)=1/2$ for $i\le n-1$, $P(X_n=n-1)=1/n=1-P(X_n=-1)$, and $x=n-1$.

Then \begin{equation*} P(S_n\ge x)=P(S_n\ge n-1)\ge P(S_{n-1}\ge0)P(X_n\ge n-1)\ge\frac12\,\frac1n=\frac1{2n}. \end{equation*} On the other hand, here $B^2=2(n-1)$, $M=\frac2n\,(n-1)$, $B^2+nM^2<6(n-1)$, and hence \begin{equation*} \exp-\frac{x^2}{C(B^2+nM^2)}=\exp-\frac{(n-1)^2}{C(B^2+nM^2)}<\exp-\frac{n-1}{6C}, \end{equation*} which is much, much less than $\frac1{2n}=P(S_n\ge x)$ for large $n$. Thus, (1) fails to hold, and it is clear that even much weaker bounds of the same mold will be false in general.

By the way, the result by Maurer you referred to (and even a better version of it) was obtained earlier in Theorem 7 in http://epubs.siam.org/doi/abs/10.1137/1134032 , and further improvements were obtained recently in https://projecteuclid.org/euclid.ejp/1457706456 .