The birthday problem and Markov chain Monte Carlo
From MaRDI portal
Publication:6478619
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)
