Daniil Ryabko
email: daniil@ryabko.net

On Finding Predictors for Arbitrary Families of Processes

The problem is sequence prediction in the following setting. A sequence x 1 , . . . , x n , . . . 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 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.

Introduction

Given a sequence x 1 , . . . , x n of observations x i ∈ X , where X is a finite set, we want to predict what are the probabilities of observing x n+1 = x for each x ∈ X , or, more generally, probabilities of observing different x n+1 , . . . , x n+h , before x n+1 is revealed, after which the process continues. It is assumed that the sequence is generated by some unknown stochastic process µ, a probability measure on the space of one-way infinite sequences X ∞ . The goal is to have a predictor whose predicted probabilities converge (in a certain sense) to the correct ones (that is, to µ-conditional probabilities). In general this goal is impossible to achieve if nothing is known about the measure µ generating the sequence. In other words, one cannot have a predictor whose error goes to zero for any measure µ. The problem becomes tractable if we assume that the measure µ generating the data belongs to some known class C. The questions addressed in this work are a part of the following general problem: given an arbitrary set C of measures, how can we find a predictor that performs well when the data is generated by any µ ∈ C, and whether it is possible to find such a predictor at all. An example of a generic property of a class C that allows for construction of a predictor, is that C is countable. Clearly, this condition is very strong. An example, important from the applications point of view, of a class C of measures for which predictors are known, is the class of all stationary measures. The general question, however, is very far from being answered.

The contribution of this work to solving this question is, first, in that we provide a specific form in which to look for a predictor. More precisely, we show that if a predictor that predicts every µ ∈ C exists, then such a predictor can also be obtained as a weighted sum of countably many elements of C. This result can also be viewed as a justification of the Bayesian approach to sequence prediction: if there exists a predictor which predicts well every measure in the class, then there exists a Bayesian predictor (with a rather simple prior) that has this property too. In this respect it is important to note that the result obtained about such a Bayesian predictor is pointwise (holds for every µ in C), and stretches far beyond the set its prior is concentrated on. Next, we derive some characterizations of families C for which a predictor exist. We first analyze what is furnished by the notion of separability, when a suitable topology can be found: we find that it is a sufficient but not always a necessary condition. We then derive some sufficient conditions for the existence of a predictor which are based on local (truncated to the first n observation) behaviour of measures in the class C. Necessary conditions cannot be obtained in this way (as we demonstrate), but sufficient conditions, along with rates of convergence and construction of predictors, can be found.

The motivation for studying predictors for arbitrary classes C of processes is two-fold. First of all, prediction is a basic ingredient for constructing intelligent systems. Indeed, in order to be able to find optimal behaviour in an unknown environment, an intelligent agent must be able, at the very least, to predict how the environment is going to behave (or, to be more precise, how relevant parts of the environment are going to behave). Since the response of the environment may in general depend on the actions of the agent, this response is necessarily non-stationary for explorative agents. Therefore, one cannot readily use prediction methods developed for stationary environments, but rather has to find predictors for the classes of processes that can appear as a possible response of the environment.

Apart from this, the problem of prediction itself has numerous applications in such diverse fields as data compression, market analysis, bioinformatics, and many others. It seems clear that prediction methods constructed for one application cannot be expected to be optimal when applied to another. Therefore, an important question is how to develop specific prediction algorithms for each of the domains.

Prior work. As it was mentioned, if the class C of measures is countable (that is, if C can be represented as C := {µ k : k ∈ N}), then there exists a predictor which performs well for any µ ∈ C. Such a predictor can be obtained as a Bayesian mixture ρ S := k∈N w k µ k , where w k are summable positive real weights, and it has very strong predictive properties; in particular, ρ S predicts every µ ∈ C in total variation distance, as follows from the result of [Blackwell and Dubins(1962)]. Total variation distance measures the difference in (predicted and true) conditional probabilities of all future events, that is, not only the probabilities of the next observations, but also of observations that are arbitrary far off in the future (see formal definitions below). In the context of sequence prediction the measure ρ S was first studied by [Solomonoff(1978)]. Since then, the idea of taking a convex combination of a finite or countable class of measures (or predictors) to obtain a predictor permeates most of the research on sequential prediction (see, for example, [Cesa-Bianchi and Lugosi(2006)]) and more general learning problems [Hutter(2005), Ryabko and Hutter(2008a)]. In practice it is clear that, on the one hand, countable models are not sufficient, since already the class µ p , p ∈ [0, 1] of Bernoulli i.i.d. processes, where p is the probability of 0, is not countable. On the other hand, prediction in total variation can be too strong to require; predicting probabilities of the next observation may be sufficient, maybe even not on every step but in the Cesaro sense. A key observation here is that a predictor ρ S = w k µ k may be a good predictor not only when the data is generated by one of the processes µ k , k ∈ N, but when it comes from a much larger class. Let us consider this point in more detail. Fix for simplicity X = {0, 1}. The Laplace predictor

λ(x n+1 = 0|x 1 , . . . , x n ) = #{i ≤ n : x i = 0} + 1 n + |X | (1)
predicts any Bernoulli i.i.d. process: although convergence in total variation distance of conditional probabilities does not hold, predicted probabilities of the next outcome converge to the correct ones. Moreover, generalizing the Laplace predictor, a predictor λ k can be constructed for the class M k of all k-order Markov measures, for any given k. As was found by [Ryabko(1988)], the combination ρ R := w k λ k is a good predictor not only for the set ∪ k∈N M k of all finite-memory processes, but also for any measure µ coming from a much larger class: that of all stationary measures on X ∞ .

Here prediction is possible only in the Cesaro sense (more precisely, ρ R predicts every stationary process in expected time-average Kullback-Leibler divergence, see definitions below). The Laplace predictor itself can be obtained as a Bayes mixture over all Bernoulli i.i.d. measures with uniform prior on the parameter p (the probability of 0). However, as was observed in [Hutter(2007)] (and as is easy to see), the same (asymptotic) predictive properties are possessed by a Bayes mixture with a countably supported prior which is dense in [0, 1] (e.g. taking ρ := w k δ k where δ k , k ∈ N ranges over all Bernoulli i.i.d. measures with rational probability of 0). For a given k, the set of k-order Markov processes is parametrized by finitely many [0, 1]-valued parameters. Taking a dense subset of the values of these parameters, and a mixture of the corresponding measures, results in a predictor for the class of k-order Markov processes. Mixing over these (for all k ∈ N) yields, as in [Ryabko(1988)], a predictor for the class of all stationary processes. Thus, for the mentioned classes of processes, a predictor can be obtained as a Bayes mixture of countably many measures in the class. An additional reason why this kind of analysis is interesting is because of the difficulties arising in trying to construct Bayesian predictors for classes of processes that can not be easily parametrized. Indeed, a natural way to obtain a predictor for a class C of stochastic processes is to take a Bayesian mixture of the class. To do this, one needs to define the structure of a probability space on C. If the class C is well parametrized, as is the case with the set of all Bernoulli i.i.d. process, then one can integrate with respect to the parametrization. In general, when the problem lacks a natural parametrization, although one can define the structure of the probability space on the set of (all) stochastic process measures in many different ways, the results one can obtain will then be with probability 1 with respect to the prior distribution (see, for example, [START_REF]Bayesian representation of stochastic processes under learning: de Finetti revisited[END_REF]Jackson, Kalai, and Smorodinsky]). Pointwise consistency cannot be assured (see e.g. [Diaconis and Freedman(1986)]) in this case, meaning that some (well-defined) Bayesian predictors are not consistent on some (large) subset of C. Results with prior probability 1 can be hard to interpret if one is not sure that the structure of the probability space defined on the set C is indeed a natural one for the problem at hand (whereas if one does have a natural parametrization, then usually results for every value of the parameter can be obtained, as in the case with Bernoulli i.i.d. processes mentioned above). The results of the present work show that when a predictor exists it can indeed be given as a Bayesian predictor, which predicts every (and not almost every) measure in the class, while its support is only a countable set.

A related question is formulated as a question about two individual measures, rather than about a class of measures and a predictor. Namely, one can ask under which conditions one stochastic process predicts another. In [Blackwell and Dubins(1962)] it was shown that if one measure is absolutely continuous with respect to another, than the latter predicts the former (the conditional probabilities converge in a very strong sense). In [START_REF] Ryabko | [END_REF], Ryabko and Hutter(2008b)] a weaker form of convergence of probabilities (in particular, convergence of expected average KL divergence) is obtained under weaker assumptions.

The results. First, we show that if there is a predictor that performs well for every measure coming from a class C of processes, then a predictor can also be obtained as a convex combination k∈N w k µ k for some µ k ∈ C and some w k > 0, k ∈ N. This holds if the prediction quality is measured by either total variation distance, or expected average KL divergence: one measure of performance that is very strong, the other rather weak. The analysis for the total variation case relies on the fact that if ρ predicts µ in total variation distance, then µ is absolutely continuous with respect to ρ, so that ρ(x 1..n )/µ(x 1..n ) converges to a positive number with µ-probability 1 and with a positive ρ-probability. However, if we settle for a weaker measure of performance, such as expected average KL divergence, measures µ ∈ C are typically singular with respect to a predictor ρ. Nevertheless, since ρ predicts µ we can show that ρ(x 1..n )/µ(x 1..n ) decreases subexponentially with n (with high probability or in expectation); then we can use this ratio as an analogue of the density for each time step n, and find a convex combination of countably many measures from C that has desired predictive properties for each n. Combining these predictors for all n results in a predictor that predicts every µ ∈ C in average KL divergence. The proof techniques developed have a potential to be used in solving other questions concerning sequence prediction, in particular, the general question of how to find a predictor for an arbitrary class C of measures.

We then exhibit some sufficient conditions on the class C, under which a predictor for all measures in C exists. It is important to note that none of these conditions relies on a parametrization of any kind. The conditions presented are of two types: conditions on asymptotic behaviour of measures in C, and on their local (restricted to first n observations) behaviour. Conditions of the first type concern separability of C with respect to the total variation distance and the expected average KL divergence. We show that in the case of total variation separability is a necessary and sufficient condition for the existence of a predictor, whereas in the case of expected average KL divergence it is sufficient but is not necessary.

