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?
2 Answers
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(j1))$, 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(j1)}\sqrt{2/\pi}=\frac{2}{\sqrt{\pi}}\sqrt{j1} $$ where $\sqrt{2/\pi}=\mathbb Ex$ 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{j1} $$ 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{j1}=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 wellchosen $\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}). $$

$\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$ Nov 14, 2019 at 2:57

$\begingroup$ Ah ok, thanks for the clarification and great answer :) $\endgroup$ Nov 14, 2019 at 14:27

$\begingroup$ @SamZbarsky did you mean $\sum \limits_{i<j}\sigma_i(Z_{ij}+Z_{ji})\sim N(0,\sqrt{2(j1)})$ instead of $\sigma_{i<j}(Z_{ij}+Z_{ji})\sim N(0,\sqrt{2(j1)})$? 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$– sigmatauNov 14, 2019 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$ Nov 14, 2019 at 21:23
This is related to the SherringtonKirkpatrick 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})$.