Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Space
Geoffrey Wolfer Aryeh Kontorovich
Abstract
We investigate the statistical complexity of estimating the parameters of a discrete-state Markov chain kernel from a single long sequence of state observations. In the finite case, we characterize (modulo logarithmic factors) the minimax sample complexity of estimation with respect to the operator infinity norm, while in the countably infinite case, we analyze the problem with respect to a natural entry-wise norm derived from total variation. We show that in both cases, the sample complexity is governed by the mixing properties of the unknown chain, for which, in the finite-state case, there are known finite-sample estimators with fully empirical confidence intervals.
中文速览
从一条长序列中估计马尔可夫链（Markov chain）的转移概率矩阵，是统计学和计算机科学的经典难题，难点在于样本之间并不独立、而是存在时序依赖。本文针对有限状态和可数无限状态两种情形，分别在算子无穷范数和由全变差（total variation）导出的逐元范数下，精确刻画了这一估计问题的极小化极大（minimax）样本复杂度。核心发现是：所需序列长度由链的混合性质（mixing properties）主导——具体体现在伪谱间隙（pseudo-spectral gap）和混合时间（mixing time）上——而这些量恰好可以从同一条观测序列中以数据驱动的方式估计出来，并附带有限样本置信区间。在有限状态情形，文章给出了上下界均匹配（至多相差对数因子）的首个完整极小化极大刻画，证明估计整个转移矩阵与估计伪谱间隙本质上同样困难；这一结果对实践中依赖单条轨迹推断马尔可夫链参数的场景具有重要的理论指导价值。
原文 arXiv:1809.05014;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1809.05014v6