Let $X\sim N(0, I_d)$ be a $d$-dimensional Gaussian random vector. Let $W_1, \ldots, W_k \in \mathbb{R}^d$ be $k$ fixed vectors in general positions. It is clear that $w_i^\top X, \ldots, w_k^\top X$ are jointly Gaussian random variables. Let $$ Y = \max _{i \in [k]} W_i^\top x ,$$ my question is how to compute $\mathbb{E} [ Y\cdot X]$.

My idea is to use a smooth approximation of the max function and the Stein's identity. Let $$ f(y, \alpha ) = \alpha^{-1} \log \left [ \exp(\alpha y_1) + \ldots + \exp( \alpha y_k ) \right ],$$ it is known that $ \left | \max_i y_i - f(y, \alpha) \right | \leq \log k / \alpha$. Then by Stein's identity, we consider \begin{align} \mathbb{E} \left [ f(WX , \alpha) \cdot X \right ] = \mathbb{E} [ \nabla_{X} f(W X , \alpha) ] = \mathbb{E} \left [ \frac{ \sum_{i \in [k]} \exp ( \alpha \cdot W_i ^\top X ) \cdot W_i }{ \sum_{i \in [k]} \exp(\alpha \cdot W_i ^\top X )} \right ]. \end{align} If I naively take $\alpha \rightarrow +\infty$, I would get \begin{align} &\lim_{\alpha\rightarrow +\infty} \mathbb{E} \left [ f(WX , \alpha) \cdot X \right ] = \mathbb{E} \left[ \sum_{j\in[k]} I\left\{ j =\arg\max _{i\in[k]} W_i^\top X \right \} \cdot W_j \right ] \\ &\quad = \sum_{j\in [k]} \mathbb{P}\left (j =\arg\max _{i\in[k]} W_i^\top X \right ) \cdot W_i. \end{align} I wonder whether my naive derivation gets the correct answer and whether such derivation could be made rigorous.

  • 1
    $\begingroup$ Is Y is a scalar-valued variable, and if so, why the dot in $E[Y \cdot X]$? As I see it, here is a simpler formulation of the case d=2: Let (x,y) be bivariate normal, and let (t,u) and (v,w) be fixed vectors. What are E[max(tx+uy,vx+wy)x] and E[max(tx+uy,vx+wy)y]? If that's not what you meant, it would help to state the d=2 case in similar vector-free, subscript-free terms. $\endgroup$ – Matt F. Jul 22 '17 at 20:40
  • 1
    $\begingroup$ Looks correct and completely rigorous (What is so naiive about passing to the limit? The dominated convergence theorem is still valid and integrable majorants are easy to find:-) ). $\endgroup$ – fedja Jul 22 '17 at 20:54
  • 1
    $\begingroup$ @fedja Thanks very much. I suppose the higher order derivatives can be obtained similarly using DCT. $\endgroup$ – Steve Jul 23 '17 at 11:57
  • 1
    $\begingroup$ @MattF. Sorry for the confusion. The dot in $Y\cdot X$ is the scalar product, that is, $Y$ is multiplied to every entry of $X$. Your statement of the $d=2$ case is exactly what I meant. Thanks! $\endgroup$ – Steve Jul 23 '17 at 12:00

In the $d=2$ case the result is explicit and nice.

Let $x$ and $y$ be i.i.d standard normal, and let $(t,u)$ and $(v,w)$ be fixed vectors.

Let $M = \begin{pmatrix} t & u \\ v & w \\ \end{pmatrix}, \text{ and } X = \begin{pmatrix} x \\ y \\ \end{pmatrix} $. We want $E\big[\max(MX)\,X\big]$.

The first coordinate is \begin{align} &E\big[\max(tx+uy,vx+wy)x\big] \\ ={}&E\big[(tx+uy+vx+wy)x+\left|tx+uy-vx-wy\right|x\big]\ /\ 2 \\ ={}&E\big[(tx+uy+vx+wy)x\big]\ /\ 2 \\ ={}&(t+v)\ /\ 2 \end{align} The first equation uses the identity $\max(a,b)=(a+b+|a-b|)/2$. (This is the part specific to $d=2$: are there any analogs with more than two variables being maximized?)

The second equation uses the symmetry of $(x,y)$ and $(-x,-y)$ in the distribution.

The third equation uses the standard normal variance and independence of $X$ and $Y$.

So using similar reasoning for the second coordinate, $$ E\big[\max(MX)\,X\big]= \frac{1}{2} \begin{pmatrix} t+v\\ u+w\\ \end{pmatrix}. $$

| cite | improve this answer | |

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.