On the mixing time of coordinate Hit-and-Run

DOI10.1017/S0963548321000328MaRDI QIDQ5886322zbMATH OpenOpenAlexFDO

Authors Hariharan Narayanan, Piyush Srivastava

Publication date 31 March 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

convex bodiesMarkov chainssampling

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Hit-and-run mixes fast
• Hit-and-run from a corner
• Hit-and-Run from a Corner
• Blocking Conductance and Mixing in Random Walks
• Random walks in a convex body and an improved volume algorithm

Cites work

• A random polynomial-time algorithm for approximating the volume of convex bodies
• Concentration inequalities. A nonasymptotic theory of independence
• Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Fast MCMC sampling algorithms on polytopes
• Geodesic walks in polytopes
• Hit-and-Run from a Corner
• Hit-and-run mixes fast
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Random walks and anO*(n5) volume algorithm for convex bodies
• Random walks in a convex body and an improved volume algorithm
• Random walks on polytopes and an affine interior point method for linear programming
• Randomized interior point methods for sampling and optimization
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Strong self-concordance and sampling
• The Kannan-Lovász-Simonovits conjecture

Cited in

(7)

• Hit-and-run from a corner
• Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
• A practical algorithm for volume estimation based on billiard trajectories and simulated annealing
• Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo
• Localization schemes: a framework for proving mixing bounds for Markov chains
• Sampling from convex sets with a cold start using multiscale decompositions
• On the _0 isoperimetric coefficient for measurable sets

This page was built for publication: On the mixing time of coordinate Hit-and-Run

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