Anzeige
Erschienen in:
05.04.2019
On Approximating the Stationary Distribution of Time-Reversible Markov Chains
Erschienen in: Theory of Computing Systems | Ausgabe 3/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 π(v) of a state v in a chain with mixing time τ, 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 π(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-π(v) barrier”.