How good is Good-Turing for Markov samples?
Authors: Prafulla Chandra
Andrew Thangaraj
Nived Rajaraman
Venue: Accepted by TMLR ()

Abstract: The Good-Turing (GT) estimator for the missing mass (i.e., total probability of missing symbols) in $n$ samples is the number of symbols that appeared exactly once divided by $n$. For i.i.d. samples, the bias and squared-error risk of the GT estimator can be shown to fall as $1/n$ by bounding the expected error uniformly over all symbols. In this work, we study convergence of the GT estimator for missing stationary mass (i.e., total stationary probability of missing symbols) of Markov samples on an alphabet $\mathcal{X}$ with stationary distribution $[\pi_x:x\in\cX]$ and transition probability matrix (t.p.m.) $P$. This is an important and interesting problem because GT is widely used in applications with temporal dependencies such as language models assigning probabilities to word sequences, which are modelled as Markov. We show that convergence of GT depends on convergence of $(P^{\sim x})^n$, where $P^{\sim x}$ is $P$ with the $x$-th column zeroed out. This, in turn, depends on the Perron eigenvalue $\lambda^{\sim x}$ of $P^{\sim x}$ and its relationship with $\pi_x$ uniformly over $x$. For randomly generated t.p.ms and t.p.ms derived from New York Times and Charles Dickens corpora, we numerically exhibit such uniform-over-$x$ relationships between $\lambda^{\sim x}$ and $\pi_x$. This supports the observed success of GT in language models and practical text data scenarios. For Markov chains with rank-2, diagonalizable t.p.ms having spectral gap $\beta$, we show minimax rate upper and lower bounds of $1/(n\beta^5)$ and $1/(n\beta)$, respectively, for the estimation of stationary missing mass. This theoretical result extends the $1/n$ minimax rate for i.i.d. or rank-1 t.p.ms to rank-2 Markov, and is a first such minimax rate result for missing mass of Markov samples. We also show, through experiments, that the MSE of GT decays at a slower rate as the rank of the t.p.m increases.

