On approximating the stationary distribution of time-reversible Markov chains

DOI10.1007/S00224-019-09921-3zbMath1436.60035OpenAlexW3021997320WikidataQ128095692 ScholiaQ128095692MaRDI QIDQ1987513

Luca Pretto, Marco Bressan, Enoch Peserico

Publication date: 15 April 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8494/

zbMATH Keywords

Markov chainsrandomized algorithmsMCMC samplingsublinear algorithmslarge graph algorithms

Mathematics Subject Classification ID

Stationary stochastic processes (60G10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Sublinear Algorithms for Local Graph-Centrality Estimation

Uses Software

• fast-ppr

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Choice-memory tradeoff in allocations
• On tail probabilities for martingales
• A Sublinear Time Algorithm for PageRank Computations
• Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified
• Sublinear Time Algorithms
• Bidirectional PageRank Estimation: From Average-Case to Worst-Case
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Multiscale Matrix Sampling and Sublinear-Time PageRank Computation
• Estimating Sum by Weighted Sampling
• Monte Carlo sampling methods using Markov chains and their applications

This page was built for publication: On approximating the stationary distribution of time-reversible Markov chains