The conditions of the second kind concern the "capacity" of the sets C n := {µ n : µ ∈ C}, n ∈ N, where µ n is the measure µ restricted to the first n observations. Intuitively, if C n is small (in some sense), then prediction is possible. We measure the capacity of C n in two ways. The first way is to find the maximum probability given to each sequence x 1 , . . . , x n by some measure in the class, and then take a sum over x 1 , . . . , x n . Denoting the obtained quantity c n , one can show that it grows polynomially in n for some important classes of processes, such as i.i.d. or Markov processes. We show that, in general, if c n grows subexponentially then a predictor exists that predicts any measure in C in expected average KL divergence. On the other hand, exponentially growing c n are not sufficient for prediction. A more refined way to measure the capacity of C n is using a concept of channel capacity from information theory, which was developed for a closely related problem of finding optimal codes for a class of sources. We extend corresponding results from information theory to show that sublinear growth of channel capacity is sufficient for the existence of a predictor, in the sense of expected average divergence. Moreover, the obtained bounds on the divergence are optimal up to an additive logarithmic term.

The rest of the paper is organized as follows. Section 2 introduces the notation and definitions. In Section 3 we show that if any predictor works than there is a Bayesian one that works, while in Section 4 we provide several characterizations of predictable classes of processes. Section 4.1 is concerned with separability, while Section 4.2 analyzes conditions based on local behaviour of measures. Finally, Section 5 provides outlook and discussion.

As running examples that illustrate the results of each section we use countable classes of measures, the family of all Bernoulli i.i.d. processes and that of all stationary processes.

Preliminaries

Let X be a finite set. The notation x 1..n is used for x 1 , . . . , x n . We consider stochastic processes (probability measures) on (X ∞ , F) where F is the sigma-field generated by the cylinder sets [x 1..n ],

x i ∈ X , n ∈ N, where [x 1..n ] is the set of all infinite sequences that start with x 1..n . For a finite set A denote |A| its cardinality. We use E µ for expectation with respect to a measure µ.

Next we introduce the measures of the quality of prediction used in this paper. For two measures µ and ρ we are interested in how different the µ-and ρ-conditional probabilities are, given a data sample x 1..n . Introduce the (conditional) total variation distance

v(µ, ρ, x 1..n ) := sup A∈F |µ(A|x 1..n ) -ρ(A|x 1..n )|. Definition 1. We say that ρ predicts µ in total variation if v(µ, ρ, x 1..n ) → 0 µ-a.s.
This convergence is rather strong. In particular, it means that ρ-conditional probabilities of arbitrary far-off events converge to µ-conditional probabilities. Moreover, ρ predicts µ in total variation if [Blackwell and Dubins(1962)] and only if [Kalai and Lehrer(1994)] µ is absolutely continuous with respect to ρ:

Theorem 1 ( [Blackwell and Dubins(1962), Kalai and Lehrer(1994)]). If ρ, µ are arbitrary probability measures on (X ∞ , F), then ρ predicts µ in total variation if and only if µ is absolutely continuous with respect to ρ.

Thus, for a class C of measures there is a predictor ρ that predicts every µ ∈ C in total variation if and only if every µ ∈ C has a density with respect to ρ. Although such sets of processes are rather large, they do not include even such basic examples as the set of all Bernoulli i.i.d. processes. That is, there is no ρ that would predict in total variation every Bernoulli i.i.d. process measure δ p , p ∈ [0, 1], where p is the probability of 0. Therefore, perhaps for many (if not most) practical applications this measure of the quality of prediction is too strong, and one is interested in weaker measures of performance.

For two measures µ and ρ introduce the expected cumulative Kullback-Leibler divergence (KL divergence) as

d n (µ, ρ) := E µ n t=1 a∈X µ(x t = a|x 1..t-1 ) log µ(x t = a|x 1..t-1 ) ρ(x t = a|x 1..t-1 ) , (2)
In words, we take the expected (over data) average (over time) KL divergence between µ-and ρ-conditional (on the past data) probability distributions of the next outcome.

Definition 2. We say that ρ predicts µ in expected average KL divergence if

1 n d n (µ, ρ) → 0.
This measure of performance is much weaker, in the sense that it requires good predictions only one step ahead, and not on every step but only on average; also the convergence is not with probability 1 but in expectation. With prediction quality so measured, predictors exist for relatively large classes of measures; most notably, [Ryabko(1988)] provides a predictor which predicts every stationary process in expected average KL divergence. A simple but useful identity that we will need (in the context of sequence prediction introduced also in [Ryabko(1988)]) is the following

d n (µ, ρ) = - x 1..n ∈X n µ(x 1..n ) log ρ(x 1..n ) µ(x 1..n ) , (3)
where on the right-hand side we have simply the KL divergence between measures µ and ρ restricted to the first n observations. Thus, the results of this work will be established with respect to two very different measures of prediction quality, one of which is very strong and the other rather weak. This suggests that the facts established reflect some fundamental properties of the problem of prediction, rather than those pertinent to particular measures of performance. On the other hand, it remains open to extend the results below to different measures of performance.

Fully nonparametric Bayes predictors

In this section we show that if there is a predictor that predicts every µ in some class C, then there is a Bayesian mixture of countably many elements from C that predicts every µ ∈ C too. This is established for the two notions of prediction quality that were introduced: total variation and expected average KL divergence. After the theorems we present some examples of families of measures for which predictors exist.

Theorem 2. Let C be a set of probability measures on (X ∞ , F). If there is a measure ρ such that ρ predicts every µ ∈ C in total variation, then there is a sequence µ k ∈ C, k ∈ N such that the measure ν := k∈N w k µ k predicts every µ ∈ C in total variation, where w k are any positive weights that sum to 1. This relatively simple fact can be proven in different ways, relying on the mentioned equivalence [Blackwell and Dubins(1962), Kalai and Lehrer(1994)] of the statements "ρ predicts µ in total variation distance" and "µ is absolutely continuous with respect to ρ." The proof presented below is not the shortest possible, but it uses ideas and techniques that are then generalized to the case of prediction in expected average KL-divergence, which is more involved, since in all interesting cases all measures µ ∈ C are singular with respect to any predictor that predicts all of them. Another proof of Theorem 2 can be obtained from Theorem 4 in the next section. Yet another way would be to derive it from algebraic properties of the relation of absolute continuity, given in [START_REF] Plesner | [END_REF]].

Proof. We break the (relatively easy) proof of this theorem into 3 steps, which will make the proof of the next theorem more understandable.

Step 1: densities. For any µ ∈ C, since ρ predicts µ in total variation, by Theorem 1, µ has a density (Radon-Nikodym derivative) f µ with respect to ρ. Thus, for the set T µ of all sequences x 1 , x 2 , ... ∈ X ∞ on which f µ (x 1,2,... ) > 0 (the limit lim n→∞ ρ(x 1..n ) µ(x 1..n ) exists and is finite and positive) we have µ(T µ ) = 1 and ρ(T µ ) > 0. Next we will construct a sequence of measures µ k ∈ C, k ∈ N such that the union of the sets T µ k has probability 1 with respect to every µ ∈ C, and will show that this is a sequence of measures whose existence is asserted in the theorem statement.

Step 2: a countable cover and the resulting predictor. Let

ε k := 2 -k and let m 1 := sup µ∈C ρ(T µ ). Clearly, m 1 > 0. Find any µ 1 ∈ C such that ρ(T µ 1 ) ≥ m 1 -ε 1 , and let T 1 = T µ 1 . For k > 1 define m k := sup µ∈C ρ(T µ \T k-1 ). If m k = 0 then define T k := T k-1 , otherwise find any µ k such that ρ(T µ k \T k-1 ) ≥ m k -ε k , and let T k := T k-1 ∪ T µ k . Define the predictor ν as ν := k∈N w k µ k .
Step 3: ν predicts every µ ∈ C. Since the sets

T 1 , T 2 \T 1 , . . . , T k \T k-1 , . . . are disjoint, we must have ρ(T k \T k-1 ) → 0, so that m k → 0 (since m k ≤ ρ(T k \T k-1 ) + ε k → 0). Let T := ∪ k∈N T k .
Fix any µ ∈ C. Suppose that µ(T µ \T ) > 0. Since µ is absolutely continuous with respect to ρ, we must have δ := ρ(T µ \T ) > 0. Then for every k > 1 we have

m k = sup µ ′ ∈C ρ(T µ ′ \T k-1 ) ≥ ρ(T µ \T k-1 ) ≥ ρ(T µ \T ) = δ > 0,
which contradicts m k → 0. Thus, we have shown that

µ(T ∩ T µ ) = 1. ( 4
)
Let us show that every µ ∈ C is absolutely continuous with respect to ν. Indeed, fix any µ ∈ C and suppose µ(A) > 0 for some A ∈ F. Then from (4) we have µ(A ∩ T ) > 0, and, by absolute continuity of µ with respect to ρ, also ρ

(A ∩ T ) > 0. Since T = ∪ k∈N T k we must have ρ(A ∩ T k ) > 0 for some k ∈ N. Since on the set T k the measure µ k has non-zero density f µ k with respect to ρ, we must have µ k (A ∩ T k ) > 0. (Indeed, µ k (A ∩ T k ) = A∩T k f µ k dρ > 0.) Hence, ν(A ∩ T k ) ≥ w k µ k (A ∩ T k ) > 0,
so that ν(A) > 0. Thus, µ is absolutely continuous with respect to ν, and so, by Theorem 1, ν predicts µ in total variation distance.

Thus, examples of families C for which there is a ρ that predicts every µ ∈ C in total variation, are limited to families of measures which have a density with respect to some measure ρ. On the one hand, from statistical point of view, such families are rather large: the assumption that the probabilistic law in question has a density with respect to some (nice) measure is a standard one in statistics. It should also be mentioned that such families can easily be uncountable. On the other hand, even such basic examples as the set of all Bernoulli i.i.d. measures does not allow for a predictor that predicts every measure in total variation. Indeed, all these processes are singular with respect to one another; in particular, each of the non-overlapping sets T p of all sequences which have limiting fraction p of 0s has probability 1 with respect to one of the measures and 0 with respect to all others; since there are uncountably many of these measures, there is no measure ρ with respect to which they all would have a density (since such a measure should have ρ(T p ) > 0 for all p) . As it was mentioned, predicting in total variation distance means predicting with arbitrarily growing horizon [Kalai and Lehrer(1994)], while prediction in expected average KL divergence is only concerned with the probabilities of the next observation, and only on time and data average. For the latter measure of prediction quality, consistent predictors exist not only for the class of all Bernoulli processes, but also for the class of all stationary processes [Ryabko(1988)]. The next theorem establishes the result similar to Theorem 2 for expected average KL divergence.

