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 \begin{equation} 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) \end{equation}

and here is my trial:


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)$,

\begin{equation} 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) \end{equation}


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?



You must log in to answer this question.