2026-07-25T14:52:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8494 2024-03-06T10:42:17Z ddc:004 open_access

On Approximating the Stationary Distribution of Time-reversible Markov Chains Bressan, Marco Peserico, Enoch Pretto, Luca Markov chains MCMC sampling large graph algorithms randomized algorithms sublinear algorithms Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require tilde{O}(tau/pi(v)) operations to approximate the probability pi(v) of a state v in a chain with mixing time tau, and even the best available techniques still have complexity tilde{O}(tau^1.5 / pi(v)^0.5); and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier". Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco Bressan and Enoch Peserico and Luca Pretto 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.18 urn:nbn:de:0030-drops-84949 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.18 eng https://creativecommons.org/licenses/by/3.0/legalcode