# Chernoff bound for i.i.d. $[-a,a]$ bounded random variables.

I am trying to find a version of the Chernoff bounds which would allow the random variables to take negative values while still providing a multiplicative guarantee. More precisely, I am familiar with the following statement:

Let $X_1,\dots,X_m$ be $m$ independent random variables taking values in $[0,1]$, with $\mathbb{E} X_i = p_i$, and $\sum_{i=1}^m p_i = P$. For any $\gamma \in (0,1]$ we have

\begin{align*} \mathbb{P}\left\{\sum_{i=1}^m X_i > (1+\gamma)P\right\} &< \exp_-\frac{\gamma^2P}{3}\\ \mathbb{P}\left\{\sum_{i=1}^m X_i < (1-\gamma)P\right\} &< \exp_-\frac{\gamma^2P}{2} \end{align*}

What I would like is something similar, but relaxing the $[0,1]$ assumption:

Let $X_1,\dots,X_m$ be $m$ independent random variables taking values in $[-1,1]$, with $\mathbb{E} X_i = p_i$, and $\sum_{i=1}^m p_i = P \geq 0$. For any $\gamma \in (0,1]$ we have (?)

\begin{align*} \mathbb{P}\left\{\sum_{i=1}^m X_i > (1+\gamma)P\right\} &< \exp_-\frac{\gamma^2P}{3}\\ \mathbb{P}\left\{\sum_{i=1}^m X_i < (1-\gamma)P\right\} &< \exp_-\frac{\gamma^2P}{2}\\ \end{align*}

Does anyone know a good reference where such a statement exists (if there is some)? (actually, even constraining the $X_i$'s to be iid would be enough for what I need).

(I was thinking of proving it directly by following the standard proof and just fixing it to work in this setting, but the minimization part is somehow messy -- if I could do without reinventing the wheel, that'd be great)

Thanks,

-
Wouldn't change of variable $Y_i=(X_i+1)/2$ help? –  S.B. Jul 15 '13 at 22:57
@S.B. it will shift the expectation, and thus won't give the multiplicative bound I want. –  Clement C. Jul 15 '13 at 23:16
Did you consider the fact that $p_i$s will shift as well? –  S.B. Jul 15 '13 at 23:22
Yes. The $\pm\gamma P$ will be for the new, shifted $P$, not the original one. –  Clement C. Jul 15 '13 at 23:28

After discussing it with my adviser, it looks like such a bound cannot exist in general, at least without further assumptions: indeed, if the $X_i$'s are i.i.d. with \begin{align*} \mathbb{P}\{X_i=1\} = 1-\mathbb{P}\{X_i=-1\}= \frac{1}{2}+\varepsilon \end{align*} then $\mathbb{E} X_i=2\varepsilon$, $P=2m\varepsilon$, and even taking $\gamma=\frac{1}{2}$ would result in $$\mathbb{P}\left\{\frac{1}{m}\sum_{i=1}^m X_i < \frac{\varepsilon}{2}\right\} < \exp_-\frac{m\varepsilon}{8}$$ which is at most $1/3$ for $m=\left\lceil\frac{10}{\varepsilon}\right\rceil$; contradicting the fact that distinguishing a fair coin from a $(\frac{1}{2}+\varepsilon)$-biased one with probability at least $2/3$ requires $\Omega\left(\frac{1}{\varepsilon^2}\right)$ samples.