Stochastic Billiards for Sampling from the Boundary of a Convex Set

DOI10.1287/moor.2014.0701zbMath1331.60152arXiv1410.5775OpenAlexW2169266106WikidataQ125575584 ScholiaQ125575584MaRDI QIDQ3465938

A. B. Dieker, Santosh Vempala

Publication date: 29 January 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

samplingMarkov chain Monte Carlo methodconvex setrapid mixingstochastic billiards

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Related Items (6)

Rapid mixing of geodesic walks on manifolds with positive curvature ⋮ Random sampling: billiard walk algorithm ⋮ Sampling from the complement of a polyhedron: an MCMC algorithm for data augmentation ⋮ Stochastic billiards with Markovian reflections in generalized parabolic domains ⋮ Explicit Speed of Convergence of the Stochastic Billiard in a Convex Set ⋮ Uniform distributions and random variate generation over generalized \(l_p\) balls and spheres

Cites Work

• Unnamed Item
• Computing the volume is difficult
• Stochastic search in a convex region
• Stochastic billiards on general tables
• Hit-and-run mixes fast
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Heat flow and a faster algorithm to compute the surface area of a convex body
• Isoperimetric Bounds on Convex Manifolds
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Sampling Hypersurfaces through Diffusion
• Shake-and-bake algorithms for the identification of nonredundant linear inequalities
• Shake-and-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra
• Isoperimetric constants and the first eigenvalue of a compact riemannian manifold
• A general framework for approximate sampling with an application to generating points on the boundary of bounded convex regions
• Random walks in a convex body and an improved volume algorithm
• On The Complexity of Computing Mixed Volumes
• Hit-and-Run from a Corner
• Sampling from a Manifold
• Billiards in a general domain with random reflections

This page was built for publication: Stochastic Billiards for Sampling from the Boundary of a Convex Set