Gibbs/Metropolis algorithms on a convex polytope (Q455635): Difference between revisions

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.