Optimal prediction of Markov chains with and without spectral gap conditions
Year: 2021

Abstract:
We study the following learning problem with dependent data: Observing a trajectory of length n from a stationary Markov chain with k states, the goal is to predict the next state. For 3 ≤ k ≤ O( √ n), using techniques from universal compression, the optimal prediction risk in Kullback-Leibler divergence is shown to be Θ( 2 n log n k2 ), in contrast to the optimal rate of Θ( log logn n ) for k = 2 previously shown in [FOPS16]. These rates, slower than the parametric rate of O( 2 n ), 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 O( 2 n ), which coincides with that of an iid model with the same number of parameters.

text: We study the following learning problem with dependent data: Observing a trajectory of length n from a stationary Markov chain with k states, the goal is to predict the next state. For 3 ≤ k ≤ O( √ n), using techniques from universal compression, the optimal prediction risk in Kullback-Leibler divergence is shown to be Θ(k 2
n log n k2 ), in contrast to the optimal rate of Θ( log logn n ) for k = 2 previ-
ously shown in [FOPS16]. These rates, slower than the parametric rate of O(k 2
n ), 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 O(k 2
n ), which coincides with that of an iid model with the same number of parameters.

heading: 1 Introduction
text: Learning distributions from samples is a central question in statistics and machine learning. While significant progress has been achieved in property testing and estimation based on independent and identically distributed (iid) data, for many applications, most notably natural language processing, two new challenges arise: (a) Modeling data as independent observations fails to capture their temporal dependency; (b) Distributions are commonly supported on a large domain whose cardinality is comparable to or even exceeds the sample size. Continuing the progress made in [FOPS16, HOP18], in this paper we study the following prediction problem with dependent data modeled as Markov chains.
Suppose X1, X2, . . . is a stationary first-order Markov chain on state space [k] ≜ {1, . . . , k} with unknown statistics. Observing a trajectory Xn ≜ (X1, . . . , Xn), the goal is to predict the next state Xn+1 by estimating its distribution conditioned on the present data. We use the KullbackLeibler (KL) divergence as the loss function: For distributions P = [p1, . . . , pk] , Q = [q1, . . . , qk], D(P∥Q) = ∑k i=1 pi log pi qi if pi = 0 whenever qi = 0 and D(P∥Q) = ∞ otherwise. The minimax
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
prediction risk is given by
Riskk,n ≜ inf M̂ sup π,M E[D(M(·|Xn)∥M̂(·|Xn))] = inf M̂ sup π,M k∑ i=1 E[D(M(·|i)∥M̂(·|i))1{Xn=i}] (1)
where the supremum is taken over all stationary distributions π and transition matrices M (rowstochastic) such that πM = π, the infimum is taken over all estimators M̂ = M̂(X1, . . . , Xn) that are proper Markov kernels (i.e. rows sum to 1), and M(·|i) denotes the ith row of M . Our main objective is to characterize this minimax risk within universal constant factors as a function of n and k.
The prediction problem (1) is distinct from the parameter estimation problem such as estimating the transition matrix [Bar51, AG57, Bil61, WK19] or its properties [CS00, KV16, HJL+18, HKL+19] in that the quantity to be estimated (conditional distribution of the next state) depends on the sample path itself. This is precisely what renders the prediction problem closely relevant to natural applications such as autocomplete and text generation. In addition, this formulation allows more flexibility with far less assumptions compared to the estimation framework. For example, if certain state has very small probability under the stationary distribution, consistent estimation of the transition matrix with respect to usual loss function, e.g. squared risk, may not be possible, whereas the prediction problem is unencumbered by such rare states.
In the special case of iid data, the prediction problem reduces to estimating the distribution in KL divergence. In this setting the optimal risk is well understood, which is known to be k−12n (1 + o(1)) when k is fixed and n → ∞ [BFSS02] and Θ( kn ) for k = O(n) [Pan04, KOPS15].
1 Typical in parametric models, this rate kn is commonly referred to the “parametric rate”, which leads to a sample complexity that scales proportionally to the number of parameters and inverse proportionally to the desired accuracy.
In the setting of Markov chains, however, the prediction problem is much less understood especially for large state space. Recently the seminal work [FOPS16] showed the surprising result that for stationary Markov chains on two states, the optimal prediction risk satisfies
Risk2,n = Θ
( log log n
n
) , (2)
which has a nonparametric rate even when the problem has only two parameters. The follow-up work [HOP18] studied general k-state chains and showed a lower bound of Ω(k log lognn ) for uniform (not necessarily stationary) initial distribution; however, the upper bound O(k 2 log logn
n ) in [HOP18] relies on implicit assumptions on mixing time such as spectral gap conditions: the proof of the upper bound for prediction (Lemma 7 in the supplement) and for estimation (Lemma 17 of the supplement) is based on Berstein-type concentration results of the empirical transition counts, which depend on spectral gap. The following theorem resolves the optimal risk for k-state Markov chains:
Theorem 1 (Optimal rates without spectral gap). There exists a universal constant C > 0 such that for all 3 ≤ k ≤ √ n/C,
k2 Cn log ( n k2 ) ≤ Riskk,n ≤ Ck2 n log ( n k2 ) . (3)
Furthermore, the lower bound continues to hold even if the Markov chain is restricted to be irreducible and reversible.
Remark 1. The optimal prediction risk of O(k 2
n log n k2 ) can be achieved by an average version of
the add-one estimator (i.e. Laplace’s rule of succession). Given a trajectory xn = (x1, . . . , xn) of length n, denote the transition counts (with the convention Ni ≡ Nij ≡ 0 if n = 0, 1)
Ni = n−1∑ ℓ=1 1{xℓ=i}, Nij = n−1∑ ℓ=1 1{xℓ=i,xℓ+1=j}. (4)
1Here and below ≍,≲,≳ or Θ(·), O(·),Ω(·) denote equality and inequalities up to universal multiplicative constants.
The add-one estimator for the transition probability M(j|i) is given by
M̂+1xn (j|i) ≜ Nij + 1
Ni + k , (5)
which is an additively smoothed version of the empirical frequency. Finally, the optimal rate in (3) can be achieved by the following estimator M̂ defined as an average of add-one estimators over different sample sizes:
M̂xn(xn+1|xn) ≜ 1
n n∑ t=1 M̂+1xnn−t+1 (xn+1|xn). (6)
In other words, we apply the add-one estimator to the most recent t observations (Xn−t+1, . . . , Xn) to predict the next Xn+1, then average over t = 1, . . . , n. Such Cesàro-mean-type estimators have been introduced before in the density estimation literature (see, e.g., [YB99]). It remains open whether the usual add-one estimator (namely, the last term in (6) which uses all the data) or any add-c estimator for constant c achieves the optimal rate. In contrast, for two-state chains the optimal risk (2) is attained by a hybrid strategy [FOPS16], applying add-c estimator for c = 1logn for trajectories with at most one transition and c = 1 otherwise. Also note that the estimator in (6) can be computed in O(nk) time. To derive this first note that given any j ∈ [k] calculating M̂+1
xn−11 (j|xn−1) takes O(n)
time and given any M+1 xn−1n−t+1 (j|xn−1) we need O(1) time to calculate M̂+1xn−1n−t+2 (j|xn−1). Summing over all j we get the algorithmic complexity upper bound.
Theorem 1 shows that the departure from the parametric rate of k 2
n , first discovered in [FOPS16, HOP18] for binary chains, is even more pronounced for larger state space. As will become clear in the proof, there is some fundamental difference between two-state and three-state chains, resulting in Risk3,n = Θ( logn n ) ≫ Risk2,n = Θ( log logn n ). It is instructive to compare the sample complexity for prediction in the iid and Markov model. Denote by d the number of parameters, which is k − 1 for the iid case and k(k − 1) for Markov chains. Define the sample complexity n∗(d, ϵ) as the smallest sample size n in order to achieve a prescribed prediction risk ϵ. For ϵ = O(1), we have
n∗(d, ϵ) ≍  d ϵ iid d ϵ log log 1 ϵ Markov with 2 states
d ϵ log 1 ϵ Markov with k ≥ 3 states.
(7)
At a high level, the nonparametric rates in the Markov model can be attributed to the memory in the data. On the one hand, Theorem 1 as well as (2) affirm that one can obtain meaningful prediction without imposing any mixing conditions;2 such decoupling between learning and mixing has also been observed in other problems such as learning linear dynamics [SMT+18, DMM+19]. On the other hand, the dependency in the data does lead to a strictly higher sample complexity than that of the iid case; in fact, the lower bound in Theorem 1 is proved by constructing chains with spectral gap as small as O( 1n ) (see Section 3). Thus, it is conceivable that with sufficiently favorable mixing conditions, the prediction risk improves over that of the worst case and, at some point, reaches the parametric rate. To make this precise, we focus on Markov chains with a prescribed spectral gap.
It is well-known that for an irreducible and reversible chain, the transition matrix M has k real eigenvalues satisfying 1 = λ1 ≥ λ2 ≥ . . . λk ≥ −1. The absolute spectral gap of M , defined as
γ∗ ≜ 1−max {|λi| : i ̸= 1} , (8)
quantifies the memory of the Markov chain. For example, the mixing time is determined by 1/γ∗ (relaxation time) up to logarithmic factors. As extreme cases, the chain which does not move (M is identity) and which is iid (M is rank-one) have spectral gap equal to 0 and 1, respectively. We refer the reader to [LP17] for more background. Note that the definition of absolute spectral gap requires irreducibility and reversibility, thus we restrict ourselves to this class of Markov chains (it is possible to use more general notions such as pseudo spectral gap to quantify the memory of the
2To see this, it is helpful to consider the extreme case where the chain does not move at all or is periodic, in which case predicting the next state is in fact easy.
process, which is beyond the scope of the current paper). Given γ0 ∈ (0, 1), define Mk(γ0) as the set of transition matrices corresponding to irreducible and reversible chains whose absolute spectral gap exceeds γ0. Restricting (1) to this subcollection and noticing the stationary distribution here is uniquely determined by M , we define the corresponding minimax risk:
Riskk,n(γ0) ≜ inf M̂ sup M∈Mk(γ0)
E [ D(M(·|Xn)∥M̂(·|Xn)) ] (9)
Extending the result (2) of [FOPS16], the following theorem characterizes the optimal prediction risk for two-state chains with prescribed spectral gaps (the case γ0 = 0 correspond to the minimax rate in [FOPS16] over all binary Markov chains): Theorem 2 (Spectral gap dependent rates for binary chain). For any γ0 ∈ (0, 1)
Risk2,n(γ0) ≍ 1
n max
{ 1, log log ( min { n, 1
γ0
})} .
Theorem 2 shows that for binary chains, parametric rate O( 1n ) is achievable if and only if the spectral gap is nonvanishing. While this holds for bounded state space (see Corollary 4 below), for large state space, it turns out that much weaker conditions on the absolute spectral gap suffice to guarantee the parametric rate O(k 2
n ), achieved by the add-one estimator applied to the entire trajectory. In other words, as long as the spectral gap is not excessively small, the prediction risk in the Markov model behaves in the same way as that of an iid model with equal number of parameters. Similar conclusion has been established previously for the sample complexity of estimating the entropy rate of Markov chains in [HJL+18, Theorem 1]. Theorem 3. The add-one estimator in (5) achieves the following risk bound.
(i) For any k ≥ 2, Riskk,n(γ0) ≲ k 2 n provided that γ0 ≳ ( log k k ) 1/4.
(ii) In addition, for k ≳ (log n)6, Riskk,n(γ0) ≲ k 2 n provided that γ0 ≳ (log(n+k))2 k .
Corollary 4. For any fixed k ≥ 2, Riskk,n(γ0) = O( 1n ) if and only if γ0 = Ω(1).

