Hoeffding's inequality for general markov chains and its applications to statistical learning

Jianqing Fan, Bai Jiang, Qiang Sun

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


This paper establishes Hoeffding's lemma and inequality for bounded functions of general-statespace and not necessarily reversible Markov chains. The sharpness of these results is characterized by the optimality of the ratio between variance proxies in the Markov-dependent and independent settings. The boundedness of functions is shown necessary for such results to hold in general. To showcase the usefulness of the new results, we apply them for non-asymptotic analyses of MCMC estimation, respondent-driven sampling and high-dimensional covariance matrix estimation on time series data with a Markovian nature. In addition to statistical problems, we also apply them to study the time-discounted rewards in econometric models and the multi-armed bandit problem with Markovian rewards arising from the field of machine learning.

Original languageEnglish (US)
Pages (from-to)1-35
Number of pages35
JournalJournal of Machine Learning Research
StatePublished - Aug 1 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


  • General state space
  • Hoeffding's inequality
  • Markov chain
  • Markov chain Monte Carlo


Dive into the research topics of 'Hoeffding's inequality for general markov chains and its applications to statistical learning'. Together they form a unique fingerprint.

Cite this