  The use of sparse precision (inverse covariance) matrices has become popular
because they allow for efficient algorithms for joint inference in
high-dimensional models. Many applications require the computation of certain
elements of the covariance matrix, such as the marginal variances, which may be
non-trivial to obtain when the dimension is large. This paper introduces a fast
Rao-Blackwellized Monte Carlo sampling based method for efficiently
approximating selected elements of the covariance matrix. The variance and
confidence bounds of the approximations can be precisely estimated without
additional computational costs. Furthermore, a method that iterates over
subdomains is introduced, and is shown to additionally reduce the approximation
errors to practically negligible levels in an application on functional
magnetic resonance imaging data. Both methods have low memory requirements,
which is typically the bottleneck for competing direct methods.
