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.)
Sums of products of bernoulli random variables
pr.probability;randomized algorithms;randomness;chernoff bound