Following this [question](https://mathoverflow.net/questions/345915/what-is-mathbbe-max-sigma-in-pm-1-n-sigmat-z-sigma-for-a-ra) I was thinking about ways to improve the upper bound and came up with the following argument. We want to find an upper bound for


\begin{equation}
\mathbb{E} [\max\_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma]
\end{equation}


where $W$ is a symmetric matrix with independent entries $W\_{ij} \sim \mathcal{N}(0,1)$, except for the symmetry condition. This is a slightly different version of the problem mentioned in the link but the argument is analogous. I came across the following [result](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.239.5246&rep=rep1&type=pdf) for gaussian processes



> 
> Let $(X\_1, \ldots, X\_n)$ and $(Y\_1, \ldots, Y\_n)$ be gaussian random vectors with $\mathbb{E}(X\_i) = \mathbb{E}(Y\_i)$ for each $i$. For $1 \leq i,j \leq n$, let $\gamma\_{ij}^{X} = \mathbb{E}(X\_i - X\_j)^2$ and $\gamma\_{ij}^{Y} = \mathbb{E}(Y\_i - Y\_j)^2$, and let $\gamma = \max\_{1 \leq i,j \leq n} | \gamma\_{ij}^{X} - \gamma\_{ij}^{Y}|$. Then
> 
> 
> \begin{equation}
> |\mathbb{E}(\max\_{1 \leq i \leq n} X\_i) - \mathbb{E}(\max\_{1 \leq i \leq n} Y\_i) | \leq \sqrt{\gamma \log n}.
> \end{equation}
> 
> 
> 


I was thinking about applying this result with the random vectors $Y,X \in \mathbb{R}^{2^n}$ s.t. $Y\_i = 0$ and $X\_i = 2 \sum \limits\_{s<t} A\_{ij} \sigma\_{s}^{i} \sigma\_{t}^{i}$ for $1 \leq i \leq 2^{n} $, where $\sigma^{i}$ is the $i$-th hypercube vertex for some ordering of the vertices.


**Question**: Is the following Argument sound? Did I make a mistake or overlook something?




---


It is clear that $Y$ is a gaussian random vector. I think $X$ is also a gaussian random vector because for any real numbers $\alpha\_1, \ldots, \alpha\_n$ we have


\begin{equation}
\alpha\_1X\_1 + \ldots + \alpha\_n X\_n = \sum \limits\_{s<t} A\_{st}(\sum \limits\_{i=1}^{n} \alpha\_i \sigma\_{s}^{i} \sigma\_{t}^{i})
\end{equation}


Which is a gaussian random variable. Furthermore we have


\begin{equation}
\mathbb{E}(\sum \limits\_{s<t} A\_{st}\sigma\_{s}^{i} \sigma\_{t}^{i}) = \sum \limits\_{s<t} \mathbb{E}(A\_{st})\sigma\_{s}^{i} \sigma\_{t}^{i} = 0 
\end{equation}


and


\begin{equation}
\gamma\_{ij}^{X} = \sum \limits\_{s<t}(\sigma\_{s}^i \sigma\_{t}^i - \sigma\_{s}^{j} \sigma\_{t}^{j})^2 \leq 2n^2
\end{equation}


Together with $\gamma\_{ij}^Y = 0$ we have


\begin{equation}
\mathbb{E} [\max\_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma] \leq \sqrt{2n^2 \log 2^n}
\end{equation}


The right hand side can be simplified to $\sqrt{2\log(2)} n^{3/2}$. If I understood correctly the author of the cited paper uses $\log$ to denote the natural logarithm. This would lead us to an upper bound of the order $\sim 1.177 n^{3/2}$, which is not too far away from the actual value for large $n$ which is $\sqrt{2} \cdot 0.7633 n^{3/2} \sim 1.079 n^{3/2}$.




---


Thank you very much for your help.



Tighter upper bound for $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T W \sigma]$
$\newcommand\si{\sigma}$
$\newcommand\Si{\Sigma}$
$\newcommand\R{\mathbb R}$
Let $\Si:=\{\pm 1\}^n$. The map 
$$\R^{n\times n}\ni w\mapsto f(w):=(w\_\si)\_{\si\in\Si}\in\R^\Si, $$
where $w\_\si:=\si^T w\si$, is linear. Therefore and because $W$ is zero-mean Gaussian, we see that 
$$(W\_\si)\_{\si\in\Si}:=f(W):=f\circ W$$
is zero-mean Gaussian, with $W\_\si:=\si^T W\si=\sum\_{i,j}\si\_i\si\_j W\_{ij}$; everywhere here, the summation indices run over the set $\{1,\dots,n\}$. Also, for all $\rho$ and $\si$ in $\Si$
$$EW\_\rho W\_\si=\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l EW\_{ij}W\_{kl} \\
=\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l 1\_{\{i,j\}=\{k,l\}} \\
=\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l 1\_{i=j=k=l}\\
+\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l 1\_{i=k\ne j=l} \\ 
+\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l 1\_{i=l\ne j=k} \\ 
=2\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l 1\_{i=k,j=l} \\
-\sum\_{i,j,k,l}\rho\_i\rho\_j\si\_k\si\_l 1\_{i=j=k=l} \\
=2\sum\_{i,j}\rho\_i\rho\_j\si\_i\si\_j -\sum\_i\rho\_i\rho\_i\si\_i\si\_i \\
=2(\rho\cdot\si)^2-n, 
$$
where $\rho\cdot\si:=\sum\_i\rho\_i\si\_i$; in particular, $EW\_\si^2=EW\_\rho^2=2n^2-n$. 
So, 
$$E(W\_\si-W\_\rho)^2=EW\_\si^2+EW\_\rho^2-2EW\_\rho W\_\si
=4n^2-4(\rho\cdot\si)^2\le4n^2.
$$
So, the bound you are getting is actually $2\sqrt{\log2\,}\, n^{3/2}$, $\sqrt2$ times as large as you suggested. 


