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.

  • $\begingroup$ 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.) $\endgroup$ – Thomas Ahle Dec 27 '18 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.