6
$\begingroup$

Given $$\left(\begin{array}{c} X_1 \\ X_2 \end{array}\right) \sim \mathcal{N} \left(\left(\begin{array}{c} 0 \\ 0 \end{array}\right), \left(\begin{array}{cc} 1 & \rho \\ \rho & 1 \end{array}\right)\right),$$

I want to show that $$\mathbb{E}\left[ \text{sign}(X_1) \text{sign}(X_2)\right] = \frac{2}{\pi}\sin^{-1}(\rho)$$

This seems to be the essence of the proof of Geomans-Williamson MAX-CUT SDP relaxation. Is there an easy way to see it?

$\endgroup$
8
$\begingroup$

For convenience let's call $\operatorname{sgn}(X_1),\operatorname{sgn}(X_2)$ as $S_1$ and $S_2$, respectively.

There are only $9$ possible combinations of $(S_1,S_2)$: $(\pm1,\pm1)$, and at least one of the $S$ being $0$. Now, since we are looking for $E[S_1S_2]$, ignoring the states of $S=0$ will not affect the result. Hence, \begin{align*}E[S_1S_2]&=1\times P(S_1=1,S_2=1)+1\times P(S_1=-1,S_2=-1)\\ &\quad+(-1)\times P(S_1=1,S_2=-1)+(-1)\times P(S_1=-1,S_2=1)\\ &=1\times P(X_1>0,X_2>0)+1\times P(X_1<0,X_2<0)\\ &\quad+(-1)\times P(X_1>0,X_2<0)+(-1)\times P(X_1<0,X_2>0).\end{align*}

Further, one can show that $$P(X_1>0,X_2>0)=P(X_1<0,X_2<0)=\frac{1}{4}+\frac{1}{2\pi}\sin^{-1}(\rho),$$ and $$P(X_1>0,X_2<0)=P(X_1<0,X_2>0)=\frac{1}{2\pi}\cos^{-1}(\rho).$$ So \begin{align*}E[S_1S_2]&=\frac{1}{2}+\frac{1}{\pi}\sin^{-1}(\rho)-\frac{1}{\pi}\left(\frac{\pi}{2}-\sin^{-1}(\rho)\right)\\ &=\frac{2}{\pi}\sin^{-1}(\rho).\end{align*}

$\endgroup$
  • $\begingroup$ Is there an easy way to see the integral? That was where I was stuck before as well. All references I see seem to do it the messy way. $\endgroup$ – Devil Aug 3 '16 at 18:06
  • 3
    $\begingroup$ @Devil: it's possible to turn integrations into trigonometric inequalities with the help of Box-Muller transformation, this thread may help. $\endgroup$ – Francis Aug 3 '16 at 20:47
6
$\begingroup$

$$\mathbb{E}[ \text{sign}(X_1) \text{sign}(X_2)] = 1 * (P(X_1 \ge 0,X_2 \ge 0) + P(X_1 \le 0,X_2 \le 0)) - (P(X_1 \ge 0,X_2 \le 0) + P(X_1 \le 0,X_2 \ge 0))$$ which in turn $$= 2P(X_1 \ge 0,X_2 \ge 0) - 2P(X_1 \ge 0,X_2 \le 0)$$ by symmetry.

Plugging in the Bivariate Normal density, this evaluates (integrates) to $\frac{2}{\pi} sin^{-1}(\rho)$. The details of performing the integration are left to you.

Edit: Have changed what was $\sigma^2$ to $\rho$ to match edit of question.

$\endgroup$
  • 1
    $\begingroup$ +1 for that last comment since the implications of writing $\sigma^2$ are that the parameter cannot be negative and that it can exceed $1$. $\endgroup$ – Dilip Sarwate Aug 3 '16 at 15:39
  • $\begingroup$ Ah. I did not realise that. Have fixed it. $\endgroup$ – Devil Aug 5 '16 at 3:05

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.