Gibbs/Metropolis algorithms on a convex polytope
The paper discusses the convergence of a Gibbs/Metropolis algorithm for the approximation of a uniform distribution on a convex polytope \(\Omega\) in \(\mathbb{R}^d\). The main application the authors are interested in is the sampling of random doubly stochastic matrices from a uniform distribution. One step of the algorithm works as follows. Start in \(x\in\Omega\) and pick a direction \(e\) out of a finite set and set \(y=x+ue\), where \(u\) is chosen uniformly in \([-h,h]\). The proposal is rejected if \(y\notin \Omega\). The authors prove that this Markov chain converges (under some conditions) uniformly in the total variation norm to the uniform distribution on \(\Omega\). The rate of convergence is proved to be exponential, i.e., of order \(e^{ng(h)}\). The result is obtained by studying the spectral properties of the Metropolis operator connected to this algorithm, where \(g(h)\) in the convergence rate is the spectral gap. It is proven to be asymptotically equal to \(\nu h^2\) where \(\nu\) is the first non zero eigenvalue of a Laplacian operator defined on \(\Omega\). The authors discuss some extensions of their main result. No numerical examples are given.
- 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
- 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
- scientific article; zbMATH DE number 3622441 (Why is no real title available?)
- 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?
- False discovery variance reduction in large scale simultaneous hypothesis tests
- A Gibbs sampler on the \(n\)-simplex
- Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation
- Spectral analysis of hypoelliptic random walks
- Rejoinder—A Gibbs Sampler for a Class of Random Convex Polytopes
- A Gibbs Sampler for a Class of Random Convex Polytopes
- Singular relaxation of a random walk in a box with a Metropolis Monte Carlo dynamics
- Harnack inequalities and Gaussian estimates for random walks on metric measure spaces
- Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
- Geometric analysis for the Metropolis algorithm on Lipschitz domains
- Metropolis Monte Carlo sampling: convergence, localization transition and optimality
- Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
- Measuring exposure to dependence risk with random Bernstein copula scenarios
- Bayesian estimation of generalized partition of unity copulas
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)
