# Concentration bound for absolute value of sum of Bernoulli variables

Let $a_1, \ldots a_n$ be i.i.d random variables that take the value $1$ and $-1$ with equal probability. Fix a unit vector $(x_1,\ldots, x_n)$ (such that $\sum_j x_j^2 = 1$).

Consider $v = \langle a, x\rangle$. It's easy to see that $E[v] = 0$. It's also easy to bound Pr($|v| > t$) via standard Hoeffding bounds.

What I'm looking for is a more accurate analysis of the distribution of $|v|$. Heuristically, it seems that $E[|v|]$ should be around $\sqrt{n}$, and what I'd like are concentration bounds around $E[|v|]$ (specifically, bounds on lower and upper tails). My feeling is that this is either easy, well known, or both :), and I'm wondering if there's a quick reference or argument.

-
Wouldn't you expect E[|v|] to be roughly 1? (because $\sum_i x_i^2=1$). If $a_i$ were Gaussian this would be precisely true (E[|v|] would be a constant times $|x|_2$). Maybe there's an invariance principle to move to $\{\pm 1\}$? – user13075 Jul 7 '11 at 17:43
Don't you need to make assumptions on $x$, otherwise what about the case when $x_1 = 1$ and $x_i = 0$ for $i >1$. – Arin Chaudhuri Jul 7 '11 at 20:19

You can try and see what these values should be under the Central Limit Theorem, and then use the Berry-Esseen bounds to prove that your guess is correct. You can't get large deviation bounds this way since the error is too big (and indeed, the normal approximation doesn't hold for the tails), but for your purposes it might be enough.

-

(I'm just a student so I'm sorry if I offend anyone with obvious comments)

If one takes the intuitive case $x_i = 1/\sqrt{n}$, the exact distribution is to linear transformations that of the Binomial distribution. Naturally, one should not expect to understand the tail bounds of your case better than this well-studied one. Additionally, if one is interested in "the worst case", then I phantom it should be precisely this. If not, perhaps the more successful approaches carry over.

-

This is another question instead of an answer, but I was thinking about a similar problem and I was wondering if one could use the cumulants to derive bounds, since they are relatively simple in the binomial case. Sorry if this is inappropriate.

-