Abstract

We compute the finite-sample minimax (modulo logarithmic factors) samplecomplexity of learning the parameters of a finite Markov chain from a singlelong sequence of states. Our error metric is a natural variant of totalvariation. The sample complexity necessarily depends on the spectral gap andminimal stationary probability of the unknown chain - for which, at least inthe reversible case, there are known finite-sample estimators with fullyempirical confidence intervals. To our knowledge, this is the first PAC-typeresult with nearly matching (up to logs) upper and lower bounds for learning,in any metric in the context of Markov chains.

 

Quick Read (beta)