Let $(\Omega, \mathcal{A}, \mathbb{P})$ be a probability space and $X_1, \dots , X_n: \Omega \to \mathbb{R}$ be iid random variables satisfying $0 \leq X_i \leq 1$. Furthermore, let $\mu = \mathbb{E}[X_i]$. I was asked to prove that for every $\varepsilon > 0$
$$\mathbb{P}\left(\sum_{i=1}^n\left(X_i – \mu\right)\geq \varepsilon\right) \leq \exp\left(-\frac{\varepsilon^2}{2n}\right).$$
A hint was given, that we should employ the markov inequality with the function $f(x) = \exp(zx)$ where $z > 0$ is to be determined later. Let $Y_i := X_i – \mu$ and $Y := \sum_{i=1}^n Y_i$. Then by markov's inequality we have
$$\mathbb{P}\left(Y \geq \varepsilon\right) \leq \frac{\mathbb{E}[\exp(zY)]}{\exp(z\varepsilon)} = \frac{\mathbb{E}\left[\prod_{i=1}^n \exp(zY_i)\right]}{\exp(z\varepsilon)} = \frac{\left(\mathbb{E}\left[\exp(zY_i)\right]\right)^n}{\exp(z\varepsilon)},$$
where the last equality follows from the fact that the $Y_i$ are iid because the $X_i$ are. Now the hint wants us to use the convexity of $\exp$ to show that $\exp(zY_i) \leq \frac{1-Y_i}{2}\exp(-z) + \frac{1+Y_i}{2}\exp(z)$ but I don't see how $\frac{1-Y_i}{2} \in [0,1]$. Does this follow from $0 \leq X_i \leq 1$?
Best Answer
Indeed: since $0\leqslant X_i\leqslant 1$, one has $0\leqslant \mu\leqslant 1$, that is, $-1\leqslant -\mu\leqslant 0$ hence $-1\leqslant X_i-\mu\leqslant 1$ which shows that $-1\leqslant -Y_i\leqslant 1$ hence $0\leqslant -Y_i+1\leqslant 2$ and analogously, $0\leqslant Y_i+1\leqslant 2$.