# [PERSON] and Mendell-Elston Estimation of the High-Dimensional Multivariate Normal Distribution
## 3 Algorithms  
We examined the performance of two algorithms that appear particularly well suited to estimation of the high-dimensional mvn distribution. The first of these is the Mendell-Elston (me) procedure (Algorithm 1), a deterministic, non-error-bounded procedure that approximates the mvn distribution as a sequence of conditional univariate normal integrals [1; 8; 11; 12]. The second algorithm is the elegant transformation and estimation procedure described by [PERSON] [13; 14] (Algorithm 2). In this approach the original \(n\)-variate distribution is transformed into an easily sampled \((n-1)\)-dimensional hypercube and estimated by Monte Carlo methods (e.g., [42; 43]). ```
Estimate the standardized \(n\)-variate mvn distribution, having zero mean and correlation matrix \(\mathbf{R}\), between vector-valued limits \(\mathbf{s}\) and \(\mathbf{t}\). The function \(\phi(z)\) is the univariate normal density at \(z\), and \(\Phi(z)\) is the corresponding univariate normal distribution. See [PERSON] [12] for discussion of the approximation, extensions, and applications. 1. input \(n\), \(\mathbf{R}\), \(\mathbf{s}\), \(\mathbf{t}\)
2. initialize\(f=1\)
3. for\(i=1,2,\ldots,n\) (a) [update the total probability] \[p_{i}=\Phi(t_{i})-\Phi(s_{i})\] \[f\gets f\!\cdot\!p_{i}\] if (\(i=n\)) return \(f\)
4. [peel variable i] \[a_{i}=\frac{\phi(s_{i})-\phi(t_{i})}{\Phi(t_{i})-\Phi(s_{i})}\] \[V_{i}=1+\frac{s_{i}\phi(s_{i})-t_{i}\phi(t_{i})}{\Phi(t_{i})- \Phi(s_{i})}-a_{i}^{2}\] \[v_{i}^{2}=1-V_{i}\] (c) [condition the remaining variables] for\(j=i+1,\ldots,n\), \(k=j+1,\ldots,n\) \[s^{\prime}_{j}=\big{(}s_{j}-r_{ij}\,a_{i}\big{)}/\sqrt{1-r_{ij}^{2} \,v_{i}^{2}}\] \[t^{\prime}_{j}=\big{(}t_{j}-r_{ij}\,a_{i}\big{)}/\sqrt{1-r_{ij}^{ 2}\,v_{i}^{2}}\] \[V^{\prime}_{j}=V_{j}/\left(1-r_{ij}^{2}\,v_{i}^{2}\right)\] \[v^{\prime 2}_{j}=1-V^{\prime}_{j}\] \[r^{\prime}_{jk}=\left(r_{jk}-r_{ij}\,r_{ik}\,v_{i}^{2}\right)/ \left(\sqrt{1-r_{ij}^{2}\,v_{i}^{2}}\sqrt{1-r_{ik}^{2}\,v_{i}^{2}}\right)\] [end loop over j,k]
```
1:Input \(n\), \(\mathbf{R}\), \(\mathbf{s}\), \(\mathbf{t}\)
2:Initialize\(f=1\)
3:for\(i=1,2,\ldots,n\)do  
approximation [31; 33; 44; 45]. Consequently, the me approximation is most accurate for small correlations and for selection in the tails of the distribution, thereby minimizing departures from normality following selection and conditioning. Conversely, the error in the me approximation is greatest for larger correlations and selection closer to the mean [1]. Estimate the \(m\)-variate mvn distribution having covariance matrix \(\boldsymbol{\Sigma}\), between vector-valued limits \(\boldsymbol{\mathrm{a}}\) and \(\boldsymbol{\mathrm{b}}\), to an accuracy \(\epsilon\) with probability \(1-\alpha\), or until the maximum number of integrand evaluations \(N_{\max}\) is reached. The procedure returns the estimated probability \  
To facilitate testing a simple driver program was written for each algorithm. The driver program accepts arguments defining the estimation problem (e.g., number of dimensions, correlations, limits of integration), and any algorithm-specific parameters (e.g., convergence criteria). The driver program then initializes the problem (i.e., generates the correlation matrix and limits of integration), calls the algorithm, records its execution time, and reports results. For the deterministic ME algorithm there are no essential user options; the only input quantities are those defining the MVN distribution and region of integration. The driver program for the Genz MC algorithm provides options for setting parameters unique to Monte Carlo estimation such as the (maximum) error in the estimate and the (maximum) allowed number of iterations (integrand evaluations) [13]. The actual software implementation of the estimation procedures and their respective driver programs is not critical; experiments with multiple independent implementations of these algorithms have shown consistent and reliable performance irrespective of programming language or style [2; 3; 7; 10; 46].