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?

  • $\begingroup$ Did you notice that $\mathbb{P}\left( j = \arg\max_{i \in [d]} X_i \right)=1/d$ for each $j=1,\dots,d$? $\endgroup$ Oct 6 '17 at 3:25
  • $\begingroup$ @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. $\endgroup$
    – Steve
    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$.

  • $\begingroup$ 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. $\endgroup$ Oct 6 '17 at 1:26

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.