Stochastic billiards for sampling from the boundary of a convex set

2014/10/21 by A. B. Dieker, Santosh Vempala, Dieker, A. B. +1
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Statistical Methods and Inference #cs.DS #math.PR

paper · pdf · doi:10.48550/arxiv.1410.5775

arxiv created 2014/10/21 · openalex publication_date 2014/10/21 · arxiv updated 2014/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo (MCMC) paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets.

Related

• Explicit speed of convergence of the stochastic billiard in a convex set
• Stochastic Perturbations of Convex Billiards
• An MCMC Method to Sample from Lattice Distributions
• Automatic Markov Chain Monte Carlo Procedures for Sampling from Multivariate Distributions
• Area and Perimeter of the Convex Hull of Stochastic Points