2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ ok, Now I've edited accordingly. $\endgroup$ Commented Mar 20, 2020 at 20:15

1 Answer 1

1
$\begingroup$

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.

[1] Boucheron, Lugosi, and Bousquet, "Concentration Inequalities". http://www.econ.upf.edu/~lugosi/mlss_conc.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .