Mixing time estimation in reversible Markov chains from a single sample path

DOI10.1214/18-AAP1457zbMath1466.60143arXiv1708.07367OpenAlexW2963818535MaRDI QIDQ2330466

Daniel Hsu, Yuval Peres, David A. Levin, Geoffrey Wolfer, Csaba Szepesvári, Leonid (Aryeh) Kontorovich

Publication date: 22 October 2019

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainsspectral gapmixing timeempirical confidence interval

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Inference from stochastic processes (62M99)

Related Items

Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation, Simple and Optimal Methods for Stochastic Variational Inequalities, II: Markovian Noise and Policy Evaluation in Reinforcement Learning, Improved estimation of relaxation time in nonreversible Markov chains, Statistical estimation of ergodic Markov chain kernel over discrete state space, Function-specific mixing times and concentration away from equilibrium, Information geometry of reversible Markov chains, Mixing time estimation in reversible Markov chains from a single sample path

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Markov chain Monte Carlo confidence intervals
• Information geometry approach to parameter estimation in Markov chains
• Markov chains and stochastic stability
• Estimating beta-mixing coefficients via histograms
• Learning from dependent observations
• Basic properties of strong mixing conditions. A survey and some open questions
• Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
• Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions
• On tail probabilities for martingales
• Rates of convergence for empirical processes of stationary mixing sequences
• Applications of Paz's inequality to perturbation bounds for Markov chains
• Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
• Estimating the second largest eigenvalue of a Markov transition matrix
• Sensitivity of finite Markov chains under perturbation
• Rates of uniform convergence of empirical means with mixing processes
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Statistical estimation of ergodic Markov chain kernel over discrete state space
• Mixing time estimation in reversible Markov chains from a single sample path
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• The Computational Complexity of Estimating MCMC Convergence Time
• Mathematical Aspects of Mixing Times in Markov Chains
• The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
• A Chernoff Bound for Random Walks on Expander Graphs
• Extension of the PAC framework to finite and countable Markov chains
• On the continuity of the group inverse
• Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes
• Perturbation bounds for the stationary probabilities of a finite Markov chain
• Testing Closeness of Discrete Distributions
• Advanced Lectures on Machine Learning
• An Introduction to Matrix Concentration Inequalities
• Monte Carlo strategies in scientific computing
• Comparison of perturbation bounds for the stationary distribution of a Markov chain
• An improvement on the perturbation of the group inverse and oblique projection