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.

Let {Xn}n=0¿be a stationary real-valued Gaussian time series. We estimate the conditional expectation E(Xn+1|X0, ...,Xn) from a growing number of observations X0,..., Xnin a pointwise consistent way along a sequence of stopping times.

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.

We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from previous developments of the theory of the prediction of individual sequences. We show that if the sequence is a realization of a stationary and ergodic random process then the average number of mistakes converges, almost surely, to that of the optimum, given by the Bayes predictor. The desirable finite-sample properties of the predictor are illustrated by its performance for Markov processes. In such cases the predictor exhibits near-optimal behavior even without knowing the order of the Markov process. Prediction with side information is also considered.

This article concerns problems of time-series forecasting under the weakest of assumptions. Related results are surveyed and are points of departure for the developments here, some of which are new and others are new derivations of previous findings. The contributions in this study are all negative, showing that various plausible prediction problems are unsolvable, or in other cases, are not solvable by predictors which are known to be consistent when mixing conditions hold.

This paper considers estimation of a univariate density from an individual numerical sequence. It is assumed that (1) the limiting relative frequencies of the numerical sequence are governed by an unknown density, and (2) there is a known upper bound for the variation of the density on an increasing sequence of intervals. A simple estimation scheme is proposed, and is shown to be L/sub 1/ consistent when (1) and (2) apply. In addition, it is shown that there is no consistent estimation scheme for the set of individual sequences satisfying only condition (1).

The conditional distribution of the next outcome given the infinite past of a stationary process can be inferred from finite but growing segments of the past. Several schemes are known for constructing pointwise consistent estimates, but they all demand prohibitive amounts of input data. We consider real-valued time series and construct conditional distribution estimates that make much more efficient use of the input data. The estimates are consistent in a weak sense, and the question whether they are pointwise-consistent is still open. For finite-alphabet processes one may rely on a universal data compression scheme like the Lempel-Ziv (1978) algorithm to construct conditional probability mass function estimates that are consistent in expected information divergence. Consistency in this strong sense cannot be attained in a universal sense for all stationary processes with values in an infinite alphabet, but weak consistency can. Some applications of the estimates to on-line forecasting, regression, and classification are discussed.