The birthday problem and Markov chain Monte Carlo

Simple item page
dc.creatorBenjamini, Itai
dc.creatorMorris, Ben
dc.date2007-01-14
dc.date.accessioned2026-07-07T07:41:00Z
dc.date.available2026-07-07T07:41:00Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/math/0701390
dc.identifierhttp://arxiv.org/abs/math/0701390
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/121954
dc.subjectProbability
dc.subjectCombinatorics
dc.titleThe birthday problem and Markov chain Monte Carlo
dc.typetext

Files

Collections

arXiv