Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
    
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

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.