Statistical Estimation of Ergodic Markov Chain Kernel over Discrete
  State Space
  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.
