The birthday problem and Markov chain Monte Carlo
From MaRDI portal
Publication:6478619
arXivmath/0701390MaRDI QIDQ6478619FDOQ6478619
Authors: Itai Benjamini, Ben Morris 
Publication date: 14 January 2007
Abstract: We study the problem of generating a sample from the stationary distribution of a Markov chain, given a method to simulate the chain. We give an approximation algorithm for the case of a random walk on a regular graph with n vertices that runs in expected time O^*(sqrt{n} x L^2-mixing time). This is close to the best possible, since sqrt{n} is a lower bound on the worst-case expected running time of any algorithm.
This page was built for publication: The birthday problem and Markov chain Monte Carlo
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478619)