heading: 1.1 Proof techniques
text: The proof of Theorem 1 deviates from existing approaches based on concentration inequalities for Markov chains. For instance, the standard program for analyzing the add-one estimator (5) involves proving concentration of the empirical counts on their population version, namely, Ni ≈ nπi and Nij ≈ nπiM(j|i), and bounding the risk in the atypical case by concentration inequalities, such as the Chernoff-type bounds in [Lez98, Pau15], which have been widely used in recent work on statistical inference with Markov chains [KV16, HJL+18, HOP18, HKL+19, WK19]. However, these concentration inequalities inevitably depends on the spectral gap of the Markov chain, leading to results which deteriorate as the spectral gap becomes smaller. For two-state chains, results free of the spectral gap are obtained in [FOPS16] using explicit joint distribution of the transition counts; this refined analysis, however, is difficult to extend to larger state space as the probability mass function of (Nij) is given by Whittle’s formula [Whi55] which takes an unwieldy determinantal form.
Eschewing concentration-based arguments, the crux of our proof of Theorem 1, for both the upper and lower bound, revolves around the following quantity known as redundancy:
Redk,n ≜ inf QXn sup PXn D(PXn∥QXn) = inf QXn sup PXn ∑ xn PXn(x n) log PXn(x n) QXn(xn) . (10)
Here the supremum is taken over all joint distributions of stationary Markov chains Xn on k states, and the infimum is over all joint distributions QXn . A central quantity which measures the minimax regret in universal compression, the redundancy (10) corresponds to minimax cumulative risk (namely, the total prediction risk when the sample size ranges from 1 to n), while (1) is the individual minimax risk at sample size n – see Section 2 for a detailed discussion. We prove the following reduction between prediction risk and redundancy:
1 n Redsymk−1,n − log k n ≲ Riskk,n ≤ 1 n− 1 Redk,n (11)
where Redsym denotes the redundancy for symmetric Markov chains. The upper bound is standard: thanks to the convexity of the loss function and stationarity of the Markov chain, the risk of the Cesàromean estimator (6) can be upper bounded using the cumulative risk and, in turn, the redundancy. The proof of the lower bound is more involved. Given a (k − 1)-state chain, we embed it into a larger state space by introducing a new state, such that with constant probability, the chain starts from and gets stuck at this state for a period time that is approximately uniform in [n], then enters the original chain. Effectively, this scenario is equivalent to a prediction problem on k − 1 states with a random (approximately uniform) sample size, whose prediction risk can then be related to the cumulative risk and redundancy. This intuition can be made precise by considering a Bayesian setting, in which the (k − 1)-state chain is randomized according to the least favorable prior for (10), and representing the Bayes risk as conditional mutual information and applying the chain rule.
Given the above reduction in (11), it suffices to show both redundancies therein are on the order of k2
n log n k2 . The redundancy is upper bounded by pointwise redundancy, which replaces the average
in (10) by the maximum over all trajectories. Following [DMPW81, CS04], we consider an explicit probability assignment defined by add-one smoothing and using combinatorial arguments to bound the pointwise redundancy, shown optimal by information-theoretic arguments.
The optimal spectral gap-dependent rate in Theorem 2 relies on the key observation in [FOPS16] that, for binary chains, the dominating contribution to the prediction risk comes from trajectories with a single transition, for which we may apply an add-c estimator with c depending appropriately on the spectral gap. The lower bound is shown using a Bayesian argument similar to that of [HOP18, Theorem 1]. The proof of Theorem 3 relies on more delicate concentration arguments as the spectral gap is allowed to be vanishingly small. Notably, for small k, direct application of existing Bernstein inequalities for Markov chains in [Lez98, Pau15] falls short of establishing the parametric rate of O(k 2
n ) (see Remark 4 in Section 7.2 for details); instead, we use a fourth moment bound which turns out to be well suited for analyzing concentration of empirical counts conditional on the terminal state.
For large k, we further improve the spectral gap condition using a simulation argument for Markov chains using independent samples [Bil61, HJL+18]. A key step is a new concentration inequality for D(P∥P̂+1n,k), where P̂ +1 n,k is the add-one estimator based on n iid observations of P supported on [k]:
P ( D(P∥P̂+1n,k) ≥ c · k
n +
polylog(n) · √ k
n
) ≤ 1
poly(n) , (12)
for some absolute constant c > 0. Note that an application of the classical concentration inequality of McDiarmid would result in the second term being polylog(n)/ √ n, and (12) crucially improves this to polylog(n) · √ k/n. Such an improvement has been recently observed by [MJT+20, Agr20, GR20]
in studying the similar quantity D(P̂n∥P ) for the (unsmoothed) empirical distribution P̂n; however, these results, based on either the method of types or an explicit upper bound of the moment generating function, are not directly applicable to (12) in which the true distribution P appears as the first argument in the KL divergence.

