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.)

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

In case anyone's interested, I have implemented computing this expectation in two ways

  1. via a multivariate normal integral, using Alan Genz' MVNEXP FORTRAN library: (Check out the conditionalExp method down the page)
  2. Via Gibbs sampling, using a truncated normal distribution for MCMC (also check out this paper)

In regards to @whuber's comment, the integration is NOT necessarily the faster approach; the Gibbs sampling is numerically simpler and can be sped up significantly by using fast (but less accurate) versions of the univariate normal. The multivariate normal integral is also tricky to use and has a tradeoff between accuracy and speed...just like the Gibbs sampler.

In preliminary testing, it's inconclusive which one is faster for a given accuracy.


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.