Published in Transactions on Machine Learning Research (MM/YYY)
How good is Good- for Markov samples?
Prafulla Chandra
cc16d4020cc..ibnn wit.:/e...iiimc........
Deportment of Electricol Engineering, IIT Madras Chennai, India
Andrew Thangaraj
andrew@ee. wite ac ac.in in
Department of Electricol Engineering, IIT Madras Chennai, India
Nived Rajaraman
nived. feiidddmwooreman@@maalcooo
Deportment of Electricol Engineering and Computer Science
Universily of California Berkeley, CA 94720-1776, USA
Reviewed on OpenReview: https: // openreview. net/ forum? id= KokkkP2Q22
Abstract
The Good-Turine (GT) estimator for the missing mass (i.e., total probability of missing symbols) in n samples is the number of symbols that appeared exactly once divided by n. For iidd samples, the bias and squared-error risk of the GT estimator can be shown to fall as 1/n by bounding the expected error uniformly over all symbols. In this work, we study convergence of the GT estimator for missing stationary mass (i.e., total stationary probability of missing symbols) of Markov samples on an alphabet X' with stationary distribution [m, : X and transition probability matrix (t.p.m) P. This is an important and interesting problem because GT is widely used in applications with temporal dependencies such as language models assigning probabilities to word sequences, which convergence of GT depends on convergence of (P**)", where p is P with the æ-th column zeroed out. This, in lurn, depends on the Perron eigenvalue \~ of p and its relationship with Tz uniformly over x. For randomly generated t.p.ms and t.p.ms derived from New York Times and Charles Dickens corpora, we numerically exhibit such uniform-over-u relationships between ^~ and Tg. This supports the observed success of GT in language models and practical text data scenarios. For Markov chains with rank-2, diagonalizable t.p.ms having spectral gap 3, show minimax rate upper and lower bounds of 1/(n35) and 1/(n8), respectively, for the estimation of stationary missing mass. This theorelical result extends the 1/n minimax rate for i.id or rank-1 t.p.ms to 2 Markov, and is a first such minimax rate result for missing mass of Markov samples. We also show, through experiments, that the MSE of GT decays at slower rale as the rank of the t.p.m increases.
modelled Markov. We show that
1 Introduction
When observing sequence of symbols from an unknown alphabet and distribution, we are often interested in the probability that the next sampled symbol is going to be new, i.e. symbol that has not been seen far. This probability is the sum of the probabilities of all the symbols missing in the sequence of samples observed so far, and is called the missing mass. Good and Turing (Good) 1953) had originally studiod this problem in the context of solving the enigma code. The popular Good-Turing (GT) estimator estimales missing mass as the ratio of the number of symbols seen exactly once in the samples to the sample size. Today, estimation of
missing mass finds applications language modelling (W. (W.Church A.G. A.Gale 1991 Gale & Sampson, 1995
Chen & Goodman 1996), ecology CCao & Lee 1992: Shen al. (0033) and in entropy estimation (Vu al.
2007), and it has been studied in the i.i.d samples setting by multiple authors (McAllester & Schapire
2000

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Berend & Kontorovich 2013 Chandra et al.
2019
Ohannessian & Dahleh
2012 Mossel & Ohannessian 2019
Orlitsky & Suresh 2015 Rajaraman et al.
2017
Acharya et al. 2018 Cohen et al. 2020: Painsky 2022
The mean-squared error for estimating missing mass using the GT estimator in the ii.d setting [Rajaraman gt all 2017) falls as (sample-size)- with no further assumptions on the alphabet size or restrictions to the distribution. So, whenever the missing mass is expected to be non-vanishing, it can be reliably estimated in the i.i.d case.
While missing mass and the GT estimator are well-studied in the i.d samples regime, their definitions and properties in cases where the samples have memory have not been extensively considered in the literature. Many applications like natural language text processing involve data with temporal dependencies, which are often modelled as Markov chains (Chen & Goodman 1996). In this work, we study missing mass and its estimation through GT estimator in cases when the samples form a Markov chain. Estimation from Markov samples has been considered (Wolfer & Kontorovich] 2019 Hao et al., 2018 Han et al.] 2018 Hsu et al.
2019 Han ct al., 2021] and forays towards missing mass estimation from Markov chains were made in (Skorski, Chandra et al. 2020 Chandra et. al. 2022). Though GT missing mass estimates are used as part of distribution estimation in cases where the samples have memory, theoretical properties of the estimation of
2020
missing mass in such scenarios is, to the best of our knowledge, considered for the first time here.
2
Missing stationary mass of a Markov chain
A sequence X" = (X1, .2....,.................. .,),, X2 E N, is said to be Markov chain if Pr(X:=x;|X
xI= Pr(X==o||X
for = 2,..., and all F; E X. The X/'s are called states and X is called the state space. K _ |x(| is the size of the alphabet X. The transition probability matrix (t.p.m) of the Markov chain, denoted P, is the K x K matrix with (i,j)-th element P. e Pr(X2 = j| = i). A distribution π = [TI...... π on X said to be a stationary or invariant distribution of the Markov chain if TP = π |Gallager 1996.. A Markov chain X" is said to be stationary if X1 ~ n, which implies that X; ~ æ for all i. We denote by X Markov TT, a stationary Markov chain with t.p.m. P and state distribution
Let I(-) and E||] denote the indicator random variable and expectation, respectively, and let [K] denote the set 21,2.... K}. For x E X, (X") A Ei I(X, = x) is the number of occurrences of x in X", also called the frequency of x. For 1 = 0,1,2,.... (x") A Exex T(N=(X") =)) is the number of letters that have occurred times in X
The missing stationary mass of a Markov chain X" ~ Markov (P, x), which is the missing mass π in X", is defined as
MO(T, X") A Σ I(N,(X") = 0).
(1)
PEX
Estimation of the missing mass Mo(T,XX) when X ~ Markov(P, T) and the quantities X, K, π and P are unknown is important for many applications and in theory (see the role of missing mass excess risk of competitive distribution estimation in &Orlitsky & Suresh 2015)). Note that Mo(T, is a random variable that is a function of both the samples X" and the distribution л. This makes estimation of missing mass and its analysis non-trivial even in the classical i..d regime where X ~ i.idd P = 1r. For X ~ Markov(P: rT) with general P, the samples are not drawn exactly as per π, which is the weight for measuring missing mass. This makes the study of missing stationary mass of a Markov chain more challenging, when compared to an i.dd sequence.
Markov chain with
The Good-Turing (GT) estimator GGoo 1953 for the missing mass Mo(T, X²) defined as
(X""
M GT (X")
(2)
which is the fraction of symbols that have appeared exactly once in the samples.
2

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The minimax squared-error risk of estimating missing mass class of distributions P, denoted R, (P), is defined as
(P)
min Estimator Mo (PT)EP
max (xV--Manter(/:mm((0((0111)) - MM(TT,
(3)
The GT estimator has worst-case squared error risk of O(1/n) in the i.i.d regime and is known to be minimax rate-optimal (Rajaraman al. 2017 Acharya al. 2018 A common approach to use estimator that works well on i..d sequences in the (non-i.i.d) Markov setting is to sub-sample the Markov chain at intervals of mixing time and apply the estimator on the resultant, nearly i..d, sub-sampled sequence. But such an estimate using the GT estimator will have a non-vanishing bias for the missing stationary mass of a Markov chain, since the missing mass of the subsampled sequence would different and possibly greater than the missing mass of the whole Markov chain. Moreover, through examples, we demonstrate how the GT estimator fails converge the missing mass for Markov chains with mixing time 3.
Another metric that is extensively used in the study of Markov chains is spectral gap Gaalaaerr 1996 Levin el all 2008). A chain with nonzero, constant spectral gap shares several properties of i.i.d sequences. However, through a counter example, we show how the GT estimator fails to converge to missing mass for Markov chains with a non-vanishing spectral gap. Honce, the success of the GT estimator for missing mass in the Markov case appears to require a new measure of closeness to i.i.d, and we study such closeness property this work.
We make two main contributions. Firstly, we study the Good-Turing (GT) estimator and characterise the classes of Markov chains t.p.ms for which it converges to missing stalionary mass. A large class of t.p.ms occurring in practical scenarios are likely to satisfy these characterisations.
Secondly, on the thcoretical side, we characterise the minimax squared-error risk estimating missing stationary mass over a class of rank-2 Markov t.p.ms with a spectral gap. To the best of our knowledge, this work presents the first minimax rate result for a Markov case.
3
Main Results
3.1
Convergence of GT estimator
We first provide a simplified expression for the bias of the GT estimator for missing stationary mass, using which convergence analysis becomes possible. We require the following notation.
For E X, let per be modified transition matrix equal to P in all positions except the x-th column, which is set as the all-O vector. So, under p=x, the symbol x is never observed. Let po & P - p~= be all-zero except for the æ-th column, which is set as the æ-th column of P. Let π ~~ be equal to the vector x in all positions except the æ-th entry, which is set as 0. Let 1 be the X x vector with all entries as and e be the 1 x | vector with the z-th entry as and all other entries as zeros.
Lemma For stationary Markow chain X Markov(P, π), the bias of the Good- Turing estimator can be expressed as follows:
([MOT(X*) Mo(T, X"]]
1
Σ TE
The (e, 22) (pww)(n-1) 1
~ (m~z)(m-2) (Pfz pNx) (p-z)(n-m) 1/ (4)
m=2
Proof. Section 5
In where missing expected to vanish with n, relative error is meaningful shown in Mossel & Ohannessiarg 2019). However, in many interesting large alphabet scenarios, missing mass is non-vanishing for large n, and estimation critical in the non-vanishing case. So, consider additive error in this work.
3

---

Published in Transactions on Machine Learning Research (MM/YYYY)
For X iid n, the t.p.m 1 ग., p== n² and the bias of the GT estimator equals Exea T (1 ma)" = 0(1n)). Therefore, the Good-Turing estimator has vanishing bias for the missing stationary mass in the i.id case and one might expect M to perform similarly over Markov chains that are close to the iid regime, say, in mixing time or spectral gap, In Section 3.3, we show through simulations that there exists non-iidd Markov chain with mixing time small as 2 (or 3), which is the closest non-ii.d Markov chains can get to the ii.d regime in terms of mixing time, for which the Good-Turing estimator does not converge to the missing stalionary mass. A similar counterexample is shown for spectral gap as well. So we need a different notion of proximity to the iidd regime to extend the i.dd result on the convergence of the GT estimator to the Markov regime.
=
In the following theorem, we present sufficient conditions on the t.p.m P for the convergence of the GT estimator to Mo(TT,X)) These conditions require powers of por to be close to 1s which is P of the corresponding i.idd chain with t.p.m Pia = 1s and stationary distribution æ. In Section 3. verify that these conditions are satisfied by randomly generated t.p.ms, empirical t.p.ms built using language corpora and the GT estimator has vanishing MSE for Mo(TI, of the stationary Markov chains from these t.p.ms.
Theorem 2. The absolute bias of the Good Turing estimator MOT(X"), for the missing stationary mass of stalionary Markov chain X Markoo(P, P, x) is bounded as
2(2no +1) + -B3moon + 20 + e-1
e-1
(I MT, X*]]
I
n -4 + a0
(5)
n
ci(n - 2)
where no, Ca, ag and 6i (defined below) satisfy the following conditions:
1. there evist no = o(n), d E [0, for E X' and ck, > O such that for any x E X' and k 2 no,
(a) (2 - (2,a) π xx S e₂ (Pmeyk S (Ah-1 + (k,)) x", 2 1 X,
(b) dx S 1 cI a E [0,
2. there erists ao > O such that Par S ao Th for all x E X.
The MSE of the GT estimator (XT(X") for Mo (o(TI.X)) of X" ~ Markou P. π) is bounded as
31
(X(M)T(X*) Mo(TT, s n
(5n' + +2)
2 c2(1 - 2) Eno.n + +6 +G + mn )2 + (C )3
n 6 2 (8e-1 + + + + (3+
1
Sagaage (3+
1)]]
(6)
i, in addition to the above mentioned conditions, there exist n/ o(n), (ME E [0, : x, y E X, x A y} and
kn > O such that for any x. y E X, x # y and l: 2 n/g
(A) (Xtr)) ((,)) π ~ < c₂ (Pra.yy s (Xi + (hn) π ~IN E X,
(B) Az.y S 1 - c2(  + Ty), 02 E [0, 1],
where the matria p-a.y equals the t.p.m P in all entries except in the x-th and y-th columns which are set to 0 and -am is the vector obtained by setting the x-th and y-th entries to 0 in π.
Proof. Section
6
It is easy to retrieve the classical ((1/n) bounds on the bias and MSE of the GT estimator for missing mass
in i..d samples from Theorem 2 by checking that the conditions required for (5) and (6) are satisfied in the i.i.d case with d₂= = 1 Tz, An.y
(T. + Ty), cx,n then 0, Cı = ap and n10 = n/ = 1.
The conditions on the t.p.m P in the above theorem constrain the rows of (p~z)* to be similar to those of (1 ~ (1 - )-1 1 n ro This is reasonable and may be satisfied by many t.p.ms since the k-th
4

---

Published in Transactions on Machine Learning Research (MM/YYYY)
power of non-negative matrix converges to the k-th power of its Perron eigenvalue, i.c. the eigenvalue with the largest magnitude, times the outer-product of the corresponding right and left eigenvectors and we expect such left and right eigenvectors of p to be close to those of 1 i.e. पh and 1, and the Perron cigenvalue of p to be close to 1 - Tg, the only non-zero eigenvalue of 1 π n. The conditions on P-ayy have similar interpretations.
The error term in the convergence of (P>Z)& which we have denoted ck,n: may, in general, be function of k and n (note that entries of P may be scaling with well). The convergence of bias to zero depends on the convergence of E to zero. This may be numerically verified for many interesting t.p.ms, shown later. Similarly, the convergence of MSE to zero depends on the convergence of 2iim to zero.
The condition on Pae (self-loop probability) is necessary for successful convergence of the GT estimator as shown later by counter example. This condition is also expected to be satisfied by wide range of t.p.ms such those arising from natural language text because word seldom follows itself in writing.
The conditions of Theorem 2 need to be satisfied only for those letters æ that are most likely to contribute to the missing mass. For example, if πT > 1/n, the letter x will appear in n samples with high probability and p need not satisfy the conditions. We have not explicitly stated such modifications for simplicity.
The conditions of Theorem 2 constrain a Markov t.p.m to be close to the i.i.d regime an analytical way. Next, we shift to an algebraic view, and study missing mass estimation from Markov chains with t.p.ms that are close to the i..d regime in rank. Note that the ii.d t.p.m has rank 1. As natural next step, we consider t.p.ms with rank equal to 2.
3.2 Rank-2 Markov chains
Consider a Markov chain with a rank-2 t.p.m P, which we will call, loosely, as a rank-2 Markov chain. Since P has all entries in [0, 1] with each row adding to and since it has rank the eigenvalues of P will be 1, A2 0, ..., O, and -1 A2 S 1 (by Perron-Frobenius theorem) (Pillai al. 2005). The value of X2 determines several important properties of the chain. If A2 = the chain is roducible. If X2 -1, the chain is periodic with period 2. If X2 O, the chain is i.i.d For -1 < A2 < 1, the chain is irreducible and aperiodie. We define the spectral gap of a t.p.m P as
3(P) A 1 A2 E [0.2].
In this section, we let P2,3 denote the family of rank-2 diagonalizable t.p.ms with spectral gap B.
3.2.1 Bias of GT estimator
The absolute bias of the GT estimator converges as (/(n52)+11////1 1/(33*) for rank-2 Markov chains with spectral gap 3. This is shown in the next theorem.
Theorem 3. For P P2,3 with stationary distribution π and B > 30( n)/nnnnnnnnnnn ()) 1/2 constants C₁, 02 > 0, such that
there erists universal
FIMOT(X) - Mo(TT X
C2
+ ((1/n).
(8)
n2
n33
In comparison to Theorem 2 we see that the bias is explicitly bounded in terms of the spectral gap, which that the bias of the GT estimator converges if
is an important parameter of the chain. For 3 < 1, (I/(2)3)) + 0, or B3 is higher than c/ V/ for large n. So, even in cases where the spectral gap is asymptotically vanishing, the GT estimator converges if the rate of fall is not too rapid.
3.2.2 Minimax rate
For rank-2 chains, a much stronger result than convergence of bias can be shown. We next characterise the minimax rate R", (P2,9) of the squared error risk of estimating Mo(T, T,, X²) of X Markov(P, л)) for the class P2.9.
5

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Theorem 4. The mánimaz squared error risk Ry (P2.3) is bounded as follows:
1. For B ((160ln))/(n ())
(P2,)) & O(1/n5").
(9)
2. For n sufficiently large, there is constant such that
(Ps) 2 R2 2
c nB
(10)
We get the upper bound in (9 by analyzing the worst-case MSE (over P2.9) of the GT estimator MCT(X") Φi (X") in estimating ( from X ~ Markov(P, π) with P P2.3. The simplifications in the upper bound are fairly involved and an outline of the proof is presented in Section 7 The complete proof is provided in the Appendix.
To get the lower bound (10), we modify the Te Cam two point method. The usual Le Cam method for lower bounds on minimax risk Yu 1997) directly applies when the estimand does not depend on the samples, and is parameter of the distribution alone. Using concentration propertics, we extend the Le Cam two-point method to the case of estimating missing stationary mass Mo(x, X") that clearly depends By constructing two Markov chains (with t.p.ms in P2,s) close in distribution and separated in Mo( (T, X"), we get the lower bound in 110b on (P2,)) Since P2, is contained in P3, the class of all Markov chains with spectral gap 8, the same lower bound extends to R, (P²) as well. Specific details are provided in the Appendix.
the samples X".
Overall, we see that the minimax rate behaves 1/n for rank-2 chains. This extends the previously known 1/n rate for i..d samples. The behaviour with respect to 8 differs in the upper and lower bounds (1/(n8") 1/(n3)), and this gap could be closed in future work.
3.3 Synthetic and corpora-based illustrations
In this section, we present the results of our simulations studying the performance of the GT estimator in estimating the missing stationary mass of Markov sequences drawn using rank 2 t.p.ms, higher rank t.p.ms, randomly generated t.p.ms, and empirical t.p.ms built over natural language text.
3.3.1
Rank-2 synthetic t.p.m
We consider K K rank-2 t.p.m with spectral gap formed by K/2 K/2 blocks as follows:
CK,8
CK,
C
3/2
0
:
CK,8
CK,8
CK,8
3/2
0
B/2
CK,8
CK,8
CK,9
:
0
B/2
CK,8
CK,8
CK.9
where CK29 (1 -1 (/2) We generated stationary Markov sequences of lengths 30, 60, 120, 240, 500, 1000 from the rank-2 t.p.m specified above with K = 1.2n and with f 1/2 f = 1/n and computed the missing mass Mo and the GT estimate over 5000 trials. The mean values with standard deviation bars are shown in Fig. [ For comparison, similar results are shown for i.i.d sequences from the same stationary distribution. As predicted by the theoretical results, the GT estimate converges in the rank-2 case for 3 = 022 while is away by constant value for B 1/n. In the i.i.d caso, there is convergence in all cases. We see that the variances the rank-2 case are noticeably higher when compared to the i.i.d case.

---

Published in Transactions on Machine Learning Research (MM/YYY)
0.5
B 1/n
= 1/n
Mean with std dev
0.6
0.4
0.4
Mg rank
Mo iid
0.3
GT iid
0.2
GT rank
200
500
1000
200
500
1000
Sample size n
Figure 1: Missing mass and GT estimates for rank-2 chain and i.dd sequence.
Rank t.p.m. with spectral gap
Rank sticky t.p.m.
10
10
* I = 1.2n
10
9 L = n
MSE
10
nn
10
L = n.
0.25
0.5
10
10
10 10-4
3
1/
0.2
10-5
10-4
100
400
1600
6400
100
400
1600
6400
Sample size
Figure 2: MSE of GT for a rank-2 chain with spectral gap 33 and rank L sticky t.p.m.
A plot of MSE of GT versus is shown in Fig. 2 for larger range of values for n for the rank-2 chain considered above. The parameters were chosen as K = 1.2n, = 1/n 1/n0,,, 1/n0. 1/n, and the MSE was averaged over 16000 trials for each n. We observe that the MSE falls with n for 3 higher than 1/n, while it stays flat for 3 1/n. So, this particular case, it appears that the actual MSE as per the lower bound of Theorem in terms of
3.3.2 Markov chains with rank of t.p.m above 2
The mean square error of the GT estimator for the missing stationary mass Markov chain with t.p.m rank greater than considered next for simulations. Through these simulations, we show the following:
The rate of decay (with number of samples) of MSE of the GT estimator for the missing stationary mass of Markov chain appears to vary with the rank of the t.p.m, possibly one of the parameters.
Rapid mixing of a Markov chain is not sufficient for convergence of GT estimator of missing mass.
Large spectral gap of Markov chain is not sufficient for convergence of GT estimator of missing mass.
We consider K x K l.p.m P with the i-th row as (recall that e; is vector with 1 at the i-th position and zero elsewhere)
P e a) p. for = 1, 2, ... L, and P; p, for L 1...., K,
7

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where [0, 1] and == (Ps X) is probability distribution on X' {l..... Nh..,,KK, distribution of this t.p.m is such that
K}. The stationary
1 aj 7 pi, for 1,2,... ........ L, and n, 7 ps; for i L. 1...., K;
1-7
where 7 1-
For a >>000 0 and L = K, π = and we refer to the above l.p.m as a (geometrically) sticky t.p.m or a sticky Markoy chain. For a > and L < K, we refer to the above t.p.m as a partially sticky t.p.m. For a = 0, we retrieve the i.i chain. Note that the rank of this t.p.m L + for << and K, i.c. full rank, for
K.
We generated stationary Markov sequences of lengths n 100, 200, 400, 800, 1600, 3200, 6400 from the t.p.m specified above with K = 1.2m, L = no.25 n nooT 1.2m, 0.5 and p as the uniform distribution.
The scaling of the alphabet size K (and, as result, the parameters of the t.p.m) with the sample size n models the large alphabet nature of applications like language text where the alphabet size is greater or of the same order as the data size. The missing mass estimation problem is non-trivial in cases such as these since, for example, the (expected value of) missing mass in n samples drawn from a uniform distribution on en letters, e being a constant, converges e 1/c as n + 00, whereas in cases with the alphabet size parameters of t.p.m independent of n, the (expected value of) missing mass in n samples of sequence generated from such t.p.ms converges to 0 n increases. Note that the MSE of the GT estimator for the missing mass in n i.idd samples (i.e. rank-1 t.p.m) of a uniform distribution on en letters decays as 1/n (Rajaraaan et al.) 2017
A plot of the MSE (averaged over 16000 trials) of GT against n, for these choices of L, is shown in Fig 2 From the plot, we observe that the MSE of the GT estimator, for missing stationary mass of Markov chain with the above specified t.p.m, increases with the rank of the t.p.m and the rate of decay of the MSE depends the rank.
Further, the MSE is non-vanishing (with n) when the t.p.m is of full rank which is geometrically sticky t.p.m in this case. Note that the geometrically sticky Markov chain considered here with = 0.5 has mixing times of 2 and 3 for total-variation distances of 1/4 and 1/8 to the stationary distribution æ. Further, the spectral gap 1 a = 0.5. Therefore, even in the regime mixing times close i.id (the mixing time an i.i.d chain is 1) and constant spectral gap, there exist Markov chains for which the GT estimator does not converge Mo(TTX X").
The geometrically sticky chain violates Condition 2 of Theorem i.e. Pau a a (1 a) S0 Te is not satisfied for > wg. The authors of (Chandra et al. 2022) suggest a scaling of the GT estimator, which converges to missing mass in this case.
3.3.3 T.p.ms generated at random and from corpora
Analytical characterisation of non-i.id t.p.ms that satisfy the conditions in Theorem 2 a challenging problem. While there are counterexamples such the sticky channels, the GT estimator appears to work in practice for several text-based corpora, which behave like Markov chains. To study this phenomenon under the setting of Theorem 2 we construct some random t.p.ms and some t.p.ms from text corpora and verify conditions in Theorem 2 numerically.
We consider class of randomly generated t.p.ms, and two classes of t.p.ms from text corpora.
Each entry is first drawn i.i.d from the uniform distribution over [0, 1] and each row is then scaled to make the row sum equal to 1.
Punif-gen:
NYT:
The New York Times (NYT) corpus consists of randomly collected articles from the front pages of New York Times from the years 2017 and 2018. To build an empirical t.p.m, consider an
available under CCO:Public domain license at httpp:// http///wwwwkgggg/ www.kaggle.com. haa.://eaeoemmattttte///aaaaaaae htt. york-times
8

---

Published in Transactions on Machine Learning Research (MM/YYYY)
article in the NYT corpus and set the empirical transition probability (from word Wi to w2) Pwr, as /wr, where Ner,, is the number of times the word W2 follows wi in the article and No. is the number of occurences of the word w in the article The empirical probability To is set to /w/ (total wordcount) of the article.
GE: The novel Great Expectations (GE) by Charles Dickens is available under the project Gutenberg To construct a t.p.m, we consider a chapter from the novel and repeat
(https:// https//wwwggg.. www.gutenberggooo the same process as NYT above.
We specifically use two Panif-gen t.p.ms with support sizes K = 1250, 1.2n and three empirical t.p.ms, cach built using a chapter of the novel Great Expeclations and five empirical t.p.ms, each built using an article with more than 1600 words from the NYT corpus. To verify Condition in Theorem D we use the Perron eigenvalue 2r, the eigenvalue of pow with the largest magnitude. We consider the difference between the ratio (P**))=/Tr RT and (x1.a)==1 and denote by Ck,n,z, the maximum of the absolute value of this difference over all the entrics of (P^²)*, except the entrics of the z-th column which are Ck, is the maximum of fk.n. over all x. Fig 3 shows two scaller plots, for k = 16 and 64, of n,, against 1 1- Tr for Punif-gon l.p.m 100, 200 and 400. From these plots, we see that ct,n,z falls with both & and n. Fig 3 also shows a scatter plot of λ1 against - Tx for the same t.p.m with n = 100, 200 and 400, which indicates linear relation between λ1.x and 1 - Tx. From the plots in Fig 3 we see that Condition 1 in Theorem 2 is satisfied by this t.p.m with Xa as 21,z as cn, decreases with n.
with K = 1.2n and
k = 16
-10-2 k = 64
10
2
2
1.2
0.998
n 400
Y1 = 100
1.5
0.996
Ck,n,
n 200
0.8
Y1 200
1
0.6
0.5
71 400
0.4
0.991
100
0.991
0.995
0.998
0.991
0.995
0.998
0.991
0.995
0.998
1 Tx
Figure 3: 6k,, VS 1 - Tx and \1,5 vs 1 - -T for P Punif-gen t.p.ms with K = 1.2n
Figure 4 showss scatter plots of 1 - λ1, against the stationary probability गे for the remaining three t.p.ms.
All the plots show a linear upper bound relation between 1 1- -A1, and He closely matching the Condition 1(b) in Theorem sufficiently high ng.
2 In addition, these l.p.ms satisfy Condition (a)) Theorem as nn. is negligible for a
For the randomly generated t.p.ms Punifigen with K = 1250 and K = 1.2m, Pau was found to be less than 10Tz, for any For the empirical t.p.ms built from language text, Pzz for any Therefore, the t.p.ms under consideration also satisfy Condition 2 in Theorem 2 Since Eng.n falls with n for the Punif-gen t.p.m with K = 1.2n and is negligible for a suitable choice of no for the other t.p.ms, Theorem 2 implies that the GT estimator should converge to the missing stationary mass of Markov chains from these t.p.ms.
Figure plots the MSE of the GT estimator for Mo(TT X²) of stationary Markov chain X" generated using the t.p.mss Punif-gon with K- 1250, 1.2n, the three empirical t.p.ms from GE and the five empirical t.p.mss from NYT corpora, for 100, 200, 400, 800, 1600, 3200, 6400 and averaged over 16000 trials. The curves for GE and NYT correspond to MSE averaged over the three t.p.ms from Great Expectations and the five t.p.ms from the NYT corpus. We observe that MSE falls for all of these t.p.ms.
We change all the words in the article lower case, lemmatize the words and ignore punctuations.
9

---

Published in Transactions on Machine Learning Research (MM/YYYY
3 Empjrical t.p.ms from GE 5 Empirical t.p.ms from NYT
Pmiif-gen with K 1250
-10"
-10
.10
8.4
8
6
8.2
X1æ
2
7.8
2
7.6
(99
4
6
8
7.6
7.8
8
8.2
8.4
-10-2
-10
-10
-10
slationary/empirrial probability Ta
Figure 4: 1 1 21, Th for randomly generated t.p.m and t.p.ms from corpora.
10-3
MSE
10
Puntf- K 1250
Punit-gen: K
1.2n
10
GR
NYT
100
200
400
800
1600
6400
Sample size
Figure 5: MSE GT for randomly generated t.p.ms and t.p.ms from corpora.
4 Conclusion and Future Directions
In conclusion, our study of the Good-Turing (GT) estimator for missing stationary mass of a Markov chain with t.p.m P and stationary probability π (with support size assumed to be unknown) indicates that convergence of GT depends on relationships between the spectrum of per (P with æ-th column zeroed out) and wy to be satisfied uniformly for all x that contribute to missing mass. We derive specific sufficient conditions for convergence absolute bias in terms of the nature of convergence of powers of p** with respect to powers of P. These conditions are verified numerically for t.p.ms derived from text corpora, which supports the success of GT in practice. Analytical understanding of relationships between the spectrum of p~x and Tu for arbitrary t.p.ms is topic for futurr study. In the case when P has rank 2 with spectral gap of 8, we derive lower (c/(n3)) and upper (c/((n35)) bounds on the minimax squared-error risk. The bounds extend the 1/n minimax rate result from the i.i.d case to rank-2 Markov, Characterizing the exact dependence on B is a topic for future work. Through our simulations on high-rank t.p.ms, we see that the rate of decay (with n) of the MSE of the GT estimator for the missing stationary mass might vary with rank of the t.p.m.
5 Proof of Lemma
To prove we begin with the expressions for the expected values of Mo(T, X²) and MOT
using ~ prm
and p0
10

---

Published in Transactions on Machine Learning Research (MM/YYY)
Since Mo(t,, X")) EvEX Tx (X 0), we have
([Mo(T,X")) = Σ EEt
Th Pr(Na(X")) = 0) Σ
Tx nh (pragnn1 1.
(1)
DE
Since M = (1(x))/n= 1. EBEx (XN) = 1), we have
E [X =
Σ
Pr((N((")) = = Σ
Σ
Pr(Xm = x; Xi + 2, m, sl)n)
nEX
mEX
m
Tx (p~z)(n-1) 1+
π
(p~z)m-2 P (P~z)u-m 1
(12)
REX
m=2
Taking the difference
12
and
we get 14
This completes the proof of Lemma
6 Proof of Theorem 2
In this section, we provide a proof for (5) in Theorem 2 The proof for (6) is similar. To prove the bound on the bias of M in (5), we first bound the expectation of M Let X & (X...... Xm 11 Xmtl X,), the samples X1 Xn except Xm, for m = n..
EIMOT(X')) (X")]
1 Σ
(x(N =
Σ
Pr(Xm = (X =0)
FEX
TEX m=1
Σ
Pr(Xm = x. (x = 0) +
Σ
To
= x2 Nr 0)
n
ZEN
m= 1 R- + 1
m=no+2
(4)
1 Σ
Σ
Pr(Xm = xx) +
n Ro
Σ
Pr(Xm = xx Nz = =0)
71
TEX
n- ng
m=
nL-Ro To
Σ
(2no + 1) Tx
Σ
(pwrym-2 pb (prryn-m 1
11
ZEN
+2
(6) 1
R-no Σ
Σ
(2no + 11 Fx +
π N (Am-3 + mm-2 1 ~ Plz (x--m-1 + cn-m,) 1 n ~a 1
n
NEX
m m= ng +2
(c)
1
Σ
(2mo + 1) Tx +
12-
Σ
Tx (1 Pax) (1 nz)² (25- + Cn-m,n 2m-3 + 2,n a=-m-1
12
#EX
+2
+ 2m 6n-ma))
(d)
2no + 1
+ (1- 2noo + 1
Σ
(1 C1-Pat -Px)) (1 - J²) (2--1 + 22 + 2 20
n
XEX
(6) 2(2mo + +1
+ (1- 2no +
[Zenoin + 2 2n + Σ Tx (1-Pzz) (1 - (1= \² n
(13)
n
n
xEX
where we get (a) by using Pr(Xm = I; x1 # 2,1 + m, 1 S n) < Pr(Xm = x) = =Tz (b) by using
Condition 1(a) of Theorem 2 (c) by using π = 1 - nτ and π ~ p0
n2 (1 Pam)) ) (d) by using
EBEX Te [A2l < and cn- > Eng.r cm-2,n > Eng.n for m n2 2, 2,..., n ng and (e) by using
Erex na (1 Pax) (1 )² -= < Ezex nx (1 Pax) (1 n. 2 < Σ E Tx =1 1.
11

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Using similar method, we lower bound the expectation of Mo(TT, (x)) as
(a)
[[M)(TXX = Σ
Te π nh (pro)n-11
1
Σ
Ty π
(A cn-1,n) ) 1 π
ZE
ZEN
Σ
Tx (1 Tz) ) (2 2- en 1n-1,
(14)
where we get (a) by using Condition (a) of Theorem 2
Using
13
and 14 we gel.
(0000(x")) F M
2(2 + +1)
+ [3emo. + mannl
+
Ta (1 - nz \/
[ Pax 12
DEN
IN
2(2ngg +
+ [3eno.n + no
T
Tx 122-1110
2(1 Ax) + ao
n
VEX
2(2 + 2
+ [3eno.n + engnnl +
E
+ 40 c1(n - 2)
E
(15)
n
4
where we get (a) by using EvEx Te (1- - Tx)² cn-1,n S Cn
EmEx Tx S Cn-1,n S Cna.n (b) by using + d $ 2, Paz ag nx and (c) by using d S CTTT from Condition 1 in Theorem along with max4e[o,1] t (1 t) /
Using a similar method, we can show that
2(2mg + 11
+ [e + Go + e-
e- + ap c1(n 2)
(x")
s
n
n 4
This completes the proof of 5 in Theorem 2
7 Proof of Theorems 3 and 4
A proof of Theorem is given in Section A of the Appendix. In the proof,
we split the alphabet X' into three sets: letters with T. = Paz, which we refer to as rid-like letters, infrequent letters with nx * Pazs frequent letters with T& * Paz and bound the letter- letter-wise bias of the GT estimator I2 A 1 (x = 1) nı Pr(NN((X) = 0), i.. E[MPT
M =
Ezex Iz, over these scts. The infrequent letters contribute the most to missing mass, expectation.
For the letters with nх Paw, (X"), = 0) = (1 1--my m2) and Pr(N,(X") =) = n ne (1 - ug n
and the sum of [x| over all the iid-like letters is bounded as O(1/n).
We bound the sum of [ over all infrequent letters (with * Paz) by using the eigenvalue decomposition of p~a in (4) along with bounds of the form \1, S - Co co being a function of the spectral gap 8, on the Perron eigenvalue d1. of pmz
To bound the sum of [r] (over all frequent letters) with Tх * Paz, we bound Pr(Nz(X") = 0) and Px(N)=(X') = 1) using the eigenvalue decomposition of p along with bounds of the form λ1,z < 1 Co and use these to upper bound the absolute value of Tz.
The upper bound on the bias of the GT estimator in 8 is obtained by combining the bounds the sum of Tal over these three sets and choosing suitable threshold stationary probability to split the alphabet X into frequent and infrequent letters.
The proof of the upper bound in Theorem also uses ideas similar to the above. See Section in the Appendix.
The lower bound in Theorem 4 is proved by an extension of the standard Le Cam method to estimation of the missing mass random variable. See Section C in the Appendix.
12

---

Published in Transactions on Machine Learning Research (MM/YYY)
References
J. Acharya, Y. Bao, Y. Kang, and Z. Sun. Improved bounds for minimax risk of estimating missing mass. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 326 330, June 2018, doi: 10.1109/ISI 2018.8437620.
Daniel Berend and Aryeh Kontorovich. On the concentration of the missing mass. Blectron. Commun. Probab., 18:7 pp., 2013.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalilies: A Nonasymplolic Theory of Indepen- dence. Oxford University Press, Oxford, UK, 2013. ISBN 9780199535255.
P. Chandra, A. Thangaraj, and N. Rajaraman. Missing mass of Markov chains. In 2020 IEEE International Symposium Information Theory (TSIT), pp. 1207-1212, 2020. doi: 10. 1100/TTTT444884220000917177
Prafulla Chandra, Aditya Pradeep, and Andrew Thangaraj. Improved tail bounds for missing mass and confidence intervals for good-turing estimator. In 2019 National Conference on Communications (NCC), pp. 6, 2019. doi: (0009/NCC.2019..7770
Prafulla Chandra, Andrew Thangaraj, and Nived Rajaraman. Missing mass estimation from sticky channels. 2022 IEEE International Symposium on Information Theory (ISIT), pp. 910 915, 2022. doi: 10. 10.1109/ ISIT50566. 0025006666.022.9888888 2022.983457.. URL https://arxiv. www.aarwwwv...raoeeeeeea /2tpp//f/2022...2 02772. pdf
Anne Chao and Shen Ming Lee. Estimating the number of classes via sample coverage. Journal of the American Statistical Association, 87(417):210-21 217, 1992.
Stanley F. Chen and Joshua Goodman. An empirical study of smoothing techniques for language modeling. Proceedings of the 34th. Annual Meeting on Association for Computational Linguisties, ACL 196, pp- 310 318, 1996.
Doron Cohen, Aryeh Kontorovich, and Geoffrey Wolfer. Learning discrete distributions with infinite support. Advances in Neural Information Processing Systems, 33:3942 3951, 2020.
William A. Gale and Geoffrey Sampson. GoodTuring frequency estimation without tears. Journal of Quantilative Linguistics, 2(3):217 237, 1995.
Robert G Gallager. Finite state Markov chains. In Discrete Stochastic Processes, pp. 103 147. Springer, 1996.
I. J. Good. The population frequencies of species and the estimation of population parameters. Biometrika, (1//44)233 264, 1953.
Yanjun Han, Jiantao Jiao, Chuan-Zhema Lee, Tsachy Weissman, Yihong Wu, and Tiancheng Yu. Entropy rate ostimation for markov chains with large state space. In Proceedings of the 32nd International Conference on Newral Information Processing Syslems, NIPS'18, pp. 98039814, Red Hook, NY, USA, 2018. Curran Associates Inc.
Yanjun Han, Soham Jana, and Yihong Wu. Optimal prediction of markov chains with and without spectral gap. In Advances in Neural Information Processing Systems, volume 34, pp. 11233 11246, 2021.
Yi Hao, Alon Orlitsky, and Venkatadheeraj Pichapati. On learning Markov chains. Tn Advances in Newral Information Processing Systems, pp. 648 657, 2018.
Daniel Hsu, Aryeh Kontorovich, David A. Levin, Yuval Peres, Csaba Szepesvári, and Geoffrey Wolfer. Mixing time ostimation in reversible Markov chains from single sample path. The Annals of Applied Probability, 244:2443 2480, 2019. doi: 10.1214/8-AAP1457. AAP1457.
D.A. Levin, Y. Peres, and E.L. Wilmer. Markov Choins and Miring Times. American Mathematical Soc., 2008. ISBN 9780821886274.
David A. McAllester and Robert E. Schapire. On the convergence rate of Good-Turti estimators. In Proceedings of the Thirleenth Annual Conference on Computational Learning Theory, pp. 1-6, 2000.
13

---

Published in Transactions on Machine Learning Research (MM/YYY)
Elchanan Mossel and Mesrob I. Ohannessian, On the impossibility of learning the missing mass. Entropy, 21 (1), 2019.
M.I. Ohannessian and M.A. Dahleh. Rare probability estimation under regularly varying heavy tails. Conference on Learning Theory, pp. 21.1 21.24, 2012.
Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why good-turing good. Advances in Neural Information Processing Systems, 28, 2015.
Amichai Painsky. Generalized good-turing improves missing mass estimation. Journal of the Americon 25020020060822 Publisher Copyright:
Statistical Association, 2022. TSSN 0162-1459. doi: c 2022 American Statistical Association.
Unnikrishna Pillai, Torsten Suel, and Scunghun Cha. The perron-frobenius theorem: some of its applications. IEEE Signal Processing Magazine, 22(():62-77) 2005.
N. Rajaraman, A. Thangaraj, and A. T. Suresh. Minimax risk for missing mass estimation. In 2017 IEEE International Symposium on Information Theory (ISIT), pp. 3025 3029, June 2017.
Tsung-Jen Shen, Anne Chao, and Chih- Lin. Predicting the number of new species in further taxonomic sampling. Ecology, 84(3))798-804, 2003. ISSN 00129658, 19399170.
Maciej Skorski. Missing mass concentration for markov chains. arxiv preprinl arXiv:2001.083 03603, 2020.
Vincent Q Vu, Bin Yu, and Robert Kass. 401:4403-4060 2007.
Coverage-adjusted entropy estimation. Statistics medicine,
Kenneth W. ChChrhh and William A.Gale. Probability scoring for spelling correction. Statistics and Computing, 1:93- 103, 1991.
Geoffrey Wolfer and Aryeh Kontorovich. Minimax learning of ergodic Markov chains. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pp. 904-930, 2019.
Bin Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam, pp. Springer, 1997.
A Proof of Theorem 3
Consider rank-2, K K diagonalizable t.p.m P with stationary distribution π [mm тx] and spectral gap B. By the standard eigenvector decomposition for the rank-2 matrix P, there exist vectors [ug ug] and v = [mi ... ux]" satisfying the decomposition
1 0 0 1
P= RDS with SR
where R= [1 u). 1-3
and
π u.
Since is a t.p.m, we have, for 1 1 S K,
0 < P. = m Boru S 1,
(16)
where the notation ā A a.
Since P = RDS, we have pmv = RDS where ~~ is obtained by setting the x-th column in to zeros. Now, the matrix per, when diagonalizable, can be written as
pvr
Xi.z U. II
u.
(17)
14

---

Published in Transactions on Machine Learning Research (MM/YYY)
with
eigenvalues Ar _ 0. + B(L Ugul) + (-11)+1 Ao), )
(18)
right eigenvectors is = 1 + (1/2 [Sp + (-1)² [=] v,
(19)
left eigenvectors " NF = (1/) (11/2) A + (-1)* 8z) π ~r + (-1)² BTZ u ux)
(20)
for == 1,2, where A2 A 8 Uz and 8, - Tx + Brzug- We use u denote the vector u with w-th entry set 0. Note TU; x for 1,2, since NO p in the rank-2 case, not diagonalizable when both its non-zero eigenvalues equal Tz with only one non-trivial eigenvector and this case is handled separately later (refer lemma
The right and left eigenvectors of p are expressed in terms of and π (or ")) the right and left eigenvectors of P. However, the difference terms involve the eigenvalues and eigenvector coordinates, which need to be carefully bounded.
The following lemma contains important relationships between Ai, T5 and B.
Lemma 5. 1.
A. E [-(((1 - -2) + Paw), (3(1 ( n.) + Pax)], if f [0.
(21)
2.
Ag 11-(8+ (1 B)ooua), (8 (1- (1+())a)u B [1,2]
(22)
Me 1 1 - 2) i= 1,2,
(23)
where C3 = 3 for 3 E (0, 1], cB = 1 for 3 E [1,2].
4.
B²
Me S
Tz, i 1,2.
(24)
2(3 + 2)
Proof. See Scction
A.4
In the eigenvalue docomposition of P, let thw & uu for w, X. The following lemma bounds summation terms that typically occur in the analysis. Lemma 6. For x. X,
Σ xEX
(T))
W 1 I 3, for a. a. 1,,1,2,3,... and + + c
(25)
Proof. Sce Scction
A.4
Let J. A 1 (X = 1) - Tu Pr(N)(X") = 0) be the letter-wise bias of the GT estimator i.c. n E E (X") - MO(T, x"]] = EnEx Pr. To bound rg, we divide the alphabet X' into three sets,
Ao A ( X n. Pew). (iid-lkee
A(8) A (a X'
Ag : n. < 8), (infrequent)
A(8) {o X Ao n. 8), (frequent)
with 0 < 8 < 8/5. For 5= O((n)) n)) the letters in the A(8) are less likely to occur in X", than the letters in A(8), and contribute more to the missing mass Mo(T, X²).
15

---

Published in Transactions on Machine Learning Research (MM/YYY)
A.1 Case 1: Infrequent letters
Using 17 and the ensuing expressions in oblain
T3
(1ia)= (u,"1) (u, mz P Txdi,a)
+ (1/n) A=' [(,1,)) - (22,.))
E
(u
(ut m Pfe
(26)
[EE|B ifj
For I E A(6), we will show by careful analysis that Exen(s) [Tzl is bounded. The following lemma bounds the absolute value of the factors multiplying λi,z powers in the above expression for Tz when x & Ap- Lemma 7. For I E X Ao.
1. For i = 1,2,
(1)"1) (uç Pfz oi - nodiz) S A=? [4 (Iveal + TT) Tx + The A1 (1 )1.r)).
(27)
2. For i,j in (1 with i *
(ug 1) (uz Pf u5am)
S A== xg.
(28)
Proof. To prove Lemma we use the expressions for u. and ui in 19 and
20 to get
u 1 1 1+
Sz
i 1,
(29)
Nzdi =
(A + (-1) -)i,a)
Dg
(-1)tt1 Dr >1,e) B(TT + vzux)l
== 1,2. (30)
3.
1
"1
Phz U2
A1,z
n + ( ( + sn)
(31)
A
2
vx
=
A,
f x2
Tz + 2
(Ar - 8x)
(32)
Proof of Lemma Using
part 7
29
and
30
we have
(m4 2 mar
Le vsa Vix
A-2 (1/4) (A - 22) (B -M..)
+ (-1))=-1 (1/2) (A, + (-1)i-1sp) sz)) Te Di (1 - \i,a) B( + v ux
A-2
3 [v (B - >;,)) (1/2) (-1)² (An + (-1)-- -1)i-1sa)
(w) (TT + vruual
(-1)---1 (1/2) (A, + (-1)i-1 sz) The ds (1 )a,x)
16

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Using (1/2) (A,- Sx) Rx - )1, (1/2) (A, + 82) = Rx 22, along with Vez B2 13 S 1,
Tz S and |Rx S 1, we get
-2 (ur*1) "i 2v Ptz 2/ - n 1
Baar + +Tx) Tx + 2 Tx A1,r (1 )1,20)
(u²²1) u2 Piz U2"
22,00
-
4(1xbeel + Txx) Tx + 2 vi A1, (1 - )
Proof of Lemma part
Using (9 along with 31 and 322
we have
(u
1 1) (ui x Pfe
U/
A We
T - -(1-11 111-A1, + Vea \1,z - B
(di
A 2 Tx
ui " 1
U2
Pfe
U1
A 2
Ne
3 22,0
[1- Tx )2,x) + Dan
(dg)
S
A=² 2 Tan
where we gel (di) and (d2) using | S 1, Ar,
S 1, nT S and Weal S
Using 27 and 28 in to bound the absolute value of ra for x E A(0), we have
Tz S 2 (A1 A=² [4 (Iveal + Tz) T2 + 2 ne A1 (1 - {1.0r
+ (12/n) 3 [(>1,²)" (22,z)")
(br)
A - [4 (1vizal + TT) T (~1,.)) n--1 + nTz (2I,0)" (1 )1
+ (24/n) A=3 n
(22)
< 4 (1/n) A 2 (4//c)) (Ivanl + T.) + + + 6 A= Taa
(33)
where we get (b1) by using aA $ 1, = 1,2, and (b2) by using 23 along with maxpe(0.1) (1 -cp)"
min(e=>/(en), 1/c(n + 1)}.
We next claim that Ag bounded away from 0 for x E A(6).
Claim 1: A2 3/3, for A()).
Proof. Using Bu 2 -a from 16 we get
8 Te + B0 Uu 2 - 2T
4T Bunu 2 -4
Using the above in the expression for A
A (B गх Bu + 4T Bu where we use Ny < B/5 to get (a).
(8 2 )2 4m 32 437, 8115 32/9,
(34)
7
Using the above lower bound on AS for x E A(d) in 33
we gel.
Tg < 36 (1/n3²) (4/cp) (Luzal + T2) (e -e +188B) T..
(35)
Taking the sum of 35 over in A(0), get
(01)
Σ 2 < 36 (1/n89) (e-1 + 16/c3 + 34/3),
(36)
where we get (a1) by using ExeA(e) 7 1 and Lemma G ExEA(e) |Mezl
EmEx Idhal $ 1.
17

---

Published in Transactions on Machine Learning Research (MM/YYY)
A.2 Other two cases
When & A()), we require computation of the probabilities Pr(Na(X") 0) and Pr(Na(X")) = 1) occurring in the definition of Tz. Pr(NV((X) = 0) can be written as
Px(N)(X")) = 0) (a) (prejn-11 1 = (π 2) D (D)" gmm
b
T2 -(1 (1-10 B)TT (S RDDーー
1
(37)
Uz
where we get (a) by noting that the entry of the (K x 1) vector (P^*)*-1 1 corrosponding to any state E X is the probability of not passing through the state x in the next n 1 steps, given the present state is 2, (b) by using m1 = 1, π 0, and ul (x 1) can be written as
Pr(N{(X"))1) =1) = Σ
Pr Pm = Nx N =0)
Pr(Xm: x, Nx 0) Pr(N) = = x)
Pr(Xi = = Nx(x;)) 0) Pr(Xi = Nx = 0),
(38)
where we get (a) by using the Markov property, (b) using
Pr(X,, =2, N2 (X (X 0) Pr(X1=x, N (X?") 0)
(39)
and noting that Pr(N (X = 0 Xm = x) x Pr(Xi No (X (Xp-m+t) 0). Now,
Pr(Xi = x, N, = 0) = Tx Cx (prrym-1 1 = Ta en R (S RD) RD)m- 5m
[ - T
=T Big] (S""(S"" RD)m- m-
(40)
-ug
where 6x is 1 K vector with æ-th entry 1 and all other entries 0.
The expressions for Pr(N)(X") = 0) and Px"N 1) involve powers of the 2 matrix SRRD. Using the eigen decomposition, we find expressions for terms in powers of S RD and derive bounds for Pr(N>(X") = 0), Pr(N=(X**) 1) and Tzz|- This is done differently for the two remaining cases.
A.2.1 Case iid-like letters
Since Pzz TT + (1 B), Pax implies that un = 0 Uh = 0. For this scenario, the powers of S RD simplify as shown in the following lemma.
nz' 0
Lemma 8. 1. For x E X, with V2 = u2 = 0,(5~=RD)
=
0
B
For x E X, with Fg Pax = B,
(a) Us Ur + 0:
0
(S<*RD)²
-lu T.
(b) + 0, Ux 0:
(S RD)
0
18

---

Published in Transactions on Machine Learning Research (MM/YYY)
8. For E X, with Nx Pax # B,
(a) = 0, Ur #0. 0:
0
1
0
(S RD)
(41)
3
3x 8
1
(b) Ur + Ux = 0:
1
0
Bi
(8 (S*ERD)
3
(42)
B
0
0
Proof. Since SR = I, we have S R
Tx
and
U2 Uzz
Wx
Ux B(1 vaul))
S
(43)
Un
1. We substitute Urr = 0 in 43 and raise the power on both sides to I.
(a) Substituting U, 0, ue in we get S RD
Note that this matrix is
- Ux Te
not diagonalizable since both its eigenvalues are equal to Tr with [O
11" as the only non-trivial
eigenvector. Using induction on the exponent I, we get (S RDD'
W5 Tu W
0
(b) Substituting u, n. in 43 get S RD Tx
TT Tz
Similar to the above case,
π
this matrix is also not diagonalizable with both its eigenvalues lues ग. and [1 0 the only trivial cigenvector. Using induction on the exponent 1, we get (S RD)'
-m U Tx
nT
3. (a) Substituting = in 43 get gooRD
We observe that w., B are the
Mhr
0
eigenvalues of ~ RD with and
their respective right eigenvectors resulting in
[
the diagonalised form
T
-BT
(b) Substituting u₂ 0 in
we get Smar RD
We observe that म.. 3 are the their respective right eigenvectors resulting in
0
B
1
eigenvalues of RDRRD with
and
ne n
1
the diagonalised form in
Substituting the corresponding form of (5~0 RD) in 137 and 40 gives
Pr(N)(X")) = 0) na
(44)
=I, 0) (1 na m
Using the above in 38
get
Pr(N.(X") = n オτ n
19

---

Published in Transactions on Machine Learning Research (MM/YYY)
So, we have (in manner reminiscent of the iid case)
Tal = Ta (1 -z)" -
Tx
nz)" ( - nz) "= I T max p(1 - p11- = Tx O(1/n).
This results in the following bound:
Σ O(1/n). zE.A0
(45)
A.2.2 Case 3: Frequent letters
In this case, ax > 8 and the letters x are likely to occur multiple times. So, Pr(N)((")) 0) and Pr(N = will both be small, and bound them both. Further, since Pax Tay we have that un and Up * 0. For this scenario, the powers of SRRD simplify shown in the following lemma. Lemma 9. For E X, with Ux F O, ux + 0,
(A1,x) 0
O (22,z)
(S RDY V~r
(Vary-1
(46)
where V~-
D
Dr 8x
2B
2BT Ux
82 Nx B(1 U2 Ux))
Proof. Solving det(s RDD AT) O, we gel Ai, 0.5 T. 3(1 Un + (-1)++1Aa) i 1,2,
the cigenvalues of 5 RD with
(A, sn)/(23T,,0) 1 (A, + s2 (2 as their respoctive right
eigenvectors, where A = 3 + 43TT 8x = - - ((1-vxux) resulting in the diagonalised form in
46
Substituting the diagonalized form of RD)=- from 46 into
37
40
and simplifying, we get
Pr(N)(X")) = 00 (d1,z)" (A2,z)")
1
8x
(1 )m
(A2,z))
(47)
1=0
m mm-
Pr(X1 = Nx 0)
2 Ty
(A1x))-1 + (A2,0) m-
(A1,x) m-
m
+ nτ
8z
(A m- 2
2
1=0
(48)
Claim 2: |sa| <
Proof. Using | < 1, Te S and Be, Ur S TT from
16 in Se
=
-B+ Bu Ux we get |s S.
Using triangle inequality on the R.H.S of
gel
|8
Pr(N.(X") = 0) K
(1a nMh + (122,z))
+
Σ
2
2
1=0
IN5
0.5cAR + n|sz|
-0.5(n-1)cam
2
1 1 2
3n
c -0.5(n 1))0-
(o)
I+
3n
e u.. 1)c86
(49)
2
where we use (23) along with 1 S -= to get (a), e= and the above Claim get (b), and n. 2 8 for A()) to get (c).
20

---

Published in Transactions on Machine Learning Research (MM/YYY)
Claim 3: For in A(6),
I, Pr(X1 z, (x2") 0) S T. (1 (5/2) (m (0n-1) 1)) expf-(ng 2) oB 6/2].
Proof. To get the above bound, we bound
48 using cg002 (from (3) along with 1 Seet
(Claim above), Buuuusl S 1, and [dra S
Using Claim 3 in 38 we get
Pr(N.(X") 1) Σ
T2 (1 + (5/2) (m 1)) expl-(m) c3 6/2)
(1+ (5/2) (n m)) expl- - m 1) cg 8/2)
The g(n) expl-(t 33 ca 6/2),
where g(m) [1 (5/2) (n 1) (1+ (5/12) (n 2))] So,
T Pr(NN(X")) =) n. Pr (X*) = 0 - Pr(NN =1) n. Pr(N
(ppf- S Fx (())) expf- (n 3) os 8/2] + (1 + (3/2) n) expl-(n - 1) cs 5/2)
Summing over x in A(6) and using ΣxEd(0) nx S , gel
Σ
I S g(n) expl 3) cB 8/2) + (1+ n) expf-(n- 1) co 8/2]
(50)
#EA(()
A.3 Combining all cases
Taking the sum of 36
45 and 50 and choosing = (6/cg) (Inn)/(n - -3), we get
E - Mo( X">|| < 36 (1/n8²) (1 16/c3 + 18/3) + O(1/n),
for 3 > (0(lnn)/(n - 3) 1/2
(since < 3/5). This concludes the proof of Theorem
A.4 Proofs of some lemmas
A.4.1 Proof of Lemma 6
1. We first consider the case with 1.
(
(8)
Σ (Tx) l0bb l
Σ
T2
1,
ZEX
where we get (f) by using (pzzh vevll <
(from 16
and (g) by using T S Tz.
2. We now consider the case with O. Since +b+c 1, atleast one of b, must be 2 1.
(a) Say c 2 1.
(a)
Σ #
Σ
Wyrz
xEX
=Ed':0y==
(c)
2
Tz 5 2,
zE <0
NE <0
where we get (a) by using bharl, 1. px < 1 (from 16)). (b) by using Exex Wyyz 0, and (c) by using y/ I U. (from (16)
21

---

Published in Transactions on Machine Learning Research (MM/ (YYY
(b) Say b 2 1.
(a) -
Σ
1
105g
Σ Nowll
N +
Ver
xE <0
(1 B) +
xEAl:U2=<0 <0
(c)
1 1+2
Σ
nx S 3
DEX: <0
where we get (a) by using |M/aal 1yyzl S (c) by using- aa S we. (from (66
(from
(b) by using Σ Var (1 - B8), and
This completes the proof.
A.4.2 Proof of Lemma 5
To prove
21 we first start with the expression for A and bound it in the following way:
A [(1 - π2) - (1- - v2u=)] + 4(1 U2
[1 - nz) + (1- (1- - 02u,)] - B)( Tx - U2 Ux)
(
[8+ (1 ,) + (1 + + 226 - -B) + 2,8 ((3 - 2) (1 B)uzuz]
(6)
<
[8(1 - Tx) + P 1 + -5 + 28 B)) + 28TT - 2) + 2,8T -1-10 T2) (1-T22
[8(1 )²) + Pa.! - B (3 1)
[3(1 - n.)) + Pax] 1
where (a) follows by using 1(1 - Tx) + (1 - 3) 1 ]]² 18 (1 (1-111110 11--)) 3)TT + (1 3)e, Ux + BTg - 2] and
simplyfying, (b) follows by using Pa. = nr + (1 - 3),, (1 (1- B) I 11-1 T from (6 and (c) follows from
B < 1. Since B(1 - π2) + Paw 2 O, we get AS E (- - TT) + Par), (8(1 - nz) + Pax) ). This completes the
proof of (1
To prove
22 we again start with the expression for A but bound it in a different way as shown below:
A
[[1 π.) - (1- - B) - u2 )1 + 4(1 - B)muuzu
[8 + (1 -3)ez Ux nz| + 4(1 T. Ma
[8 + (1 3) -,,TT + + + 2(1 Unll
(a)
[B + (1 B) 2,3TT + n + 2 Tx)
3) [B + (1 3)u, uz 12 + 2T 13) n
=
(
< [B (1 - |rv
where (a) follows by using (1 8)r,4, S n₂ from 16 and (b) follows from B 2 1. Since B 3+1 (1 u
is positive for 1, we get A. (- + (1 f),, (3 (1 B)u,,u)) This completes the proof of 22
Using (21 and 22 in the expression \1,x ((1 T2) + (1 (1 Ux) (- 1))++ i 1,2, we get
Ni,r < 0.5,3 3 E [0,1] and Air < 1 - 0.5mz B E [1,2] for i = 1,2. Using 342 < g for 8 E (0. 1 and
8²
g2 2 for 3 E [1.2] completes the proof of Lemma 5
B Proof of Theorem 4 Upper bound
In this appendix, we provide proof for the upper bound in theorem
22

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The minimax risk R, (P2.3) is upper bounded by the worst-case risk (over P2,3) of the Good Good-Turing estimator. Our next lemma gives expression for the MSE of the GT estimator.
Lemma 10. Consider a stationary Markov chain X" with state distribution л. Let Q7(a) & Pr(N)(X")= = a). =
and Q a.y (a, b) & (x") = a, (x*)))= b) for x, y E X and a, E 1....
EI(Mo(TT, X") - MXTT(""))
Σ
2 T (0) (1/m)² 2201
E Σ
T
2 (1,1
(51)
xy
n²(n 1)
ZEX
FEX yEA
where 2y
- Fy Qa (0,0) (T (1, + F5 2 1)) + mi- (1,1)
Proof. Substituting Mo ,T = ( = 0) and (x*( = (L/n) Emex ((N, = 1) into FI(Mo(X""; ,T) - -MOT (x*))
(N2 [ and taking expectation of each term in the square of the summation,
(Um) 27
EI(Mo -
1000 ) = E
To = 0) - O)) zEX
Σ
Σ
2 Pr(Ns = 0) + (1/n)² Pr(N2 =1))
x zEX
ΣΣ
Tray N₂ -0) - n
-ry = N, 0)
z ZEX yE
1
T.Pr(N 0,Ng = =1) +
Pr(N2 = N2 1)
n
n²
Σ
Tz (7 + (1/n) 2201 - Σ Σ
22 22 (1.1)
n²(n 1)
E
Σ
Ta 27 (0,0) - (TT Qn (1, 0) + T (7,,
xEX yEA
+ n(n 1) 2x (1.1),
(52)
where we get (a) by expanding 1/n²² as 1/n² Ii--Ij In- 1I and using the definitions of Q% Dr
(a, b).
Using the definition of T z,y in 52 completes the proof of
To bound El(Mo - N)), we begin with the following expression for (1).
(1) = Pr(No(X")= = 1) = Σ Pr(Xi= = Xm S Σ
Pr(Xi= = no
(53)
1=1
This implies
(1/n²) (1) 1/n
(54)
xx
Similarly,
Q (1,1) Pr(N, = N2 1) Σ
Σ
Pr(Xi, x, xI, = y, + x
# (1,12)
h= 4
+ R-1
Σ
Σ
Pr(X, = y, X1, = = Xm # 26, N. m # 4,
(55)
1=
23

---

Published in Transactions on Machine Learning Research (MM/YYY)
For 12 > 1 2 1,
Pr(X,, 2, X12 = y, Xm # I Pr(Xt, I, X1, =z)
ax Pr(X(, 1/ X1; = x)
(56)
Similarly, Pr(Xi, y, X12 = I, X 2
S Ty Pr(X12 =x|X1= v)
(57)
Plugging 56
and 57
into 55
(1,1) $ 2-1
Σ Tz Pr(Xi, = X1, = x)
1=112=1++1
Σ
Σ
Ty Pr(Xi, x|X1, = y)
1114=
Since Exex EvEx Tr Pr(Xi, = r) < Exex To S 1, we gel
EvEx /xEX uto Q8 0g,(1,1) & n(n - 1). Therefore,
Σ E ZER yEX.y#
(2 S 1/n
(58)
n²(n-17
To bound Exex n (0), we consider the sets Au, A(0) and A(o) (with 0 S 6 < 3/5) defined in section that make up X.
For A(6), have
n-1
()) PX(N = (1/2) (A1.z) "+ (22,z)
(sx//2
Σ
(A1,z)
1
1=0
from 47
Since the claim 1 (in section A.1
implies A1 - 122 = Ao > for x E A(6), 8 E (0,2), we get
-a-d (22,)' A. (d(() (Xe x A(d)
(59)
1=0
Substituting (5 in and applying triangle incquality on the absolute value of the R.H.S, we get
[sal
(0) <
+
(1Ai,al)" + ((A2,xl)')
Ar
+
Ar
8z
(1-
(1
C3
2
nm
1 +
3
(1
Cf
2
(60)
where use 23 to get (a) and the claims 1 and 2 from section A to get (b). Therefore, for A(0).
Σ
THZ (0)
(a1)
1+ B
Σ T
(1
C3
Tx
2
zE)(6)
x(A(8)
(b))
2 1
9
(1/ncs)
Σ
(c)
2 1 9 0) (1/nce)
(61)
3
B
xEA(6)
(1- n+1 )" S on
where we get (a1) by using 60). (b1) by using maxpe(0.1) P (1-cp)) c[++1]
and (c1)
by using Exe मं 1 1.
24

---

Published in Transactions on Machine Learning Research (MM/YY MYYY
For A()),
(az)
(1+
3n
(e))
(1
3n
Σ TZ (2(0)) xEA(6)
[+
e 0-..((n-1)cp
1)036
Σ
2
1+
e-0.5(n-1)es)
(62)
2
xEA(6)
where we get (a2) by using 49 and (c2) by using E ExEA(() Tx
S 1.
For Ao(o),
T (0)
(ag)
Σ
Fz (1- nz) n
(bp)
1/n
Σ Te
(co)
S 1/n
(63)
Ao
Ao
where we get (an) by using 44 (bu) by using maX)E((01) P (1 [1p))" p)"
1
(1-nta)
n+1) )=
1 and (co) by
(x+1)
using Exe Ao I 1. Since X' A(0) A()) Ao.
Σ
T (7)
Σ
TH (2(0) + Σ 2 (2(0) + Σ
2 "e (0)
ZEX
zEAo
SEA(S)
AEA(()
(0)
9 9) (1/ncy) + 1+
3n 2
1 1/n + 2
1
e 0.5(( 1)cz6
where we get (a) by combining 61
62 and 63
Choosing 8 (8/cg) (In (Inn)/(n - 1) and using
1, we get
9 3) (1 (1/nes) + 0(1/n),
Σ _ (0) S
(1+g)
1+
(64)
xEN
where C3 = 3 for 3 E (0, and c3 = for 3 E [1.2].
To bound Exex Enex my we divide {(x, v) X, X, + y} into two sets:
B(6) ((x,1) k.y E X, * v, nं + < 6}
B(5) A ((..1) x,y E X, x y, Tu + Ty 2 6}
with 0 S 5 < 3/5. Similar to the sets A(8) and A()), defined in section A the ordered pairs in B(6) have atleast one frequent letter that is likely to be seen in X", while the set B(d) contains ordered pairs of rare letters that are less likely to be seen in X and hence contribute more to the missing mass Mo(TT, X").
In the following lemma, we provide bounds on Thy for (I,y) in B(8), B(O).
Lemma 11. For a rank-2 diagonalizable l.p.m P with spectral gap B, and E 8/55)
For (x,y) in B()),
(
8²
n-2
Thy I day (1/39) (To + Tyy
(xx + TTy)
2(3 + 2)
2(3+22
+ Gzy (1/ngl) 1+
6
(65)
-1n
3(n
2. For (I, u) in B()),
B²
Im S dh O(n²) exp {
(n 5)
8)
(66)
2(B + 2)
25

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where the positive constonts Qay Aay. and d'y such that ((a))x lay Eiewexx day and E(eoeex> d'y are constant. u.r.l. Tt.
Proof. We get 655 by using method similar to the upper bound the letter wise bias Tz; for infrequent.
letters, in section A.1 660 is obtained by following method similar to the upper bound T for frequent
letters, in section A.2.2
J
We first the bound the sum of Tyy over (z,y) in B()) using (65)
(B+2)
Σ
T
2 Lay
Σ
lay (1/nBt)
3(n - 1) 1 +
(6 -
(z)))EB(6)
(2.))E((8)
(z.))e
IA In3
(B+2)
Σ
dau)
Σ
(2
n2g4
30 -
(2,0)EX²
(x.N)E
O(1/n55),
(67)
cp)m~2 (c))))) dn-1)): (b) by using E(Ene by S (awsex Ixys E(aw) day SE Kays and (c) because [(an)ex> Jav. E(awjex> Lay are constant w w.r.t. n.
where get (a) by using maxpejo.jjp(1
Similarly, we get
Σ
T S O(n²) exp { (n 2(B + 2)
((
(8+2) using 66 Choosing 8 8 (x-5)
In n, we have
Σ ((1))
Tot S 0(1nn).
(68)
Combining 67 with 68). we get.
Σ T < 0(1ng3)) #EX yyy
(69)
Combining 54
58
64
and
69
to upper bound
51
completes the proof of the upper bound on R (P2.a)
in Theorem 4
C Proof of Theorem 4 Lower bound
To prove the lower bound on (P2.9) in 10 we use the Cam method. The standard Le Cam method
Yu 1997) is for estimating constant parameters of distribution whereas Mo(Tr, X") is function of both the distribution and the samples. To get (10), use the following extension of Le Cam method for estimands
that depend on both the distribution and its samples.
Le Cam lower bound for estimating random variables: Lot Q be a family of distributions over an alphabet y and Y be a random variable distributed according to Q E Q. Let 0(Y, Q), taking values in a pseudometric space with pseudometric d, be a function of both and the distribution Q. We assume that the D is bounded i.e. the distance d(u,v) v) between any two points u, v D at most A. Let d(D1, D2) & minuED,,eDD, d(u, v) be the distance between the subsets D1, D2 of 'D Let ō(Y) be an estimator for 0(Y, Q) and co Q) denote the convex hull of @
The following lemma provides lower bound on the worst-case risk (over Q) of any estimator î(Y) for Q)
26

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Lemma 12. (Chandra et al. 2022 Lemma 5) Let 11, D2 be two subsets of D, and Q1, Q2 be two subsets of
Q such that for any Qi E 2i O(Y, Qi) E Di with probability at least 1 - 6; i= = 1,2. Let 5 _ d(Di, D2)/22 and 11Q1 A Q2ll A 1 - 1Q Q2llTV denote the affinity of the two distributions Q1 and Q2. Then
sup Fid00(), 2 8 qee
sup (.)
|1Q1 11Q Qalll (e1 +2)
(70)
To prove the lower bound 10 in theorem we apply Lemma 12 P2,9, the family of rank-2 diagonalizable t.p.ms with spectral gap 3, using two specifically constructed t.p.ms E P2, that are hard to distinguish.
We first prove
110) for B E (0, 1.6).
1-61 61
RR) 1ixk-1 (2-52)/Rt 1K-IXK-1
Let P61
be a K x K t.p.m paramcterizod by 61, 82, with 1ixk-1
82 1x-Ix1
and 1 --1x1 denoting the row and column vectors with all entries 1, and 1 - denoting the K 1 x K -1 matrix with all entries as 1.
Let P1 = { and P2 = [P2} be two subsets of P2.9, where Pi = Pl0.53,0.33 0.53], P2 = P
a, 0,5. + a] are two t.p.ms on the alphabet (1,2,..., 13 with क = 0.5 [1 (1/L)l1x1] and n² = [0.5 + (a/3) (0.5-(a/) (a/5))/L 11x1] as their respective stationary distributions. For cach element of P2 to lie in [0, 1] and each row of Pg to sum up to 1, we require that a I min 1 0.533. Both P1 and Pa have the same spectral gap 33 (and hence E P2,3) and a, L. are choosen appropriately to get the best lower bound on R2 (P2.0).
For i == 1, if X" is stationary Markov chain with t.p.m P., then Mo(X", TT.) satisfies
(a)
- Mo(X", n.))
2
0.5 0.5 (i (i+ 1) I(N, #0)
(71)
1 Mo(X", n.)
(b)
S
0.5 (i (i-11 1)
I(N, #0) + n T 0.5 (i (i-1) (1-1)
(72)
Le. Mo(X", )I;) E
0.5 0.55 (i (1
3 (1-²) (0.5- -0-((i-)) (0.5-(i-11 (1-1) 1
a
with probability - 0.5 (i a 1) (1- 8 - (i-1)a)
n-1
(73)
2
where we get the bounds in (a) and (b) by considering the cases : (1) the letter 1 occuring in all the samples X" and (ii) all the n samples. X", being distinct with the letter occurring only once, respectively. We get
the confidence interval in (73 by using the bounds in 71 and 72 in the event of the letter occurring atleast once.
1,2, are non-overlapping. Using lemma 12 with Q = P2.9. Y = _=."000 ((Y, Q) Mo( I X" X"), D. = 10,1),((u,v) = (u v) 1, Q. = Pi.
Let 0.53n/L, so that the above confidence intervals in 73 for
and D; as the confidence interval in 73 for i = 2, we get.
sup E[(M((X)) - (ooTT.X))) 2 0.5 PEP
a
n 2L
[IP((") A [IP(X""A PX(")|I - 1 88
(74)
B
Our next lemma gives an upper bound on the total variation distance between Px(X) and P2(X").
Lemma 13. For the t.p.ms P2, E P2,9, constructed above and X being a stationary Markov chain,
[1((X" - S (V2a/3) ("
1 (050mnm - -2)33 0.5
0.5(n
(75)
1- - 0.5,3
Proof- Section C.1
27

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Since
Pi (X*) P2(X")) = [P((X)) lax using the above Lemma to lower bound the R.H.S
in
74
we get.
sup ("MM((X")) - X=))
2 0.5
a
1 (v2a/3)
1+ 0.5(n - 2)
PEP
2L
1.0.8
1
n-1
(76)
2
0.5
Substituting a
1+0.5(n 215 and L, = e in 76 completes the proof of 10 for 8 E (0, 1.6)-
1-0.58
2/2
We now prove where
10 for 3 E [1.6,2] 2|.
Let Pf = {P]} and P/ = {Pa} two subsets of P2.9, with 3 E [1.6, 2].
3
0.5(3 1)
(0.5(3 L) lixL
Pl
1 11x++1
1++111+
3
0.5 - 1)
((0.5(8 1) - - 11xE are two t.p.ms on the alphabet
P/- 11x++1
0++1I1+1
(1, 2, ...., L+ with q| = [1/3
-,5B-11)/ 0.5(8 - 1)/BL 11x1] and
(05(B-1)-a)//33 1ıx1] as their respective stationary distributions and 0 0++Ix being the L+1x L+ all zero matrix. For each element of P/ to lic in [0, 1] and each row
T = [1/3 (0.5(3 1) + a
of P/ sum up to 1, we require that a' S min - 1), 0.5(3 - 1)). Both Pf and P3 have the same
spectral gap (and hence P) and a', L are choosen appropriately to get the best lower bound on R2 (P2.0).
Following method similar to the proof of 10 for E (0, we get
a' n
2 (B 11)
sup EI(Mo(X") - Mo(T, 2 P'EP'
-
(77)
2 8
2LB
Our next lemma gives upper bound the total variation distance between P((X") and PA(X").
Lemma 14. For the t.p.ms P1 Pg E P2.3, constructed above and X being a stationary Markov chain,
P s V2na'/ (BB31/
(78)
Proof. Section C.1
Using the above lemma lower bound the R.H.S in 77 and choosing a' 0.5 /2n, L e. completes the proof of [10) for $ [1.6,2].
This completes the proof of the lower bound on R, (P2.3).
C.1 Proof of Lemmas 13
To show the bound in 75 we first bound the total variation distance between Pi(X") and P2(X by the KL divergence D (Pi(Pi(X*)) (PXX))))((X") using Pinsker's inequality.
Lemma 15. Pinkser's inequality (Boucheron el al. 2013, Theorem 4.19)
[XP((X)) - PA(X") <
22 (DL((P((X))[IPPXXX)
(79)
where DxL(P(("))IP(XX))) is the KL divergence between Pi(X)) and Pz(X").
Our next lemma expresses DKL DKL(PI (PXX)))))))) terms of the KL divergence between the stationary distributions ni n2 and the KT. divergence between the corresponding of P and Pz.
28

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Lemma 16. For any two t.p.ms P1, P2. X, with Ti, n2
their respective stationary distributions,
DKL(P(((")1I3(("")) = (TI(TTIlTT)) + (n-
Σnd (KL(P)(tz)) P2(+(z)
(80)
TEX
where P:(-)x) denoles the row of the l.p.m Ps; = 1.2, with Irunsition probabililies from the slate x.
Proof. Let xn & (21, E X..
DRL(R((""|IB((X"))
= Σ Pz( In(P((("//P3(=")
Pi(x = ri X/ = x1-1)
Σ P1( In /
In
P2(Xi ri X1-1 x1-1)
E
1=2
( (TI(T(|/22)
+ Σ P(()) In
P((z))
Pi(i - x X1-1 x1-1 Pa( zi X1-1 =
I=2 diex
(KI(Til
P1(X; = xn X1-1 = 17-1)
Σ -1.=-1 10XI=1XX1111 = x1-1) In
Pa(x; = xi X1-1 = I1-1)
1=2 #t B1-1NEEN
(KL(mll T2) + (n-1)
Σ xEX
The (KL(PI((IZ) Pa(+z))
where we get (a) by using the Markov property P((x")= =T,;, = 21|Xi11 = =
i == 1,2, (b)
and (c) by appropriately marginalizing Pi (1x)..
C.1.1 Proof of Lemma 13
Using the values specified for Tız. Pi(22 = y|X1 = x) for I. (1...,, 1}, i i= 1,,2, in the section C we get
(KI(TI][Te) -0.5 In (1 4a² 1B²
Dxz(Pi(-1)) || Pa(+L)) = -155) In (1 +1+ a1- - 0.5 8 In (1 - 2a/3) (Ku(Pi (-I=) || P2(+))) = --(1 0.5.3) (1 - a/(1 - 00553)) - 0.5 8 In (1 + 2n/ /8),
for x E [o....,,111,
Using the above three equations in
80
we get
Dxr( (X)x))()))(
-05 (n- - 1) [(1 0.5,3) In (1 - a²/(1 (1-5)))))) + 0.5 3 In (1 - 4 13)]
=
- 0.5 (1 - 4a /82
a²
+2 a
+ 4 a²
a²
(n 1)
+ 0.5(n 2)
0.5.
f2
32
0.5.9)
where we get (a) by using the proof of Lemma 13
In(1 x) S 2z, for x E (0, 0.5). Plugging the above bound into completes
29

---

Published in Transactions on Machine Learning Research (MM/YYY)
C.1.2 Proof of Lemma 14
Using the values specified for Thay P.(22 - y/|x = x) for x, y E {I,..., + 2), == 1,2, in the section
we
get.
(3-1)
2a' 2
DKI(Fi||TT2)
In 1
2,3
20x 2
(xI(P(((11) I| P(((1)) -0.5 11) In
3
1
(xI(P(((()) |I P2(+(x))
for (2..... T. + 2}.
Using the above three equations in 80) and following a method similar to C.1.1
get 112((X
Pa(X")]lvv /2naa /3(3- - 1). This completes the proof of Lemma 14
30


Reviews:
[{"review_id": "9ACd9ALmww", "reviewer": "Reviewer_3aVP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. Contribute towards a fundamental problem in statistics.\n2. Illustration of theoretical claims with numerical evidence.\n\n**Weaknesses**\n1. The discussion on the relevant literature is largely insufficient.\n2. Conditions in Theorem 2 seem rather artificial and are challenging to verify in general. This is acknowledged by the authors at the beginning of Section 3.3.3.\n3. The argument proposing that the rank of the transition matrix captures the minimax sample complexity is not convincing.\n\nPlease refer to the comments in the “Requested changes” section for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of missing mass estimation in a Markovian setting. Namely, from a single trajectory of length $n$ sampled from an unknown transition matrix $P$, the goal is to estimate the stationary mass of yet unobserved symbols.\n\nThe authors consider the popular Good-Turing (GT) estimator, which has been analyzed extensively in the iid setting.\n\nContributions:\n1. Propose sufficient conditions for the GT estimator to converge to the missing stationary mass and bound the absolute bias of the GT estimator in terms of some properties of the transition matrix.\n2. Propose an analysis of the minimax sample complexity over the class of rank 2 Markov chains with prescribed spectral gap.\n3. Propose experiments based on both synthetic data and existing text corpora.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Major**\n\n1. Increase the discussion on prior work on the topic of missing mass estimation in the Markovian setting. What estimators were considered? What was their limitation? How does the present study improve upon them? For instance, how do the approaches, assumptions and results compare with Chandra et al. [2020, 2022], Skorski [2020]?\n\n2. Are there connections between the missing mass problem and the notion of surprise probabilities analyzed in Norris et al. [2014]? If so, could the authors discuss these connections? \n\n3. The idea that the rank of the transition matrix should control the minimax sample complexity is not convincing. The rank is a brittle property. A randomly infinitesimally perturbed uniform matrix (iid) will have almost surely full-rank while we should not expect the statistical problem to become significantly larger. This makes the definition of the minimax problem over this class of chain rather unnatural.\n\n4. In Theorem 4: can the authors make precise the statement “for $n$ sufficiently large”? Is the constant $c$ universal?\n\n5. Can the authors put forward natural reasons for a transition matrix to enjoy rank 2 (beyond mathematical convenience)? Is there a probabilistic interpretation? For instance, reversibility of a Markov chain is also brittle, but many physical processes obeying are thought to be reversible in nature.\n\n6. At the top of page 3, the authors argue that taking a thinned Markov trajectory, where observations are spaced by the order of the mixing time, would overestimate the missing mass. Leaving out the problem of obtaining a bound on the mixing time, sub-sampling is not a necessity for estimation problems; the mixing time or the inverse of the spectral gap often simply enters the sample complexity multiplicatively. See for instance Paulin [2015, Proposition 3.16.] for the problem of estimating the stationary distribution.\n\n**Minor**\n\n1. On page 3, the authors seems to make a distinction between behaviors they would expect for small mixing times and large spectral gaps. However, at least in the reversible setting, both are known to be closely related. It is not clear why the authors have decided to make such a distinction.\n\n2. On page 3, could the authors give a reference as to how to obtain $\\sum_{x \\in \\mathcal{X}} \\pi_x^2(1 - \\pi_x)^{n-1} = O(1/n)$. For\ninstance, please point to some analysis in the iid setting.\n\n3. The minimax problem in framed in terms of a stationary start. Could the authors comment on this assumption, and how it might be relaxed to an arbitrary starting state?\n\n4. The authors should consider moving Section 5, Section 6 and Section 7 to the appendix and dedicate a section to summarizing the SOTA in the Markovian setting.\n\n5. Please only number equations which are referred to somewhere in the manuscript.\n\n6. Small typo: p.8 in the footnote “Pubilc”.\n\n**References**\n\nP. Chandra, A. Thangaraj, and N. Rajaraman. Missing mass of markov chains. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 1207–1212. IEEE, 2020.\n\nP. Chandra, A. Thangaraj, and N. Rajaraman. Missing mass estimation from sticky channels. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 910–915. IEEE, 2022.\n\nJ. Norris, Y. Peres, and A. Zhai. Surprise probabilities in markov chains. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1759–1773. SIAM, 2014.\n\nD. Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. 2015.\n\nM. Skorski. Missing mass concentration for markov chains. arXiv preprint arXiv:2001.03603, 2020.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "f3rMrYDuQH", "reviewer": "Reviewer_Yr9V", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. \n- The problem studied is fundamental. \n- The paper is quite complete in the sense that it provides estimation error bounds, characterizes the minimax error for rank-2 Markov chains, and conducts empirical studies on real data. \n\nWeaknesses. \n- I wonder if the problem formulation is appropriate. \n    - Considering that most known results for the Good-Turing estimator pertain to the i.i.d. case, it also appears natural, if not more natural, to propose a generalized estimator in the Markov case that reduces to the GT estimator in the i.i.d. case. \n    - I am not an expert of this topic. It appears that there are other definitions of the missing mass for the Markov case. For instance, the definition of missing mass proposed by Skorski (2020) also looks reasonable\n    - This paper justifies the significance of missing mass estimation in Markov chains only via citing existing papers for the i.i.d. case. Please verify that those significances carry over to the Markov case. \n- The correctness of Theorem 2 is unclear. After establishing the bound $E[ \\hat{M}_0^{\\text{GT}} ( X^n ) ] - E [ M_0 ( \\pi, X^n ) ] \\leq c$ for some $c > 0$, the paper claims that the bound $E [ M_0 ( \\pi, X^n ) ] - E[ \\hat{M}_0^{\\text{GT}} ( X^n ) ] \\leq c$ can be similarly proved, yet provides no details. The derivation of the second inequality is not apparent.\n- The meaning and necessity of Lemma 1 are unclear to me. Lemma 1 is not used for deriving later lemmas and theorems. Lemma 1 surely justifies the GT estimator for the i.i.d. case, but it is already known that the GT estimator is good for the i.i.d. case. \n- Assumptions in Theorem 2: Regarding Theorem 2, it is unclear if the condition $n > n_0$ is required, as well as $n > 4$ for the first bound and $n > 6$ for the second bound.\n- Theorem 2: It appears unclear why \"we expect such left and right eigenvectors of $P^{\\sim x}$ to be close to those of $1 \\pi^{\\sim x}$ and the Perron eigenvalue of $P^{\\sim x}$ to be close to $1 - \\pi_x$\". \n- Comparison with exising literature does not appear to be complete. (See the requested change for p.2 below.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Consider the problem of estimating the missing mass of a Markov chain given random variables $X_1, \\ldots, X_n$ following the chain. This paper derives estimation error bounds for the Good-Turing (GT) estimator, showing that they recover the known $O ( 1 / n )$ rate for the i.i.d. case and providing sufficient conditions for the error bounds to vanish as $n \\to \\infty$. In addition, for the special case where the transition matrix is of rank 2, this paper provides a $\\Omega ( 1 / (n \\beta) )$ error lower bound and proves that the GT estimator satisfies a $O ( 1 / ( n \\beta^5 ) )$ error upper bound, where $\\beta$ denotes the spectral gap.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please justify studying the standard GT estimator for the Markov case. \n- Please justify the definition of the missing mass studied in this paper and its significance. \n- Please elaborate on the meaning of Lemma 1. \n- p. 2: Please provide more information about the \"forays towards missing mass estimation from Markov chains.\" In particular, please compare them with this paper. \n- Theorem 2: \n    - Please provide the proof details and check if there are missing assumptions on $n$. \n    - Please justify the conditions on the transition matrix $P$. \n- Typos: \n    - p. 2: worst case -> worst-case. \n    - p. 3: how GT estimator... -> how the GT estimator...", "broader_impact_concerns": "N/A. This is a theory work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NPoQikdwFB", "reviewer": "Reviewer_25AQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- I believe that the work certainly contains novel contributions. To the best of my knowledge, missing mass estimation has primarily been done for iid samples. The extension to Markov samples is of practical interest as most data cannot be modelled as an iid stochastic process, so the Markovian assumption brings us closer to reality. \n\n- The paper is also fairly well written and the results are easy to understand. It is clear that the authors have put in a great deal of effort to explain their contributions as lucidly as possible. \n\n- The bounds, while not tight for the case of rank-2 Markov chains, are the first step to understanding this problem and serve as a starting point for others to build on. The proof techniques are rather novel, from what I can tell. \n\nWeaknesses:\n\n- The reviewer did not really get how \"a chain with non-zero, constant spectral gap\" results in the GT estimator failing to converge. Presumably, this is done via the experiments, but using the experiments to illustrate this counterexample is not particularly illuminating. Can the authors use an analytical example to make this point?\n\n- The authors also claim that they demonstrate through examples that the GT estimator fails to converge to the true missing mass for Markov chains \"whose mixing times are 2 or 3\". First, the notion of \"mixing time\" has not been formally defined. There are different definitions for this, and they depend on some $\\epsilon$, Second, what is so special about the (integer) numbers 2 and 3? Mixing times can be non-integer-valued. Third, the demonstrations are again empirical. Having an analytical demonstration or counterexample would be clearer. \n\n- Of course, there is a big gap between the minimax upper and lower bounds; they depend on $1/\\beta^5$ and $1/\\beta$ respectively. I suppose the authors conjecture that the upper bound is loose due to their experiment in Section 3.3.1. How can it be strengthened? \n\n- I would usually imagine that the chain is fixed so that $\\beta$ is constant. It is rather strange that the authors discuss the case that $\\beta$ varies with $n$ below Theorem 3. What one would do to find the right dependence on $\\beta$ is to consider several chains, with different $\\beta$. Run the GT estimator on each of the chains. Estimate the dependence of the minimax risk on $\\beta$ from the different experiments. Currently, the authors are looking at a single chain parametrized by $\\beta$ and varying $\\beta$ as a function of $n.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a classical problem of missing mass estimation via the Good--Turing estimator but for Markov samples, instead of the usual iid case. Bounds on the bias and squared error risk are derived and shown to be dependent on the convergence rate of $(P^{\\sim x})^n$ over all $x$ that contribute to the missing mass. Additionally, for rank-2 Markov chains, the authors show bounds on the minimax risk that depend on the spectral gap $\\beta$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please consider the comments above.", "broader_impact_concerns": "NIL", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is one minor concern raised by Reviewer 3aVP, that the authors should address in their revision. I am copying the reviewer's comments below:

> The authors make the following claim: "The minimax rate of missing mass estimation for Markov chains will depend on the rank of the t.p.m." This claim is backed up by the experiment which is illustrated in Figure 2 (right), for the GT estimator. In their experiment, the authors construct a family of chains whose rank can be controlled by a parameter L. They show that increasing L leads to different decays of the MSE with respect to the sample size. However, besides increasing the rank in their construction, they are also changing other properties of the chain, so that it is difficult to see that it is really the rank that matters. 

Please acknowledge and clarify this point in your revision.
Decision: Accept (poster)