On Approximating the Stationary Distribution of Time-reversible Markov Chains

DOI10.4230/LIPIcs.STACS.2018.18zbMath1487.60072arXiv1801.00196OpenAlexW2963911730MaRDI QIDQ3304112

Enoch Peserico, Luca Pretto, Marco Bressan

Publication date: 5 August 2020

Full work available at URL: https://arxiv.org/abs/1801.00196

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

Partial sorting problem on evolving data, Sublinear Algorithms for Local Graph-Centrality Estimation, Unnamed Item

Uses Software

• fast-ppr

Cites Work

• 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