Theorem 3. Let C be a set of probability measures on (X ∞ , F). If there is a measure ρ such that ρ predicts every µ ∈ C in expected average KL divergence, then there exist a sequence µ k ∈ C, k ∈ N and a sequence w k > 0, k ∈ N, such that k,∈N w k = 1, and the measure ν := k∈N w k µ k predicts every µ ∈ C in expected average KL divergence.

A difference worth noting with respect to the formulation of Theorem 2 (apart from a different measure of divergence) is in that in the latter the weights w k can be chosen arbitrarily, while in Theorem 3 this is not the case. In general, the statement " k∈N w k ν k predicts µ in expected average KL divergence for some choice of w k , k ∈ N" does not imply " k∈N w ′ k ν k predicts µ in expected average KL divergence for every summable sequence of positive w ′ k , k ∈ N," while the implication trivially holds true if the expected average KL divergence is replaced by the total variation. This is illustrated in the last example of this section. An interesting related question (which is beyond the scope of this paper) is how to chose the weights to optimize the behaviour of a predictor before asymptotic.

The idea of the proof of Theorem 3 is as follows. For every µ and every n we consider the sets T n µ of those x 1..n on which µ is greater than ρ. These sets have to have (from some n on) a high probability with respect to µ. Then since ρ predicts µ in expected average KL divergence, the ρ-probability of these sets cannot decrease exponentially fast (that is, it has to be quite large). (The sequences µ(x 1..n )/ρ(x 1..n ), n ∈ N will play the role of densities of the proof of Theorem 2, and the sets T n µ the role of sets T µ on which the density is non-zero.) We then use, for each given n, the same scheme to cover the set X n with countably many T n µ , as was used in the proof of Theorem 2 to construct a countable covering of the set X ∞ , obtaining for each n a predictor ν n . Then the predictor ν is obtained as n∈N w n ν n , where the weights decrease subexponentially. The latter fact ensures that, although the weights depend on n, they still play no role asymptotically. The technically most involved part of the proof is to show that the sets T n µ in asymptotic have sufficiently large weights in those countable covers that we construct for each n. This is used to demonstrate the implication "if a set has a high µ probability, then its ρ-probability does not decrease too fast, provided some regularity conditions." The proof is broken into the same steps as the (simpler) proof of Theorem 2, to make the analogy explicit and the proof more understandable.

Proof. Define the weights w k := wk -2 , where w is the normalizer 6/π 2 .

Step 1: densities. Define the sets

T n µ := x 1..n ∈ X n : µ(x 1..n ) ≥ 1 n ρ(x 1..n ) . (5)
Using Markov's inequality, we derive

µ(X n \T n µ ) = µ ρ(x 1..n ) µ(x 1..n ) > n ≤ 1 n E µ ρ(x 1..n ) µ(x 1..n ) = 1 n , (6)
so that µ(T n µ ) → 1. (Note that if µ is singular with respect to ρ, as is typically the case, then ρ(x 1..n ) µ(x 1..n ) converges to 0 µ-a.e. and one can replace 1 n in ( 5) by 1, while still having µ(T n µ ) → 1.) Step 2n: a countable cover, time n. Fix an n ∈ N. Define m n 1 := max µ∈C ρ(T n µ ) (since X n are finite all suprema are reached). Find any

µ n 1 such that ρ n 1 (T n µ n 1 ) = m n 1 and let T n 1 := T n µ n 1 . For k > 1, let m n k := max µ∈C ρ(T n µ \T n k-1 ). If m n k > 0, let µ n k be any µ ∈ C such that ρ(T n µ n k \T n k-1 ) = m n k , and let T n k := T n k-1 ∪ T n µ n k ; otherwise let T n k := T n k-1 .
Observe that (for each n) there is only a finite number of positive m n k , since the set X n is finite; let K n be the largest index k such that m n k > 0. Let

ν n := Kn k=1 w k µ n k . (7)
As a result of this construction, for every n ∈ N every k ≤ K n and every x 1..n ∈ T n k using (5) we obtain

ν n (x 1..n ) ≥ w k 1 n ρ(x 1..n ). ( 8
)
Step 2: the resulting predictor. Finally, define

ν := 1 2 γ + 1 2 n∈N w n ν n , ( 9
)
where γ is the i.i.d. measure with equal probabilities of all x ∈ X (that is, γ(x 1..n ) = |X | -n for every n ∈ N and every x 1..n ∈ X n ). We will show that ν predicts every µ ∈ C, and then in the end of the proof (Step r) we will show how to replace γ by a combination of a countable set of elements of C (in fact, γ is just a regularizer which ensures that ν-probability of any word is never too close to 0).

Step 3: ν predicts every µ ∈ C. Fix any µ ∈ C. Introduce the parameters ε n µ ∈ (0, 1), n ∈ N, to be defined later, and let

j n µ := 1/ε n µ . Observe that ρ(T n k \T n k-1 ) ≥ ρ(T n k+1 \T n k )
, for any k > 1 and any n ∈ N, by definition of these sets. Since the sets

T n k \T n k-1 , k ∈ N are disjoint, we obtain ρ(T n k \T n k-1 ) ≤ 1/k. Hence, ρ(T n µ \T n j ) ≤ ε n µ for some j ≤ j n µ , since otherwise m n j = max µ∈C ρ(T n µ \T n j n µ ) > ε n µ so that ρ(T n j n µ +1 \T n j n µ ) > ε n µ = 1/j n µ , which is a contradiction. Thus, ρ(T n µ \T n j n µ ) ≤ ε n µ . (10)
We can upper-bound µ(T n µ \T n j n µ ) as follows. First, observe that

d n (µ, ρ) = - x 1..n ∈T n µ ∩T n j n µ µ(x 1..n ) log ρ(x 1..n ) µ(x 1..n ) - x 1..n ∈T n µ \T n j n µ µ(x 1..n ) log ρ(x 1..n ) µ(x 1..n ) - x 1..n ∈X n \T n µ µ(x 1..n ) log ρ(x 1..n ) µ(x 1..n ) = I + II + III. (11)
Then, from (5) we get

I ≥ -log n. ( 12
)
Observe that for every n ∈ N and every set A ⊂ X n , using Jensen's inequality we can obtain

- x 1..n ∈A µ(x 1..n ) log ρ(x 1..n ) µ(x 1..n ) = -µ(A) x 1..n ∈A 1 µ(A) µ(x 1..n ) log ρ(x 1..n ) µ(x 1..n ) ≥ -µ(A) log ρ(A) µ(A) ≥ -µ(A) log ρ(A) - 1 2 . ( 13
)
where in the second inequality we have usedlog ε n µ = o(n) and d n (µ, ρ) = o(n), in the last inequality we have again used the fact that the entropy is maximized when all events are equiprobable, while the last equality follows from (17). Moreover, from (9) we find

II ≤ log 2 - x 1..n ∈X n \T n j n µ µ(x 1..n ) log γ(x 1..n ) µ(x 1..n ) ≤ 1 + nµ(X n \T n j n µ ) log |X | = o(n), (21)
where in the last inequality we have used γ(x 1..n ) = |X | -n and µ(x 1..n ) ≤ 1, and the last equality follows from (17). From ( 19), ( 20) and ( 21) we conclude 1 n d n (ν, µ) → 0.

Step r: the regularizer γ. It remains to show that the i.i.d. regularizer γ in the definition of ν (9), can be replaced by a convex combination of a countably many elements from C. Indeed, for each n ∈ N, denote

A n := {x 1..n ∈ X n : ∃µ ∈ C µ(x 1..n ) = 0},
and let for each x 1..n ∈ X n the measure µ x 1..n be any measure from C such that µ

x 1..n (x 1..n ) ≥ 1 2 sup µ∈C µ(x 1..n ). Define γ ′ n (x ′ 1..n ) := 1 |A n | x 1..n ∈An µ x 1..n (x ′ 1..n ),
for each x ′ 1..n ∈ A n , n ∈ N, and let γ ′ := k∈N w k γ ′ k . For every µ ∈ C we have

γ ′ (x 1..n ) ≥ w n |A n | -1 µ x 1..n (x 1..n ) ≥ 1 2 w n |X | -n µ(x 1..n )
for every n ∈ N and every x 1..n ∈ A n , which clearly suffices to establish the bound II = o(n) as in ( 21).

Example: countable classes of measures. A very simple but rich example of a class C that satisfies the conditions of both the theorems above, is any countable family C = {µ k : k ∈ N} of measures. In this case, any mixture predictor ρ := k∈N w k µ k predicts all µ ∈ C both in total variation and in expected average KL divergence. A particular instance that has gained much attention in the literature is the family of all computable measures. Although countable, this family of processes is rather rich. The problem of predicting all computable measures was introduced in [Solomonoff(1978)] where a mixture predictor was proposed. Example: Bernoulli i.i.d. processes. Consider the class C B = {µ p : p ∈ [0, 1]} of all Bernoulli i.i.d. processes: µ p (x k = 0) = p independently for all k ∈ N. Clearly, this family is uncountable. Moreover, each set T p := {x ∈ X ∞ : the limiting fraction of 0s in x equals p}, has probability 1 with respect to µ p and probability 0 with respect to any µ p ′ : p ′ = p. Since the sets T p , p ∈ [0, 1] are non-overlapping, there is no measure ρ for which ρ(T p ) > 0 for all p ∈ [0, 1]. That is, there is no measure ρ with respect to which all µ p are absolutely continuous. Therefore, by Theorem 1, a predictor that predicts any µ ∈ C B in total variation does not exist, demonstrating that this notion of prediction is rather strong. However, we know (e.g. [Krichevsky(1993)]) that the Laplace predictor (1) predicts every Bernoulli i.i.d. process in expected average KL divergence (and not only). Hence, Theorem 2 implies that there is a countable mixture predictor for this family too. Let us find such a predictor. Let µ q : q ∈ Q be the family of all Bernoulli i.i.d. measures with rational probability of 0, and let ρ := q∈Q w q µ q , where w q are arbitrary positive weights that sum to 1. Let µ p be any Bernoulli i.i.d. process. Let h(p, q) denote the divergence p log(p/q) + (1p) log(1p/1q). For each ε we can find a q ∈ Q such that h(p, q) < ε. Then

