Estimating the Lengths of Memory Words
Gusztáv Morvai, Benjamin Weiss · IEEE Transactions on Information Theory · 2008
For a stationary stochastic process {Xn} with values in some setA, a finite wordwisinAKis called a memory word if the conditional probability ofX0given the past is constant on the cylinder set defined byX-K-1=w. It is a called a minimal memory word if no proper suffix ofwis also a memory word. For example in aK-step Markov processes all words of lengthKare memory words but not necessarily minimal. We consider the problem of determining the lengths of the longest minimal memory words and the shortest memory words of an unknown process {Xn} based on sequentially observing the outputs of a single sample {xi1,xi2,...xin}. We will give a universal estimator which converges almost surely to the length of the longest minimal memory word and show that no such universal estimator exists for the length of the shortest memory word. The alphabetAmay be finite or countable.