heading: 1.2 Related work
text: While the exact prediction problem studied in this paper has recently been in focus since [FOPS16, HOP18], there exists a large body of literature on relate works. As mentioned before some of our proof strategies draws inspiration and results from the study of redundancy in universal compression, its connection to mutual information, as well as the perspective of sequential probability assignment as prediction, dating back to [Dav73, DMPW81, Ris84, Sht87, Rya88]. Asymptotic characterization of the minimax redundancy for Markov sources, both average and pointwise, were obtained in [Dav83, Att99, JS02], in the regime of fixed alphabet size k and large sample size n. Non-asymptotic characterization was obtained in [Dav83] for n ≫ k log2 k and recently extended to n ≍ k2 in [TJW18], which further showed that the behavior of the redundancy remains unchanged even if the Markov chain is very close to being iid in terms of spectral gap γ∗ = 1− o(1). The current paper adds to a growing body of literature devoted to statistical learning with dependent data, in particular those dealing with Markov chains. Estimation of the transition matrix [Bar51, AG57, Bil61, Sin64] and testing the order of Markov chains [CS00] have been well studied in the large-sample regime. More recently attention has been shifted towards large state space and
nonasymptotics. For example, [WK19] studied the estimation of transition matrix in ℓ∞ → ℓ∞ induced norm for Markov chains with prescribed pseudo spectral gap and minimum probability mass of the stationary distribution, and determined sample complexity bounds up to logarithmic factors. Similar results have been obtained for estimating properties of Markov chains, including mixing time and spectral gap [HKL+19], entropy rate [KV16, HJL+18, OS20], graph statistics based on random walk [BHOP18], as well as identity testing [DDG18, CB19, WK20, FW21]. Most of these results rely on assumptions on the Markov chains such as lower bounds on the spectral gap and the stationary distribution, which afford concentration for sample statistics of Markov chains. In contrast, one of the main contributions in this paper, in particular Theorem 1, is that optimal prediction can be achieved without these assumptions, thereby providing a novel way of tackling these seemingly unavoidable issues. This is ultimately accomplished by information-theoretic and combinatorial techniques from universal compression.

