# Expectation of max of Gaussian multiplied by a functional of Gaussian

Let $X \in \mathbb{R}^{d}$ follows the standard Gaussian distribution $N(0, I_d)$. Let $Y = \max_{j\in[d] } X_j$. It is not hard to see that \begin{align} \mathbb{E}\left [ Y \cdot X\right] = \sum_{j=1}^d \mathbb{P}\left( j = \arg\max_{i \in [d]} X_i \right) \cdot e_j, \end{align} where $e_i$ is the standard basis in $\mathbb{R}^d$. Now I was wondering how to compute $$\mathbb{E} \left[ Y\cdot (X X^\top - I_d) \right ].$$ Is there a closed form solution?

• Did you notice that $\mathbb{P}\left( j = \arg\max_{i \in [d]} X_i \right)=1/d$ for each $j=1,\dots,d$? Oct 6 '17 at 3:25
• @IosifPinelisThanks for your comment and great answer. This is indeed a great observation. However, the motivation of my problem come from the general setting where $Y = \max_{j\in[k]} \langle w_j, X \rangle$ where $w_1, \ldots, w_k$ are $k$-vectors and $X$ is a standard Gaussian vector. It would be interesting to recover those $w_j$'s from the moments of $Y$ and $X$. In this case, the probability is not equal to $1/k$ in general. Oct 6 '17 at 6:23

