Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Space
This work addresses a fundamental statistical estimation problem for researchers in probability theory and machine learning, providing theoretical bounds that are incremental to existing literature on Markov chain analysis.
The paper tackles the problem of estimating the transition kernel of an ergodic Markov chain from a single long sequence of observations, characterizing the minimax sample complexity in terms of mixing properties for both finite and countably infinite state spaces, with results including logarithmic factors and entry-wise norms.
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.