5
$\begingroup$

Given an $n \times n$ random matrix $\mathbf{Z}$ with each entry i.i.d. $\mathcal{N} (0,1)$, what is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ as $n \to \infty$? If this is too much to ask, are there any good known upper or lower bounds?

$\endgroup$
5
$\begingroup$

This gives a lower bound of $\frac{4}{3\sqrt{\pi}}n^{3/2}+O(\sqrt{n})$ and an upper bound of $2n^{3/2}+O(\sqrt{n})$. Note: in the arguments below, I messed up the constants somewhere, so I'm not sure what the correct constants they should give is. The arguments should still work.

To get a lower bound, we can try to build $\sigma$ greedily. Choose $\sigma_1$ arbitrarily, and choose $\sigma_j$ depending on $\{\sigma_i,Z_{ij},Z_{ji}\mid i<j\}$. When we are choosing $\sigma_j$, we are trying to maximize $$ \sigma_j\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji}). $$ Since all the $Z_{ij}$ and $Z_{ji}$ are iid $\mathcal N(0,1)$ independent of $\{\sigma_i\mid i<j\}$, we get that $\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji})\sim \mathcal N(0,2(j-1))$, so by the right choice of $\sigma_j$, we can get $$ \mathbb E\left[\sigma_j\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji})\right]=\sqrt{2(j-1)}\sqrt{2/\pi}=\frac{2}{\sqrt{\pi}}\sqrt{j-1} $$ where $\sqrt{2/\pi}=\mathbb E|x|$ for $x\sim \mathcal N(0,1)$. Finally, we get $$ \mathbb E[ \sigma^TZ\sigma]=E\left[\sum_{i=1}^n Z_{ii}\sigma_i^2+\sum_{j=1}^n \sigma_j\sum_{i<j} \sigma_i(Z_{ij}+Z_{ji})\right]=\frac{2}{\sqrt{\pi}}\sum_{j=1}^n \sqrt{j-1} $$ I'm sure there are more precise ways to evaluate the last sum, but just comparing it to Riemann sums from above and below, we can get $$ \sum_{j=1}^n \sqrt{j-1}=n^{3/2}\int_0^1\sqrt{x} dx+O(\sqrt{n})=\frac{2}{3}n^{3/2}+O(\sqrt{n}) $$ putting it all together, this greedy construction yields a lower bound of $$ \mathbb E[ \sigma^TZ\sigma]\ge \frac{4}{3\sqrt{\pi}}n^{3/2}+O(\sqrt{n}) $$ for well-chosen $\sigma$ (hopefully I didn't mess up the coefficient in front).

To get the upper bound, we note that for any fixed $\sigma$, we have that $\sigma^TZ\sigma\sim \mathcal N(0,n^2)$, so (this is not using optimal bounds on erf) $$ \mathbb P\left[\sigma^TZ\sigma>Cn^{3/2}\right]<\exp\left(-\frac{C^2}{2}n\right) $$ so, since there are only $2^n$ choices for $\sigma$, we have $$ \mathbb P\left[\max_\sigma \sigma^TZ\sigma>Cn^{3/2}\right]<\exp\left(\left(2-\frac{C^2}{2}\right)n\right) $$ Then we use $$ \mathbb E(\max_\sigma \sigma^TZ\sigma>Cn^{3/2})\le 2n^{3/2}+n^{3/2}\int_{2n^{3/2}}^\infty \mathbb P(\max_\sigma \sigma^TZ\sigma>s) ds\le n^{3/2}\left(2+\int_{2}^\infty \exp\left(\left(2-\frac{t^2}{2}\right)n\right) dtdt\right)=2n^{3/2}+O(\sqrt{n}). $$

$\endgroup$
  • $\begingroup$ @Sandeep Silwal Where does the polylog come from? If you're taking the sum of $n^2$ variables, each of which is the absolute value of a Gaussian and thus has positive constant expectation, the expected value will go like $n^2$ $\endgroup$ – Sam Zbarsky Nov 14 '19 at 2:57
  • $\begingroup$ Ah ok, thanks for the clarification and great answer :) $\endgroup$ – Sandeep Silwal Nov 14 '19 at 14:27
  • $\begingroup$ @SamZbarsky did you mean $\sum \limits_{i<j}\sigma_i(Z_{ij}+Z_{ji})\sim N(0,\sqrt{2(j-1)})$ instead of $\sigma_{i<j}(Z_{ij}+Z_{ji})\sim N(0,\sqrt{2(j-1)})$? Also, could you clarify on how you get the square root in the variance? Its not clear to me. Thank you for your help. $\endgroup$ – sigmatau Nov 14 '19 at 14:35
  • 1
    $\begingroup$ @sigmatau Thank you, I fixed that. I messed up my notation. I thought for some reason that in $\mathcal N(0,b)$, the $b$ was supposed to be standard deviation, not variance. It's fixed now. $\endgroup$ – Sam Zbarsky Nov 14 '19 at 21:23
7
$\begingroup$

This is related to the Sherrington-Kirkpatrick Spin Glass model. In arxiv.org/pdf/1412.0170.pdf, Dmitry Panchenko writes that $$\lim_{N\to\infty} \frac{1}{N} \mathbb{E}\big[\max_\sigma \frac{1}{\sqrt{N}} \sum_{i<j} g_{ij} \sigma_i \sigma_j \big] \approx 0.7633$$ with $g_{ij}$ iid standard normals. This is a consequence of the Parisi formula. I believe your desired asymptotic should then be $0.7633\sqrt{2}N^{3/2}+ o(N^{3/2})$.

$\endgroup$

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.