# Concentration inequalities for $P(\sum_{i=1}^n \epsilon_i X_i > t)$

Let $\epsilon_i \sim \text{Bernoulli}(p)$ and $X_i \sim \text{Normal}(0, \sigma^2 / n)$ for $i=1,\ldots,n$. I am interested in getting a sub-Gaussian type upper bound for $$P\left(\sum_i \epsilon_i X_i > t\right).$$ Ideally, it would look something like \begin{align} P\left(\sum_i \epsilon_i X_i > t\right) \le K\exp\left(C\frac{-t^2}{2\sigma^2 p}\right) \tag{1} \end{align} for some constants $K$ and $C$, although I'm thinking this isn't true; I'm also not sure how to incorporate $n$ here into $K$ or $C$. It's important that the bound quantifies the deviation in terms of $p$, so that I have good control over what is going on as $p \to 0$. The furthest I've gotten is that, by iterated expectation and the usual Gaussian concentration stuff, \begin{align} P\left(\sum_i \epsilon_i X_i > t\right) \le E\left\{\exp\left(\frac{-t^2 n}{2\sigma^2 \sum_i \epsilon_i}\right)\right\} \tag{2} \end{align} which, for fixed $p$, gives $$\limsup_n P\left(\sum_i \epsilon_i X_i > t\right) \le \exp\left(\frac{-t^2}{2\sigma^2 p}\right)$$ by the law of large numbers. But this approach doesn't seem strong enough, since a little bit of numeric investigation shows that (2) is quite a bit worse than (1) as $p \to 0$. Some quantification of how $p$ and $n$ play into the bound (2) would also be good.

• Have you tried using Bernstein's inequality? (Use the version that requires a bound on the moments, rather than the one that requires a bound on the maximum value.) – Thomas Ahle Dec 27 '18 at 0:16