heading: 1.3 Notations and preliminaries
text: For n ∈ N, let [n] ≜ {1, . . . , n}. Denote xn = (x1, . . . , xn) and xnt = (xt, . . . , xn). The distribution of a random variable X is denoted by PX . In a Bayesian setting, the distribution of a parameter θ is referred to as a prior, denoted by Pθ. We recall the following definitions from information theory [CK82, CT06]. The conditional KL divergence is defined as as an average of KL divergence between conditional distributions:
D(PA|B∥QA|B |PB) ≜ EB∼PB [D(PA|B∥QA|B)] = ∫ PB(db)D(PA|B=b∥QA|B=b). (13)
The mutual information between random variables A and B with joint distribution PAB is I(A;B) ≜ D(PB|A∥PB |PA); similarly, the conditional mutual information is defined as
I(A;B|C) ≜ D(PB|A,C∥PB|C |PA,C). The following variational representation of (conditional) mutual information is well-known
I(A;B) = min QB D(PB|A∥QB |PA), I(A;B|C) = min QB|C D(PB|A,C∥QB|C |PAC). (14)
The entropy of a discrete random variables X is H(X) ≜ ∑
x PX(x) log 1 PX(x) .
The rest of the paper is organized as follows. In Section 2 we describe the general paradigms of minimax redundancy and prediction risk and their dual representation in terms of mutual information. We give a general redundancy-based bound on the prediction risk, which leads to the upper bound in Theorem 1. Section 3 presents the main idea of the lower bound construction. In the supplement, Section 4 discusses the assumptions and implications of our results and several open problems. Sections 5 and 6 contain the full proof for the upper and lower bound in Theorem 1. Due to space limitations, proofs for spectral-gap dependent risk bounds in Theorems 2 and 3 are given in Section 7.

