Lune

NeurIPS2021Top-tier venue

Optimal prediction of Markov chains with and without spectral gap

Yanjun Han, Soham Jana, Yihong Wu

Abstract

We study the following learning problem with dependent data: Observing a trajectory of length <inline-formula> <tex-math notation="LaTeX">nn </tex-math></inline-formula> from a stationary Markov chain with <inline-formula> <tex-math notation="LaTeX">kk </tex-math></inline-formula> states, the goal is to predict the next state. For <inline-formula> <tex-math notation="LaTeX">3≤k≤O(n)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">Θ(k2nlog⁡nk2)\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">Θ(log⁡log⁡nn)\Theta \left({\frac {\log \log n}{n}}\right) </tex-math></inline-formula> for <inline-formula> <tex-math notation="LaTeX">k=2k=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(k2n)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(k2n)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.

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. An Analysis of Tokenization: Transformers under Markov DataNived Rajaraman, Jiantao Jiao, Kannan RamchandranNeurIPS 2024 · 16 citations
  2. Learning In-context n-grams with Transformers: Sub-n-grams Are Near-Stationary PointsAditya Varre, Gizem Yüce, Nicolas FlammarionICML 2025

Related papers

  1. Learning with little mixingIngvar M. Ziemann, Stephen TuNeurIPS 2022 · 41 citations
  2. How to Store a Random WalkEmanuele Viola, Omri Weinstein, Huacheng YuSODA 2020 · 4 citations
  3. 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
  4. Regularized Modal Regression on Markov-Dependent Observations: A Theoretical AssessmentTieliang Gong, Yuxin Dong, Hong Chen, Wei Feng et al.AAAI 2022 · 1 citation
  5. Online Prediction of Stochastic Sequences with High Probability Regret BoundsMatthias Frey, Jonathan H. Manton, Jingge ZhuICLR 2026
Dusk over the sea between two cliffs drawn in fine vertical lines