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

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.

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.
• Thank you so much! This answers my original question :) I was wondering if we could get $\mathbb{P} \left (\sum_{i=1}^n X_i > t \right ) \stackrel{?}{\leq} \exp \left ( -\frac{\tfrac{1}{2} t^2}{\sum \mathbb{E} \left[X_j^2 \right ]+\tfrac{1}{3} \sum_i M_i/n t} \right ).$ and using your example with $t=nM$ leads to same conclusion. Such a bound cannot exist in general. Thank you! – Jean Claude Feb 1 '18 at 22:56