Optimal prediction of Markov chains with and without spectral gap
Authors: Yanjun Han
Soham Jana
Yihong Wu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Markov chains
prediction
redundancy
spectral gap
mixing time
Kullback Leibler risk

Abstract: We study the following learning problem with dependent data: Given a trajectory of length $n$ from a stationary Markov chain with $k$ states, the goal is to predict the distribution of the next state. For $3 \leq k \leq O(\sqrt{n})$, the optimal prediction risk in the Kullback-Leibler divergence is shown to be $\Theta(\frac{k^2}{n}\log \frac{n}{k^2})$, in contrast to the optimal rate of $\Theta(\frac{\log \log n}{n})$ for $k=2$ previously shown in Falahatgar et al in 2016. These nonparametric rates 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(\frac{k^2}{n})$, which coincides with that of an iid model with the same number of parameters. 

Optimal prediction of Markov chains with and without spectral gap conditions
Yanjun Han
Soham Jana
Simons Institute for the Theory of Computing University of California, Berkeley
Department of Statistics and Data Science Yale University
Berkeley, CA 94720 y yjannberkelley edu
New Haven, CT 06520 s janamyala.aaeeeeeaa edu
Yihong Wu
Department of Statistics and Data Science Yale University
New Haven, CT 06520 yihong. wu@yale. edu edu
Abstract
We study the following learning problem with dependent data: Observing a tra- jectory of length n from a stationary Markov chain with A states, the goal is to predict the next state. For 3 S k S O(yn), using techniques from universal compression, the optimal prediction risk in Kullback-
divergence is shown
be O log F ), in contrast the optimal rate of O log log for k 2 previ-
ously shown in [FOPS16]. These rates, slower than the parametric rate of O K2 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, show that, long the spectral gap is not excessively small, the prediction risk in the Markov model O k" ), which coincides with that of an iid model with the same number of parameters.
Introduction
Learning distributions from samples is central question in statistics and machine learning. While significant progress has been achieved in property testing and estimation based on independent and identically distributed (jid) 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
commonly supported a large domain whose cardinality is comparable to or even exceeds the sample size. Continuing the progress made [FOPS16, HOP18], in this paper study the following prediction problem with dependent data modeled as Markov chains.
Suppose X1, X2,... is stationary first-order Markov chain state space [k]] (1...., k} with unknown statistics. Observing trajectory X" á (XI...., Xn). the goal is to predict the next state X by estimating its distribution conditioned on the present data. We use the Kullback- Iq1.... 9x). D(PIIQ) Σ p: log Pi if p: whenever q: and D(P = otherwise. The minimax
Leibler (KL) divergence the loss function: For distributions P [p....., .Pi.....Pll pk]
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

