<p>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| &gt; t)$. </p>

<p>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|&lt;\sqrt{t})$ and $Pr(|y_1 + \dots + y_n|&lt;\sqrt{t})$ by application of simple chernoff bounds. </p>

<p>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}}})?$$ </p>

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

CC BY-SA 3.0
2013-07-09T17:58:40.193Z
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 : http://www2.math.uu.se/~svante/papers/sj148.pdf.
Skoro
CC BY-SA 3.0
2013-07-10T21:01:27.467Z
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?
NAg
CC BY-SA 3.0
2013-07-17T18:11:32.853Z
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.
minar
CC BY-SA 3.0
2017-07-27T10:38:39.030Z
@minar That also sounds like the right solution to me. Maybe write it as an answer?
Thomas Ahle
<pr.probability><randomized-algorithms><randomness><chernoff-bound>
Sums of products of bernoulli random variables
NAg
# Sums of products of bernoulli random variables

(Asked by: username_0 on 2013-07-08)

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

**Tags:** pr.probability, randomized-algorithms, randomness, chernoff-bound
> **Comments:**
> **username_1**: 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 : http://www2.math.uu.se/~svante/papers/sj148.pdf.  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_3**: @minar That also sounds like the right solution to me. Maybe write it as an answer?  

---

## 0 answers

