Gibbs/Metropolis algorithms on a convex polytope

DOI10.1007/S00209-011-0924-5zbMATH Open1254.60079arXiv1104.0749OpenAlexW2050942782MaRDI QIDQ455635FDOQ455635

Authors: Gilles Lebeau, Laurent Michel, Persi Diaconis 

Publication date: 22 October 2012

Published in: Mathematische Zeitschrift (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (13)

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

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)