Optimal prediction of Markov chains with and without spectral gap
Abstract
We study the following learning problem with dependent data: Observing a trajectory of length <inline-formula> <tex-math notation="LaTeX"> </tex-math></inline-formula> from a stationary Markov chain with <inline-formula> <tex-math notation="LaTeX"> </tex-math></inline-formula> states, the goal is to predict the next state. For <inline-formula> <tex-math notation="LaTeX"> </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"> </tex-math></inline-formula>, in contrast to the optimal rate of <inline-formula> <tex-math notation="LaTeX"> </tex-math></inline-formula> for <inline-formula> <tex-math notation="LaTeX"> </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"> </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"> </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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
Related papers
- Learning with little mixingIngvar M. Ziemann, Stephen TuNeurIPS 2022 · 41 citations
- How to Store a Random WalkEmanuele Viola, Omri Weinstein, Huacheng YuSODA 2020 · 4 citations
- Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert SpacesVladimir Kostic, Pietro Novelli, Andreas Maurer, Carlo Ciliberto et al.NeurIPS 2022 · 109 citations
- Regularized Modal Regression on Markov-Dependent Observations: A Theoretical AssessmentTieliang Gong, Yuxin Dong, Hong Chen, Wei Feng et al.AAAI 2022 · 1 citation
- Online Prediction of Stochastic Sequences with High Probability Regret BoundsMatthias Frey, Jonathan H. Manton, Jingge ZhuICLR 2026