1 n d n (µ p , ρ) = 1 n E µp log log µ p (x 1..n ) log ρ(x 1..n ) ≤ 1 n E µp log log µ p (x 1..n ) w q log µ q (x 1..n ) = - log w q n + h(p, q) ≤ ε + o(1). ( 22
)
Since this holds for each ε we conclude that 1 n d n (µ p , ρ) → 0 and ρ predicts every µ ∈ C B in expected average KL divergence. Example: stationary processes. In [Ryabko(1988)] a predictor ρ R was constructed which predicts every stationary process ρ ∈ C S in expected average KL divergence. (This predictor is obtained as a mixture of predictors for k-order Markov sources, for all k ∈ N.) Therefore, Theorem 3 implies that there is also a countable mixture predictor for this family of processes. Such a predictor can be constructed as follows (the proof in this example is based on the proof in [Ryabko and Astola(2006)], Appendix 1). Observe that the family C k of k-order stationary binaryvalued Markov processes is parametrized by 2 k [0, 1]-valued parameters: probability of observing 0 after observing x 1..k , for each x 1..k ∈ X k . For each k ∈ N let µ k q , q ∈ Q 2 k be the (countable) family of all stationary k-order Markov processes with rational values of all the parameters. We will show that any predictor ν := k∈N q∈Q 2 k w k w q µ k q , where w k , k ∈ N and w q , q ∈ Q 2 k , k ∈ N are any sequences of positive real weights that sum to 1, predicts every stationary µ ∈ C S in expected average KL divergence. For µ ∈ C S and k ∈ N define the k-order conditional Shannon entropy h k (µ) := E µ log µ(x k+1 |x 1..k ). We have h k+1 (µ) ≥ h k (µ) for every k ∈ N and µ ∈ C S , and the limit

h ∞ (µ) := lim k→∞ h k (µ) (23)
is called the limit Shannon entropy, see e.g. [Gallager(1968)]. Fix some µ ∈ C S . It is easy to see that for every ε > 0 and every k ∈ N we can find a k-order stationary Markov measure µ k qε , q ε ∈ Q 2 k with rational values of the parameters, such that

E µ log µ(x k+1 |x 1..k ) µ k qε (x k+1 |x 1..k ) < ε. (24)
We have

1 n d n (µ, ν) ≤ - log w k w qε n + 1 n d n (µ, µ k qε ) = O(k/n) + 1 n E µ log µ(x 1..n ) - 1 n E µ log µ k qε (x 1..n ) = o(1) + h ∞ (µ) - 1 n E µ n k=1 log µ k qε (x t |x 1..t-1 ) = o(1) + h ∞ (µ) - 1 n E µ k t=1 log µ k qε (x t |x 1..t-1 ) - n -k n E µ log µ k qε (x k+1 |x 1..k ) ≤ o(1) + h ∞ (µ) - n -k n (h k (µ) -ε), ( 25
)
where the first inequality is derived analogously to ( 22), the first equality follows from (3), the second equality follows from the Shannon-McMillan-Breiman theorem (e.g. [Gallager(1968)]), that states that 1 n log µ(x 1..n ) → h ∞ (µ) in expectation (and a.s.) for every µ ∈ C S , and (3); in the third equality we have used the fact that µ k qε is k-order Markov and µ is stationary, whereas the last inequality follows from (24). Finally, since the choice of k and ε was arbitrary, from ( 25) and ( 23) we obtain lim n→∞ 1 n d n (µ, ν) = 0. Example: weights may matter. Finally, we provide an example that illustrates the difference between the formulations of Theorems 2 and 3: in the latter the weights are not arbitrary. We will construct a sequence of measures ν k , k ∈ N, a measure µ, and two sequences of positive weights w k and w ′ k with k∈N w k = k∈N w ′ k = 1, for which ν := k∈N w k ν k predicts µ in expected average KL divergence, but ν ′ := k∈N w ′ k ν k does not. Let ν k be a deterministic measure that first outputs k 0s and then only 1s, k ∈ N. Let w k = w/k 2 with w = 6/π 2 and w ′ k = 2 -k . Finally, let µ be a deterministic measure that outputs only 0s. We have

d n (µ, ν) = -log( k≥n w k ) = O(log n), but d n (µ, ν ′ ) = -log( k≥n w ′ k ) = -log(2 -n+1 ) = n -1 = o(n), proving the claim.

Characterizing predictable classes

Knowing that a mixture of a countable subset gives a predictor if there is one, a notion that naturally comes to mind when trying to characterize families of processes for which a predictor exists, is separability. Can we say that there is a predictor for a class C of measures if and only if C is separable? Of course, to talk about separability we need a suitable topology on the space of all measures, or at least on C. If the formulated questions were to have a positive answer, we would need a different topology for each of the notions of predictive quality that we consider. Sometimes these measures of predictive quality indeed define a nice enough structure of a probability space, but sometimes they do not. The question whether there exists a topology on C, separability with respect to which is equivalent to the existence of a predictor, is already more vague and less appealing. Nonetheless, in the case of total variation distance we obviously have a candidate topology: that of total variation distance, and indeed separability with respect to this topology is equivalent to the existence of a predictor, as the next theorem shows. This theorem also implies Theorem 2, thereby providing an alternative proof for the latter. In the case of expected average KL divergence the situation is different. While one can introduce a topology based on it, separability with respect to this topology turns out to be a sufficient but not a necessary condition for the existence of a predictor, as is shown in Theorem 5.

Separability

Definition 3 (unconditional total variation distance). Introduce the (unconditional) total variation distance v(µ, ρ)

:= sup A∈F |µ(A) -ρ(A)|.
Theorem 4. Let C be a set of probability measures on (X ∞ , F). There is a measure ρ such that ρ predicts every µ ∈ C in total variation if and only if C is separable with respect to the topology of total variation distance. In this case any measure ν of the form ν = ∞ k=1 w k µ k , where {µ k : k ∈ N} is any dense countable subset of C and w k are any positive weights that sum to 1, predicts every µ ∈ C in total variation. Proof. Sufficiency and the mixture predictor. Let C be separable in total variation distance, and let D = {ν k : k ∈ N} be its dense countable subset. We have to show that ν := k∈N w k ν k , where w k are any positive real weights that sum to 1, predicts every µ ∈ C in total variation. To do this, it is enough to show that µ(A) > 0 implies ν(A) > 0 for every A ∈ F and every µ ∈ C. Indeed, let A be such that µ

(A) = ε > 0. Since D is dense in C, there is a k ∈ N such that v(µ, ν k ) < ε/2. Hence ν k (A) ≥ µ(A) -v(µ, ν k ) ≥ ε/2 and ν(A) ≥ w k ν k (A) ≥ w k ε/2 > 0.
Necessity. For any µ ∈ C, since ρ predicts µ in total variation, µ has a density (Radon-Nikodym derivative) f µ with respect to ρ. We can define L 1 distance with respect to ρ as follows

L ρ 1 (µ, ν) = X ∞ |f µ -f ν |dρ.
The set of all measures that have a density with respect to ρ is separable with respect to this distance (for example a dense countable subset can be constructed based on measures whose densities are step-functions with finitely many steps, that take only rational values, see e.g. [Kolmogorov and Fomin(1975)]); therefore, its subset C is also separable. Let D be any dense countable subset of C. Thus, for every µ ∈ C and every ε there is a µ ′ ∈ D such that L ρ 1 (µ, µ ′ ) < ε. For every measurable set A we have

|µ(A) -µ ′ (A)| = A f µ dρ - A f µ ′ dρ ≤ A |f µ -f µ ′ |dρ ≤ X ∞ |f µ -f µ ′ |dρ < ε. Therefore, v(µ, µ ′ ) = sup A∈F |µ(A) -µ ′ (A)| < ε and the set C is separable in total variation distance.
Definition 4 (asymptotic KL "distance" D). Define asymptotic expected average KL divergence between measures µ and ρ as

D(µ, ρ) = lim sup n→∞ 1 n d n (µ, ρ). (26)
Theorem 5. For a set C of measures, separability with respect to the asymptotic expected average KL divergence D is a sufficient but not a necessary condition for the existence of a predictor:

(i) If there exists a countable set D := {ν k : k ∈ N} ⊂ C such that for every µ ∈ C and every ε > 0 there is a measure µ ′ ∈ D such that D(µ, µ ′ ) < ε, then every measure ν of the form ν = ∞ k=1 w k µ k , where w k are any positive weights that sum to 1, predicts every µ ∈ C in expected average KL divergence.

(ii) There is an uncountable set C of measures and a measure ν such that ν predicts every µ ∈ C in expected average KL divergence, but

µ 1 = µ 2 implies D(µ 1 , µ 2 ) = ∞ for every µ 1 , µ 2 ∈ C; in particular, C is not separable with respect to D. Proof. (i) Fix µ ∈ C. For every ε > 0 pick k ∈ N such that D(µ, ν k ) < ε. We have d n (µ, ν) = E µ log µ(x 1..n ) ν(x 1..n ) ≤ E µ log µ(x 1..n ) w k ν k (x 1..n ) = -log w k + d n (µ, ν k ) ≤ nε + o(n).
Since this holds for every ε, we conclude 1 n d n (µ, ν) → 0. (ii) Let C be the set of all deterministic sequences (measures concentrated on just one sequence) such that the number of 0s in the first n symbols is less than √ n. Clearly, this set is uncountable. It is easy to check that µ 1 = µ 2 implies D(µ 1 , µ 2 ) = ∞ for every µ 1 , µ 2 ∈ C, but the predictor ν given by ν(x n = 0) = 1/n independently for different n, predicts every µ ∈ C in expected average KL divergence.

Examples. Basically, the examples of the preceding section carry over here. Indeed, the example of countable families is trivially also an example of separable (with respect to either of the considered topologies) family. For Bernoulli i.i.d. and k-order Markov processes, the (countable) sets of processes that have rational values of the parameters, considered in the previous section, are dense both in the topology of the parametrization and with respect to the asymptotic average divergence D. It is also easy to check from the arguments presented in the corresponding example of Section 3 that the family of all k-order stationary Markov processes with rational values of the parameters, where we take all k ∈ N, is dense with respect to D in the set C S of all stationary processes, so that C S is separable with respect to D. Thus, the sufficient but not necessary condition of separability is satisfied in this case. On the other hand, neither of these latter families is separable with respect to the topology of total variation distance.

Conditions based on the local behaviour of measures.

