Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum $$S = \sum_{i,j} x_iy_j.$$ I wish to upper bound the probability $P(|S| > t)$.

The best bound I have right now is $$2\exp(-\frac{ct}{\max(a,b)})$$ where $c$ is a universal constant. This is achieved by lower bounding the probability $Pr(|x_1 + \dots + x_n|<\sqrt{t})$ and $Pr(|y_1 + \dots + y_n|<\sqrt{t})$ by application of simple chernoff bounds.

Can I hope to get something that is significantly better than this bound? For starters, can I at least get $$\exp({-\frac{ct}{\sqrt{ab}}})?$$

If I can get sub-Gaussian tails that would probably be the best but can we expect that? (I don't think so but can't think of an argument.)

  • 2
    $\begingroup$ The quantity you are interested in has been considered in literature under the name of Radamacher Chaos. For instance, you might find the following article interesting : www2.math.uu.se/~svante/papers/sj148.pdf. $\endgroup$
    – Skoro
    Jul 9, 2013 at 17:58
  • $\begingroup$ Thanks for the link. I tried going through the article but unfortunately found a little hard to read. It seems somehow that Rademacher chaos is a much more general sum as compared to what I have which is extremely specific. I ll try giving the paper a read again but if the ideas could be presented simply, could you please do so? $\endgroup$
    – NAg
    Jul 10, 2013 at 21:01
  • 1
    $\begingroup$ Can't you simply rewrite $S=\sum_{i,j}x_iy_j=\left(\sum_ix_i\right)\left(\sum_jy_j\right)?$ This should greatly simplify the analysis. $\endgroup$
    – minar
    Jul 17, 2013 at 18:11
  • $\begingroup$ @minar That also sounds like the right solution to me. Maybe write it as an answer? $\endgroup$ Jul 27, 2017 at 10:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.