Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$.
What is the computational complexity (both space or time) of calculating the cumulative distribution function 


$\int\_{-\infty}^{y\_1}dx\_{1}\cdots\int\_{-\infty}^{y\_n}dx\_{n}\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)
 $


?


This should be a function of $n$. If the suggested integration method is approximate (e.g., using monte-carlo methods), then the complexity may also depend on some required mean relative accuracy (std/mean) $\epsilon$.


Thanks in advance!



Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
To some extent this depends on the model of computation. Some remarks:


1. The problem must always involve an accuracy parameter $\epsilon$, since in general the answer will not be rational
2. Even in the case of a standard 1-dimensional normal, the question is not so easy. I believe this can be done to accuracy $\epsilon$ in $\widetilde{O}(\log^2 (1/\epsilon))$ time -- i.e., essentially quadratic time in the number of digits of accuracy. The best reference here (I think) is Brent and Zimmerman's book "Modern Computer Arithmetic"; see their discussion of the erf and erfc functions.
3. In the general $n$-dimensional case, I'm not sure whether you can get a $\mathrm{poly}(n, \log(1/\epsilon))$ running time. I'd possibly guess 'yes', but I don't know any reference. I would say that "in practice" the easiest solution would indeed be a naive Monte Carlo estimation. Assume first that you can generate standard Gaussians and do real arithmetic in constant time. Then you can get the answer (with high probability) to additive accuracy $\epsilon$ with $O(1/\epsilon^2)$ samples. Assuming you have the square-root of $\Sigma$, you could then probably get the answer in $O(n^2/\epsilon^2)$ time. (But then one technically has to worry about assumptions like generating standard Gaussians to sufficient accuracy, doing the real arithmetic, factorizing $\Sigma$ if necessary...)


Long story short, $\mathrm{poly}(n,1/\epsilon)$ time is surely okay, $\mathrm{poly}(n,\log(1/\epsilon))$ time I'm not sure about.