Next we provide some sufficient conditions for the existence of a predictor based on local characteristics of the class of measures, that is, measures truncated to the first n observations. First of all, it must be noted that necessary and sufficient conditions cannot be obtained this way. The basic example is that of a family C 0 of all deterministic sequences that are 0 from some time on. This is a countable class of measures which is very easy to predict. Yet the class of measures on X n obtained by truncating all measures in C 0 to the first n observation coincides with what would be obtained by truncating all deterministic measures to the first n observation, the latter class being obviously not predictable at all (see also examples below). Nevertheless, considering this kind of local behaviour of measures, one can obtain not only sufficient conditions for the existence of a predictor, but also rates of convergence of the prediction error. It also gives some ideas of how to construct predictors, for the cases when the sufficient conditions obtained are met.

For a class C of stochastic processes and a sequence x 1..n ∈ X n introduce the coefficients

c x 1..n (C) := sup µ∈C µ(x 1..n ). ( 27
)
Define also the normalizer c n (C) :=

x 1..n ∈X n c x 1..n (C). ( 28
)
Definition 5 (NML estimate). The normalized maximum likelihood (e.g. [Krichevsky(1993)]) estimator λ is defined as

λ C (x 1..n ) := 1 c n (C) c x 1..n (C), ( 29
)
for each x 1..n ∈ X n .

The family λ C (x 1..n ) (indexed by n) in general does not immediately define a stochastic process over X ∞ (λ C are not consistent for different n); thus, in particular, using average KL divergence for measuring prediction quality would not make sense, since

d n (µ(•|x 1..n-1 ), λ C (•|x 1..n-1 ))
can be negative, as the following example shows. Example: negative d n for NML estimates. Let the processes µ i , i ∈ {1, . . . , 4} be defined on the steps n = 1, 2 as follows. µ 1 (00) = µ 2 (01) = µ 4 (11) = 1, while µ 3 (01) = µ 3 (00) = 1/2. We have

λ C (1) = λ C (0) = 1/2, while λ C (00) = λ C (01) = λ C (11) = 1/3. If we define λ C (x|y) = λ C (yx)/λ C (y) we get λ C (1|0) = λ C (0|0) = 2/3. Then d 2 (µ 3 (•|0), λ C (•|0)) = log 3/4 < 0.
Yet, by taking an appropriate mixture, it is still possible to construct a predictor (a stochastic process) based on λ, that predicts all the measures in the class.

Definition 6 (predictor ρ c ). Let w := 6/π 2 and let w k := 1 wk 2 . Define a measure µ k as follows. On the first k steps it is defined as λ C , and for n > k it outputs only zeros with probability 1; so, µ k (x 1..k ) = λ C (x 1..k ) and µ k (x n = 0) = 1 for n > k. Define the measure ρ c as

ρ c = ∞ k=1 w k µ k . (30)
Thus, we have taken the normalized maximum likelihood estimates λ n for each n and continued them arbitrarily (actually, by a deterministic sequence) to obtain a sequence of measures on (X ∞ , F) that can be summed.

Theorem 6. For a class C of stochastic processes the predictor ρ c defined above satisfies

1 n d n (µ, ρ c ) ≤ log c n (C) n + O log n n ; (31) in particular, if log c n (C) = o(n). ( 32
)
then ρ c predicts every µ ∈ C in expected average KL divergence.

Proof. Indeed,

1 n d n (µ, ρ c ) = 1 n E log µ(x 1..n ) ρ c (x 1..n ) ≤ 1 n E log µ(x 1..n ) w n µ n (x 1..n ) ≤ 1 n log c n (C) w n = 1 n (log c n (C) + 2 log n + log w). ( 33
)
Example: i.i.d., finite-memory. To illustrate the applicability of the theorem we first consider the class of i.i.d. processes C B over the binary alphabet X = {0, 1}. It is easy to see that for each x 1 , . . . , x n sup

µ∈C B µ(x 1..n ) = (k/n) k (1 -k/n) n-k
where k = #{i ≤ n : x i = 0} is the number of 0s in x 1 , . . . , x n . For the constants c n (C) we can derive

c n (C) = x 1..n ∈X n sup µ∈C B µ(x 1..n ) = x 1..n ∈X n (k/n) k (1 -k/n) n-k = n k=0 n k (k/n) k (1 -k/n) n-k ≤ n k=0 n t=0 n k (k/n) t (1 -k/n) n-t = n + 1, so that c n (C) ≤ n + 1.
In general, for the class C k of processes with memory k over a finite space X we can get polynomial c n (C) (see e.g. [Krichevsky(1993)], and also [START_REF] Ryabko | [END_REF]). Thus, with respect to finite-memory processes, the conditions of Theorem 6 leave ample space for the growth of c n (C), since (32) allows subexponential growth of c n (C). Moreover, these conditions are tight, as the following example shows. Example: exponential coefficients are not sufficient. Observe that the condition (32) cannot be relaxed further, in the sense that exponential coefficients c n are not sufficient for prediction. Indeed, for the class of all deterministic processes (that is, each process from the class produces some fixed sequence of observations with probability 1) we have c n = 2 n , while obviously for this class a predictor does not exist. Example: stationary processes. For the set of all stationary processes we can obtain c n (C) ≥ 2 n /n (as is easy to see by considering periodic n-order Markov processes, for each n ∈ N), so that the conditions of Theorem 6 are not satisfied. This cannot be fixed, since uniform rates of convergence cannot be obtained for this family of processes, as was shown in [Ryabko(1988)].

Optimal rates of convergence. A natural question that arises with respect to the bound (31) is whether it can be matched by a lower bound. This question is closely related to the optimality of the normalized maximum likelihood estimates used in the construction of the predictor. In general, since NML estimates are not optimal, neither are the rates of convergence in (31). To obtain (close to) optimal rates one has to consider a different measure of capacity.

To do so, we make the following connection to a problem in information theory. Let P(X ∞ ) be the set of all stochastic processes (probability measures) on the space (X ∞ , F), and let P(X ) be the set of probability distributions over a (finite) set X . For a class C of measures we are interested in a predictor that has a small (or minimal) worst-case (with respect to the class C) probability of error. Thus, we are interested in the quantity inf

ρ∈P(X ∞ ) sup µ∈C D(µ, ρ), (34)
where the infimum is taken over all stochastic processes ρ, and D is the asymptotic expected average KL divergence (26). (In particular, we are interested in the conditions under which the quantity (34) equals zero.) This problem has been studied for the case when the probability measures are over a finite set X , and D is replaced simply by the KL divergence d between the measures. Thus, the problem was to find the probability measure ρ (if it exists) on which the following minimax is attained

R(A) := inf ρ∈P(X ) sup µ∈A d(µ, ρ), (35)
where A ⊂ P(X ). This problem is closely related to the problem of finding the best code for the class of sources A, which was its original motivation. The normalized maximum likelihood distribution considered above does not in general lead to the optimum solution for this problem. The optimum solution is obtained through the result that relates the minimax (35) to the so-called channel capacity.

Definition 7 (Channel capacity). For a set A of measures on a finite set X the channel capacity of A is defined as C(A) := sup

P ∈P 0 (A) µ∈S(P ) P (µ)d(µ, ρ P ), ( 36
)
where P 0 (A) is the set of all probability distributions on A that have a finite support, S(P ) is the (finite) support of a distribution P ∈ P 0 (A), and ρ P = µ∈S(P ) P (µ)µ.