prediction risk is given by
Riskg, & inf sup (I E
inf sup
(D(MM( (x.=)) (1)
M a.
M R.M
where the supremum is taken over all stationary distributions л and transition matrices M (row- stochastic) such that TM = π, the infimum is taken over all estimators M = M, that proper Markov kernels (i.e. rows sum to 1), and (-]o) denotes the ith row of M. Our main objective is to characterize this minimax risk within universal constant factors as function of n and k.
The prediction problem (1) is distinct from the parameter estimation problem such as estimating the transition matrix [Bar51, AG57, Bi161, 1K1 or its properties [CS00, KV16, HJI++ 1K] 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 the estimation framework. For example, if certain state has very small probability under the stationary distribution, consistent estimation of the transition matrix with respect 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 estimating the distribution in KL. divergence. In this setting the optimal risk is well understood, which is known to be k-1 (1 + o(1)) when l is fixed and n oo [BFSS02] and ( for k: On)) [Pan04, KOPS15). Typical in parametric models, this rate is commonly referred to the "parametric rate", which leads to a sample
2n
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 two states, the optimal prediction risk satisfies
log log
Riskg,n θ
(2)
n2
which has nonparametric even when the problem has only two parameters. The follow-up work [HOP18] studied general s-state chains and showed lower bound of 12( k log logn) for uniform
(not necessarily stationary) initial distribution; however, the upper bound O 1.2 log log in [HOP18] relies on implicit assumptions on mixing time such as spectral gap conditions: the proof of the upper bound for prediction (Lemma 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 (Optimal rates without spectral gap). There exists universal constant C > 0 such that for all 3 < k < Vn/C,
222 Cn
Ck2
log
Riske.n
log
(3)
1.2
Furthermore, the lower bound continues to hold even if the Markov chain restricted to be irreducible and reversible.
Remark 1. The optimal prediction risk of O log ) can be achieved by an average version of the add-one estimator (i.e. Laplace's s rule of succession). Given trajectory x. (I,,..., Fn) of length denote the transition counts (with the convention N;- = Núj 0 0,
n-1
N
(a=())
Ny = Σ
(4)
Here and below X, S. 2 or O(-, ((-) denote equality and inequalities up universal multiplicative constants.

---

The add-one estimator for the transition probability M(]() is given by
N + N +
(5)
which is an additively smoothed version of the empirical frequency. Finally, the optimal rate in (3) can achieved by the following estimator M defined as an average of add-one estimators over different sample sizes:
Man (1n+11/5))
A
M 2 (1n+1l1n))
(6)
1=1
In other words, we apply the add-one estimator to the most recent t observations (Xn-c+1:--. X,) to predict the next Xn+1, then average over == I,..., .....,7. 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 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 log for trajectories with at most one transition and c = otherwise. Also note that the estimator in (6) can be computed in (nkk) time. To derive this first note that given any j E [Ac] calculating M (J) (j] takes (n)
#1
time and given any M+1 n- (il=n-1) we need O(1) time to calculate M+1 over all j we get the algorithmic complexity upper bound.
(j 1n)) Summing 2
Theorem 1 shows that the departure from the parametric rate of k2 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., ( log n >> Riskg,n O log log"). ). It is instructive compare the sample complexity for 1 for
prediction in the iid and Markov model. 'Denote by the number of parameters, which 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 e. For O(1), we have
iid Markov with 2 states
n" ed)
x
log log log
Markov with & 2 3 states.
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 can obtain meaningful prediction without imposing any mixing conditions; such decoupling between learning and mixing has also been observed in other problems such learning linear dynamics [SMT+18. 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 is proved by constructing chains with spectral gap as small as ( (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 A real cigenvalues satisfying = t1 Z X2 2 ..... > 2 -1. The absolute spectral gap of M, defined as
1- - max (|Aa1 +
(8)
quantifies the memory of the Markov chain. For example, the mixing time is determined by 1//x* (relaxation time) up 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 possible to use more general notions such as pseudo spectral gap to quantify the memory of the
"To 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.
3

---

process, which is beyond the scope of the current paper). Given "oo (0, 1), define (70) as the set of transition matrices corresponding to irreducible and reversible chains whose absolute spectral gap exceeds To- Restricting (1) to this subcollection and noticing the stationary distribution here is uniquely determined by M, we define the corresponding minimax risk:
Riske, (no) A inf sup M McMa(10)
E (D(M()X)))
Extending the result (2) of [FOPS16], the following theorem characterizes the optimal prediction risk for two-state chains with prescribed spectral gaps (the case Too = 0 correspond to the minimax rate in [FOPS16] over all binary Markov chains):
Theorem (Spectral gap dependent rates for binary chain). For any To E (0. 1)
1 Riskg,n(10) max 1, log log min { n1 To }}
1
Theorem shows that for binary chains, parametric rate ( 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 (² ) achieved by the add-one estimator applied to the entire trajectory. In other words, as long as the spectral gap 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 l].
Theorem 3. The add-one estimator in (5) achieves the following risk bound.
(i) For any & 2 2, Riskg,m(11) S provided that "To Z (logh, /14
(ii) In addition, for ls Z (logn)s, Riska,n S 12t
provided that no Z
(log(n
k
Corollary 4. For any fixed k 2 Riske (70) = -(.)) ) if and only io 121).
1.1 Proof techniques
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, N₂ R nm, and Nij (flū), and bounding the risk in the atypical case by concentration inequalities, such as the Chernoff-type bounds [Lez98, Pau15], which have been widely used in recent work on statistical inference with Markov chains [KV16, HJL+18, 18, HOP18, HKL+19 19, WKI9]. However, these concentration inequalities inevitably depends on the spectral gap of the Markov chain, leading 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, difficult extend larger state space the probability mass function of (Niy) is given by Whittle's 's formula [Whi55] which takes an unwieldy determinantal form.
Eschewing concentration- arguments, the crux of our proof of Theorem 1, for both the upper and lower bound, revolves around the following quantity known as redundancy:
log (x"(x")
Redk,n inf sup D(Px= |xxx inf sup Σ a7
(10)
Qxn Pxn
Qx" Pxp
Qx (27)
Here the supremum is taken over joint distributions of stationary Markov chains X on k states, and the infimuum is over all joint distributions Qx=.. 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 sample size n see Section 2 for a detailed discussion. We prove the following reduction between prediction risk and redundancy:
log k
1
Ryd
Risky, S
Redk.n
(11)
n
n
n

---

where Reda denotes the redundancy for symmetric Markov chains. The upper bound is standard: thanks the convexity of the loss function and stationarity of the Markov chain, the risk of the Cesàro- mean 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 (k - 1)-state chain, we embed it into a larger state space by introducing 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 prediction problem on k -1 states with a random (approximately uniform) sample size, whose prediction risk can then related to the cumulative risk and redundancy. This intuition can be made precise by considering Bayesian setting, in which the (I: - 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 log n in (10) by the maximum over all trajectories. Following [DMPW81, CS04), consider explicit probability assignment defined by add-one smoothing and using combinatorial arguments to bound the pointwise redundancy, shown optimal by intormation-thooreee arguments.
k2 The redundancy is upper bounded by pointwise redundancy, which replaces the average
The optimal spectral gap-dependent rate in Theorem 2 relies on the key observation [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 1J. 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") in (see Remark 4 in Section 7.2 for details); instead, we use fourth moment bound which turns out 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 [Bi161, HJL+18). 18]. A key step is new concentration inequality for D(PII P+1)) where p+1 is the add-one estimator based on n iid observations of P supported on [k]: n,k
P D(P D(P))Pt) n.K 2
A -
polylog(n) Vk
(12)
(nly(n))
for some absolute constant O. Note that an application of the classical concentration inequality of McDiarmid would result in the second term being polylog(n)/ /T, and (12) crucially improves this to polylog(n) Vk/n. Such an improvement has been recently observed by [MJT* 20, Agr20, GR20J in studying the similar quantity D(P..l P) for the (unsmoothed) empirical distribution Pn; 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 the KL divergence.
1.2 Related work
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, At19,, JSO2], in the regime of fixed alphabet size i: and large sample size n. Non-asymptotic characterization was obtained in [Dav83] for >> k log² k and recently extended to x k² 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 7 = 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, Bi161, Sin64] and testing the order of Markov chains [CS00] have been well studied in the sampe regime. More recently attention has been shifted towards large state space and
5

---

nonasymptoties. For example, [WK19] studied the estimation of transition matrix in E0 + loc 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 18, OS20J, graph statistics based on random walk [BHOP 18], as well as identity testing [DDG18, CB19, WK20, FW21J. Most of these results rely assumptions on the Markov chains such as lower bounds the spectral gap and the stationary distribution, which afford concentration for sample statistics of Markov chains. In contrast, one 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 cnermaationthhoreeee and combinatorial techniques from universal compression.
1.3 Notations and preliminaries
For n N, let [n] - [l,..., n.. Denote x" ,..., Wn) and x/² (Zi,,... ,... The distribution of random variable X is denoted by Px. In a Bayesian setting, the distribution of parameter 0 is referred to prior, denoted by Pg. 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:
= /
((P A é EB-Pa (
(13)
The mutual information between random variables A and B with joint distribution PAR is [AA B) (|PP)AllPA PA): similarly, the conditional mutual information is defined as
[(A: B(C) & D(PBJA,C PPcclPAAOO
The following variational representation of (conditional) mutual information is well-known T(A; B) = min D(PB)alQs|PA))
T(A; B(C) QB
min D(PBIAcI(@SIcPPa)) (14)
QB
The entropy of a discrete random variables X is H(X) - Σ. Px(x) Px
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 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 and 3 are given in Section 7.
Two general paradigms
2.1 Redundancy, prediction risk, and mutual information representation
For E N, let (
(Px==1j : 8 E {} be collection of joint distributions parameterized by A.
"Compression". Consider sample X & (X....., Xn) of size n drawn from Px for some unknown 0 θ The redundancy of a probability assignment (joint distribution) Qx defined as the worst-case KL risk of fitting the joint distribution of X", namely
(ex sup D(Px (0lQxx)))
(15)
dee
Optimizing over Qx", the minimax redundancy is defined as
Red,, A inf Redx(Qxx), Qx"
(16)
where the infimum is over all joint distribution Qx.. 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 X that knows 0 [CT06, Chapter 13].

---

The redundanyy theorem (see [Kem74] for very general result) provides the following mutual information characterization of (16): Red,, sup [(0; X"),
(17)
Pg
where the supremum is over all distributions (priors) Po on Q In view of the variational representation (14), this result can interpreted as a minimax theorem:
Red,, inf sup 1=0xx==00xx==1 sup inf D(Px))ol(Xx-1PP))
Qx" Pe
Pg Qx"
Typically, for fixed model size and + oc, one expects that Red, = á no n11 + number of parameters; see [Ris84] for general theory of this type. Indeed, on fixed alphabet of size k, we have Red,, 2 log n1 + (1)) for iid model [Dav73] and Red,, A (k- log n(1 + (1)) for m-order Markov models [Tro74], with more refined asymptotics shown [XB97, SW12J. For large alphabets, nonasymptotic results have also been obtained. For example, for first-order Markov model, Red,, x k2 log Eo provided that n Z [Dav83, TJW18J.
o(1, where is the
k-1
"Prediction". Consider the problem of predicting the next unseen data point X,+1 based the observations X,,..., Xa, where (X1...., Xa+1) are jointly distributed as Px=+110 for some unknown / O Here, estimator is distribution (for Xn+1)
function of X" which, in turn, can be written as conditional distribution Qxa+i|x". As such, its worst-case average risk is
sup D( D( x110x Px= 8): #ge
(18)
where the conditional KL. divergence is defined in (13). The minimax prediction risk is then defined as
Risk, inf
Risk Risk(Qx.+1ix=*))
(19)
Qx,411x"
While (16) does not directly correspond a statistical estimation problem, (19) is exactly the familiar setting of "density estimation", where Qx,, (1 11 is understood as an estimator for the distribution of the unseen X,+1 based on the available data ,,....,
In the Bayesian setting where is drawn from a prior Po, the Bayes prediction risk coincides with consequence of the variational representation (14):
the conditional mutual information
inf Ee[D(Px.. x [x" o110x.... x=1Px=1))] (0:
(20)
Qx 11
Furthermore, the Bayes estimator that achieves this infimum takes the following form:
So Px dPo
Q
Bayes Xa Pxntixx=
(21)
So Px
known the Bayes predictive density [Dav73, LB04]. These representations play crucial role in the lower bound proof Theorem Under appropriate conditions which hold for Markov models (see Lemma 19 in Appendix A), the minimax prediction risk (19) also admits dual representation analogous to (17):
Risk, sup I(0: Xx+1/X")
(22)
0~T
which, in view of (20), show that the principle of "minimax-worst-caas 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.
Red,, Risk..
(23)
In addition, suppose that each Pxajo E P stationary and bh Markov. Then for all
2 m +
Red,,
Risk, Risk, n m
(24)
7

---

Furthermore, for any joint distribution Qx- factorizing as Qx = [Ti= Qx,1x--1, the prediction risk of the estimator
Qx.IX-- (Fn (In|
(25)
m t=m+1
bounded by the redundancy of Qx as
1 Red (ex
Risk Risk(Qx..
(26)
m
Remark 2. Note that the upper bound (23) on redundancy, known as the rssimation-compressioon inequality" [KOPS15, FOPS16], holds without conditions, while the lower bound (24) relies stationarity and Markovity. For iid data, the estimation-comprestiii however, this is not the case for Markov chains, both sides of (23) differ by unbounded factor of (log log for k = 2 and (log n) for fixed A 2 3 - see (2) and Theorem 1. On the other hand, Markov chains with least three states offers a rare instance where (24) tight, namely, Risk, Red,. (cf. Lemma 6).
inequality almost an equality;
2.2 Proof of the upper bound part Theorem
Specializing to first-order stationary Markov chains with ic states, we denote the redundancy and prediction risk (16) and (19) by Red,, n and Riskg, the latter of which is precisely the quantity previously defined in (I). Applying Lemma yields Riske, S n-1 Redk,n. To upper bound Red consider the following probability assignment:
n-1
Q "E Inn)
II t=1
M (1441/2))
(27)
where -1 is the add-one estimator defined in (5). This Q factorizes as ((x1) 1 and Q(1e+ (a=t) M (x14) The following lemma (proved in Section 5.2) bounds the redun- dancy of Q:
&
Lemma 6. Red(Q) S k(k - 1) [log 1 x(k-1)) + 1 + log k.
Combined with Lemma 5, Lemma 6 shows that Riske. < C log Fhr for all k < vn/C and some universal constant C, achieved by the estimator (6), which obtained by applying the rule (25) to (27).
3 Optimal rates without spectral gap
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 state chains, which is subsequently extended to & states.
3.1 Warmup: an 22 loga n
lower bound for three-state chains
Theorem 7. Risks, = log
To show Theorem consider the following one-parameter family of transition matrices:
2
1
M
M
1
P
P
00 p S
1 n
(28)
7
P
P
Note that each transition matrix in M is symmetric (hence doubly stochastic), whose corresponding chain is reversible with uniform stationary distribution and spectral gap O 1 see Fig. 1.

---

1 p
1- 1 p
1 1 n
p
Figure Lower bound construction for three-state chains.
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 for t steps, and then transitions into state 2 or 3 and never returns to state 1, where
1. Since p the single unknown parameter, the only useful observations 1......
are visits to state 2 and and each visit entails one observation about p by flipping a coin with I and we expect the best
bias roughly p. Thus the effective sample size for estimating P estimation error is of the order of z However, / 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 approximately
1 カ-1
log n n2
Intuitively speaking, the construction in Fig. "embeds" a symmetric two-state chain (with states and 3) with unknown parameter p into space of three states, by adding "nuisance" state 1, which effectively slows down the exploration the useful part of the state space, so that in a trajectory of length the effective number of observations between 1 and n.. This explains the extra log factor in Theorem 7, which actually stems from harmonic sum in Ej Uniform([[]]] We will fully explore this embedding idea in Section 3.2 to deal with larger state space.
get to make about is roughly uniformly distributed
3.2
k-state chains
The above lower bound construction for 3-state chains can be generalized k-sstae chains with k > 3. The high-level argument is again to augment a (k: stttte chain into a k-state chain. Specifically, partition the state space [k] into Markov chain such that the transition probabilities from S₁ to S2, and from S. to S₁, are both very small (on the order of (1/n)). At state the chain either stays
sets Si {1) and S2 [2,3, ... k). Consider k-state
with probability 1 1/n or moves to one of the states in S2 with equal probability nęK-1y at each state in S2. the chain moves
to with probability f;; 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 chain is follows. Let X be the event that X1, X2, .x, S1 and Xtt1, X,, E Sy. For each [n - 1). one can show that P(X) constant > Moreover, conditioned Markov chain (Y,.... ,Y, on state space S, 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 drawn from some prior. We have
) 2 c/n for some absolute the event X,, (X ..,),, equal law to stationary
inf Ey XI) M
R in ET (I = I(T; Y (h-++) +

---

where the last equality follows from the representation (20) of Bayes prediction risk conditional mutual information. Lower bounding the minimax risk by the Bayes risk, we have
Ri 2 inf Er
M
EM [ IP(2))
inl Eas
(
M
2
((+ (I(T:Y")
(29)
Note that T(T; Y1) S H(i) S log(k- 1) since Yi takes values S2. Maximizing the right hand side over the prior Pr and recalling the dual representation for redundancy in (17), the above inequality (29) leads to risk lower bound of Riske, Z (Red I,n - log k). where Red = sup (T; Yi) the redundancy for symmetric Markov chains with transition matrices still have (k²)) degrees of freedom, it is expected that Red = h2 log a for
states and sample size n. Since symmetric
g
Z k2, so that (29) yields the desired lower bound Riska,n Ω Ra log [2) in Theorem 1. The rigorous proof is carried out Section 6.2.
Acknowledgment
Wu is supported in part by NSF Grant CCF-1900507, an NSF CAREER award CCF-1651558 and an Alfred Sloan fellowship.
References
[AG57] Theodore W Anderson and Leo Goodman. Statistical inference about Markov chains. The Annals of Mathematical Statistics, pages 89-110, 1957.
[Agr20] Rohit Agrawal. samite concentration of the multinomial in relative entropy. IEEE Transactions on Information Theory, 66(10):6297-636) 2020.
[Ah121] T.D. Ahle. Sharp and simple bounds for the raw moments of the binomial and poisson distributions. 1rXiv:2103.17027, 2021.
[At19]] K. Atteson. The asymptotic redundancy Bayes rules for Markov chains. IEEE Transactions Information Theory, 45(6):2104-21000 1999.
Bar51] Maurice Bartlett. The frequency goodness of fit test for probability chains. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 47, pages
86-95. Cambridge University Press, 1951.
[BFSS02] Dietrich Braess, Jürgen Forster, Tomas Sauer, and Hans U Simon. How achieve minimax expected Kullback-Leibler distance from an unknown finite distribution. In Algorithmic Learning Theory, pages 380-394. Springer, 2002.
[ВHОР18] Anna Ben-Hamou Roberto I Oliveira, and Yuval Peres. Estimating graph parameters via random walks with restarts. In Proceedings of the Twenty-Nind Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1702-1714, SIAM, 2018
[Bi661] Billingsley. Statistical methods in Markov chains. Statistics, pages 12-40, 1961.
The Annals of Matheratical
[CB19] Yeshwanth Cherapanamjeri and Peter I. Bartlett. Testing symmetric Markov chains without hitting. In Conference on Learning Theory, pages 758-785. PMLR, 2019.
10

---

[CK82] Imre Csiszár and János Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, Inc., 1982.
[CS00]
Imre Csiszár and Paul C Shields. The consistency of the BIC Markov order estimator. The Annals of Statistics, 28(6):1001-166 2000.
[CS04] I Csiszár and PC Shields. Information theory and statistics: a tutorial. Foundations and Trends in Communications and Information Theory, 1(4):417-527, 2004.
[CT06] Thomas M. Cover and Joy A. Thomas. Elements of information theory, 2nd Ed. Wiley- Interscience, New York, NY, USA, 2006.
[Dav73] L. Davisson. Universal noiseless coding. IEEE Transactions on Information Theory, (9(6):73-7955, 1973.
[Dav83] L. Davisson. Minimax noiseless universal coding for Markov sources. IEEE Transac- tions on Information Theory, 29(2):21 1983.
(DDG18) Constantinos Daskalakis, Nishanth Dikkala, and Nick Gravin. Testing symmetric Markov chains from a single trajectory. In Conference On Learning Theory, pages 385-409, PMLR, 2018.
[DM 19] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, pages 1-47, 2019.
[DMPW81] L Davisson, R McEliece, M Pursley, and Mark Wallace. Efficient universal noiseless source codes. IEEE Transactions on Information Theory, 27(3):269-279, 1981.
[Fan53] Ky Fan. Minimax theorems. Proceedings of the National Academy of Sciences, 39(1):42- 47, 1953.
[FOPS16] M. Falahatgar, A. Orlitsky, V. Pichapati, and A.T. Suresh. Learning Markov distributions: Does estimation trump compression? In 2016 IEEE International Symposium on Information Theory (ISIT), pages 2689-2693. IEEE, July 2016.
[FW21] Sela Fried and Geoffrey Wolfer. Identity testing of reversible Markov chains. arXiv preprint arXiv:2 2021.
[GR20] F Richard Guo and Thomas S Richardson. Chernoff-tyre type concentration of empirical probabilities in relative entropy. IEEE Transactions on Information Theory, 67(1))549- 558, 2020.
[HJI,+18] Y. Han, J. Jiao, C.Z. Lee, T. Weissman, Wu, and Yu. Entropy rate estimation for Markov chains with large state space. In Advances in Neural Information Processing Systems, pages -999-9792, 2018, 1tXiv:1802.07880
[1KI++19] Daniel Hsu, Aryeh Kontorovich, David A Levin, Yuval Peres, Csaba Szepesvári, and Geoffrey Wolfer. Mixing time estimation reversible Markov chains from a single sample path. Annals of Applied Probability, 29(4):2439-244 2019.
[HOP18] Yi Hao. A. Orlitsky, and V. Pichapati. On learning Markov chains. In Advances in Neural Information Processing Systems, pages 648-657, 2018.
[Jan02] S. Janson. On concentration of probability. Contemporary combinatorics, 10(3):1-9, 2002.
[JS02] Philippe Jacquet and Wojeiech Szpankowski. A combinatorial problem arising in information theory: Precise minimax redundancy for Markov sources. In Mathematics and Computer Science II, pages 311-328. Springer, 2002.
[Kem74] JHB Kemperman. On the Shannon capacity of an arbitrary channel. In Indagationes (Paiccaaacccaeeeceeeeeeeee (Proceedings), volume 77, pages 101-115. North- Holland, 1974.
Mathematicae

---

[KOPS15] S. Kamath, A. Orlitsky, D. Pichapati, and A.T. Suresh. On learning distributions from their samples. In Conference on Learning Theory, pages 1066-1100, June 2015.
[KV16] Sudeep Kamath and Sergio Verdú. Estimation of entropy rate and Rényi entropy rate for Markov chains. In Information Theory (ISIT), 2016 IEEE International Symposium on, pages 685-689. IEEE, 2016.
[Lat97] Rafal Latala. Estimation of moments of sums of independent real random variables. The Annals of Probability, 25(3):1502-1513, 1997.
[LB04] Feng Liang and Andrew Barron. Exact minimax strategies for predictive density estimation, data compression, and model selection. IEEE Transactions Information Theory, 50(11):2708-272) 2004.
[Lez98] Lezaud. Chernoff-type bound for finite Markov chains. Annals of Applied Probability, 8(3):849-885) 867, 1998.
[LP17] D.A. Levin and Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[0] Jay Mardia, Jiantao Jiao, Ervin Tánczos, Robert D Nowak, and Tsachy Weissman. Concentration inequalities for the empirical distribution of discrete distributions: beyond the method of types. Information and Inference: A Journal of the IMA, 9(4):8 13-880, 2020.
[OS20] Maciej Obremski and Maciej Skorski. Complexity of estimating Rényi entropy of Markov chains. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2264-2269, 2020.
[Pan04] Liam Paninski. Variational minimax estimation of discrete distributions under KL loss. Advances Neurul Information Processing Systems, 17:1033-1040, 2004.
[Pau15] D. Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probubility, pages 1-20, 2015.
[Ris84] Jorma Rissanen. Universal coding, information, prediction, and estimation. IEEE Transactions on Information theory, 30(4):629 636, 1984.
[Rya88] B.Y. Ryabko. Prediction of random sequences and universal coding. Prob. Pered. Inf., 24(2):87-96, 1988.
[Sht87] Yuri M Shtarkov. Universal sequential coding of single messages. Prob. Pered. Inf., 23:175-186, 1987.
[Sin64] Richard Sinkhorn. relationship between arbitrary positive matrices and doubly stochastic matrices. The Annals of Mathematical Statisticy, 35(2):876-879, 1964.
[SMT+18] Max Simchowitz, Horia Mania, Stephen Tu, Michael Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
[SW12] Wojeiech Szpankowski and Marcelo Weinberger. Minimax pointwise redundancy for memoryless models over large alphabets. IEEE transactions on information theory, 58(():4094 4104, 2012.
[TJW18] Kedar Tatwawadi, Jiantao Jiao, and Tsachy Weissman. Minimax redundancy for Markov chains with large state space. In 2018 IEEE International Symposium Information Theory (ISIT), pages 216-220. IEEE, 2018.
[Tro74] Viktor Kupriyanovich Trofimov. Redundancy of universal coding of arbitrary Markov sources. Prob. Pered. Inf., 16-4), 1974.
[Wai19] M.J. Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press., 2019.
12

---

[Whi55] P. Whittle. Some distribution and moment formulae for the Markov chain. Journal of the Royal Statistical Society: Series B (Methodological), 17(2):235-24) 1955.
[WK19] Geoffrey Wolfer and Aryeh Kontorovich. Minimax learning ergodic Markov chains.
In Algorithmic Learning Theory, pages 904-930. PMLR, 2019.
[WK20] Geoffrey Wolfer and Aryeh Kontorovich. Minimax testing of identity reference ergodic Markov chain. In International Conference on Artificial Intelligence and Statistics, pages 191-201. PMLR, 2020.
[XB97] Qun Xie and Andrew R Barron. Minimax redundancy for the class of memoryless sources. IEEE Transactions on Information Theory, 43(2):646-657, 1997.
[YB99] Y. Yang and A. R. Barron. Information -thooretcc determination of minimax rates of convergence. The Annals of Statistics, 27(5):1564-1599 1999.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "kpvyOHv6ySF", "reviewer": "Reviewer_CoqU", "summary": "Applying techniques from universal compression, the authors characterize the optimal prediction risk in KL-divergence of the following problem: Based on a trajectory of length $n$ drawn from an unknown Markov chain with a state space of size $3\\leq k\\leq O(\\sqrt{n})$, predict the next state.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is of high quality and the results are significant and interesting. Nevertheless, while the authors do make efforts to explain their ideas and machinery, I find that the paper is hard to read and that several points are not clear or confusing. For example, even after several reads I am not sure what \"with and without spectral gap\" means. Does it mean with and without ASSUMPTIONS on the spectral gap? Section 3 is called Optimal rates without spectral gap but there is no corresponding section for \"with\". Furthermore, Section 3 is concerned merely with the lower bound. Additionally, in Section 2 there are results that make assumptions on the spectral gap and results that do not.\n\nAdding to the confusion, the connection between subsequent paragraphs is sometimes not clear and sometimes explanations for results come AFTER they appear. This makes reading difficult and hard to understand what exactly wad done by the authors and what is already known.\n\nI would also make the following specific suggestions. Whenever my remark is formulated as a question I mean that I find that an explanation IN THE TEXT is necessary.\n\n1. [line 25] While it can be assumed that if $Y\\sim P$ then $p_{i}=P(Y=i)$ and similarly for $Q$, this should be made clear.\n2. [lines 36-38] I am not sure about the correctness of the claim that “if certain state has very small probability under the stationary distribution, consistent estimation of the transition matrix may not be possible”. Under irreducibility, every state is visited infinitely many times and consistent estimation is guaranteed. Under reducibility, some states may not be visited at all and the corresponding transition probabilities cannot be estimated.\n3. [lines 50-51] Since highly related to this work, the authors should clarify what exactly “implicit assumptions on mixing time such as spectral gap conditions” that were made by HOP18 meant. (or at least point to where they are stated in HOP18, since I have not found them there).\n4. [line 53] The authors should make the phrase “with and without spectral gap” more precise. Isn't “without assumptions on the spectral gap“ or “arbitrary spectral gap” clearer?\n5. [line 87] It would be informative to explain the sudden restriction to reversible Markov chains. Is it an artifact of the analysis? Do reversibilization methods fail? What about the pseudo spectral gap?\n6. [lines 92-93] From $\\gamma_{0}>0$ it follows that the Markov chain is aperiodic. Together with irreducibility this give ergodicity. The authors might want to use this term explicitly.\n7. [line 96] In what sense is Theorem 2 an extension of (2) of [FOPS16]?\n6. [lines 124 and 131] “known as redundancy” and “is standard”. The authors might want to give references for the definition and for the result.\n8. [line 142] To which reduction do the authors refer?\n9. [line 213] Is there a reason for $X^{n+1}$ instead of $X^{n}$? What is $\\Theta$?\n10. [line 214] Shouldn't the definition $X^{n}\\overset{\\Delta}{=}(X_{1},\\ldots,X_{n})$ come before line 213? Actually, $X^{n}$ was already defined in line 23.\n11. [line 220] Here a more exact reference is given ([CT06, Chapter 13]). It would be nice if the authors could provide exact references for the well known definitions and results that are being used.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact.\nI suggest formulating the theorems in a more detailed manner that makes the assumptions made explicit.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "ZYldFXpy0S4", "reviewer": "Reviewer_AyiV", "summary": "This paper studies the prediction problem for Markov chain with more than $3$ states, and without the spectral gap.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. This paper proves the optimal prediction risk with the number of states between 3 and $\\sqrt{n}$ without the spectral gap, which requires more difficult proof technique than previous works analyzing markov chain with 2 states or with spectral gap.\n\n2. To achieve optimality, the paper defines an average of add-on estimators to be a new estimator and proves its optimality. \n\n3. The role of spectral gap is characterized clearly in the prediction risk. \n\nWeakness / comments: \n\n1. The most natural estimator for $M(j|i)$ might be the empirical frequency $N_{ij}/N_i$ instead of the add-one estimator in (5). It might be beneficial to discuss the reason why you use the add-one estimator: is it because empirical frequency is sub-optimal in nature, or just a technical issue.\n\n2. The structure of this paper is a little strange. It might be better to move the main theorems and proof techniques (Section 1.1) outside the introduction (Section 1).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper, and I think there is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "V1ivI0ep8sM", "reviewer": "Reviewer_oC8r", "summary": "From a single trajectory of $n$ observations drawn from a Markov chain over $k$ different states, we are interested in predicting the next one.\nFor some notion of risk they define, the authors prove that when $k \\geq 3$,\nthe rate is of the order $\\Theta((k^2/n) \\log (n/k))$.\nIn 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)$.\nFurthermore, they analyze the minimax problem over the set of chains whose spectral gap is controlled from below, and\nshow that under favorable (quantified) mixing conditions, one even recovers the \"iid parametric\" rate $\\Theta(k^2/n)$.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very-well written, and offers strong results. The problem is hard, and was until now only understood for the restricted 2-state case. The bounds are matching up to universal constants. The techniques are involved, enabling the authors to obtain bounds that are independent of the mixing properties of the chain (Th.1).\nAlthough this reviewer did not verify the proofs carefully, they have found no reason to doubt them. This is a strong submission; this reviewer recommends acceptance.\n\n* (L31-L38;L186-192)\nIn these two paragraphs, the authors seem to imply that there is something inherently simpler about the prediction problem than, say, estimation, illustrating this by saying that consistent estimation of the transition kernel is not possible if the stationary distribution comprises extremely small values. This last part, however, is a bit misleading and depends on the notion of distance one considers.  \nIt is true that some notions of distance lead to a minimax rate that also captures a dependence in the stationary distribution.\nBut for example, by weighing the state-wise discrepancy in terms of the stationary distribution as in Hao et al. [2018, p.2], or considering a distance in terms of the edge-measures of the chains as  in Wolfer and  Kontorovich  [2021,  Theorem  3.3], it is possible to obtain rates that are independent on the stationary distribution for the estimation problem.\n\n* (L79-81) Note that such interesting decoupling has also been observed in the Markov chain testing literature for some notion of distance (cited by the authors).\n\n* Add a few words on algorithmic complexity.\n\n* On page 1, when taking the infimum, indicate whether estimators must be (proper) Markov kernels.\n\n* Since the results are expressed up to universal constants, one can remove squares from the logs in the bounds $\\log (1 / k^2) = C \\log 1/k$.\n\n**REFERENCES**\n\n* Y. Hao, A. Orlitsky, and V. Pichapati. On learning markov chains. In NeurIPS, 2018.  \n\n* Wolfer  and  A.  Kontorovich.    Statistical  estimation  of  ergodic  markov  chain  kernel  over  discrete  space. Bernoulli, 27(1):532–553, 02 2021.  doi:  10.3150/20-BEJ1248.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed adequately.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "E7VAPfGC9O", "reviewer": "Reviewer_fh3J", "summary": "The paper studies the following problem: given data from a stationary Markov chain with discrete support, can we learn the stationary distribution? It derives the optimal rates for this learning problem when the spectral gap of the Markov chain is arbitrarily slow, and shows that when the spectral gap is bounded below, one can achieve parametric rates.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies a clear and well motivated problem, and introduces universal compression techniques to the study of Markov chains. The result for Markov chains without spectral gap assumptions is nice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is interested in predicting the next state, given $n$ observations from a single trajectory of a Markov chain. It is very well-written and offers strong, significant, interesting results.
Decision: Accept (Poster)