Let {X/sub t/} be a real-valued time series. The best nonlinear predictor of X/sub 0/ given the infinite past X/sub -/spl infin///sup -1/ in the least squares sense, is equal to the conditional mean E{X/sub 0/|X/sub -/spl infin///sup -1/}. Previously, it has been shown that certain predictors based on growing segments of past observations converge to the best predictor given the infinite past whenever {X/sub t/} is a stationary process with values in a bounded interval. The present paper deals with universal prediction schemes for stationary processes with finite mean. We also discuss universal schemes for learning the conditional mean E{X/sub 0/|X/sub -/spl infin///sup -1/Y/sub -/spl infin///sup -1/Y/sub 0/} from past observations of a stationary pair process {(X/sub t/, Y/sub t/)}, and schemes for learning the repression function m(y)=E{X|Y=y} from independent samples of (X, Y).

We discuss a family of estimators for the entropy rate of a stationary ergodic process and prove their pointwise and mean consistency under a Doeblin-type mixing condition. The estimators are Cesaro averages of longest match-lengths, and their consistency follows from a generalized ergodic theorem due to Maker (1940). We provide examples of their performance on English text, and we generalize our results to countable alphabet processes and to random fields.

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.

Combines optimization and ergodic theory to characterize the optimum long-run average performance that can be asymptotically attained by nonanticipating sequential decisions. Let {X/sub t/} be a stationary ergodic process, and suppose an action b/sub t/ must be selected in a space /spl Bscr/ with knowledge of the t-past (X/sub 0/, /spl middot//spl middot//spl middot/, X/sub t-1/) at the beginning of every period t/spl ges/0. Action b/sub t/ will incur a loss l(b/sub t/, X/sub t/) at the end of period t when the random variable X/sub t/ is revealed. The author proves under mild integrability conditions that the optimum strategy is to select actions that minimize the conditional expected loss given the currently available information at each step. The minimum long-run average loss per decision can be approached arbitrarily closely by strategies that are finite-order Markov, and under certain continuity conditions, it is equal to the minimum expected loss given the infinite past. If the loss l(b, x) is bounded and continuous and if the space /spl Bscr/ is compact, then the minimum can be asymptotically attained, even if the distribution of the process {X/sub t/} is unknown a priori and must be learned from experience.>

An irreducible Markov chain with stationary transition probabilities on a finite directed graph is considered. The probability of large deviations of the random variable denoting the empirical type of the first n transitions is investigated.>