Stochastic billiards for sampling from the boundary of a convex set

Autor:	Dieker, A. B., Vempala, Santosh
Rok vydání:	2014
Předmět:	Mathematics - Probability Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1410.5775 Zobrazit plný text záznamu View this record from Arxiv