4
$\begingroup$

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.)

Improve this question
$\endgroup$
4
  • 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$
    – Thomas Ahle
    Jul 27, 2017 at 10:38

0

Reset to default

Your Answer

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