Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
Do you mean sums of products? If so, pls change title. –  Lucozade Jul 9 '13 at 6:44
What I have written can also be read as $(\sum_i x_i)(\sum_j y_j)$, so it is a product of sums. –  user1189053 Jul 9 '13 at 6:47
This is a duplicate of a question also posted to stats.SE ... at stats.stackexchange.com/questions/63728/… ... suggest delete this one. –  wolfies Jul 9 '13 at 16:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.