# Proof of one-side version of Bennett-Bernstein inequality

I'm going to prove the following:

For independent random variables $$X_i$$, $$i \in [m]$$ satisfying $$X_i-E[X_i] \le b$$ for some constant $$b > 0$$.

Let $$\bar{X} = \dfrac{1}{m}\sum_{i=1}^m X_i$$, we have $$$$P(\bar{X}\ge E[\bar{X}]+\varepsilon) \le \exp\left(\dfrac{-m\varepsilon^2}{2(\frac{1}{m}\sum_{i=1}^m Var[X_i]+\frac{1}{3}b\varepsilon)}\right)$$$$

and here is my trial:

Lemma:

Let $$f(u) = 2\cdot\frac{e^u-u-1}{u^2}$$ and $$f(0) := 1$$. $$f'(u) \ge 0$$ and for $$u \in (0, 3)$$, $$f(u) \le \left(1-\frac{u}{3}\right)^{-1}$$.

For random variable $$X$$ with $$EX=0$$, $$P(X \le b)=1$$ and $$\lambda \in \left(0, \frac{3}{b}\right)$$, $$E[X^2] = Var[X]$$, $$f(\lambda X) \le f(\lambda b)$$,

$$$$E[\exp(\lambda X)] =1+\lambda E[X]+\frac{1}{2}\lambda^2E[X^2f(\lambda X)] \le 1+\frac{1}{2}\lambda^2(1-\frac{\lambda b}{3})^{-1} Var[X] \le \exp\left(\frac{1}{2}\lambda^2(1-\frac{\lambda b}{3})^{-1} Var[X]\right)$$$$

Proof:

For independent random variables $$X_i$$, $$i \in [m]$$ satisfying $$X_i-E{X_i} \le b$$ and $$\bar{X} = \frac{1}{m}\sum_{i=1}^m X_i$$, we have

\begin{align} P\left(\bar{X}\ge E[\bar{X}]+\varepsilon\right) &= P\left(\sum_{i=1}^m(X_i-E{X_i})\ge m\varepsilon\right) \\ &\le E[\exp(\lambda\sum_{i=1}^m(X_i-E{X_i}))] \cdot \exp(-\lambda m\varepsilon) \\ &= \prod_{i=1}^m E[\exp(\lambda(X_i-E{X_i}))] \cdot \exp(-\lambda m\varepsilon) \\ &\le \prod_{i=1}^m \exp\left(\frac{1}{2}\lambda^2(1-\frac{\lambda b}{3})^{-1} Var{[X_i]}\right) \cdot \exp(-\lambda m\varepsilon) \\ &= \exp\left(\frac{1}{2}\lambda^2(1-\frac{\lambda b}{3})^{-1} \sum_{i=1}^m Var[X_i] -\lambda m\varepsilon\right) \end{align}

Let $$\lambda = \dfrac{\varepsilon}{\frac{1}{m}\sum_{i=1}^m Var[X_i]+\frac{1}{3}b\varepsilon}$$ (Note that this time $$\lambda^2(1-\frac{\lambda b}{3})^{-1} \sum_{i=1}^m Var[X_i] = \lambda m\varepsilon$$ and the right hand side takes $$\exp\left(\dfrac{-m\varepsilon^2}{2(\frac{1}{m}\sum_{i=1}^m Var[X_i]+\frac{1}{3}b\varepsilon)}\right)$$. $$\Box$$

This seems fine. But when I try to prove it more directly, I meet some difficulty.

$$X_i-E{X_i} \le b$$ and $$\bar{X} = \frac{1}{m}\sum_{i=1}^m X_i$$, so we have $$E[\bar{X}] \le b$$ and $$Var[\bar{X}] = \frac{1}{m^2}\sum_{i=1}^m Var[X_i]$$ and \begin{align} P\left(\bar{X}\ge E[\bar{X}]+\varepsilon\right) &\le \exp\left(\frac{1}{2}\lambda^2(1-\frac{\lambda b}{3})^{-1} Var[\bar{X}]\right) \cdot \exp(-\lambda \varepsilon) \\ &= \exp\left(\frac{1}{2}\lambda^2(1-\frac{\lambda b}{3})^{-1} \sum_{i=1}^m \frac{1}{m^2} Var[\bar{X}_i]-\lambda \varepsilon\right) \end{align}

If we want to get the same result, we may consider multiply $$\lambda$$ by a factor $$m$$, but this is invalid since the $$(1-\frac{\lambda b}{3})^{-1}$$ term is unchanged and $$\lambda$$ is bounded by $$\lambda < \frac{3}{b}$$.

So where's the problem and how should I proceed?