Fan Jianqing, Jiang Bai, Sun Qiang
Department of Operations Research and Financial Engineering, Princeton University, 205 Sherred Hall, Princeton, NJ 08544.
Department of Statistical Sciences, University of Toronto, 100 St. George Street, Toronto, ON M5S 3G3, Canada.
J Mach Learn Res. 2021 Aug;22.
This paper establishes Hoeffding's lemma and inequality for bounded functions of general-state-space 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.
本文针对一般状态空间且不一定可逆的马尔可夫链的有界函数，建立了霍夫丁引理和不等式。这些结果的尖锐性通过马尔可夫相关和独立设置中方差代理之间比率的最优性来表征。一般来说，函数的有界性被证明是这些结果成立的必要条件。为了展示新结果的有用性，我们将其应用于马尔可夫性质的时间序列数据的MCMC估计、响应驱动抽样和高维协方差矩阵估计的非渐近分析。除了统计问题，我们还将其应用于研究计量经济模型中的时间贴现奖励以及机器学习领域中产生的具有马尔可夫奖励的多臂老虎机问题。
