Stochastic Billiards for Sampling from the Boundary of a Convex Set

• 成果类型: Article
• 署名作者: Dieker, A. B.; Vempala, Santosh S.
• 署名单位: Columbia University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0701
• 发表日期: 2015
• 页码: 888-901
• 关键词: hit-and-run; generating points; volume algorithm; regions

摘要

Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo 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.