1
$\begingroup$

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?

$\endgroup$
2
1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ This is quite overkill though :) $\endgroup$
    – Clement C.
    Jun 22 '19 at 20:14
  • $\begingroup$ @ClementC. Yes; I couldn’t resist I was just using these results in a paper :) $\endgroup$
    – cdipaolo
    Jun 22 '19 at 20:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – cdipaolo
    Jun 23 '19 at 4:26
  • 1
    $\begingroup$ @kvphxga Oh yes the Hanson-Wright inequality is exactly what you’re looking for. See this paper or Vershynin’s book Clement mentioned above: projecteuclid.org/euclid.ecp/1465315621 $\endgroup$
    – cdipaolo
    Jun 23 '19 at 4:28
  • 1
    $\begingroup$ @kvphxga Yes but $q^* A^*Aq =\|Aq\|^2,$ so it can be done implicitly as well. $\endgroup$
    – cdipaolo
    Jun 23 '19 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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