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.

We present here a universal estimation scheme for the problem of estimating the residual waiting time until the next occurrence of a zero after observing the first n outputs of a stationary and ergodic binary process. The scheme will involve estimating only at carefully selected stopping times but will be almost surely consistent. In case the process happens to be a genuine renewal process then our stopping times will have asymptotic density one.

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.

Estimators /spl chi//sub n/(X/sub 0/, X/sub 1/, ..., X/sub n/), are described which, when applied to an unknown stationary process taking values from a countable alphabet /spl chi/, converge almost surely to k in case the process is a kth-order Markov chain and to infinity otherwise.

For a stationary random field {x(u): u /spl isin/ Z/sup d/}, the recurrence time R/sub n/(x) may be defined as the smallest positive k, such that the pattern {x(u): 0 /spl les/ u/sub i/ < n} is seen again, in a new position in the cube {0 /spl les/ |u/sub i/| < k}. In analogy with the case of d = 1, where the pioneering work was done by Wyner and Ziv (1989), we prove here that the asymptotic growth of R/sub n/(x) for ergodic fields is given by the entropy of the random field. The nonergodic case is also treated, as well as the recurrence times of central patterns in centered cubes. Both finite and countable state spaces are treated.

Shows that for any sequence /spl rho/(n)=o(n) and any sequence of prefix codes, there is a B-process of entropy arbitrarily close to the maximum possible entropy for which the expected redundancy is at least as large as /spl rho/(n) for infinitely many n. This extends work of Shields (1993), whose examples had O entropy. The class of B-processes, that is, stationary codings of independent and identically distributed (i.i.d.) processes, includes the aperiodic Markov chains and functions thereof, aperiodic renewal and regenerative processes, and m-dependent processes, as well as many other processes of interest. In particular, the results show that the search for a universal redundancy rate for the class of all B-processes is doomed to failure, and redundancy rates for any given subclass must be obtained by direct analysis of that subclass.>

Some new ways of defining the entropy of a process by observing a single typical output sequence as well as a new kind of Shannon-McMillan-Breiman theorem are presented. This provides a new and conceptually very simple ways of estimating the entropy of an ergodic stationary source as well as new insight into the workings of such well-known data compression schemes as the Lempel-Ziv algorithm.>