Efficient Simulation of High Dimensional Gaussian Vectors

We describe a Markov chain Monte Carlo method to approximately simulate high dimensional Gaussian vectors whose covariance matrix is easy to compute. The standard Monte Carlo method is based on the Cholesky decomposition, which is performed in cubic time and quadratic storage cost in the dimension. In contrast, the storage cost of our algorithm is linear in the dimension. Under certain conditions, we show that the mean-squared error induced by our method is inversely proportional to its running time. Examples inspired from finance, communication networks and weather prediction are studied. Theoretical and simulation results show that, in some instances, our method outperforms the standard Monte Carlo method by a factor proportional to the dimension, even if Cholesky decomposition cost in not taken into account. Our algorithm runs within a few minutes to a few hours on a standard computer, depending on the examples and required precision, with dimension up to 100 thousands to 10 millions