Let $n:=d$. Assume $n\ge3$. Let $F$ and $f$ denote the cdf and pdf of $N(0,1)$, and let $I\{\cdot\}$ denote the indicator function. Each of the diagonal entries of the matrix $EYXX^T$ equals \begin{equation*} EX_1^2\max_iX_i=E_1+E_2, \end{equation*} where \begin{equation*} E_1:=EX_1^3\,I\{X_1>\max_2^n X_i\},\quad E_2:=(n-1)EX_1^2 X_2\,I\{X_2>X_1\vee\max_3^n X_i\}. \end{equation*} Note that the cdf of the maximum of $k$ iid $N(0,1)$ random variables (r.v.'s) is $F^k$. So, \begin{multline*} E_1=\int_{-\infty}^\infty d(F(c)^{n-1})\,EX_1^3\,I\{X_1>c\} =\int_{-\infty}^\infty d(F(c)^{n-1})\,\int_c^\infty dx\,x^3f(x) \\ =\int_{-\infty}^\infty dc\, F(c)^{n-1}c^3f(c), \end{multline*} by integration by parts. Next, using the identities $$EX_2\,I\{X_2>u\}=f(u)$$ and $$d_c f(u\vee c)=-cf(c)I\{c>u\}\,dc$$ for real $u$, and integrating by parts (twice), we have \begin{multline*} E_2:=\int_{-\infty}^\infty (n-1)d(F(c)^{n-2})\,EX_1^2 X_2\,I\{X_2>X_1\vee c\} \\ =\int_{-\infty}^\infty (n-1)d(F(c)^{n-2})\,EX_1^2 f(X_1\vee c) \\ =\int_{-\infty}^\infty (n-1)dc\, F(c)^{n-2}\,cf(c) EX_1^2\,I\{X_1<c\} \\ =\int_{-\infty}^\infty (n-1)dc\, F(c)^{n-2}\,cf(c) (F(c)-cf(c)) \\ =\int_{-\infty}^\infty (n-1)dc\, F(c)^{n-1}\,cf(c) -\int_{-\infty}^\infty (n-1)dc\, F(c)^{n-2}\,f(c)c^2f(c) \\ =\int_{-\infty}^\infty (n-1)dc\, F(c)^{n-1}\,cf(c) +\int_{-\infty}^\infty dc\, F(c)^{n-1}\,(2c-c^3)f(c) \\ =\int_{-\infty}^\infty dc\, F(c)^{n-1}\,((n+1)c-c^3)f(c). \end{multline*} Thus, each of the diagonal entries of the matrix $EYXX^T$ equals \begin{equation*} EX_1^2\max_iX_i=E_1+E_2=(n+1)\int_{-\infty}^\infty dc\, F(c)^{n-1}\,f(c)c \end{equation*}. Since \begin{equation*} EY=E\max_iX_i=n\int_{-\infty}^\infty dc\, F(c)^{n-1}\,f(c)c, \tag{1} \end{equation*} we conclude that each of the diagonal entries of the matrix $EY(XX^T-I)$ equals \begin{equation*} \text{diags}= EX_1^2\max_iX_i=\int_{-\infty}^\infty dc\, F(c)^{n-1}\,f(c)c=\tfrac1n\,EY. \tag{2} \end{equation*}

Each of the off-diagonal entries of the matrix $EY(XX^T-I)$ equals \begin{equation*} EX_1X_2\max_iX_i=\sum_1^n s_j, \end{equation*} where \begin{equation*} s_j:=EX_1 X_2 X_j\,I\{X_j\ge \max_1^n X_i\}. \end{equation*}

If $j\notin\{1,2\}$, then, similarly to the previous multi-line display, \begin{multline*} s_j=EX_1 X_2 X_3\,I\{X_3>X_1\vee X_2\vee \max_4^n X_i\} \\ =\int_{-\infty}^\infty d(F(c)^{n-3})\,EX_1 X_2 X_3\,I\{X_3>X_1\vee X_2\vee c\} \\ =\int_{-\infty}^\infty d(F(c)^{n-3})\,EX_1 X_2 f(X_1\vee X_2\vee c) \\ =\int_{-\infty}^\infty dc\,F(c)^{n-3}f(c)c\,EX_1 X_2 I\{X_1\vee X_2<c\} \\ =\int_{-\infty}^\infty dc\,F(c)^{n-3}f(c)c\,f(c)^2 \\ =\frac1{n-2}\,\int_{-\infty}^\infty dc\,F(c)^{n-2}(2c^2-1)\,f(c)^2 \\ =\frac2{(n-1)(n-2)}\,\int_{-\infty}^\infty dc\,F(c)^{n-1}(2c^3-5c)\,f(c). \end{multline*}

If $j\in\{1,2\}$, then \begin{multline*} s_j=EX_1 X_2^2\,I\{X_2>X_1\vee \max_3^n X_i\} \\ =\int_{-\infty}^\infty d(F(c)^{n-2})\,EX_1 I\{X_1<X_2\}X_2^2\,I\{X_2>c\} \\ =-\int_{-\infty}^\infty d(F(c)^{n-2})\,Ef(X_2)X_2^2\,I\{X_2>c\} \\ =-\int_{-\infty}^\infty d(F(c)^{n-2})\,\int_c^\infty dx\, f(x)^2x^2 \\ =-\int_{-\infty}^\infty dc\,F(c)^{n-2}\, f(c)c^2 \\ =\frac1{n-1}\,\int_{-\infty}^\infty dc\, F(c)^{n-1}\,(2c-c^3)f(c). \end{multline*}

So, each of the off-diagonal entries of the matrix $EY(XX^T-I)$ equals \begin{multline*} \text{off-diags}=EX_1X_2\max_iX_i=2s_1+(n-2)s_3= \frac2{n-1}\int_{-\infty}^\infty dc\,F(c)^{n-1}(c^3-3c)\,f(c) \\ =\frac2{(n-1)n}\,E(Y^3-3Y) \tag{3} \end{multline*} -- cf. $(1)$, $(2)$.

Mathematica claims that the value of the latter integral is $-\frac{1}{4 \sqrt{\pi }}\approx -0.141$ for $n=2,3$, but it cannot evaluate it in closed form for $n=4$ (an approximate value of that integral for $n=4$ is $-0.0969$).

Yet, it is now easy to compute the diagonal and off-diagonal entries of the matrix $EY(XX^T-I)$ numerically, and it is also easy to find their asymptotics for large $n(=d)$, using standard methods of asymptotic analysis.

Indeed, let us consider the integral \begin{equation*} J_n:=\int_{-\infty}^\infty dc\,F(c)^{n-1}(c^3-3c)\,f(c) \end{equation*} in $(3)$ for large $n$. Write \begin{multline*} J_n=J_{1n}+J_{2n}+J_{3n},\\ J_{1n}:=\int_{-\infty}^{c_n}\dots,\ J_{2n}:=\int_{c_n}^{d_n}\dots,\ J_{3n}:=\int_{d_n}^\infty\dots, \end{multline*} where \begin{gather*} c_n:=F^{-1}(e^{-w_n/n}),\quad d_n:=F^{-1}(e^{-v_n/n}) \\ v_n:=n^{-t_n},\quad w_n:=n^{t_n},\quad t_n:=1/\sqrt{\ln n}. \end{gather*} Then \begin{gather*} 0<v_n<w_n,\quad v_n\to0,\quad w_n=1/v_n\to\infty,\quad d_n>c_n\to\infty,\\ 1-F(c_n)\sim-\ln F(c_n)=w_n/n=n^{-1+o(1)},\quad 1-F(c_n)=\exp\{-c_n^2/(2+o(1))\}. \end{gather*} Hence and from similar relations for $d_n$, we find that $c_n\sim\sqrt{2\ln n}\sim d_n$, and so, \begin{equation*} c\sim\sqrt{2\ln n}\text{ uniformly in $c\in[c_n,d_n]$}. \tag{4} \end{equation*}

Next, for real $c<c_n$ we have $F(c)^{n-1}<F(c_n)^{n-1}=e^{-(n-1)w_n/n}\sim e^{-w_n} =\exp\{-e^{\sqrt{\ln n}}\}<\exp\{-\ln^2 n\}=o(1/n)$, whence \begin{equation*} |J_{1n}|\le F(c_n)^{n-1}\int_{-\infty}^{c_n} dc\,|c^3-3c|\,f(c)=o(1/n). \end{equation*}

On the other hand, \begin{equation*} |J_{3n}|\le \int_{d_n}^\infty dc\,|c^3-3c|\,f(c) \sim d_n^3(1-F(d_n))\sim-d_n^3\ln F(d_n)\sim (\sqrt{2\ln n})^3 v_n/n =o(1/n). \end{equation*}

Consider finally the integral $J_{2n}$, which is the main term of the asymptotics. In that integral, let us use the substitution $v=-n \ln F(c)$, so that the condition $c_n<c<d_n$ can be rewritten as $v_n<v<w_n$. Note also that $v=-n \ln F(c)\iff c=C_n(v):=F^{-1}(e^{-v/n})$. Also, by $(4)$, $C_n(v)\sim\sqrt{2\ln n}$ uniformly in $v\in[v_n,w_n]$. So, \begin{equation*} J_{2n}=\frac1n\,\int_{v_n}^{w_n}dv\,e^{-v}[C_n(v)^3-3C_n(v)] \sim\frac{(\sqrt{2\ln n})^3}n. \end{equation*}

Collecting all the pieces, we have \begin{equation*} \text{off-diags}=\frac2{(n-1)n}\,E(Y^3-3Y) \sim\frac{2^{5/2}\ln^{3/2} n}{n^2}. \end{equation*}

It is similar (and slightly simpler) to derive from $(2)$ the following:
\begin{equation*} \text{diags}=\tfrac1n\,EY \sim\frac{2^{1/2}\ln^{1/2} n}{n}. \end{equation*} So, one may also notice that \begin{equation*} \text{off-diags}\sim\tfrac2{n^2}\,(EY)^3. \end{equation*}

Curiously, the off-diagonal entries of the matrix $EY(XX^T-I)$ seem to be negative for $n\in\{2,\dots,6\}$ but positive for $n\ge7$.

• I have added the promised easy-to-obtain asymptotics; also added the expression for the off-diagonal expected values as the expectation of a simple polynomial function of the maximum of the iid Gaussians. Oct 6 '17 at 1:26