A Monte Carlo Method for High-Dimensional Volume Estimation and Application to Polytopes

AbstractA direct Monte Carlo method for volume estimation of star-shaped or convex domains is presented, and is generalized to a Markov Chain Monte Carlo method for high-dimensional problems. The direct approach itself, which is closely related to a method proposed by Fok and Crevier, is already applicable to some moderately high-dimensional problems. The combination with a Markov Chain Monte Carlo method and nested sampling or thermodynamic integration extends its scope considerably. Applications to the volume estimation for high-dimensional polytopes are presented, and the method is tested using exact results for the first 10 Birkho_ polytopes