Document Open Access Logo

On Approximating the Stationary Distribution of Time-reversible Markov Chains

Authors Marco Bressan, Enoch Peserico, Luca Pretto

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.18.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Marco Bressan
Enoch Peserico
Luca Pretto

Cite As Get BibTex

Marco Bressan, Enoch Peserico, and Luca Pretto. On Approximating the Stationary Distribution of Time-reversible Markov Chains. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.18

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 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".

Subject Classification

Keywords
  • Markov chains
  • MCMC sampling
  • large graph algorithms
  • randomized algorithms
  • sublinear algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Ori Gurel-Gurevich, and Eyal Lubetzky. Choice-memory tradeoff in allocations. The Annals of Applied Probability, 20(4):1470-1511, 2010. Google Scholar
  2. Anne Auger and Benjamin Doerr, editors. Theory of Randomized Search Heuristics: Foundations and Recent Developments, volume 1. World Scientific Publishing Co., Inc., 2011. Google Scholar
  3. Siddhartha Banerjee and Peter Lofgren. Fast bidirectional probability estimation in Markov models. In Proc. of NIPS, pages 1423-1431, 2015. Google Scholar
  4. Phillip Bonacich and Paulette Lloyd. Eigenvector-like measures of centrality for asymmetric relations. Social Networks, 23(3):191-201, 2001. Google Scholar
  5. Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Shang-Hua Teng. A sublinear time algorithm for pagerank computations. In Anthony Bonato and Jeannette C. M. Janssen, editors, Algorithms and Models for the Web Graph - 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings, volume 7323 of Lecture Notes in Computer Science, pages 41-53. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-30541-2_4.
  6. Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Shang-Hua Teng. Multiscale matrix sampling and sublinear-time PageRank computation. Internet Mathematics, 10(1-2):20-48, 2014. Google Scholar
  7. Marco Bressan, Enoch Peserico, and Luca Pretto. On approximating the stationary distribution of time-reversible Markov chains. CoRR, abs/1801.00196, 2018. Google Scholar
  8. Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. In Proc. of STACS, pages 124-135, 2012. Google Scholar
  9. David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100-118, 1975. Google Scholar
  10. Gene H. Golub and Charles F. Van Loan. Matrix Computations. Matrix Computations. Johns Hopkins University Press, 2012. Google Scholar
  11. Wilfred K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97-109, 1970. Google Scholar
  12. Christina E. Lee, Asuman Ozdaglar, and Devavrat Shah. Computing the stationary distribution, locally. In Proc. of NIPS, pages 1376-1384, 2013. Google Scholar
  13. Christina E. Lee, Asuman E. Ozdaglar, and Devavrat Shah. Solving systems of linear equations: Locally and asynchronously. CoRR, abs/1411.2647, 2014. Google Scholar
  14. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2009. Google Scholar
  15. Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional PageRank estimation: from average-case to worst-case. In Proc. of WAW, pages 164-176, 2015. Google Scholar
  16. Peter A. Lofgren, Siddhartha Banerjee, Ashish Goel, and C. Seshadhri. FAST-PPR: Scaling personalized PageRank estimation for large graphs. In Proc. of ACM KDD, pages 1436-1445, 2014. Google Scholar
  17. Rajeev Motwani, Rina Panigrahy, and Ying Xu. Estimating sum by weighted sampling. In Proc. of ICALP, pages 53-64, 2007. Google Scholar
  18. Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM Journal on Computing, 26(2):350-368, 1997. Google Scholar
  19. Ronitt Rubinfeld and Asaf Shapira. Sublinear time algorithms. SIAM Journal on Discrete Mathematics, 25(4):1562-1588, 2011. Google Scholar
  20. Nitin Shyamkumar, Siddhartha Banerjee, and Peter Lofgren. Sublinear estimation of a single element in sparse linear systems. In 2016 Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 856-860, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact