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 O(t/p(v)) operations to approximate the probability p(v) of a state v in a chain with mixing time t, and even the best available techniques still have complexity O(t1.5/p(v)0.5); and since these complexities depend inversely on p(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-p(v) barrier”.

On approximating the stationary distribution of time-reversible Markov chains / M. Bressan, E. Peserico, L. Pretto (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS). - In: Symposium on Theoretical Aspects of Computer Science / [a cura di] R. Niedermeier, B. Vallée. - [s.l] : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. - pp. 18:1-18:14 (( Intervento presentato al 35. convegno STACS tenutosi a Caen nel 2018 [10.4230/LIPIcs.STACS.2018.18].

On approximating the stationary distribution of time-reversible Markov chains

M. Bressan
Primo
;
2018

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 O(t/p(v)) operations to approximate the probability p(v) of a state v in a chain with mixing time t, and even the best available techniques still have complexity O(t1.5/p(v)0.5); and since these complexities depend inversely on p(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-p(v) barrier”.
Large Graph Algorithms; Markov Chains; MCMC Sampling; Randomized Algorithms; Sublinear Algorithms
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
LIPIcs-STACS-2018-18.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 606.17 kB
Formato Adobe PDF
606.17 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/922276
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact