Gibbs/Metropolis algorithms on a convex polytope

DOI10.1007/S00209-011-0924-5MaRDI QIDQ455635zbMATH OpenOpenAlexFDO

Authors Gilles Lebeau, Laurent Michel, Persi Diaconis

Publication date 22 October 2012

Published in Mathematische Zeitschrift (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.0749

zbMATH Keywords

Metropolis algorithmconvex polytopesMetropolis operator

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Discrete-time Markov processes on general state spaces (60J05)

Abstract: This paper gives sharp rates of convergence for natural versions of the Metropolis algorithm for sampling from the uniform distribution on a convex polytope. The singular proposal distribution, based on a walk moving locally in one of a fixed, finite set of directions, needs some new tools. We get useful bounds on the spectrum and eigenfunctions using Nash and Weyl-type inequalities. The top eigenvalues of the Markov chain are closely related to the Neuman eigenvalues of the polytope for a novel Laplacian.

Recommendations

• On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds
• Geometric analysis for the Metropolis algorithm on Lipschitz domains
• On convergence rates of Gibbs samplers for uniform distributions
• Random walks in a convex body and an improved volume algorithm
• scientific article; zbMATH DE number 1263187

Cites work

• scientific article; zbMATH DE number 3622441 (Why is no real title available?)
• Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Geometric analysis for the Metropolis algorithm on Lipschitz domains
• Markov chains and stochastic stability
• Micro-local analysis for the Metropolis algorithm
• Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
• Random walks in a convex body and an improved volume algorithm
• Semi-classical analysis of a random walk on a manifold
• The geometry of logconcave functions and sampling algorithms
• What do we know about the Metropolis algorithm?

Cited in

(13)

• Singular relaxation of a random walk in a box with a Metropolis Monte Carlo dynamics
• Metropolis Monte Carlo sampling: convergence, localization transition and optimality
• Bayesian estimation of generalized partition of unity copulas
• Geometric analysis for the Metropolis algorithm on Lipschitz domains
• Spectral analysis of hypoelliptic random walks
• Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation
• Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
• A Gibbs Sampler for a Class of Random Convex Polytopes
• Harnack inequalities and Gaussian estimates for random walks on metric measure spaces
• Measuring exposure to dependence risk with random Bernstein copula scenarios
• False discovery variance reduction in large scale simultaneous hypothesis tests
• A Gibbs sampler on the \(n\)-simplex
• Rejoinder—A Gibbs Sampler for a Class of Random Convex Polytopes

This page was built for publication: Gibbs/Metropolis algorithms on a convex polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q455635)