heading: 2 Two general paradigms

heading: 2.1 Redundancy, prediction risk, and mutual information representation
text: For n ∈ N, let P = {PXn+1|θ : θ ∈ Θ} be a collection of joint distributions parameterized by θ.
“Compression”. Consider a sample Xn ≜ (X1, . . . , Xn) of size n drawn from PXn|θ for some unknown θ ∈ Θ. The redundancy of a probability assignment (joint distribution) QXn is defined as the worst-case KL risk of fitting the joint distribution of Xn, namely
Red(QXn) ≜ sup θ∈Θ D(PXn|θ∥QXn). (15)
Optimizing over QXn , the minimax redundancy is defined as
Redn ≜ inf QXn Redn(QXn), (16)
where the infimum is over all joint distribution QXn . This quantity can be operationalized as the redundancy (i.e. regret) in the setting of universal data compression, that is, the excess number of bits compared to the optimal compressor of Xn that knows θ [CT06, Chapter 13].
The capacity-redundancy theorem (see [Kem74] for a very general result) provides the following mutual information characterization of (16):
Redn = sup Pθ
I(θ;Xn), (17)
where the supremum is over all distributions (priors) Pθ on Θ. In view of the variational representation (14), this result can be interpreted as a minimax theorem:
Redn = inf QXn sup Pθ D(PXn|θ∥QXn |Pθ) = sup Pθ inf QXn D(PXn|θ∥QXn |Pθ).
Typically, for fixed model size and n → ∞, one expects that Redn = d2 log n(1+o(1), where d is the number of parameters; see [Ris84] for a general theory of this type. Indeed, on a fixed alphabet of size k, we have Redn = k−12 log n(1+o(1)) for iid model [Dav73] and Redn = km(k−1) 2 log n(1+o(1)) for m-order Markov models [Tro74], with more refined asymptotics shown in [XB97, SW12]. For large alphabets, nonasymptotic results have also been obtained. For example, for first-order Markov model, Redn ≍ k2 log nk2 provided that n ≳ k 2 [Dav83, TJW18].
“Prediction”. Consider the problem of predicting the next unseen data point Xn+1 based on the observations X1, . . . , Xn, where (X1, . . . , Xn+1) are jointly distributed as PXn+1|θ for some unknown θ ∈ Θ. Here, an estimator is a distribution (for Xn+1) as a function of Xn, which, in turn, can be written as a conditional distribution QXn+1|Xn . As such, its worst-case average risk is
Risk(QXn+1|Xn) ≜ sup θ∈Θ D(PXn+1|Xn,θ∥QXn+1|Xn |PXn|θ), (18)
where the conditional KL divergence is defined in (13). The minimax prediction risk is then defined as
Riskn ≜ inf QXn+1|Xn Risk(QXn+1|Xn), (19)
While (16) does not directly correspond to a statistical estimation problem, (19) is exactly the familiar setting of “density estimation”, where QXn+1|Xn is understood as an estimator for the distribution of the unseen Xn+1 based on the available data X1, . . . , Xn.
In the Bayesian setting where θ is drawn from a prior Pθ, the Bayes prediction risk coincides with the conditional mutual information as a consequence of the variational representation (14):
inf QXn+1|Xn
Eθ[D(PXn+1|Xn,θ∥QXn+1|Xn |PXn|θ)] = I(θ;Xn+1|X n). (20)
Furthermore, the Bayes estimator that achieves this infimum takes the following form:
QBayesXn+1|Xn = PXn+1|Xn =
∫ Θ PXn+1|θ dPθ∫
Θ PXn|θ dPθ
, (21)
known as the Bayes predictive density [Dav73, LB04]. These representations play a crucial role in the lower bound proof of Theorem 1. Under appropriate conditions which hold for Markov models (see Lemma 19 in Appendix A), the minimax prediction risk (19) also admits a dual representation analogous to (17):
Riskn = sup θ∼π
I(θ;Xn+1|Xn), (22)
which, in view of (20), show that the principle of “minimax=worst-case Bayes” continues to hold for prediction problem in Markov models.
The following result (proved in Section 5) relates the redundancy and the prediction risk. Lemma 5. For any model P ,
Redn ≤ n−1∑ t=0 Riskt. (23)
In addition, suppose that each PXn|θ ∈ P is stationary and mth-order Markov. Then for all n ≥ m+ 1,
Riskn ≤ Riskn−1 ≤ Redn n−m . (24)
Furthermore, for any joint distribution QXn factorizing as QXn = ∏n
t=1 QXt|Xt−1 , the prediction risk of the estimator
Q̃Xn|Xn−1(xn|x n−1) ≜
1
n−m n∑ t=m+1 QXt|Xt−1(xn|x n−1 n−t+1) (25)
is bounded by the redundancy of QXn as
Risk(Q̃Xn|Xn−1) ≤ 1
n−m Red(QXn). (26)
Remark 2. Note that the upper bound (23) on redundancy, known as the “estimation-compression inequality” [KOPS15, FOPS16], holds without conditions, while the lower bound (24) relies on stationarity and Markovity. For iid data, the estimation-compression inequality is almost an equality; however, this is not the case for Markov chains, as both sides of (23) differ by an unbounded factor of Θ(log log n) for k = 2 and Θ(log n) for fixed k ≥ 3 – see (2) and Theorem 1. On the other hand, Markov chains with at least three states offers a rare instance where (24) is tight, namely, Riskn ≍ Rednn (cf. Lemma 6).

heading: 2.2 Proof of the upper bound part of Theorem 1
text: Specializing to first-order stationary Markov chains with k states, we denote the redundancy and prediction risk in (16) and (19) by Redk,n and Riskk,n, the latter of which is precisely the quantity previously defined in (1). Applying Lemma 5 yields Riskk,n ≤ 1n−1Redk,n. To upper bound Redk,n, consider the following probability assignment:
Q(x1, · · · , xn) = 1
k n−1∏ t=1 M̂+1xt (xt+1|xt) (27)
where M̂+1 is the add-one estimator defined in (5). This Q factorizes as Q(x1) = 1k and Q(xt+1|xt) = M̂+1xt (xt+1|xt). The following lemma (proved in Section 5.2) bounds the redundancy of Q:
Lemma 6. Red(Q) ≤ k(k − 1) [ log ( 1 + n−1k(k−1) ) + 1 ] + log k.
Combined with Lemma 5, Lemma 6 shows that Riskk,n ≤ C k 2 n log n k2 for all k ≤
√ n/C and some
universal constant C, achieved by the estimator (6), which is obtained by applying the rule (25) to (27).

heading: 3 Optimal rates without spectral gap
text: In this section, we sketch the proof of the lower bound part of Theorem 1, which shows the optimality of the average version of the add-one estimator (25). We first describe the lower bound construction for three-state chains, which is subsequently extended to k states.
3.1 Warmup: an Ω( lognn ) lower bound for three-state chains
Theorem 7. Risk3,n = Ω ( logn n ) .
To show Theorem 7, consider the following one-parameter family of transition matrices:
M = Mp = 1− 2n 1n 1n1 n 1− 1 n − p p
1 n p 1− 1 n − p
 : 0 ≤ p ≤ 1− 1 n  . (28) Note that each transition matrix in M is symmetric (hence doubly stochastic), whose corresponding chain is reversible with a uniform stationary distribution and spectral gap Θ( 1n ); see Fig. 1.
The proof of Theorem 7 is given in Section 6.1 using a Bayesian argument. The main idea is as follows. Notice that by design, with constant probability, the trajectory is of the following form: The chain starts and stays at state 1 for t steps, and then transitions into state 2 or 3 and never returns to state 1, where t = 1, . . . , n−1. Since p is the single unknown parameter, the only useful observations are visits to state 2 and 3 and each visit entails one observation about p by flipping a coin with bias roughly p. Thus the effective sample size for estimating p is n− t− 1 and we expect the best estimation error is of the order of 1n−t . However, t is not fixed. In fact, conditioned on the trajectory is of this form, t is roughly uniformly distributed between 1 and n− 1. As such, we anticipate the estimation error of p is approximately
1
n− 1 n−1∑ i=1 1 n− t = Θ ( log n n ) .
Intuitively speaking, the construction in Fig. 1 “embeds” a symmetric two-state chain (with states 2 and 3) with unknown parameter p into a space of three states, by adding a “nuisance” state 1, which effectively slows down the exploration of the useful part of the state space, so that in a trajectory of length n, the effective number of observations we get to make about p is roughly uniformly distributed between 1 and n. This explains the extra log factor in Theorem 7, which actually stems from the harmonic sum in E[ 1Uniform([n]) ]. We will fully explore this embedding idea in Section 3.2 to deal with larger state space.
3.2 k-state chains
The above lower bound construction for 3-state chains can be generalized to k-state chains with k ≥ 3. The high-level argument is again to augment a (k − 1)-state chain into a k-state chain. Specifically, we partition the state space [k] into two sets S1 = {1} and S2 = {2, 3, · · · , k}. Consider a k-state Markov chain such that the transition probabilities from S1 to S2, and from S2 to S1, are both very small (on the order of Θ(1/n)). At state 1, the chain either stays at 1 with probability 1 − 1/n or moves to one of the states in S2 with equal probability 1n(k−1) ; at each state in S2, the chain moves to 1 with probability 1n ; otherwise, within the state subspace S2, the chain evolves according to some symmetric transition matrix T . See Fig. 2 in Section 6.2 for the precise transition diagram.
The key feature of such a chain is as follows. Let Xt be the event that X1, X2, · · · , Xt ∈ S1 and Xt+1, · · · , Xn ∈ S2. For each t ∈ [n − 1], one can show that P(Xt) ≥ c/n for some absolute constant c > 0. Moreover, conditioned on the event Xt, (Xt+1, . . . , Xn) is equal in law to a stationary Markov chain (Y1, · · · , Yn−t) on state space S2 with symmetric transition matrix T . It is not hard to show that estimating M and T are nearly equivalent. Consider the Bayesian setting where T is drawn from some prior. We have
inf M̂
ET [ E[D(M(·|Xn)∥M̂(·|Xn))|Xt] ] ≈ inf T̂ ET [ E[D(T (·|Yn−t)∥T̂ (·|Yn−t))] ] = I(T ;Yn−t+1|Y n−t),
where the last equality follows from the representation (20) of Bayes prediction risk as conditional mutual information. Lower bounding the minimax risk by the Bayes risk, we have
Riskk,n ≥ inf M̂
ET [ E[D(M(·|Xn)∥M̂(·|Xn))] ] ≥ inf
M̂ n−1∑ t=1 EM [ E[D(M(·|Xn)∥M̂(·|Xn))|Xt] · P(Xt) ] ≥ c
n · n−1∑ t=1 inf M̂ EM [ E[D(M(·|Xn)∥M̂(·|Xn))|Xt] ] ≈ c
n · n−1∑ t=1 I(T ;Yn−t+1|Y n−t) = c n · (I(T ;Y n)− I(T ;Y1)). (29)
Note that I(T ;Y1) ≤ H(Y1) ≤ log(k−1) since Y1 takes values in S2. Maximizing the right hand side over the prior PT and recalling the dual representation for redundancy in (17), the above inequality (29) leads to a risk lower bound of Riskk,n ≳ 1n (Red sym k−1,n− log k), where Red sym k−1,n = sup I(T ;Y1) is the redundancy for symmetric Markov chains with k− 1 states and sample size n. Since symmetric transition matrices still have Θ(k2) degrees of freedom, it is expected that Redsymk,n ≍ k2 log n k2 for n ≳ k2, so that (29) yields the desired lower bound Riskk,n = Ω(k 2 n log n k2 ) in Theorem 1. The rigorous proof is carried out in Section 6.2.

heading: Acknowledgment
text: Y. Wu is supported in part by NSF Grant CCF-1900507, an NSF CAREER award CCF-1651588, and an Alfred Sloan fellowship.

Review summaries:
From a single trajectory of $n$ observations drawn from a Markov chain over $k$ different states, we are interested in predicting the next one. For some notion of risk they define, the authors prove that when $k \geq 3$, the rate is of the order $\Theta((k^2/n) \log (n/k))$. In particular, this shows the surprising fact that this rate has a different (worse) dependence in $n$ than chains over $k = 2$ states, known to be $\Theta((1/n)\log \log n)$. Furthermore, they analyze the minimax problem over the set of chains whose spectral gap is controlled from below, and show that under favorable (quantified) mixing conditions, one even recovers the "iid parametric" rate $\Theta(k^2/n)$.