Skip to main content
1 of 7

Product of Sums of Bernoulli variables

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_i*y_j$. I wish to upper bound the probability $P(|S| > t)$. The best bound I have right now is $2*e^{-\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 atleast get $e^{-c\frac{t}{\sqrt{ab}}}$. If I can get sub-gaussian tails that would probably be the best but can we expect that (I dont think so but can't think of an argument)?

Thanks in advance