# Concentration bound for square of sum of Rademacher random varialbes

For $$i\in[n]$$ let us define iid random variables $$u_i\sim \text{Unif}(\{-1,1\})$$, i.e. $$Pr(u_i=1)=Pr(u_i=-1)=1/2$$. Also let $$X=\sum_{i=1}^n u_i$$. My question is, how can we compute the concentration of $$X^2$$ around its mean $$\mathbb{E}[X^2]$$?

It is not hard to compute the mean by linearity of expectation: $$\mathbb{E}[X^2] =\sum_i \mathbb{E}[u_i^2] + \sum_{i\neq j} \mathbb{E}[u_i u_j ]$$ Because we always have $$u_i^2=1$$ we have $$\mathbb{E}[u_i^2] = 1$$ and also when $$i\neq j$$ then $$u_i$$ and $$u_j$$ are independent, we have $$\mathbb{E}[u_i u_j] = \mathbb{E}[u_i] \mathbb{E}[u_j] = 0$$ and therefore we can compute $$\mathbb{E}[X^2] = n$$.

However, computing the concentration seems a bit more tricky. It seems to me that if we define a new random variable $$Y_{ij}=u_i u_j$$ we can use Johnson's inequality because of little interaction between the $$Y_{ij}$$s. Any ideas on how to compute the concentration?

• You have a subgaussian r.v. $X$. $X^2$ will be subexponential, and thus you'll have exponential-type concentration bounds. Jun 22 '19 at 20:13
• Seee e.g. Section 3.1: math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf Jun 22 '19 at 20:15

This random variable $$X^2 = q^* \boldsymbol{A} q$$ where $$\boldsymbol{A}$$ is the matrix of all ones and $$q$$ is a Rademacher vector. A paper by Roosta-Khorasani and Ascher gives tight concentration results for this variable when $$\boldsymbol{A}$$ is a generic positive semi definite matrix, and they apply here.
Rephrased, they prove that $$\mathbf{P}( | X^2 - n|>\epsilon n) < 2 e^{-\tfrac{1}{2}(\tfrac{\epsilon^2}{2} - \tfrac{\epsilon^3}{3})}.$$
• @kvphxga The Frobenius norm (squared) is the trace of $\boldsymbol{A^*A}$, so you can apply this bound using that fact. I don’t know of a result for trace concentration when the matrix is indefinite, (check out the Hanson-Wright inequality maybe?) but I suspect that you would need additional factors such as the Schatten-2 norm since you could have, say, the diagonal matrix with -100 and 100 and the zero matrix having the same trace, while the former RV would have much more variance. Jun 23 '19 at 4:26
• @kvphxga Yes but $q^* A^*Aq =\|Aq\|^2,$ so it can be done implicitly as well. Jun 23 '19 at 14:44