Sampling According to the Multivariate Normal Density

This paper deals with the normal density of n dependent random variables. This is a function of the form: ce(-x/sup T/Ax) where A is an n/spl times/n positive definite matrix, a: is the n-vector of the random variables and c is a suitable constant. The first problem we consider is the (approximate) evaluation of the integral of this function over the positive orthant /spl int/(x/sub 1/=0)/sup /spl infin///spl int/(x/sub 2/=0)/sup /spl infin///spl middot//spl middot//spl middot//spl int/(x/sub n/=0)/sup /spl infin//ce(-x/sup T/Ax). This problem has a long history and a substantial literature. Related to it is the problem of drawing a sample from the positive orthant with probability density (approximately) equal to ce(-x/sup T/Ax). We solve both these problems here in polynomial time using rapidly mixing Markov Chains. For proving rapid convergence of the chains to their stationary distribution, we use a geometric property called the isoperimetric inequality. Such an inequality has been the subject of recent papers for general log-concave functions. We use these techniques, but the main thrust of the paper is to exploit the special property of the normal density to prove a stronger inequality than for general log-concave functions. We actually consider first the problem of drawing a sample according to the normal density with A equal to the identity matrix from a convex set K in R/sup n/ which contains the unit ball. This problem is motivated by the problem of computing the volume of a convex set in a way we explain later. Also, the methods used in the solution of this and the orthant problem are similar.

Authors

• Ravindran Kannan
• Guangxing Li

Keywords

• Sampling methods
• Polynomials
• Steady-state
• Mathematics
• Statistical distributions
• Gaussian distribution
• Probability distribution
• Tin
• Convergence
• Markov Chain
• Probability Density
• Convex Set
• Intensive Setting
• Unit Sphere
• Normal Density
• Rapid Convergence
• Steady State
• Independent Samples
• Step Size
• Number Of Steps
• Random Walk
• Positive Real
• Penalty Function
• Subsequent Samples
• Standard Density
• Final Paper
• Small Step Size
• Total Variation Distance
• Generalized Gaussian Distribution