## On Finding Predictors for Arbitrary Families of Processes

** Daniil Ryabko**; 11(Feb):581−602, 2010.

### Abstract

The problem is sequence prediction in the following setting. A sequence*x*of discrete-valued observations is generated according to some unknown probabilistic law (measure) μ. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure μ belongs to an arbitrary but known class

_{1},...,x_{n},...*C*of stochastic process measures. We are interested in predictors ρ whose conditional probabilities converge (in some sense) to the "true" μ-conditional probabilities, if any μ∈

*C*is chosen to generate the sequence. The contribution of this work is in characterizing the families

*C*for which such predictors exist, and in providing a specific and simple form in which to look for a solution. We show that if any predictor works, then there exists a Bayesian predictor, whose prior is discrete, and which works too. We also find several sufficient and necessary conditions for the existence of a predictor, in terms of topological characterizations of the family

*C*, as well as in terms of local behaviour of the measures in

*C*, which in some cases lead to procedures for constructing such predictors.

It should be emphasized that the framework is completely general: the stochastic processes considered are not required to be i.i.d., stationary, or to belong to any parametric or countable family.

[abs][pdf]