Optimal prediction of Markov chains with and without spectral gap

We study the following learning problem with dependent data: Observing a trajectory of length <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> from a stationary Markov chain with <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> states, the goal is to predict the next state. For <inline-formula> <tex-math notation="LaTeX">$3 \leq k \leq O(\sqrt {n})$ </tex-math></inline-formula>, using techniques from universal compression, the optimal prediction risk in Kullback-Leibler divergence is shown to be <inline-formula> <tex-math notation="LaTeX">$\Theta \left({\frac {k^{2}}{n}\log \frac {n}{k^{2}}}\right)$ </tex-math></inline-formula>, in contrast to the optimal rate of <inline-formula> <tex-math notation="LaTeX">$\Theta \left({\frac {\log \log n}{n}}\right)$ </tex-math></inline-formula> for <inline-formula> <tex-math notation="LaTeX">$k=2$ </tex-math></inline-formula> previously shown in Falahatgar et al. (2016). These rates, slower than the parametric rate of <inline-formula> <tex-math notation="LaTeX">$O\left({\frac {k^{2}}{n}}\right)$ </tex-math></inline-formula>, can be attributed to the memory in the data, as the spectral gap of the Markov chain can be arbitrarily small. To quantify the memory effect, we study irreducible reversible chains with a prescribed spectral gap. In addition to characterizing the optimal prediction risk for two states, we show that, as long as the spectral gap is not excessively small, the prediction risk in the Markov model is <inline-formula> <tex-math notation="LaTeX">$O\left({\frac {k^{2}}{n}}\right)$ </tex-math></inline-formula>, which coincides with that of an iid model with the same number of parameters. Extensions to higher-order Markov chains are also obtained.