# Prove this inequality (similar to Hoeffding's inequality)

Consider a sequence of independent variables $$X_1,X_2,\ldots$$ with mean 0 and $$|X_i| \leq c$$ for $$i=1,2,\ldots$$ Prove that:

$$P\Big( \sum_{i=1}^n X_i \geq n\varepsilon \Big) \leq \exp\left( -\frac{(1/2) n\varepsilon^2}{ \frac{1}{n} \sum_{i=1}^n E[X_i^2] + \frac{c\varepsilon}{3}}\right)$$

I am trying to take a similar approach to the proof of Hoeffding's inequality, but I am not sure why there is an extra $$\frac{c\varepsilon}{3}$$ term in the denominator? Does someone mind explaining?

• ok, Now I've edited accordingly. Commented Mar 20, 2020 at 20:15

Let $$Y_i = X_i/c, \forall i$$. Then $$Y_i \le 1$$, $$\mathbb{E}[Y_i] = 0$$ and $$\mathbb{E}[Y_i^2] = \frac{1}{c^2}\mathbb{E}[X_i^2]$$, for $$i = 1, 2, \cdots$$.
From Theorem 3 in [1], we have, for any $$\epsilon' > 0$$, $$\mathbb{P}\Big(\sum_{i=1}^n Y_i > n\epsilon'\Big) \le \mathrm{exp}\Big(- \frac{n\epsilon'^2}{2(\frac{1}{n}\sum_{i=1}^n \mathbb{E}[Y_i^2] + \frac{\epsilon'}{3})}\Big)$$ which results in $$\mathbb{P}\Big(\sum_{i=1}^n X_i > n\epsilon\Big) \le \mathrm{exp}\Big(- \frac{\frac{n}{2}\epsilon^2}{\frac{1}{n}\sum_{i=1}^n \mathbb{E}[X_i^2] + \frac{c\epsilon}{3}}\Big)$$ where $$\epsilon = c\epsilon'$$. We are done.