Two new Markov order estimators
- 格式：pdf
- 大小：181.48 KB
- 文档页数：15
a r X i v :m a t h /0506080v 1 [m a t h .S T ] 4 J u n 2005Two new Markov order estimatorsYuval Peres 1and Paul Shields 2February 1,2008Abstract.We present two new methods for estimating the order (memory depth)of a finite alphabet Markov chain from observation of a sample path.One method is based on entropy estimation via recurrence times of patterns,and the other relies on a comparison of empirical conditional probabilities.The key to both methods is a qualitative change that occurs when a parameter (a candidate for the order)passes the true order.We also present extensions to order estimation for Markov random fields.AMS 2000subject classification:Primary 62F12,62M05;Secondary 62M09,62M40,60J10Key words and phrases:Order estimation,Markov chains,Markov random fields,recurrence.1IntroductionFix afinite set A and let x n m denote the sequence x m,x m+1,...,x n,where x i∈A.A stationary,ergodic,A-valued process X={X n}is Markov of order M=0if it is i.i.d.,and Markov of order M>0if M is the least positive integer such that P(a k+1|a k1)=P(a k+1|a k k−M+1),for all a k+11such that k≥M.A consistent Markov order estimator is a sequence of functions M∗n:A n→{0,1,...},n≥1,such that for any M and any Markov process X of order M,M∗n(x n1)=M,a.s.limn(Here and throughout,“a.s.”always refers to the distribution P=P X of X.)In this paper we introduce two new Markov order estimators.Both use test functions that depend on the sample size and a candidate k for the order.The key to our methods is that as k increases,our test functions exhibit a qualitative change of behavior when k reaches the true order.Our estimators use the empirical frequencies of overlapping blocks,N n(a k1)=N n(a k1|x n1)def=|{i∈[0,n−k]:x i+k i+1=a k1}|.(1) The corresponding empirical probabilities and conditional probabilities are P n(a k+11)def=1Theorem2M#n(x n1)is a consistent Markov order estimator.A more general form of Theorem1that allows any entropy estimator with a known rate of convergence is given in Section2.An extension of Theorem2to Markov randomfields is given in Section3.1.Connections to other model selection methods are given in Section4.Careful proofs of Theorems1and2are given in Sections2and3,respectively. For the reader’s convenience,wefirst present sketches of the proofs.Sketch of proof of Theorem1:The2(log n)−1/4term incorporates the rate of convergence of[ℓ(n)]−1log n and that of h M(n)to their common almost sure limit, the entropy H(X)of X.Thus h M(n)≤[ℓ(n)]−1log n+2(log n)−1/4,eventually a.s., whence M∗n≤M eventually a.s.On the other hand,if k<M then h k(n)converges a.s.to the k-step conditional theoretical entropy H k(X),which exceeds H(X),the almost sure limit of[ℓ(n)]−1log n+2(log n)−1/4.Therefore M∗n≥M eventually a.s.Sketch of proof of Theorem2:If m<M then there exists a M+11such thatP(a M+1|a M1)>P(a M+1|a M−m+11),and henceφm(x n1)grows a.s.like cn,for somec>0.Thus M#n≥M eventually a.s.On the other hand,classical large deviations theory shows that for anyǫ>0,we haveφM(x n1)=o(n1/2+ǫ),a.s.,so M#n≤M eventually a.s.2The entropy estimator method.Wefirst review some elementary facts about entropy,see[3]or[17]for details. The conditional entropy of the next symbol given k previous symbols is defined byH k=H(X k+1|X k1)def=− a k+11P(a k+11)log P(a k+1|a k1).The sequence{H k}is nonincreasing with limit equal to the entropy H=H(X)of the process.Furthermore,the process is Markov of order M if and only ifk<M⇒H k>H(X)andk≥M⇒H k=H(X),that is,if and only if H k reaches its limit H exactly when k=M,see[17,Thm I.6.11]. The conditional k-th order empirical entropy h k(n)is defined by replacing theoret-ical probabilities by the corresponding empirical probabilities.The ergodic theorem implies that for kfixed, P n(a k+11)→P(a k+11)and P n(a k+1|a k1)→P(a k+1|a k1),each with probability1,and hence that h k(n)→H k,a.s.Furthermore,in the Markov case we have the following iterated logarithm result.Lemma1If X is Markov offinite order M then for each k there is a constant c k such that|H k− h k(n)|≤c k n,eventually a.s.as n→∞.Remark.A slightly weaker inequality(which would suffice for our application here), with an extra factor of log n on the right-hand side can be obtained by applying[3, Theorem16.3.2]instead of(4)below.Proof of Lemma1.LetΨ(x)=x log x−x+1,so thatΨ(1)=Ψ′(1)=0.For x>1/2we haveΨ′′(x)=1/x<2,whence|Ψ(x)|<(x−1)2for all x≥1/2.Consider two distributions P and Q on the same alphabet A,and suppose thatγ=maxa∈A P(a)satisfiesQ(a)D(P|Q)= a Q(a)Ψ P(a)Q(a) ≤γ2.Moreover,a P(a)−Q(a) log Q(a) ≤ a γQ(a)log Q(a) =γH(Q)≤γlog|A|. Adding the last two inequalities(using positivity of the divergence)gives|H(Q)−H(P)|≤γ2+γlog|A|.(4) under the assumption(3).By the law of the iterated logarithm forfinite-order Markov chains,there is a constant c k such thatP n(a k1)log log ngrows like e nH(X),that is,(1/n)log R n(x)→H(X)a.s.(Earlier,Wyner and Ziv,[19], established convergence-in-probability for a related recurrence idea.)In our setting ℓ(n)=max{k:R k≤n}and the Ornstein-Weiss recurrence theorem giveslimn→∞1ℓ(n)log Rℓ(n)≤1ℓ(n)log Rℓ(n)(x)≤1ℓ(n)+1 1Proof.By the Ornstein-Weiss recurrence theorem,R k≤e k(H+1)≤e k(1+log|A|),eventually a.s. Thus we can take C=(1+log|A|)−1.The lemmas yieldProposition1For any X∈M,14√ℓ(n)log n(a)≥1ℓ(n)3/8(c)≥H(X)−14√log log nℓ(n)log n+1log n+c n(c)≤14√inequality (a)by Lemma 1and the fact that H M =H ,and inequality (b)by Propo-sition 1,while inequality (c)is obvious.We conclude that M ∗n (x n1)≤M ,eventually a.s.As the above proof suggests,the entropy estimator [ℓ(n )]−1log n can be replacedby any consistent entropy estimator H (x n 1)that has an o (1)underestimation bound ,i.e.,a function u (n )→0such that for all X ∈MH (x n 1)≥H (X )−u (n ),eventually a.s.,(6)provided we replace 2/4√log n goes to 0very slowly,however,which suggests that its associated order estimator M ∗n (x n1)converges slowly to M .Furthermore,though the recurrence idea does generalize to higher dimensions,see [15],a useful rate theory for it has not been established.In Section 4.1,we present another entropy estimator that has a more rapidly convergent underestimation bound and is extendable to higher dimensions.3The maximal fluctuation method.We now prove the second theorem stated in the introduction,namely,Theorem 2M #n (x n 1)def=min {m <n −f (n ):φm (x n 1)<n3/4}is a consistent Markov order estimator.(Recall that we defined M #n (x n1)=n if this set is empty).Proof.Let δm (a k 1|x n 1)def =N n (a k 1)−N n −1(a k −11) P n (a k |a k −1k −m )and note thatφm (x n 1)=maxm<k<f (n )max a k 1δm (a k 1|x n1),(7)where f (n )=log log n .We first show that eventually a.s.underestimation does notoccur.Suppose X ∈M has order M and m <M .Choose a M +11such that P (a M +1|a M 1)>P (a M +1|a MM −m +1).By the ergodic theorem there exists ǫ>0such that,eventually a.s.,N n −1(a M 1)>ǫn and P n (a M +1|a M 1)− P n (a M +1|a M M −m +1)≥ǫ.This implies that φm (x n 1)≥ǫ2n and hence that M #n (x n1)≥M ,eventually a.s.It takes somewhat more effort to show that,eventually a.s.,φM (x n 1)≤n 3/4.We first note that for fixed k ≥M ,Z k (n )def=N n (a k 1|x n 1)−N n −1(a k −11|x n −11)P (a k |a k −1k −M ),n ≥k,(8)is a martingale with bounded differences.Indeed,with χ(B )denoting the indicator of B ,we can write Z k (n )= nj =k ∆k (j ),where∆k (j )=χ(X j j −k +1=a k 1)−χ(X j −1j −k +1=a k −11)P (a k |a k −1k −M ),and direct calculation shows that E (∆k (j )|X j −11)=0and ∆k (j ) ∞≤1for j >k.From the Hoeffding-Azuma large deviations bound for martingales with bounded differences,[11,1],the probability that |Z n |≥n 3/4is at most 2exp(−n 1/2/2).A similar argument also shows that forZ ∗k (n )def=N n (a k k −M |x n 1)−N n −1(a k −1k −M |x n −11)P (a k |a k −1k −M ),n ≥k,the probability that |Z ∗k (n )|≥n 3/4is at most 2exp(−n 1/2/2).Next we note thatZ k (n )−δM (a k 1|x n1)=N n −1(a k −11)2.S t (¯u )def=the square of width 2t +1with center at ¯u ∈Z 2.3.Λn def=the square of width n with lower left corner at (1,1).4.A configuration a (Λ)is a function a :Λ→A ;if no confusion results its restriction to Λ′⊆Λwill be denoted by a (Λ′).A random field is a collection X ={X (¯n ):¯n ∈Z 2}of random variables with values in A .Unless stated otherwise,random fields are assumed to be stationary and ergodic.We use the conditional probability notationP (a (Λ)|b (Λ′))def=Prob(X (Λ)=a (Λ),X (Λ′))=b (Λ′))2k +1−1.We assume the integer n is large enough to guarantee that T >0for all k ≤3log log n .LetΠk ={S k (¯u 1),S k (¯u 2),...,S k (¯u T 2)}be the partition of the square Λ(2k +1)T into squares of width 2k +1.For each ¯v ∈Λ2k +1,let Πk (¯v )={S k (¯v +¯u j ),1≤j ≤T 2}be the translated partition of the square¯v +Λ(2k +1)T ⊆Λn .•¯v +¯u jℓr-t -N ¯v (a (S ℓ+r S ℓ)).(9)This is maximized over configurations a (S k )and translates ¯v to produceδℓ,r,t (x (Λn ))def=max¯v ∈Λ2k +1max a (S k)δℓ,r,t,¯v (a (S k )|x (Λn )).For ℓ=⌊log log n ⌋defineφr (x (Λn ))def=max 0<t<log log nδℓ,r,t (x (Λn )).Our 2-d order estimator isR ∗n (x (Λn ))def=min {r <n −3log log n :φr ≤n 3/2},where,if there is no such r <n −3log log n ,we set R ∗n (x (Λn ))=n .Theorem 3Let X be a stationary,ergodic,finite range random field on Z d .ThenR ∗n (x (Λn ))=R (X ),eventually a.s.Proof.If r <R =R (X ),an argument similar to the 1-dimensional case shows that φr (x (Λn ))≥Cn 2,eventually a.s.,for a some C >0.Thus,underestimation eventually a.s.does not occur.To complete the proof it is enough to show that φR <n 3/2,eventually a.s.Towards this end,we fix ℓ>0and t >0,put r =R and k =ℓ+R +t ,fix a (S k )and ¯v ∈Λ2k +1,and put N =N ¯v .Our 2-d test function (9)can then be expressed as the sumN (a (S k ))−N (a (S k S ℓ))N (a (S ℓ+R ))N (a (S ℓ+R S ℓ)) N (a (S ℓ+R S ℓ))P (a (S ℓ)|a (S ℓ+R S ℓ))−N (a (S ℓ+R )) ≤ N (a (S ℓ+R S ℓ))P (a (S ℓ)|a (S ℓ+R S ℓ))−N (a (S ℓ+R )) .(10)Denote p =P (a (S ℓ)|a (S ℓ+R S ℓ))and ¯w j =¯u j +¯v .Then we can write ∆1= T 2j =1∆1,j ,where with χ(·)denoting the indicator function,∆1,j def =χ X (S k (¯w j ))=a (S k ) −χ X ([S k S ℓ](¯w j ))=a (S k S ℓ) p.Therefore,conditioned on the values a (S k S ℓ)in the square annulus,∆1is a sum of N (a (S k S ℓ))≤T 2binary i.i.d.mean 0random variables.The classical Hoeffding large deviations bound,[11],implies that the probability that |∆1|>14Extensions and related work.4.1Other entropy estimators.There are many known consistent entropy estimators,for most of which o(1) underestimation bounds for the Markov case have not been established.In addition to the recurrence estimator such an underestimation bound can be shown to hold for h f(n)(n),where for example f(n)=log log nn,eventually a.s.Proof.By the Ornstein-Weiss entropy estimation theorem,[13],the per-symbol em-pirical block entropy1H+ǫ,for someǫ>0.It is easy to see that this implies h f(n)(n)→H,a.s.,for the case f(n)=log log n2log n+n h f(n)(n)>|A|M(|A|−1)2log n−(|A|−1)4.2The“flat spot”problem.For the Markov order estimation problem,it is tempting to take as order estimator thefirst k for which h k(n)− h k+1(n)<n−1/4.This eventually a.s.gets stuck at the first k for which H k=H k+1.Suchflat spots can occur for k<M−1.This shows, incidentally,why we needed to take the maximum over a growing interval of possible orders in the definition(2)of our maximalfluctuation test function.Remark6The“noflat spot”case is“generic”for it is easy to see that in the usual parametrization of the set of X∈M of order M as a subset of|A|M(|A|−1)-dimensional Euclidean space,the set of X of order M whose conditional entropy has flat spots before M has Lebesgue measure0.This is a good example where genericity is not an interesting concept.4.3The BIC,MDL,and related methods.Two important and related methods,the Bayesian Information Criterion(BIC) and the Minimum Description Length(MDL)Principle are the basis for many model selection methods,see[2,4,6]for discussion and references to these and other meth-ods.Both the BIC and the MDL focus on selecting the correct class from a nested sequence of parametric model classes,M0⊂M1⊂M2...,based on a sample path drawn from some P∈∪M k.The BIC,introduced by Schwarz[16],is based on Bayesian principles and leads to the model estimatorM∗BIC(x n1)def=arg mink −log P ML(k)(x n1)+φ(k)Acknowledgements.We are grateful to I.Kontoyiannis,M.Krishnapur and T. Rud´a s for helpful comments.References[1]K.Azuma,“Weighted sums of certain dependent random variables,”Tˆo hokuMath.J.,19(1967),357–367.[2]A.Barron,J.Rissanen and B.Yu,“The minimum description length principlein coding and modeling,”Information theory:1948–1998.IEEE rm.Theory44(1998),no.6,2743–2760.[3]T.M.Cover and J.A.Thomas,Elements of Information Theory.Wiley,NewYork(1991).[4]I.Csisz´a r,“Large-scale typicality of Markov sample paths and consistency ofMDL order estimators,”IEEE rm.Th.,48(2002),1616–1629. [5]I.Csisz´a r and J.K¨o rner,Information Theory:Coding theorems for discrete mem-oryless systems.Akad´e miai Kiad´o,Budapest(1981).[6]I.Csisz´a r and P.Shields,“The consistency of the BIC Markov order estimator,”Ann.Statist.,28(2000),1601–1619.[7]I.Csisz´a r and Zs.Talata,“Consistent estimation of the basic neighborhood ofMarkov randomfields,”preprint(2004).[8]P.Jacquet and W.Szpankowski,“Asymptotic behavior of the Lempel-Ziv parsingscheme and digital search trees,”Theoretical Computer Science,144(1995),161–197.[9]A.Dembo and Y.Peres,“A topological criterion for hypothesis testing,”Ann.Statist.,40(1994),106–117.[10]L.Finesso,“Estimation of the order of afinite Markov chain,”in Recent Advancesin the Mathematical Theory of Systems,Control,and Network Signals,Proc.MTNS-91,H.Kimura and S.Kodama,Eds.,Mita Press,1992,643-645. [11]W.Hoeffding,“Probability inequalities for sums of bounded random variables,”Journal of the American Statistical Association,”58(1963),13-30.[12]I.Kontoyiannis,“Asymptotic recurrence and waiting times for stationary pro-cesses,”J.Theoret.Probab.11(1998),795–811.[13]D.Ornstein and B.Weiss,“How sampling reveals a process,”Ann.Probab.,18(1990),905-930.[14]D.Ornstein and B.Weiss,“Entropy and data compression,”IEEE rm.Th.,IT-39(1993),78-83.[15]D.Ornstein and B.Weiss,“Entropy and recurrence rates for stationary randomfields,”Special Issue on Shannon Theory:perspective,trends,and applications.IEEE rm.Th.,IT-48(2002),1694–1697.[16]G.Schwarz,“Estimating the dimension of a model,”Ann.Statist.6(1978),461–464.[17]P.Shields,The ergodic theory of discrete sample paths.AMS Graduate Studiesin Mathematics,American Mathematics Society,1996.[18]P.Shields,“Recurrence revisited”,Lecture at the Ornsteinfest,Stanford Univer-sity,July22,2004.[19]A.Wyner and J.Ziv,“Some asymptotic properties of the entropy of a stationaryergodic data source with applications to data compression,”IEEE rm.Th.IT-35(1989),1250–1258.[20]J.Ziv,“Coding theorems for individual sequences,”IEEE rm.Th.,IT-24(1978),405–412.。
