10
$\begingroup$

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.

  • 0
    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$.2011-07-07
  • 0
    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\}$?2011-07-07

3 Answers 3