It is shown in [Ryabko(1979), Gallager(1976Gallager( (revised 1979))] that C(A) = R(A), thus reducing the problem of finding a minimax to an optimization problem. For probability measures over infinite spaces this result (R(A) = C(A)) was generalized by [Haussler(1997)], but the divergence between probability distributions is measured by KL divergence (and not asymptotic average KL divergence), which gives infinite R(A) e.g. already for the class of i.i.d. processes.

However, truncating measures in a class C to the first n observations, we can use the results about channel capacity to analyze the predictive properties of the class. Moreover, the rates of convergence that can be obtained along these lines are close to optimal. In order to pass from measures minimizing the divergence for each individual n to a process that minimizes the divergence for all n we use the same idea as when constructing the process ρ c .

Theorem 7. Let C be a set of measures on (X ∞ , F), and let C n be the class of measures from C restricted to X n . There exists a measure ρ C such that

1 n d n (µ, ρ C ) ≤ C(C n ) n + O log n n ; (37) in particular, if C(C n )/n → 0 then ρ C predicts every µ ∈ C in expected average KL divergence.
Moreover, for any measure ρ C and every ε > 0 there exists µ ∈ C such that

1 n d n (µ, ρ C ) ≥ C(C n ) n -ε.
Proof. As shown in [Gallager(1976[Gallager( (revised 1979))], for each n there exists a sequence

ν n k , k ∈ N of measures on X n such that lim k→∞ sup µ∈C n d n (µ, ν n k ) → C(C n ).
For each n ∈ N find an index k n such that

| sup µ∈C n d n (µ, ν n kn ) -C(C n )| ≤ 1.
Define the measure ρ n follows. On the first n symbols it coincides with ν n kn and ρ n (x m = 0) = 1 for m > n. Finally, set ρ C = ∞ n=1 w n ρ n , where w k = 1 wn 2 , w = 6/π 2 . We have to show that lim n→∞ 1 n d n (µ, ρ C ) = 0 for every µ ∈ C. Indeed, similarly to (33), we have

1 n d n (µ, ρ C ) = 1 n E µ log µ(x 1..n ) ρ C (x 1..n ) ≤ log w -1 k n + 1 n E µ log µ(x 1..n ) ρ n (x 1..n ) ≤ log w + 2 log n n + 1 n d n (µ, ρ n ) ≤ o(1) + C(C n ) n . (38)
The second statement follows from the fact [Ryabko(1979), Gallager(1976Gallager( (revised 1979))] that C(C n ) = R(C n ) (cf. ( 35)).

Thus, if the channel capacity C(C n ) grows sublinearly, a predictor can be constructed for the class of processes C. In this case the problem of constructing the predictor is reduced to finding the channel capacities for different n and finding the corresponding measures on which they are attained or approached. Examples. For the class of all Bernoulli i.i.d. processes, the channel capacity C(C n B ) is known to be O(log n) [Krichevsky(1993)]. For the family of all stationary processes it is O(n), so that the conditions of Theorem 7 are satisfied for the former but not for the latter.

We also remark that the requirement of a sublinear channel capacity cannot be relaxed, in the sense that a linear channel capacity is not sufficient for prediction, since it is the maximal possible capacity for a set of measures on X n , achieved e.g. on the set of all measures, or on the set of all deterministic sequences.

Discussion

The first possible extension of the results of the paper that comes to mind is to find out whether the same holds for other measures of performance, such as prediction in KL divergence without time-averaging, or with probability 1 rather then in expectation, or with respect to other measures of prediction error, such as absolute distance. (See [START_REF] Ryabko | [END_REF]] for a discussion of different measures of performance and relations between them.) Maybe the same results can be obtained in more general formulations, for example, using f -divergences of [Csiszar(1967)].

More generally, the questions we addressed in this work are a part of a larger problem: given an arbitrary class C of stochastic processes, find the best predictor for it. We have considered two subproblems: first, in which form to look for a predictor if one exists. Here we have shown that if any predictor works then a Bayesian one works too. The second one is to characterize families of processes for which a predictor exists. Here we have analyzed what the notion of separability furnishes in this respect, as well as identified some simple sufficient conditions based on the local behaviour of measures in the class. Another approach would be to identify the conditions which two measures µ and ρ have to satisfy in order for ρ to predict µ. For prediction in total variation such conditions have been identified [Blackwell and Dubins(1962), Kalai and Lehrer(1994)] and, in particular, in the context of the present work, they turn out to be very useful. [Kalai and Lehrer(1994)] also provide some characterization for the case of a weaker notion of prediction: difference between conditional probabilities of the next (several) outcomes (weak merging of opinions). In [Ryabko and Hutter(2008b)] some sufficient conditions are found for the case of prediction in expected average KL divergence, and prediction in average KL divergence with probability 1. Of course, another very natural approach to the general problem posed above is to try and find predictors (in the form of algorithms) for some particular classes of processes which are of practical interest. Towards this end, we have found a rather simple form that some solution to this question has if a solution exists: a Bayesian predictor whose prior is concentrated on a countable set. We have also identified some sufficient conditions under which a predictor can actually be constructed (e.g. using NML estimates). However, the larger question of how to construct an optimal predictor for an arbitrary given family of processes, remains open.

Taking an even more general perspective, one can consider the problem of finding the best response to the actions of a (stochastic) environment, which itself responds to the actions of a learner. Allowing into consideration environments that change their behaviour in response to the action of the learner, clearly makes the problem much more difficult, but it also dramatically extends the range of applications. For this general problem one can pose the same questions: given a set C of environments, how can we construct a learner that is (asymptotically) optimal if any environment from C is chosen to generate the data? One can consider Bayesian learners for this formulation too [Hutter(2005)]; it would be interesting to find out whether one can show that when there is an learner which is optimal in every environment from C, then there is a Bayesian learner with a countably supported prior that has this property too.

Thus, from ( 13) and (10) we get

where in the second inequality we have used the fact that entropy is maximized when all events are equiprobable, in the third one we used |X n \T n µ | ≤ |X | n , while the last inequality follows from (6). Combining ( 11) with the bounds ( 12), ( 14) and ( 15) we obtain

we can define the parameters ε n µ in such a way thatlog ε n µ = o(n) while at the same time the bound (16) gives µ(T n µ \T n

We proceed with the proof of

where the first inequality follows from (9), the second from (8), and in the equality we have used w j n µ = w/(j n µ ) 2 and j n µ = 1/ε µ n . Next we use the decomposition

From ( 18) we find


Rachel Panckhurst

Debra Marsh

eLEN2 -2nd Generation E-Learning Exchange Networks

eLEN2 -2nd generation eLearning Exchange Networks.

Introduction

Since May 2007 the authors have explored and evaluated the use, relative merits and challenges of social networking within the context of higher education professional development programmes in France and in Britain.

The social networking tool Ning 1 was adopted for Masters' level courses at Université Paul-Valéry Montpellier 3 and the University of Hull with the specific aim of establishing an effective collaborative pedagogical environment and sense of community, by placing students at the centre of the learning process (cf. Coombes et al., 2003). This approach was used for two key reasons: a) the students' professional backgrounds are very different and it is not within the remit of the more structured 'academic' programme to cater for such diverse needs and experience; b) these students are working at a distance and have infrequent opportunity to meet face-to-face.

Analyses of three case studies conducted during [START_REF] Marsh | eLEN -eLearning Exchange Networks : reaching out to effective bilingual and multicultural University collaboration[END_REF]-2008[START_REF] Marsh | eLEN -eLearning Exchange Networks : reaching out to effective bilingual and multicultural University collaboration[END_REF]Panckhurst & Marsh, 2008a, b) strongly suggested that a social network can benefit student learning by allowing for a sense of freedom from the perceived 'constraints' of a more formalised institutionbased VLE 2 or LMS 3 . The online community of practice proved a powerful support to students who were accustomed to more directive, hand-holding pedagogy, to take up the 'independence' challenge and direct their own learning.

It was on the basis of this 'success' that case study 4 was set up. However, in the very early stages it was evident that this group would not evolve and develop in the same way as had the three previous case studies. This paper sets out some reasons why and concludes with suggestions of how to move towards 2 nd generation eLearning Exchange Networks (eLEN2) through evolving both the pedagogical approach and implementation.

Case study 4 2.1 Organisation

This fourth case study with second-year Masters' students at Montpellier University took place between October 2008 and March 2009. The focus of the network was to provide an online forum through which the students could discuss pedagogical issues related to eLearning practice, via a "private" eLEN using Ning (http://reelgaf2009.ning.com/).

The nature and general organisation of the network remained consistent with previous case studies with one modification to the organisation of the student discussions.

3 distinct phases were planned:

1. A general getting-to-know-each-other phase. Tutors "led" the initial discussion threads but quickly stepped back to encourage student autonomy in preparation for phase 2; 2. The compulsory discussion threads stage. Discussions were designed and led by individual students with peer group student participation. At the end, students were required to submit a reflective synthesis of their experience; 3. The final tutor-led phase. During this 3rd phase (new in case study 4, and in response to earlier student feedback), tutors initiated and led discussions inspired by key points from student syntheses of phase 2 discussions. From the outset, the student autonomy ratio was much higher than it had ever been before. Feedback from students themselves made it quite clear that tutor intervention during phase 3 was not appreciated. Tutors, who had taken a 'back-seat' in order to facilitate independence, hesitated to intervene, considering their contributions were unwelcome and a distraction from the studentled exchanges.

Analysis

The advent of social networks (Facebook, Beebo and Twitter 4 ) has resulted in familiarity with the concept of social networking and this group of students were clearly far more comfortable in their online exchanges and the concept of leading and initiating discussions. This said, the very nature of compulsory discussions was a problem for certain students.

The 'compulsory' discussion phase has formed an integral part of these case studies from the beginning of the research. Their conception was based upon the now recognised pedagogical practice that it is not enough to expect a group of people who are logged in to the same environment to communicate.

"The fallacy is to think that social networks are made up of people. They're not: social networks consist of people who are connected by a shared object." (Engelstrom, 2005[START_REF] Conole | Cloudworks: Social networking for learning design[END_REF].

In any social network there is a need for a sense of purpose, a structure and an end result for there to be effective interaction and exchange.

Yet, through case study 4 the authors have recognised that some of the 'success' of the early use of the social network Ning could well be attributed to the 'novelty' factor of using online forums in the learning context as much as to the pedagogical benefits. Simply continuing with the same formula as previous case studies is no longer sufficient. Students' needs, expectations and skills in online exchange have moved on. As a consequence, it is time to evolve to the next generation of social networks in education. This does not require a change of technology, but a step forward in thinking and approach in how to organise and support social networking and learning. In other words, the very nature and purpose of engagement and motivation online needs to reviewed and the results acted upon.

Conclusion: towards eLEN2

In previous research related to 1st generation eLENs (Panckhurst & Marsh 2008a) the authors have noted the following as key elements to the success of a social network:

▪ sense of purpose ▪ group cohesion ▪ tutor guidance shifting towards learner self-group management ▪ encouragement/promotion of learner independence/autonomy ▪ learners' sense of 'ownership' ▪ teaching staff /tutors 'letting go' and 'taking the back seat'

Case study 4 has shown that students more readily accept the notion of social networks now than several years ago, but they still need something around which to build their discussions. Social networking requires social objects: "The term 'social networking' makes little sense if we leave out the objects that mediate the ties between people." (Engestrom, 2005). Weller (2008) defines a social object as "something […] that facilitates conversation, and thus social interaction". In this paper, it has been suggested that eLEN2 do not require new technology, but a new, more developed pedagogy. As [START_REF] Anderson | Social Networking in Education[END_REF] states: "social networking learning designs will prove more effective, efficient and motivating ways to support learning than any previous formsincluding both traditional campus based and distance education".

The following three issues need to be explored in more depth (cf. [START_REF] Weller | Social objects in education[END_REF]):

  29 discussion threads were initiated during the 2008-2009 eLEN: 12 by the tutors, 16 compulsory threads by the students and 1 spontaneous extra-curricular thread initiated by a student.


Frédéric Planchet
email: fplanchet@winter-associes.fr

Marc Juillard

MESURE DE L'INCERTITUDE TENDANCIELLE SUR LA MORTALITE APPLICATION A UN REGIME DE RENTES EN COURS DE SERVICE

Keywords: Tables prospectives, extrapolation, lissage, rentes viagères, mortalité stochastique Prospective tables, extrapolation, adjustment, life annuities, stochastic mortality

RESUME

L'objectif de ce travail est de proposer un modèle réaliste et opérationnel pour mesurer le « risque de dérive » associé à la construction de tables de mortalité prospectives. Une application du modèle à l'évaluation de l'engagement d'un engagement de retraite est proposée. Le modèle présenté est construit sur la base d'un modèle de Lee-Carter. Les tables prospectives stochastiques sont obtenues en modélisant l'incertitude attachée au paramètre tendanciel du modèle.

INTRODUCTION

Les analyses prospectives de mortalité conduisent à anticiper les évolutions futures des taux de décès aux différents âges. Dans les modèles maintenant classiques de construction de tables prospectives, comme le modèle de Lee-Carter (voir notamment LEE et CARTER [1992], [START_REF] Lee R | The Lee-Carter method of forecasting mortality, with various extensions and applications[END_REF], [START_REF] Sithole | An investigation into parametric models for mortality projections, with applications to immediate annuitants and life office pensioners[END_REF]) ou les modèles poissoniens (cf. BROUHNS et al. [2002] et PLANCHET et THEROND [2006] pour une présentation et une discussion de ces modèles), la dérive de mortalité future est anticipée à partir des observations passées.

Même en admettant qu'il est légitime de prolonger dans les années à venir les tendances observées par le passé (on pourra se reporter à CAREY et TULAPURKAR [2003] pour des analyses intégrant des considérations biologiques et environementales, ainsi que GUTTERMAN et VANDERHOOF [1999] pour une discussion sur ce point), plusieurs sources d'incertitude viennent perturber la détermination de la tendance future : choix de la période d'observation, fluctuations stochastique des taux de mortalité, événements exceptionnels, etc.. Cette incertitude fait peser sur les assureurs de rentes viagères et les régimes de retraite un risque systématique (non mutualisable) dont l'impact financier peut être très important.

Ainsi, en France, la récente actualisation des tables utilisées par les assureurs pour le provisionnement des rentes viagères illustre les difficultés d'une telle anticipation et les enjeux financiers associés : par rapport aux tables TPG1 1993 en vigueur jusqu'au 31/12/2006, les nouvelles tables TGH 05 et TGF 05 qui entrent en vigueur le 01/01/2007 conduisent à des majorations de provision parfois supérieures à 20%, comme l'illustre le tableau suivant : Dans ce contexte il apparaît opportun de rechercher à mesurer le risque associé à cette erreur d'anticipation et de quantifier son impact en terme de provisions pour un régime de rentiers.

On utilise pour cela dans la présente étude le modèle de Lee-Carter (voir notamment LEE et CARTER [1992], [START_REF] Lee R | The Lee-Carter method of forecasting mortality, with various extensions and applications[END_REF][START_REF] Sithole | An investigation into parametric models for mortality projections, with applications to immediate annuitants and life office pensioners[END_REF]) pour construire une surface de mortalité

( ) t x, μ
. Après un ajustement des taux passés, les taux de mortalité pour les années futures se déduisent classiquement de l'extrapolation de la composante temporelle. On peut noter que l'utilisation de la variante log-Poisson (cf. [START_REF] Brouhns | A Poisson log-bilinear regression approach to the construction of projected lifetables[END_REF]) conduirait à des résultats très proches, qui ne seront pas repris ici.

A partir de ce modèle de référence, on propose un modèle stochastique de mortalité en considérant que le taux de mortalité futur ( )

t x, μ est lui-même aléatoire, et que donc ( ) t x, μ
est un processus stochastique (comme fonction de t à x fixé). L'aléa est introduit de manière à capturer l'incertitude sur l'estimation de la tendance future de la composante temporelle des taux de mortalité.

Après avoir construit un jeu de tables prospectives sur des données nationales à l'aide de ce modèle, nous l'utilisons pour calibrer l'incertitude sur la dérive anticipée et appliquons le modèle ainsi obtenu pour déterminer la distribution de l'engagement d'un régime de rentes. Les conséquences en terme d'anamyse du risque pesant sur le régime et de provisionnement sont examinées.

Le présent article complète l'analyse présentée dans PLANCHET et al. [2006], auquel le lecteur pourra se référer pour les détails méthodologiques des modèles de base.

LE MODELE DE MORTALITE

PRESENTATION

Le modèle retenu pour constuire les tables prospectives est un modèle stochastique adapté du modèle de Lee-Carter [START_REF] Lee R | Modelling and forecasting the time series of US mortality[END_REF]). On rappelle que la modélisation proposée pour le taux instantané de mortalité dans Lee-Carter est la suivante :

ln xt x x t xt k μ α β ε = + + , (1)
m t t τ = -+ et 1 M m T t t = -+ , ce
qui conduit aux expressions :

2 1 1 2 1 ˆT k k T a T τ τ + - = - ∑ et 1 2 ˆT b k a + = - , (3)
) ( )( ) 2 2 1 1 12 2 1 2 1 1 1 2 6 T T T T T T γ σ + ⎡ ⎤ - ⎢ ⎥ ⎢ ⎥ Σ = ⎢ ⎥ + + + - ⎢ ⎥ - ⎣ ⎦ (4)
On peut donc construire des réalisations de la mortalité future en effectuant des tirages dans la loi du vecteur ( )

, a b . La variable * t k ainsi obtenue est telle que ( ) * t t E k k = .
On obtient alors des réalisations des taux instantanés de sortie via :

( )

* * exp xt x x t k μ α β = + . ( 5
) Comme * t k at b = + est une variable gaussienne d'espérance t k at b = + et de variance : ( ) ( ) ( )( ) 2 2 2 2 12 1 2 1 1 2 1 T T T T T γ τ σ σ τ τ ⎛ ⎞ + + = -+ + ⎜ ⎟ -⎝ ⎠ , (6)
on note que :

( ) ( ) ( ) 2 2 2 * * exp exp x t xt x x t x x t E E k k β σ μ α β α β ⎛ ⎞ ⎜ ⎟ = + = + + ⎜ ⎟ ⎝ ⎠ , (7)
et donc :

( ) 2 2 2 * exp x t xt xt xt E β σ μ μ μ ⎛ ⎞ ⎜ ⎟ = > ⎜ ⎟ ⎝ ⎠ . ( 8
)
Le modèle stochastique a donc tendance à surestimer les taux de sortie par rapport à la surface de référence fournie par le modèle de Lee-Carter. Compte tenu du notre objectif de « perturber » la surface de mortalité, mais sous l'hypothèse que celle-ci définie correctement la tendance future espérée des taux instantanés de décès cette propriété du modèle est pénalisante et il convient d'adapter l'approche proposée. PLANCHET et al. [2006] proposent une version corrigée du biais du modèle définie par : On utilise ici une approche différente et a priori plus naturelle consistant à utiliser comme surface de référence déterministe la surface moyenne du modèle stochastique, soit ( )

2 2 2 * * exp x t xt x x t k β σ μ α β ⎛ ⎞ ⎜ ⎟ = - + ⎜ ⎟ ⎝ ⎠ (
2 2 2 * exp x t xt x x t E k β σ μ α β ⎛ ⎞ ⎜ ⎟ = + + ⎜ ⎟ ⎝ ⎠
. En effet, si le mécanisme aléatoire dont sont issus les taux de décès est bien associé à * t k at b = + , alors la mortalité de référence déterministe est bien définie par la surface moyenne ci-dessus, et non plus par la surface de Lee-Carter.

APPLICATION NUMERIQUE

On présente ici les résultats obtenus tout d'abord sur la famille de tables prospectives proposée puis, dans un second temps, les conséquences en terme de valorisation de l'engagement du régime de rentes.

La table prospective utilisée dans cette étude est celle utilisée dans PLANCHET et al. [2006] ; elle est construite à partir des tables du moment fournies par l'INED2 dans MESLE et [START_REF] Mesle | Comment améliorer la précision des tables de mortalité aux grands âges ? Le cas de la France[END_REF] et conduit à la surface de mortalité Lee-Carter suivante : La surface de référence ajustée de notre modèle stochastique est présentée sur le graphe cidessous : x(j) l'âge en 0 de l'individu j et r j le montant de sa rente annuelle.

La problématique est décrite de manière détaillée dans PLANCHET et al. [2006] ; nous retiendrons ici que l'on s'intéresse à la loi de du montant de l'engagement du régime :

( ) ( )

] [ ( )

1 1 1 1 1 ( ) ; * t t j x j t t t t j F i r T i ∞ ∞ - ∞ = = ∈ Λ = + = + ∑ ∑ ∑ J 1 ( 10
)
qui est une variable aléatoire telle que ( )

0 E L Λ = avec ( ) ∑ ∞ = - + = 1 0 1 t t t i F L .
Lorsque la mortalité future est connue (déterministe), l'analyse de la loi de Λ revient à mesurer les fluctuations d'échantillonnage qui est associé au « risque de volatilité » tel que décrit dans la modélisation proposées par les QIS 2 et 3 par exemple (cf. CEIOPS [2006]). Dans le contexte d'une mortalité stochastique, cette analyse nous fournit un moyen de quantifier le risque systématique qui vient s'ajouter à ce risque de base : ici nous pourrons donc mesurer ainsi le risque associé au choix de la dérive.

La méthode retenue consiste à simuler les durées de survie des rentiers, ( ) , ; on calcule également le coefficient de variation empirique :

( ) 2 0 1 1 1 L 1 1 λ N n n N n n N cv N λ = = - - = ∑ ∑ , ( 11
)
qui fournit un indicateur de la dispersion de l'engagement et dans une certaine mesure de sa « dangerosité ».

RESULTATS

La distribution empirique de l'engagement, représentée ici avec la distribution de référence dans le cas déterministe (avec 20 000 tirages) est présentée ci-dessous : Les résultats détaillés sont repris ci-après :

β σ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠
est proche de 1.

Sur un portefeuille de petite taille, l'impact de la mortalité stochastique sur l'engagement n'est pas très important. En effet le coefficient de variation de l'engagement stochastique n'est que 2,9 % plus élevé que celui de l'engagement déterministe.

Cependant comme nous l'avions montré dans PLANCHET et al. [2006] la taille du portefeuille est un paramètre important à prendre en compte. En effet si le niveau absolu de risque systématique ne dépend pas de la taille du portefeuille, il n'en va pas de même pour le risque mutualisable. La part de variance expliquée par la composante stochastique de la mortalité augmente donc avec la taille du portefeuille ; afin de mesurer cet effet, on construit un portefeuille fictif en répliquant le portefeuille de base n fois. En observant que l'on obtient ainsi une décomposition de l'engagement total Λ en la somme de n variables i.i.d.

( ) ( )

, .., n Λ Λ on trouve que :

( ) ( ) 1 2 V E n V E ⎡ ⎤ ⎛ ⎞ ⎡ ⎤ Λ Π = Λ Π ⎜ ⎟ ⎢ ⎥ ⎣ ⎦ ⎝ ⎠ ⎣ ⎦ et ( ) ( ) 1 E V nE V ⎡ ⎤ ⎛ ⎞ ⎡ ⎤ Λ Π = Λ Π ⎜ ⎟ ⎢ ⎥ ⎣ ⎦ ⎝ ⎠ ⎣ ⎦ , (12)
ce qui conduit, avec des notations évidentes, à : Les résultats détaillés sont repris ci-après : La prise en compte de la mortalité stochastique augmente le coefficient de variation de 63 %.

1 1 1 1 1 n n ω ω - ⎛ ⎞ ⎛ ⎞ = + - ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ , (13) avec ( ) [ ] ω
⎡ ⎤ Λ Π ⎣ ⎦ = Λ V E V . Si l'
Dans une approche « valeur à risque » (VaR), on trouve que le quantile à 75 % de la distribution de l'engagement est de 1 142 M€ dans le cas stochastique, ce qui est supérieur à la valeur obtenue dans le cas déterministe, soit 1 140 M€. En d'autres termes, la prise en compte du risque de dérive conduit ici (en suivant une approche VaR pour le calcul de la provision) à augmenter le montant provisionné de 0,17 %.

La prise en compte du risque de dérive a également pour conséquence de doubler l'imprécision dans l'évaluation de l'engagement 3 qui, au niveau de confiance de 95 %, passe de 0,7 % environ à près de 1,3 % Le graphique du « couloir de variation » de la tendance ayant mis en évidence le faible impact de la dérive de la mortalité dans le futur proche, le coefficient d'actualisation va jouer un rôle important dans la volatilité de la distribution de l'engagement.

En effet l'engagement stochastique tire sa volatilité des rentes qui vont être servies pendant longtemps. Or plus la rente à une durée de vie importante, plus le coefficient d'actualisation qui s'y applique est important. En fixant le taux d'actualisation à 0 on obtient les résultats suivant : Les résultats détaillés sont repris ci-après : En prenant un taux technique nul on augmente le coefficient de variation de l'engagement déterministe de 27 % et le coefficient de variation de l'engagement stochastique de 33 %.

Ainsi la prise en compte de la mortalité stochastique induit une plus grande sensibilité de l'engagement au taux d'actualisation.

CONCLUSION

Dans PLANCHET et al. [2006] nous avions mis en évidence le fait que l'évaluation de l'engagement d'un régime de rentiers, l'aléa associé aux fluctuations des taux de décès futurs autour de leur tendance n'avait qu'un faible impact que l'on pouvait légitimement négliger.

Le modèle mis en oeuvre ici permet de montrer que, si ces régimes sont particulièrement sensibles au risque d'erreur de spécification de la tendance future, l'incertitude sur ce point incluse dans les données passées ne suffit pas à expliquer les évolutions récentes observées.

Incidemment, on insistera sur le fait que l'on a fait ici le choix de modéliser l'aléa sur la 100,00 1 9 3 6 1 9 3 9 1 9 4 2 1 9 4 5 1 9 4 8 1 9 5 1 1 9 5 4 1 9 5 7 1 9 6 0 1 9 6 3 1 9 6 6 1 9 6 9 1 9 7 2 1 9 7 5 1 9 7 8 1 9 8 1 1 9 8 4 1 9 8 7 1 9 9 0 1 9 9 3 Génération Age TGF05 TPG1993 Linéaire (TGF05) Linéaire (TPG1993)

Fig. 9 : Evolution anticipée de l'espérance de vie à 60 ans

On observe que non seulement les niveaux absolus diffèrent sensiblement, mais également que la vitesse de croissance de l'espérance de vie à 60 ans a été sensiblement sous-estimée en 1993 : alors que les TPG 1993 anticipent une augmentation de 1,4 mois par an, les tables TGF 05 prévoient une dérive de 1,8 mois par an, soit 23 % de plus.

Ceci illustre la difficulté à anticiper la tendance de dérive de la mortalité future à partir de données historiques7 . Dans ce contexte, on peut imaginer d'utiliser comme paramètre de contrôle du modèle, en le fixant comme une contrainte ex ante par exemple l'espérance de vie à un âge donné (60 ans) et son évolution future. Cette approche, développée dans PLANCHET [2007], permet de quantifier par exemple l'impact sur les charges du régime d'une erreur de 0,1 mois/an sur la vitesse de dérive de cette espérance et d'intégrer explicitement des indicateurs de l'impact sur l'évaluation de l'engagement du régime d'une erreur de modèle. Le modèle proposé dans [START_REF] Planchet | Prospective models of mortality with forced drift -Application to the longevity risk for life annuities[END_REF] permet ainsi de proposer une valorisation de la charge associée au risque de longévité à environ 6 % de la provision mathématique des rentes. Cet ordre de grandeur est à rapprocher du taux de 0,17 % que l'on déduit de l'incertitude associée au caractère stochastique « endogène » de la mortalité dans le modèle de Lee-Carter ou ses variantes.

On peut enfin rappeler que ce type d'approche fournit un cadre opérationnel pour répondre aux exigences des futures dispositions Solvabilité 2 (et également dans le contexte de l'IFRS 4 phase 2, quoi que sur ce point les normes comptables soient moins exigeantes).

(

  objectif recherché. Toutefois, on peut lui reprocher de déformer de manière arbitraire la distribution des taux stochastiques ; en effet, si le modèle version corrigée du biais.

Fig. 2 :

 2 Fig. 2 :Surface de mortalité ajustée par Lee-Carter

Fig. 3 :σFig. 4 :

 34 Fig. 3 : Surface de mortalité de référence du modèle stochastique On remarque que la différence entre les deux graphes est très faible car du fait de la faible

Fig. 6 :

 6 Fig. 6 :Distribution empirique de l'engagement

  Fig. 7 :Distribution empirique de l'engagement (taille x30)

  Fig. 8 :Distribution empirique de l'engagement (taux technique nul)

  On constate sur le graphe que les différentes trajectoires simulées de t k prennent quasiment la même valeur en 2006. Ceci montre que le modèle tire sa volatilité de la dérive de la mortalité et non d'un saut brutal de mortalité entre 2005 et 2006. Si l'on cherche à comparer la volatilité de la dérive temporelle modélisée dans cet article avec celle du modèle utilisé dans PLANCHET et al. [2006], on obtient le graphe suivant : Si dans PLANCHET et al. [2006] les différentes trajectoires de t k étaient situées entre deux droites parallèles délimitant le couloir de variation de la tendance à 95 %, on constate sur le graphique ci-dessus que les trajectoires de la dérive temporelle sont situées entre deux droites s'éloignant l'une de l'autre avec le temps. Les variations de la tendance temporelle et celles du taux instantané de mortalité étant comparables, le graphique ci-dessus traduit l'hypothèse du modèle : la mortalité stochastique tire sa volatilité non pas des fluctuations annuelles qui,

		50
		0
		1950	1970	1990	2010	2030	2050	2070	2090
		-50
	Kt	-100
		-150
		-200
		-250
				Fig. 5 :	« couloir de variation » de la tendance

Alors que dans

PLANCHET et al. [2006]

le modèle utilisé ne prenait en compte que l'oscillation de la dérive temporelle t k autour de sa moyenne, le modèle actuel simule l'erreur d'ajustement qui a pu être faite sur la dérive temporelle passée. comme nous l'avons démontré dans

PLANCHET et al. [2006]

restent faibles, mais plutôt de la dérive aléatoire de la mortalité qui n'est vraiment observable que dans le futur.

3. APPLICATION A UN REGIME DE RENTES VIAGERES 3

  .1. PROBLEMATIQUE Dans la suite, nous utiliserons pour les applications numériques un portefeuille constitué de 374 rentiers de sexe féminin âgés en moyenne de 63,8 ans au 31/12/2005. La rente annuelle moyenne s'élève à 5,5 k€. Avec un taux d'escompte des provisions de 2,5 %, la provision mathématique initiale, s'élève à 37,9 M€ avec la table prospective déterminée supra.

	Nous noterons dans la suite de l'article :
	0 L le montant des provisions mathématiques à la date initiale,

t F ~ le flux de prestation (aléatoire) à payer à la date t, i le taux (discret) d'escompte des provisions mathématiques, J l'ensemble des individus,

  tendance future de mortalité à partir des seules fluctuations du paramètre temporel t k ; cette approche est justifiée par le fait que l'on cherche à identifier la volatilité des taux de décès non associée aux fluctuations d'échantillonnage. Compte tenu des effectifs très importants du groupe utilisé pour construire les tables utilisées ici (la population française), on peut en effet considérer qu'il n'y a plus de fluctuations d'échantillonnage significatives dans l'estimation des taux bruts 4 et que donc il est légitime de considérer la surface passée fixe.En conclusion, on peut retenir que le régime de rente est par contre soumis à un risque de modèle important. Il est ainsi possible de reformuler les conséquences du passage des tables TPG 1993 aux tables 6 TGH 05 évoquées en introduction en rapprochant l'évolution anticipée de l'espérance de vie à 60 ans dans les deux modèles prospectifs. On obtient ainsi :

	98,00
	96,00	y = 0,1472x + 90,396
	94,00
	92,00
	90,00		y = 0,1189x + 87,416
	88,00
	86,00
	84,00
	82,00
	80,00
	Une approche alternative consisterait à prendre en compte globalement l'incertitude sur le
	paramètre vectoriel	( θ α β , ,k	)

=

pour générer des surfaces de mortalité. Cette démarche est techniquement simple à mettre en oeuvre à la condition d'utiliser la variante log-Poisson du modèle de Lee-Carter, dans laquelle l'estimation de θ est effectuée par maximum de vraisemblance, puisque, alors, on peut déterminer l'information de Fischer associée et utiliser la normalité asymptotique de l'estimateur 5 .

Toutefois, elle nous semble moins pertinente dans le cas présent, notre objectif étant d'isoler le risque associé à une incertitude structurelle sur les taux et non à une incertitude d'estimation.

Tables obtenues sur la base de la mortalité de la population féminine sur la période 1961-1987, utilisées depuis le 1 er juillet 1993.

Ces tables sont disponibles sur http://www.ined.fr/publications/cdrom_vallin_mesle/Tables-demortalite/Tables-du-moment/Tables-du-moment-XX.htm

L'imprécision est mesurée par la demi-longueur relative de l'intervalle de confiance à 95 %.

Sur les adaptations du modèle de Lee-Carter au cas de petits échantillons pour lesquels cette hypothèse n'est plus vérifiée, on pourra se reporter à PLANCHET et LELIEUR[2006].

Voir par exemple HAAS [2006] pour une utilisation de cette approche dans le cas de swaps de mortalité.

On rappelle que les TPG 1993 sont des tables féminines.

Les populations de référence utilisées pour les 2 séries de tables diffèrent, mais on obtiendrait les même conclusions en utilisant des tables prospectives INSEE à la place des TGF 05.