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

share|improve this question
    
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$. –  ACARCHAU Jul 7 '11 at 20:19
add comment

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.