# Computing conditional expectation of ordered normal random variables

There are $m$ normally distributed, independent random variables $N_1, \ldots, N_m$ with distinct means $\mu_1, \ldots \mu_m$ and standard deviations $\sigma_1, \ldots, \sigma_m$. Then, we observe a permutation of the numbers $\pi = \{1, \ldots, m\}$. How can we efficiently compute the conditional expectation of the random variables in same ordering as this permutation? Added bonus: how can we compute the conditional variance?

An example:

1. we have four independent random variables $N_1, N_2, N_3, N_4$, all with different means and variances.
2. We are given the permutation $\pi = (3, 1, 2, 4)$.
3. What's $\mathbf{E}((N_1, N_2, N_3, N_4) \mid N_3 > N_1 > N_2 > N_4)$?

One way to do this is by Gibbs sampling: we can sample from the conditional distribution $(N_1, N_2, N_3, N_4) \mid N_3 > N_1 > N_2 > N_4$ by doing the following:

1. Initialize some arbitrary values $x_i^0$ such that $x_3^0 > x_1^0 > x_2^0 > x_4^0$
2. For $t = 1 \ldots M$, choose a random index $i$.
3. $x_{\pi_i}^t \sim \text{TruncatedNormal}(\mu_{\pi_i}, \sigma_{\pi_i}, x_{\pi_{i-1}}^{t-1}, x_{\pi_{i+1}}^{t-1})$, with lower/upper bounding values $-\infty$ or $\infty$ if $i=1$ or $i=m$, respectively, and $x^t = x^{t-1}$ otherwise
4. Compute the mean and variance of the $x^t$ after some break-in period.

The above is basically an MCMC method that walks over the conditional distribution to obtain an average computationally. The question is, is there a more efficient, faster, or better way to compute this expectation?

This question is related to this one on math.stackexchange about computing the probability of a particular ordering, which it turns out can be done using the multivariate normal CDF (for which there exist numerical methods.)

• For $m=4$, the numerical integration is way faster than any MCMC method and far more accurate. – whuber Jan 20 '13 at 12:16
• Can you provide more details on how you'd compute this integration numerically and how you would be able to obtain the conditional variance? – Andrew Mao Jan 20 '13 at 19:36

1. via a multivariate normal integral, using Alan Genz' MVNEXP FORTRAN library: (Check out the conditionalExp method down the page)