Universal Tests for Memory Words
Gusztáv Morvai, Benjamin Weiss · IEEE Transactions on Information Theory · 2013
The main result is a universal pointwise test that, when presented with a set of words S on a finite or countable alphabet X that purports to be a set of memory words for a stationary process, will eventually almost surely return the value YES precisely when all positive probability words in S are memory words. For example, if S consists of all of the single letters in X, then the test will eventually say yes if and only if the process is a Markov chain. Various further positive and negative results of this type are also given.