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