Dominique Bontemps

Universal Coding on Infinite Alphabets: Exponentially Decreasing Envelopes

Keywords: Data compression, universal coding, infinite countable alphabets, redundancy, Bayes mixture, adaptive compression

This paper deals with the problem of universal lossless coding on a countable infinite alphabet. It focuses on some classes of sources defined by an envelope condition on the marginal distribution, namely exponentially decreasing envelope classes with exponent α.

The minimax redundancy of exponentially decreasing envelope classes is proved to be equivalent to 1 4α log e log 2 n. Then, an adaptive algorithm is proposed, whose maximum redundancy is equivalent to the minimax redundancy.

I. INTRODUCTION

C OMPRESSION of data is broadly used in our daily life: from the movies we watch to the office documents we produce. In this article, we are interested in lossless data compression on an unknown alphabet. This has applications in areas such as language modeling or lossless multimedia codecs.

First, we present briefly the problematics of data compression. More details are available in general textbooks, like [START_REF] Cover | Elements of Information Theory[END_REF]. Then we make a short review of preceding results, in which we situate the topic of this article, exponentially decreasing envelope classes, and we announce our results.

A. Lossless data compression

Consider a finite or countably infinite alphabet X . A source on X is a probability distribution P , on the set X N of infinite sequences of symbols from X . Its marginal distributions are denoted by P n , n ≥ 1 (for n = 1, we only note P ). The scope of lossless data compression is to encode a sequence of symbols X 1:n , generated according to P n , into a sequence of bits as small as possible. The algorithm has to be uniquely decodable.

The binary entropy H(P n ) = E P n [-log 2 P n (X 1:n )] is known to be a lower bound for the expected codelength of X 1:n . From now on, log denotes the logarithm taken to base 2, while ln is used to denote the natural logarithm. Since arithmetic coding based on P n encodes a message x 1:n with ⌈log P n (x 1:n )⌉ + 1 bits, this lower bound can be achieved within two bits. Then, the expected redundancy measures the mean number of extra bits, in addition to the entropy, a coding strategy uses to encode X n . In the sequel, we use the word redundancy instead of expected redundancy. D. Bontemps is PhD fellowship holder at Laboratoire de Mathématiques, Univ. Paris-Sud 11, Orsay, 91405 France.

Furthermore, together with Kraft-McMillan inequality, arithmetic coding provides an almost perfect correspondence between coding algorithms and probability distributions on X n . In this setting, if an algorithm is associated to the probability distribution Q n , its expected redundancy reduces to the Kullbach-Liebler divergence between P n and Q n

D(P n ; Q n ) = E P n log P n (X 1:n ) Q n (X 1:n ) .
We call this quantity (expected) redundancy of the distribution Q n (with respect to P n ).

Unfortunately, the true statistics of the source are not known in general, but P n is supposed to belong to some large class of sources Λ (for instance, the class of all iid sources, or the class of Markov sources). In this paper, the maximum redundancy

R n (Q n ; Λ) = sup P ∈Λ R n (Q n ; P n )
measures how well a coding probability Q n behave on an entire class Λ. With this point of view, the best coding probability is a minimax coding probability, that achieves the minimax redundancy

R n (Λ) = inf Q n R n (Q n ; Λ).
Another way to measure the ability of a class of sources to be efficiently encoded is the Bayes redundancy

R n,µ (Λ) = inf Q n Λ R n (Q n ; P n ) dµ(P )
where µ is a prior distribution on Λ endowed with the topology of weak convergence and the Borel σ-field. Only one coding strategy achieves the Bayes redundancy: the Bayes mixture

M n,µ (x 1:n ) = Λ P n (x 1:n ) dµ(P ).
When Λ is a class of iid sources on the set X = N * = N\{0}, there is a natural parametrization of Λ by P θ (j) = θ j , with θ = (θ 1 , θ 2 , . . .) ∈ Θ Λ . Θ Λ is then a subset of

Θ =    θ = (θ 1 , θ 2 , . . .) ∈ [0, 1] N : i≥1 θ i = 1   
and it is endowed with the topology of pointwise convergence.

In this case we write µ as a prior on Θ Λ . Minimax redundancy and Bayes redundancy are linked by an important relation [START_REF] Gallager | Information Theory and Reliable Communication[END_REF], [START_REF] Davisson | A source matching approach to finding minimax codes[END_REF]; it is written here in the context of iid sources on a finite or countably infinite alphabet, but Haussler [START_REF] Haussler | A general minimax result for relative entropy[END_REF] has shown that it can be generalized for all classes of stationary ergodic processes on a complete separable metric space.

Theorem 1: Let Λ be a class of iid sources, such that the parameter set

Θ Λ is a measurable subset of Θ. Let n ≥ 1. Then R n (Λ) = sup µ R n,µ (Λ),
where the supremum is taken over all (Borel) probability measures on Θ Λ . The quantity sup µ R n,µ (Λ) is called maximin redundancy. A prior whose Bayes redundancy corresponds to the maximin redundancy is said to be maximin, or least favorable. Theorem 1 says that maximin redundancy and minimax redundancy are the same. It provides a tool to calculate the minimax redundancy.

Before speaking about known results, let us make mention of other two notions. With an asymptotic point of view, a sequence of coding probabilities (Q n ) n≥1 is said to be weakly universal if the per-symbol redundancy tends to 0 on Λ: sup P ∈Λ lim n→∞

1 n D(P n ; Q n ) = 0.
Instead of the expected redundancy, many authors consider individual sequences. In this case, the minimax regret

R * n (Λ) = inf Q n sup P ∈Λ sup x1:n∈X n log P n (x 1:n ) Q n (x 1:n )
plays the role that the minimax redundancy plays with the expected redundancy.

B. Exponentially decreasing envelope classes

In the case of a finite alphabet of size k, many classes of sources have been studied in the literature, for which estimates of the redundancy have been provided. In particular we have the class of all iid sources (see [START_REF] Krichevsky | The performance of universal encoding[END_REF]- [START_REF] Drmota | Precise minimax redundancy and regret[END_REF], and references therein), whose minimax redundancy is

k -1 2 log n 2πe + log Γ(1/2) k Γ(k/2) + o(1).
This last class can be seen as a particular case of a (k -1)dimensional class of iid sources on a (possibly) bigger alphabet, for which we have a similar result under certain conditions (see [START_REF] Clarke | Information-theoretic asymptotics of bayes methods[END_REF]- [START_REF] Barron | Information-theoretic characterization of bayes performance and the choice of priors in parametric and nonparametric problems[END_REF]). Similar results are still available for classes of Markov processes and finite memory tree sources on a finite alphabet (see [START_REF] Krichevsky | The performance of universal encoding[END_REF], [START_REF] Davisson | Minimax noiseless universal coding for markov sources[END_REF]- [START_REF] Atteson | The asymptotic redundancy of bayes rules for markov chains[END_REF]), and for k-dimensional classes of even non-iid sources on an arbitrary alphabet (see [START_REF] Rissanen | Universal coding, information, prediction, and estimation[END_REF]).

The results become less precise when one considers infinite dimensional classes on a finite alphabet. A typical example is the class of renewal processes, for which we do not have an equivalent of the expected redundancy, but we know that it is lower and upper bounded by a constant times √ n (see [START_REF] Csiszár | Redundancy rates for renewal and other processes[END_REF], [START_REF] Flajolet | Analytic variations on redundancy rates of renewal processes[END_REF]). Eventually, it is well known that the class of stationary ergodic sources on a finite alphabet is weakly universal (see [START_REF] Cover | Elements of Information Theory[END_REF]). However, Shields [START_REF] Shields | Universal redundancy rates do not exist[END_REF] showed that this class does not admit non-trivial universal redundancy rates.

In the case of a countably infinite alphabet, the situation is significantly different. Even the class of all iid sources is not weakly universal (see [START_REF] Kieffer | A unified approach to weak universal source coding[END_REF], [START_REF] Györfi | There is no universal source code for an infinite source alphabet[END_REF]). Kieffer characterized weakly universal classes in [START_REF] Kieffer | A unified approach to weak universal source coding[END_REF] (see also [START_REF] Györfi | There is no universal source code for an infinite source alphabet[END_REF], [START_REF]On universal noiseless source coding for infinite source alphabets[END_REF]):

Proposition 1: A class Λ of stationary sources on N * is weakly universal if and only if there exists a probability distribution Q on N * such that for every P ∈ Λ, D(P ; Q) < ∞.

In the literature, we find two main ways to deal with infinite alphabets. The first one [START_REF] Orlitsky | Universal compression of memoryless sources over unknown alphabets[END_REF]- [START_REF] Choi | Pattern matching in constrained sequences[END_REF] separates the message into two parts: a description of the symbols appearing in the message, and the pattern they form. Then the compression of patterns is studied.

A second approach [START_REF]On universal noiseless source coding for infinite source alphabets[END_REF], [START_REF] Elias | Universal codeword sets and representations of the integers[END_REF]- [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] studies collections of sources satisfying Kieffer's condition, and proposes compression algorithms for these classes. A result from [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] indicates us such a way:

Proposition 2: Let Λ be a class of iid sources over N * . Let the envelope function f be defined by f (x) = sup P ∈Λ P (x). Then the minimax regret verifies

R * n (Λ) < ∞ ⇔ x∈N * f (x) < ∞.
It is therefore quite natural to consider classes of iid sources with envelope conditions on the marginal distribution. In this article we study specific classes of iid sources introduced by [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], and called exponentially decreasing envelope classes.

Definition 1: Let C and α be positive numbers satisfying C > e 2α . The exponentially decreasing envelope class Λ Ce -α• is the class of sources defined by

Λ Ce -α• = {P : ∀k ≥ 1, P (k) ≤ Ce -αk
and P is stationary and memoryless.}

The first condition addresses mainly the queue of the distribution of X 1 ; it means that great numbers must be rare enough. It does not mean that the distribution is geometrical: if C is big enough, many other distributions are possible. Furthermore we will see that the exact value of C does not change significantly the minimax redundancy, unlike α.

Since in this paper we are going to only talk about exponentially decreasing envelope classes, we simplify the notations

R n (Q n ; Λ Ce -α• ), R n (Λ Ce -α• ), and R n,µ (Λ Ce -α• ) into R n (Q n ; C, α), R n (C, α), and R n,µ (C, α) respectively. The subset of Θ corresponding to Λ Ce -α• is denoted by Θ C,α = {θ = (θ 1 , θ 2 , . . .) ∈ [0, 1] N : i≥1 θ i = 1 and ∀i ≥ 1, θ i ≤ Ce -αi }. (1)
We present two main results about these classes. In Section II we calculate the minimax redundancy of exponentially decreasing envelope classes, and we find that it is equivalent to 1 4α log e log 2 n as n tends to the infinity. This rate is interesting for two main reasons. Up to our knowledge, exponentially decreasing envelope classes are the first family of classes on an infinite alphabet for which an equivalent of the minimax redundancy is known. Then, even the rate is new: until now only rates in log n or √ n have been obtained.

Once the minimax redundancy of a class of sources is known, we are interested in finding a minimax coding algorithm. Section III proposes a new adaptive coding algorithm, and we show that its maximum redundancy is equivalent to the minimax redundancy of exponentially decreasing envelope classes.

Eventually, the Appendix contains some proofs and some auxiliary results used in the main analysis.

II. MINIMAX REDUNDANCY

In this section we state our main result. Theorem 2 below gives an equivalent of the minimax redundancy of exponentially decreasing envelope classes. To get it, we use a result due to Haussler and Opper [START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF].

Theorem 2: Let C and α be positive numbers satisfying C > e 2α . The minimax redundancy of the exponentially decreasing envelope class

Λ Ce -α• verifies R n (C, α) ∼ n→∞ 1 4α log e log 2 n.
Theorem 2 improves on a preceding result of [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]Theorem 7]. In that article the following bounds of the minimax redundancy of exponentially decreasing envelope classes are given:

1 8α log e log 2 n (1 + o(1)) ≤ R n (C, α) ≤ 1 2α log e log 2 n + O(1).
In subsection II-A we outline the work done in [START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF], and then we use it in subsection II-B to prove Theorem 2. Eventually, we discuss in subsection II-C the adaptation of this method to other envelope classes.

A. From the metric entropy to the minimax redundancy

To study the redundancy of a class of sources, [START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF] considers the Hellinger distance between the first marginal distributions of each source. Bounds on the minimax redundancy are provided in terms of the metric entropy of the set of the first marginal distributions, with respect to the Hellinger distance. As a consequence, that method can be applied only to iid sources. However it is very efficient in the case of exponentially decreasing envelope classes.

First, we need to define the Hellinger distance and the metric entropy. In the case of sources on a countably infinite alphabet, the Hellinger distance can be defined in the following way:

Definition 2: Let P and Q two probability distributions on N * . Then the Hellinger distance between P and Q is defined by

h(P, Q) = k≥1 P (k) -Q(k) 2 .
A related metric can be defined on the parameter set Θ:

d(θ, θ ′ ) = h(P θ , P θ ′ ) = k≥1 θ k -θ ′ k 2 .
From a metric we can define the metric entropy. We need to define first some numbers.

Definition 3: Let S be a subset of Θ, and ǫ be a positive number.

1) We denote by D ǫ (S, d) the cardinality of the smallest finite partition of S with sets of diameter at most ǫ, or we set D ǫ (S, d) = ∞ if no such finite partition exists.

2) The metric entropy of (S, d) is defined by

H ǫ (S, d) = ln D ǫ (S, d). 1
3) An ǫ-cover of S is a subset A ⊂ S such that, for all x in S, there is an element y of A with d(x, y) < ǫ.

The covering number N ǫ (S, d) is the cardinality of the smallest finite ǫ-cover of S, or we define

N ǫ (S, d) = ∞ if no finite ǫ-cover exists. 4) An ǫ-separated subset of S is a subset A ⊂ S such
that, for all distinct x, y in A, d(x, y) > ǫ. The packing number M ǫ (S, d) is the cardinality of the largest finite ǫ-separated subset of S, or we define M ǫ (S, d) = ∞ if arbitrary large ǫ-separated subsets exist. The following lemma explains how these numbers are linked. It is a classical result that can be found for instance in [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes[END_REF].

Lemma 1: Let S be a subset of Θ. For all ǫ > 0,

M 2ǫ (S, d) ≤ D 2ǫ (S, d) ≤ N ǫ (S, d) ≤ M ǫ (S, d).
Lemma 1 enables us to choose the most convenient number to calculate the metric entropy.

From the metric entropy one can define the notion of metric dimension, which generalizes the classical notion of dimension. But the metric entropy lets us know in some way how dense the elements are in a set, even infinite dimensional.

Another quantity that [START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF] uses is the minimax risk for the

(1 + λ)-affinity R λ (Λ) = inf Q sup θ∈Θ λ k≥1 P θ (k) 1+λ Q(k) -λ ,
defined for all λ > 0. More precisions about the (1 + λ)-affinity are given in [START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF]. See also [START_REF] Bontemps | Redondance bayésienne et minimax, sources stationnaires sans mémoire en alphabet infini[END_REF] for a special regard payed to envelope classes.

In the case of an envelope class Λ f defined by an integrable envelope function f , it is easy to see that R λ < ∞ for all λ > 0. Indeed the choice

Q(k) = f (k) l≥1 f (l) leads to the relation R λ ≤   k≥1 f (k)   λ .
We can now write a slightly modified version2 of Theorem 5 of [START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF] in the context of data compression on an infinite alphabet.

Theorem 3: Let Λ be a class of iid sources on N * , such that the parameter set Θ Λ is a measurable subset of Θ. Assume that there exists λ > 0 such that R λ < ∞. Let h(x) be a continuous, non-decreasing function defined on the positive reals such that, for all γ ≥ 0 and C > 0, 1)

lim x→∞ h (Cx (h(x)) γ ) h(x) = 1 and 2) lim x→∞ h (Cx(ln x) γ ) h(x) = 1. Then 1) If H ǫ (Θ Λ , d) ∼ ǫ→0 h 1 ǫ , then R n (Λ) ∼ n→∞ (log e) h( √ n). 3
2) If, for some α > 0 and c > 0,

lim inf ǫ→0 H ǫ (Θ Λ , d) (1/ǫ) α h(1/ǫ) ≥ c, then lim inf n→∞ R n (Λ) n α/(α+2) h(n 1/(α+2) ) 2/(α+2) > 0.
3) If, for some α > 0 and C > 0,

lim sup ǫ→0 H ǫ (Θ Λ , d) (1/ǫ) α h(1/ǫ) ≤ C, then lim sup n→∞ R n (Λ) (n ln n) α/(α+2) h(n 1/(α+2) ) 2/(α+2) < ∞.
The conditions concerning the function h mean that h cannot grow too fast. For instance, h can grow like C(ln x) β , with β ≥ 0. The first case in the theorem is the one we use for exponentially decreasing envelope classes. In this case, the fast decreasing envelope produces a "not too big" metric entropy. Theorem 3 gives us an equivalent of the minimax redundancy of the class of sources when n goes to the infinity. This turns out very useful, as it improves a preceding result of [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. However it is only an asymptotic result, without any convergence speed.

The second and the third items correspond to bigger classes of sources. In these cases the result is a bit less interesting: it gives a speed for the growth of the redundancy, but without the associated constant factor. Furthermore there is a gap of (ln n) α/(α+2) between the lower bound of point 2 and the upper bound of point 3. However it allows us to retrieve more or less a result of [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] for another type of envelope classes.

We develop now these applications.

B. The minimax redundancy of exponentially decreasing envelope classes

Here we want to prove Theorem 2 by applying Theorem 3. Thus we have to calculate the metric entropy of exponentially decreasing envelope classes. This is done by Proposition 3:

Proposition 3: Let C and α be positive numbers satisfying C > e 2α . The metric entropy of the parameters set Θ C,α verifies

H ǫ (Θ C,α , d) = (1 + o(1)) 1 α ln 2 (1/ǫ),
where o( 1) is a function g(ǫ) such that g(ǫ) → 0 as ǫ → 0. Proof of Theorem 2: Just apply Theorem 3, with h(x) = 1 α ln 2 (x), to get the result.

Proof of Proposition 3:

The outlines of the proofs of the next lemmas can be found in Appendix A. The corollaries are simple applications and the proofs are skipped.

We start with general considerations. Let Λ f be the envelope class defined by the integrable envelope function f . Let Θ f be the corresponding parameter set

Θ f = {θ = (θ 1 , θ 2 , . . .) ∈ [0, 1] N : i≥1 θ i = 1 and ∀i ≥ 1, θ i ≤ f (i)}. The function θ → ( √ θ 1 , √ θ 2 , . . .
) is an isometry between the metric space (Θ f , d) and the subset A f ∩ { x = 1} of ℓ 2 , equipped with the classical euclidean norm • , where A f is defined by

A f = {(x k ) k∈N * ∈ ℓ 2 : ∀k ∈ N * , 0 ≤ x k ≤ f (k)}. (2)
The metric entropy of (Θ f , d) can be calculated in this space.

Next we truncate some coordinates, to work in a finite dimensional space instead of ℓ 2 . Together with an adequate use of Lemma 1, this helps us to obtain upper and lower bounds for the metric entropy of (Θ f , d). We start with the upper bound.

Lemma 2: Let Λ f be the envelope class defined by the integrable envelope function f , and let ǫ be a positive number. Let N ǫ denote the integer

N ǫ = inf    n ≥ 1 : k≥n+1 f (k) ≤ ǫ 2 16    .
For U ∈ R N and a > 0, let B R N (U, a) denote the ball in R n with center U and radius a. Then

H ǫ (Θ f , d) ≤ N ǫ ln(1/ǫ) + 3N ǫ ln 2 + A(N ǫ ) + B(ǫ),
where

A(N ) = -ln Vol (B R N (0, 1)) = ln Γ( N 2 + 1) π N 2
and

B(ǫ) = Nǫ k=1 ln f (k) + ǫ 4 . Furthermore A(N ǫ ) ∼ ǫ→0 N ǫ 2 ln N ǫ .
Note that

-N ǫ ln(1/ǫ) -2N ǫ ln 2 ≤ B(ǫ) ≤ ǫ 4 N ǫ .
These bounds on B(ǫ) show that B(ǫ) tends to decrease the upper bound, while A(N ǫ ) contributes to its growth. If ln N ǫ behaves like ln(1/ǫ) up to a constant factor, then the upper bound given in Lemma 2 corresponds to a constant times N ǫ ln N ǫ , and we are concerned with the point 3 of Theorem 3.

If we apply Lemma 2 to the case of exponentially decreasing envelope classes, we obtain the upper bounds

N ǫ ≤ 2 α ln(1/ǫ) + 1 α ln 16C 1 -e -α B(ǫ) ≤ - α 4 N 2 ǫ + ln C 2 + 1 √ 1 -e -α N ǫ .

This leads to

Corollary 1: Let C and α be positive numbers satisfying C > e 2α . The metric entropy of the parameter set Θ C,α defined by ( 1) verifies

H ǫ (Θ C,α , d) ≤ (1 + o(1)) 1 α ln 2 (1/ǫ),
where o( 1) is a function g(ǫ) such that g(ǫ) → 0 as ǫ → 0. Now we need to get a lower bound on the metric entropy. In this case too, we want to truncate some coordinates to bring ourselves to a smaller finite dimensional space. This time we truncate the first coordinates. Let us consider the number

l f = min{l ≥ 0 : k≥l+1 f (k) ≤ 1}.
Lemma 3: Let Λ f be the envelope class defined by an integrable envelope function f , which verifies

k≥1 f (k) ≥ 2.
Let ǫ > 0 be a positive number, and let m ≥ 1 be an integer. Then

H ǫ (Θ f , d) ≥ 1 2 l f +m k=l f +1 ln f (k) + m ln 1 ǫ + A(m),
where A(m) is defined as in Lemma 2:

A(m) = -ln Vol (B R m (0, 1)) ∼ m→∞ m 2 ln m.
Note that exponentially decreasing envelopes verify the condition k≥1 f (k) ≥ 2. Indeed the envelope of exponentially decreasing envelope classes is

f (k) = min(1, Ce -αk ),
and the condition C > e 2α entails that f (1) = f (2) = 1.

From Lemma 3 we can infer the following corollary, with the choice m = 2 α ln 1 ε . Corollary 2: Let C and α be positive numbers satisfying C > e 2α . The metric entropy of the parameters set Θ C,α verifies

H ǫ (Θ C,α , d) ≥ (1 + o(1)) 1 α ln 2 (1/ǫ),
where o(1) is a function g(ǫ) such that g(ǫ) → 0 as ǫ → 0.

Note that the bound is the same as in Corollary 2. Therefore this concludes the proof of Proposition 3.

C. What about other envelope classes?

In [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] the redundancy of another type of envelope classes is also studied. The power-law envelope class Λ C• -α is defined, for C > 1 and α > 1, by the envelope function f α,C (x) = min(1, C

x α ). The bounds obtained in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]Theorem 6] are

A(α)n 1/α log⌊Cζ(α)⌋ ≤ R n (Λ C• -α ) ≤ 2Cn α -1 1/α (log n) 1-1/α + O(1), (3)
where

A(α) = 1 α ∞ 1 1 -e -1/(ζ(α)u) u 1-1/α du,
and

ζ denotes the classical function ζ(α) = k≥1 1 k α , for α > 1.
If one adapts the calculus made earlier to the power-law envelope classes, one can get the following upper and lower bounds: There are two (calculable) constants K 1 , K 2 > 0 such that, for all ǫ > 0,

K 1 1 ǫ 2 α-1 ≤ H ǫ ≤ K 2 (1 + o(1)) 1 ǫ 2 α-1 ln 1 ǫ .
Unfortunately this formula leaves a gap between the lower bound and the upper bound. The application of Theorem 3 makes the gap worse. Indeed the polynomial part 1 ǫ 2 α-1 of the metric entropy causes an additional gap of log 1/α n. In practice the bounds are the following: There are two (unknown) constants C, c > 0 such that, for all n ≥ 1,

c(1+o(1))n 1/α ≤ R n (Λ C• -α ) ≤ C(1+o(1))n 1/α log n. (4)
These inequalities improve in no way the result of [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. May a better calculus of the metric entropy improve either their lower bound or their upper bound? Anyway the metric entropy of power-law envelope classes is "too big" to efficiently apply Theorem 3: it does not leave the hope for an equivalence, as for exponentially decreasing envelope classes. To summarize, the strategy based on the metric entropy and Theorem 3 turns out efficient for "small" classes of sources.

III. AUTOCENSURING CODE

This section presents a new algorithm called AutoCensuring Code (ACcode). It is in fact a modification of the Censuring Code proposed by Boucheron, Garivier and Gassiat in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. We keep the idea that big symbols are very few, and must be encoded differently, with an Elias code. Smaller symbols are encoded by arithmetic coding based on Krichevsky-Trofimov mixtures, which are known to be effective for finite alphabets. Our innovation is a data-driven cutoff M i = sup 1≤k≤i X k used to encode X i+1 : with this choice we do not need to know the exact parameters of the exponentially decreasing envelope.

ACcode is a prefix code on the set of all finite length messages, and it works on line. Its maximum redundancy on an exponentially decreasing envelope class Λ Ce -α• is equivalent to the minimax redundancy of this class of sources.

Furthermore ACcode is adaptive, as the same algorithm verifies this property with all exponentially decreasing envelope classes. This is formulated in the following theorem, proved in Appendix B. Let ACcode(x 1:n ) denote the binary string produced by ACcode when it encodes the message x 1:n , and let l(•) denote the length of a string.

Theorem 4: For any positive numbers C and α satisfying C > e 2α , sup

P ∈Λ Ce -α• E P n [l(ACcode(X 1:n )) -H(P n )] ∼ n→∞ R n (C, α).
The difference between the redundancy of ACcode and the minimax redundancy is not necessarily bounded: there may exist codes whose redundancy is smaller than the redundancy of ACcode, but with a benefit negligible with respect to log 2 n.

Additionally, Theorem 4 enables us to retrieve the upper bound of the minimax redundancy obtained in the section II.

Let us now define ACcode. Let n ≥ 1 be some positive integer, and let x 1:n = x 1 x 2 . . . x n be a string from N n * to be encoded. We define the sequence of maxima

m 0 = 0 and m i = sup 1≤k≤i x k , for all 1 ≤ i ≤ n.
The sequence (m i ) 1≤i≤n is non-decreasing, piecewise constant. For 1 ≤ i ≤ n, let n 0 i = i j=1 ½ mj >mj-1 be the number of plateaus between 1 and i. For 1 ≤ k ≤ n 0 n , let m k be the k th new maximum:

m i = m n 0 i . (5)
We define also m 0 = 0. Let string m be the sequence ( m 1m 0 + 1), . . . , ( m n 0 nm n 0 n -1 + 1), 1. m is encoded into a binary string C2 by applying Elias penultimate code (see [START_REF] Elias | Universal codeword sets and representations of the integers[END_REF]) to each number in m. It is a prefix code which uses l E (x) bits to encode a positive integer x, with

l E (1) = 1, l E (x) = 1 + ⌊log x⌋ + 2 ⌊log⌊log x⌋ + 1⌋ if x ≥ 2. (6)
Meanwhile the sequence of censored symbols is encoded using side information from m. Consider the censored sequence x 1:n = x 1 x 2 . . . x n defined by

x i = x i ½ xi≤mi-1 = x i if x i ≤ m i-1 , 0 otherwise.
All symbols greater than m i-1 are encoded together: they are replaced by the extra symbol 0, and this extra symbol is encoded instead. 0 has a special use in our setting: it makes the decoder to know when m i changes, and that the new value has to be read in C2. We add at the end of x 1:n an additional 0, which acts as a termination signal together with the last 1 in m. This makes our code to be prefix on the set of all finite length messages (whatever n).

Therefore we produce the binary string C1 by arithmetic coding of x 1:n 0. The conditional coding probabilities are defined by

Q i+1 ( X i+1 = j|X 1:i = x 1:i ) = n j i + 1 2 i + mi+1 2 if 1 ≤ j ≤ m i , Q i+1 ( X i+1 = 0|X 1:i = x 1:i ) = 1/2 i + mi+1 2 ,
where for j ≥ 1 and i ≥ 0, n j i is the number of occurrences of symbol j in x 1:i (with convention n j 0 = 0 for all j ≥ 1).

If i ≤ n -1, the event { X i+1 = 0} is equal to {X i+1 > M i }. If x i+1 = j > m i ,
then n j i = 0, and we still have

Q i+1 ( X i+1 = 0|X 1:i = x 1:i ) = n j i + 1 2 i + mi+1 2 .
In the sequel we note the coding probability used to encode the entire string x 1:n 0 by

Q n+1 ( x 1:n 0) = Q n+1 (0|x 1:n ) n-1 i=0 Q i+1 ( x i+1 |x 1:i ).
A remark we can do is that the symbol 0 is always considered as new: when x i+1 > m i , we encode 0 but we increment the counter n xi+1 i . (This choice has been made to simplify the calculation of the redundancy of ACcode, but we suspect that changing this behavior could improve the performances.)

Now we have defined C1 and C2, we have to describe how they are transmitted. To keep our code on line, we overlap these two strings in the following way.

Arithmetic code needs a certain amount of bits, say l i , to send the first i symbol of x 1:n . Unfortunately, l i depends on whether i = n + 1 or not. In previous case l n+1 = ⌈log Q n+1 ( x 1:n 0)⌉ + 1, and in later one l i depends on the following symbols and has to be computed. ACcode begins with C2, by the transmission of the Elias code of m 1 + 1. Then the transmission of C1 is initiated. Suppose that x i = 0 and n 0 i = k. As soon as l i bits of C1 have been sent, the ACcode algorithm sends the Elias code of m km k-1 + 1. Then C1 is transmitted again, from the next bit.

To decode the i th symbol in C1, the knowledge of the current maximum m i-1 is needed; it is obtained from the beginning of the string C2. The decoder also needs the counters (n j i-1 ) j≥1 , which can be computed from the first i -1 decoded symbols. As soon as l i bits of C1 have been received, x i can be decoded. When the decoder meets a 0 at the i th position, he knows that the next bits are the Elias code of the next symbol in m, and deduces m i via [START_REF] Krichevsky | The performance of universal encoding[END_REF]. Since the Elias code is prefix, the decoder knows when he receives C1 again. Then the (i + 1) th symbol can be processed.

Fig. 1 shows an illustration of the transmission process. In this example, the initial message is x 1:4 = 5, 3, 2, 7. Then the message encoded in C1 is x 1:4 0 = 0, 3, 2, 0, 0. 13 bits are needed to transmit the second 0, and 15 bits for the last one. In C2 we transmit m = 6, 3, 1.

In the previous example, exact calculations have been performed, but this is not sensible for a practical implementation of arithmetic coding. Some rule is needed to set the precision 01110 0110011001101 0101 00 1

↓ beginning of C1 ↓ last bits of C1 ↓ Elias code of m 1 + 1 Elias code of m 2 -m 1 + 1 Elias code of 1 Fig. 1. Example of ACcode
in calculus, and it must be used by both coder and decoder. To avoid a too big extra redundancy caused by approximations, precision can grow as n grows. For instance, calculations can be made in memory with a further precision of 2 ⌈log i⌉ bits, in addition to the ⌈log Q i ( x 1:i )⌉ + 1 bits needed to encode x 1:i ; this insures that the extra redundancy is bounded.

APPENDIX A METRIC ENTROPY OF EXPONENTIALLY DECREASING ENVELOPE CLASSES

We give here the outlines of the lemmas we stated in subsection II-B.

Proof of Lemma 2: N ǫ denotes the threshold from which we want to truncate the coordinates. If y = (y n ) n≥1 is an

element of A f , its truncated version is y = (y n ½ n≤Nǫ ) n≥1 .
One can check that

y -y ≤ ǫ 4 .
Suppose now that S is an ǫ/4-cover of {y ∈ A f : ∀n ≥ N ǫ , y n = 0}. Let z denote an element of A f . Then it exists some y ∈ S such that zy ≤ ǫ/4. Thus zy ≤ ǫ/2, and S is an ǫ/2-cover of A f . This leads to

D ǫ (Θ f , d) ≤ M ǫ/4   1≤k≤Nǫ 0, f (k) , • R Nǫ   ≤ Vol 1≤k≤Nǫ -ǫ 8 , f (k) + ǫ 8 Vol B R Nǫ (0, ǫ 8 ) A first consequence of that calculus is that D ǫ (Θ f , d) is finite for all ǫ > 0.
The first assertion of Lemma 2 is then obtained by applying the logarithm function.

The rest of Lemma 2 follows from the Feller bounds, in their version proposed by [40, ch. XII]:

Γ(x) = √ 2π x x-1/2 e -x e β 12x , with β ∈ [0, 1]. (7)
Proof of Lemma 3: Let m ≥ 1 be an integer. We project the set A f ∩ { x = 1} over the m-dimensional space

E m = {0} l f × R m × {0} {k:k≥l f +m+1}
generated by the coordinates from l f + 1 to l f + m. This leads to

D ǫ (Θ f , d) ≥ N ǫ   l f +m k=l f +1 0, f (k) , • R m   ≥ Vol l f +m k=l f +1 0, f (k) Vol (B R m (0, ǫ))
.

It only remains to apply the logarithm function.

APPENDIX B REDUNDANCY OF ACcode

A. Moments of M n

We first need a lemma which contains several useful results about the moments of M n .

Lemma 4: Let C and α be positive numbers satisfying C > e 2α . Then, for all n ≥ 1,

1)

sup

P ∈Λ Ce -α• E P [M n ] ≤ 1 α ln n + ln C 1 -e -α + 1 .

2)

sup P ∈Λ Ce -α• E P M n ½ Mn> 1 α ln Cn 2 1-e -α = O ln n n .
3) sup

P ∈Λ Ce -α• E P [M n ln M n ] = o(ln 2 n).
Proof: Let F denote the distribution function associated with P . For t ≥ 0, we have

P(X 1 > t) = k≥⌊t⌋+1 P (k) ≤ C 1 -e -α e -α(⌊t⌋+1) ≤ e -α(t-β) , where β = 1 α ln C 1-e -α . Therefore F (t) ≥ G(t) for all t ∈ R, where
G(t) = ½ t≥β 1 -e -α(t-β) .
We can identify in G the distribution function of the random variable β + Y , where Y follows the exponential distribution with parameter α.

Let U 1 , . . . , U n be n iid random variables following the uniform distribution on [0, 1]. For 1 ≤ i ≤ n, let us define

X ′ i = F -1 (U i ) Y i = G -1 (U i ) -β,
where F -1 and G -1 denote the pseudo-inverses of F and G:

∀t ∈ [0, 1], F -1 (t) = inf{x ∈ R : F (x) ≥ t}.
Then the n-dimensional vector X ′ 1:n = (X ′ 1 , . . . , X ′ n ) has the same distribution as X 1:n , and the maxima M ′ n = sup 1≤i≤n X ′ i and M n follow the same distribution. On the other hand, the relation

F ≥ G entails X ′ i ≤ β + Y i , for all 1 ≤ i ≤ n. As the consequence, if M ′′ n = sup 1≤i≤n Y i denotes the maximum of all Y i , we have M ′ n ≤ β + M ′′ n .
Since the random variables Y i are independent, the probability distribution of M ′′ n is easy to calculate. Indeed for all t > 0,

P(M ′′ n ≤ t) = P(∀ 1 ≤ i ≤ n, Y i ≤ t) = 1 -e -αt n .
We can write down the density function of M ′′ n :

f (t) = n α e -αt (1 -e -αt ) n-1 if t > 0, 0 otherwise.
Now we look for an upper bound of E[M n ] by taking advantage of the knowledge of that distribution:

E[M n ] = E[M ′ n ] ≤ E[β + M ′′ n ] = β + ∞ 0 t n α e -αt (1 -e -αt ) n-1 dt = β + ∞ 0 1 -(1 -e -αt ) n dt
integrating by parts. Use now the change of variables

u = 1 -e -αt t = -ln(1-u) α E[M n ] ≤ β + 1 α 1 0 1 -u n 1 -u du ≤ 1 α ln n + 1 + ln C 1 -e -α .
Since the upper bound does not depend on P , that achieves the proof of the point 1. We can handle the point 2 in the same way. For all t > 0, we have

E [M n ½ Mn>β+t ] ≤ E (β + M ′′ n )½ M ′′ n >t ≤ ∞ t (β + u)n α e -αu du = ne -αt t + 1 α + β .
With t = 2 α ln n, we get the second point of Lemma 4. The third item is similar. Since the function x → x ln x is increasing on [1, +∞) and

1 ≤ M ′ n ≤ β + M ′′ n , we have E [M n ln M n ] ≤ E [(β + M ′′ n ) ln(β + M ′′ n )] = E ½ M ′′ n ≤β (β + M ′′ n ) ln(β + M ′′ n ) + E ½ M ′′ n >β ½ M ′′ n ≤ 2 α ln n (β + M ′′ n ) ln(β + M ′′ n ) + E ½ M ′′ n >β ½ M ′′ n > 2 α ln n (β + M ′′ n ) ln(β + M ′′ n ) ≤ 2β ln(2β) + 4 α (ln n) ln 4 α ln n + E 2M ′′ n ln(2M ′′ n )½ M ′′ n > 2 α ln n ≤ 2β ln(2β) + 4 α ln 4 α ln n + 4 α (ln n)(ln ln n) + E 4M ′′ n 2 ½ M ′′ n > 2 α ln n . Let us define γ(n) = 2β ln(2β) + 4 α ln 4 α ln n + 4 α (ln n)(ln ln n). Note that γ(n) = o(ln 2 n). Then E [M n ln M n ] ≤ γ(n) + ∞ 2 α ln n 4u 2 n α e -αu du = γ(n) + 4ne -2 ln n α 2 (4 ln 2 n + 4 ln n + 2).
Taking the supremum over P , we get sup

P ∈Λ Ce -α• E P [M n ln M n ] ≤ γ(n) + 16 ln 2 n + 16 ln n + 8 α 2 n = o(ln 2 n).

B. Contribution of C1

Proposition 4: Let C and α be positive numbers satisfying C > e 2α . Then

sup P ∈Λ Ce -α• E P n [-log Q n ( X 1:n ) -H(P n )] ≤ (1 + o(1)) 1 4α log e log 2 n.
Proof: We give here the sketch of the proof, and we delay the proofs of ( 8), ( 9), [START_REF] Drmota | Precise minimax redundancy and regret[END_REF], and [START_REF] Clarke | Information-theoretic asymptotics of bayes methods[END_REF].

Here we deal with the quantity

(A) = sup P ∈Λ Ce -α• E P n [-log Q n ( X 1:n ) -H(P n )].
that corresponds to the contribution of C1. As we saw in Section III, the coding probability Q n is based on Krichevsky-Trofimov mixtures. For k ≥ 1, let KT k denote the usual Krichevsky-Trofimov mixture on the alphabet {1, . . . , k}, whose conditional probabilities are, for all 0 ≤ i ≤ n -1 and for all 1

≤ j ≤ k, KT k (X i+1 = j|X 1:i = x 1:i ) = n j i + 1 2 i + k 2 .
Let us choose k = m n + 1. In this case, there is a simple relation between KT mn+1 and Q n . For any sequence of n positive integers

x 1:n ∈ N n * , Q i+1 ( X i+1 = x i+1 |X 1:i = x 1:i ) = 2i + 1 + m n 2i + 1 + m i KT mn+1 (X i+1 = x i+1 |X 1:i = x 1:i ).
As a consequence, we can link the redundancy of Q n to the redundancy of KT mn+1 :

log Q n ( X 1:n ) = log KT Mn+1 (X 1:n ) + n-1 i=0 log 2i + 1 + M n 2i + 1 + M i
and therefore

(A) = sup P ∈Λ Ce -α• (A1) E P n -log KT Mn+1 (X 1:n ) -H(P n ) - (A2) E P n n-1 i=0 log 2i + 1 + M n 2i + 1 + M i .
Note that (A 2 ) corresponds to the gain in redundancy of Q n with respect to KT Mn+1 . It illustrates the benefit of taking M i instead of M n as cutoff to encode X i+1 . On the one hand, we have

(A 1 ) ≤ E[M n ] 2 log n + E[log(M n + 1)]. (8)
Since

E[log M n ] ≤ E[M n ], Lemma 4 entails sup P ∈Λ Ce -α• E[log(M n + 1)] = o(log 2 n).
Applying Lemma 4 again, we see that (A 1 ) produces a redundancy equivalent to 1 2α log e log 2 n, which is twice bigger than the minimax redundancy obtained in Theorem 2. So, we will hope the corrective term (A 2 ) to be about 1 4α log e log 2 n. To deal with (A 2 ), we use the concavity of the log function, and we group the terms in the sum, M n by M n . Let m = n-1 Mn be the number of bundles. To simplify the expression, we also neglect few terms at the beginning of the sum. Let (h n ) n≥1 be a non-decreasing sequence of positive integers, such that h n → ∞ as n → ∞, and let us define λ n = 2h n log 1 + 1 2hn . Then

(A 2 ) ≥ λ n E P n m k=hn+1 M n -M kMn 2(k + 1) . (9)
It is easy to verify that the function x → x log 1 + 1

x is nondecreasing, and tends to log e when x tends to the infinity; therefore (λ n ) tends to log e. We can write now

(A) ≤ sup P ∈Λ Ce -α• E[M n ] 2 log n -λ n E m k=hn+1 M n -M kMn 2(k + 1) + o(log 2 n) ≤ 1 2 (A3) sup P ∈Λ Ce -α• E P n M n log n -λ n M n m k=hn+1 1 k + 1 + λ n 2 (A4) sup P ∈Λ Ce -α• E P n m k=hn+1 M kMn k + 1 + o(log 2 n) Let us choose h n = max{1, ⌊ln n -2⌋}. Then (A 3 ) = o(log 2 n) (10)
(A 4 ) ≤ log 2 n 2α log 2 e + o(log 2 n). (11)
Therefore we have

(A) ≤ (1 + o(1)) 1 4α log e log 2 n
which concludes the proof of Proposition 4.

Proof of ( 8): Let

P n (x 1:n ) = sup P n P n (x 1:n ) = j∈{x1,...,xn} n n j n n n j
be the maximum likelihood of the string x 1:n over all iid distribution on N n . Then

(A 1 ) ≤ E P n log P n (X 1:n ) KT Mn+1 (X 1:n ) ≤ E P n sup x1:n∈{1,...,Mn+1} log P n (x 1:n ) KT Mn+1 (x 1:n )
Now we can apply a result from Catoni [9, prop 1.4.1]:

Lemma 5: For all k ≥ 1 and for all x 1:n ∈ {1, . . . , k} n ,

-log KT k (x 1:n ) + log P n (x 1:n ) ≤ k -1 2 log n + log k.
Proof of ( 9): We group the terms in (A 2 ), M n by M n :

(A 2 ) ≥ E P n   m-1 k=1 (k+1)Mn i=kMn+1 log 1 + M n -M i 2i + M i + 1   . From the relation M k ≤ M k ′ for all k ′ ≥ k ≥ 1, we can infer, for all i ≥ kM n , M n -M i 2i + M i + 1 ≤ M n 2kM n = 1 2k
Since log is a concave function, we have log(1 + x) ≥

x log(1+a) a for all a > 0 and 0 ≤ x ≤ a. Consequently, if we choose a = 1 2k ,

(A 2 ) ≥ E P n   m-1 k=1 (k+1)Mn i=kMn +1 2k log 1 + 1 2k M n -M i 2i + M i + 1   ≥ E P n m k=hn+1 λ n M n -M kMn 2k + 2 .
Proof of [START_REF] Drmota | Precise minimax redundancy and regret[END_REF]: We have

(A 3 ) = sup P ∈Λ Ce -α• j≥1 P n (M n = j) × j log n -λ n j ⌊ n-1 j ⌋ k=hn+1 1 k + 1 .
Then we plug in h n = ⌊ln n-2⌋. For n large enough, h n ≥ 1, and we have

j ⌊ n-1 j ⌋ k=hn+1 1 k + 1 ≥ j ⌊ n-1 j ⌋+1 ln n-1 dx x + 1 = j ln n -1 j + 2 -ln(ln n)
≥ j ln(n -1)j ln jj ln(ln n), and therefore

(A 3 ) ≤ sup P ∈Λ Ce -α• (log e -λ n )E[M n ] ln n + λ n E[M n ] ln n n -1 + λ n E[M n ln M n ] + λ n E[M n ] ln(ln n) .
Then, if we use Lemma 4 and the fact that λ n tends to log e, we get [START_REF] Drmota | Precise minimax redundancy and regret[END_REF].

Proof of [START_REF] Clarke | Information-theoretic asymptotics of bayes methods[END_REF]: We want to commute the expected value and the sum in (A 4 ). To do it, we need to get rid of m. We can note that the condition k ≤ m = ⌊ n-1 Mn ⌋ entails kM n ≤ n -1. Consequently, for n big enough,

(A 4 ) ≤ sup P ∈Λ Ce -α• E P n m k=3 M kMn k + 1 ≤ sup P ∈Λ Ce -α• E P n n-1 k=3 M kMn ½ kMn≤n-1 k + 1 ≤ n-1 k=3 sup P ∈Λ Ce -α• E P n [M kMn ½ Mn≤ln ] k + 1 + sup P ∈Λ Ce -α• E P n [M n ½ Mn>ln ] n-1 k=3 1 k + 1
,

where l n = 1 α 2 ln n + ln C 1-e -α
. We can now plug in the results of Lemma 4:

(A 4 ) ≤ n-1 k=3 ln(kl n ) + 1 + ln C 1-e -α (k + 1)α + o(1) n-1 k=3 1 k + 1 ≤ 1 α n-1 k=3 ln k k + 1 + 1 α (ln l n + O(1)) n-1 k=3 1 k + 1 .
Note that l n = O(ln n), and consequently ln l n = O(ln ln n). So

(A 4 ) ≤ 1 α n 3 ln x x dx + O(ln ln n) n 3 dx x ≤ 1 2α ln 2 n + o(ln 2 n).

C. Contribution of C2

Proposition 5: Let C and α be positive numbers satisfying C > e 2α . Then

sup P ∈Λ Ce -α• E P n [l(C2)] ≤ o(log 2 n).
Proof: Like in the previous subsection, we give first the sketch of the proof, and we delay several technical lemmas.

sup P ∈Λ Ce -α• E P n [l(C2)] ≤ 1 + sup P ∈Λ Ce -α• n i=1 E P n ½ Xi>Mi-1 l E (X i + 1) .
We deal with this sum thanks to the following lemma: Lemma 6: Let g be a positive and non-decreasing function on [1, ∞). Let (K n ) n≥1 be a non-decreasing sequence of positive integers. Then, for all n ≥ 1, sup

P ∈Λ Ce -α• n i=1 E P n ½ Xi>Mi-1 g(X i ) ≤ (1 + o(1))g(K n ) 1 α ln n + C n ∞ Kn g(x +
1)e -αx dx.

To apply Lemma 6, we extend the definition of l E on [1, ∞) by Note that, for all 1 ≤ i ≤ n, X i and M i-1 are independent random variables, and In the general case, we can split the sum at K n , and we get The supremum is correctly defined and bounded, because the function x → log x + 2 log log x + 1 log x is continuous and tends to 1 as x tends to the infinity.

l E (x) = 1 if x ∈ [1, 2), 1 + ⌊log x⌋ + 2 ⌊log⌊log x⌋ + 1⌋ if x ≥ 2.
P n (M i ≤ k) = P n (∀ 1 ≤ j ≤ i, X j ≤ k) = (1 -p(k)) i .

Then we can write

D. Proof of Theorem 4

The message sent by the ACcode algorithm is compound of two strings C1 and C2. C1 corresponds to the part of the message encoded by the arithmetic code, with coding probability Q n+1 . The arithmetic code encodes a message x 1:n 0 with ⌈log Q n+1 ( x 1:n 0)⌉ + 1 bits. We have We conclude thanks to Propositions 4 and 5.

E P n [-log Q n+1 (0|X

PPE

  ∈Λ Ce -α• E P n [l(C2)] ≤ (1 + o(1)) l E (K n + 1) α ln n + C n ∞ Kn l E (x + 2)e -αx dxThen we can choose K n = max{1, ⌊ 1 α ln n⌋}. This entailsl E (K n + 1) ∼ n→∞ log K n ∼ log log n = o(log n),and therefore1 α l E (K n + 1) ln n = o(log 2 n).The remaining term is treated by Lemma 7, which achieves the proof of Proposition 5:Lemma 7: Let α > 0 be a real number, and letK n = max{1, ⌊ 1 α ln n⌋}. Then n ∞ Kn l E (x + 2)e -αx dx = o(log n).Proof of Lemma 6: Let P be an element of Λ Ce -α• . Let us define, for all k ≥ 0, p(k) = P (X 1 > k) = j≥k+1 P n ½ Xi>Mi-1 g(X i ) .

(B 1 1 -½ Xi>Mi- 1 ≤

 111 (1p(m -1)) n p(m -1).If we take g(x) = 1 for all x, we getm≥1 P (m) 1 -(1p(m -1)) n p(m -1) = E n i=1 E[M n ].

(B 1 1 -P (m) 1 -

 111 (1p(m -1)) n p(m -1)≤ g(K n ) m≥1 (1p(m -1)) n p(m -1) + m≥Kn+1 nP (m)g(m) ≤ g(K n )E[M n ] + C n m≥Kn+1 g(m)e -αm .At this point, we can take the supremum over all sources P in Λ Ce -α• :supP ∈Λ Ce -α• n i=1 E P n ½ Xi>Mi-1 g(X i ) ≤ (1 + o(1))g(K n ) 1 α ln n + C n ∞ Kn g(x + 1)e -αx dx.Proof of Lemma 7:n ∞ Kn l E (x + 2)e -αx dx ≤ n ∞ Kn (log(x + 2) + 2 log log(x + 3) + 1) e -αx dx ≤ ne -αKn log(K n + 3) ∞ Kn+3 log x + 2 log log x + 1 log(K n + 3) e -α(x-Kn-3) dx ≤ e α log(K n + 3) sup x≥Kn+3 log x + 2 log log x + 1 log x ∞ Kn+3 log x log(K n + 3)e -α(x-Kn-3) dx = O(log K n )

  1:n )] = E P n [log(M n + 1 + 2n)] ≤ log(2n) + E P n [M n + 1] 2n = O(log n)thanks to Lemma 4. Therefore the redundancy of ACcode can be upper bounded, for all n ≥ 2, by supP ∈Λ Ce -α• E P n [l(C1) + l(C1)] -H(P n )] ≤ sup P ∈Λ Ce -α• E P n [-log Q n ( X 1:n ) -H(P n )]

	+ sup P ∈Λ Ce -α•	E P n [l(C2)] + O(log n).

We follow[START_REF] Haussler | Mutual information, metric entropy and cumulative relative entropy risk[END_REF] in this definition of the metric entropy. Several authors use a slightly different definition, based on the covering number or the packing number.

The separation of the upper and lower bounds have no effect on the proof given by Haussler and Opper. A complete justification is available in[START_REF] Bontemps | Redondance bayésienne et minimax, sources stationnaires sans mémoire en alphabet infini[END_REF].

The (log e) factor comes from the use of the logarithm taken to base 2, in the definition of Rn.

ACKNOWLEDGMENT

I wish thank Elisabeth Gassiat for her helpful advice, for the many ideas in this paper she suggested me, and for her constant availability to my questions.

Thanks also to Aurélien Garivier and to Stéphane Boucheron for the useful discussions we had. I don't forget the ideas I got from my classmates, especially Rafik Imekraz.


Lucien Wald

POTENTIALS OF IMAGES FROM GEOSTATIONARY SATELLITE DATA FOR THE ASSESSMENT OF SOLAR ENERGY PARAMETERS

Images taken by meteorological geostationary satellites are currently used to map global radiation. Several methods exist which process these images. Among them, the Heliosat method ranks as one of the most accurate and one of the easiest to use. Typical uncertainties (rms.) of such assessment are about 10 % for the monthly mean global irradiance on the ground, about 10 % for the daily value, and about 20 % for the hourly value. Use of ground measurements and proper processing (e. g. kriging) increase the accuracy of the estimates in global radiation.

Splitting the global radiation into its direct and diffuse components is not currently made on an operational basis. This requires additional information, such as turbidity in clear skies and geometrical and optical properties of the clouds, which is not available from the current geostationary satellites. However, some methods have been proposed which make use of the sole satellite data and which rely on assumptions replacing the missing information. In assessing the components of the global radiation, one should take care of the space-time scales he is dealing with: they are of paramount importance in designing a method, of its usefulness, as well as in the evaluation of its accuracy. It is emphasized that satellite images are measurements taken by a radiometer and as such obey the theory of signal processing, particularly space-time sampling constraints. The application of such images and of their processing is limited to time scales equal or greater than 1 hour, and to space scale equal or

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 greater than two pixels (about 20 km). Therefore, we cannot treat the case of fragmented cloud coverage, unless additional external information is available. An important aspect to be taken into account when satellite-derived and ground-measured information are to be compared, either for calibration or validation, is the fact that satellite information is a snapshot over a large area, while ground information is a time-integrated pinpoint measurement.

Of course practical problems to be solved are strongly dependent upon the particular applications, with major effects of space and time samplings. For example, in daylighting for a peculiar building, detailed spatial distribution is required for a very accurate assessment of the luminance. The large size of a pixel prevents from having this information, and the best and most useful that can be got is likely a sky class together with some relevant probabilities.

In daylighting as well as in many other applications in solar energy, it is necessary to split the global radiation into its diffuse and direct components in order for example to be able to compute values on tilted surfaces. Keeping in mind the above-mentioned limitations, several works have been made to infer diffuse radiation from satellite images. Some of these works are briefly presented, their principles and their uncertainties. Then future tracks are discussed which rely heavily on numerical models of the radiative transfer within the cloudy or cloud-free atmosphere. The advantages and drawbacks, as well as the pending questions are presented. Such approaches require additional information that are not available by the sole use of the data of the geostationary satellites. The supply of these data, the robustness of the method to these data are discussed, too.

It is shown that some properties, such as turbidity, geometrical and optical properties of the clouds, are predominant for the assessment of the diffuse and direct components. These properties are best estimated by some other satellites and it is recommended to use them in order to gain in accuracy. However this leads to a large increase in complexity of the processing chain as well of the fundamental problems to be solved with respect to the spacetime characteristics.

INTRODUCTION -THE HELIOSAT METHOD

Images taken by meteorological geostationary satellites are currently used to map global radiation. Several methods exist which process these images. Among them, the Heliosat method ranks as one of the most accurate and one of the easiest to use. The principle of the Heliosat method is the construction of a "cloud index" resulting from a comparison of what is observed by the sensor to what should be observed over that pixel if the sky were clear, which is related to the "clearness" of the atmosphere. In preparation to the determination of the cloud index, a reference map of the albedo for clear sky is constructed [START_REF] Moussu | A method for the mapping of the apparent ground brightness using visible images from geostationary satellites[END_REF]. Given a time-series of images, it is evaluated at each pixel in a recursive fashion by minimizing the variance between the measured radiances and those resulting from the clear sky model, the cloudy cases being eliminated at each step [START_REF] Cano | A method for the determination of the global solar radiation from meteorological satellites data[END_REF]. Figure 1 provides a diagram of the method.

At each pixel of the current image, the apparent albedo is computed as: apparent albedo = (DC -DC0) (extraterrestrial radiation) (geometry factor)(clear sky transmittance) where Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 • DC means 'digital count', DC0 being what can be called the sensor zero (DC is not necessarily calibrated),

• the extraterrestrial radiation is computed for the current day,

• the geometry factor accounts for the illumination and the viewing geometry,

• the clear sky transmittance is provided by simple empirical models.

The cloud index n t (i,j) at point (i,j) for given time t is defined as a function of the characteristic reference albedo ρ(i,j), the apparent albedo at the same point measured by the satellite ρ t (i,j), and the average albedo of the cloud tops ρ c (see Figure 1). The computation of ρ c is performed using the inverse of the algorithm used for determining the reference albedo map and retaining only the cloudy areas. The histogram of this "only cloud" image provides an estimation of ρ c . The clearness index KT(i,j) is defined as the ratio of global radiation at ground on an horizontal surface G(i,j) to the horizontal irradiance outside the atmosphere G o (i,j):

KT(i,j) = G(i,j) / G o (i,j)
Several previous studies did show a linear relationship between the cloud index and the clearness index, where a and b are positive and have been determined once for ever: KT t = -a n t + b Then the hourly global radiation at ground level on a horizontal plane is determined according

to: G t (i,j) = -KT t (i,j) G o t (i,j)
The Heliosat method can run in a fully automatic fashion on any kind of Meteosat visible data (Diabaté et al. 1989;[START_REF] Wald | A technical note on a low-cost high-quality system for the acquisition and digital processing of images of WEFAX type provided by meteorological geostationary satellites[END_REF]. It provides accurate hourly estimates of the global radiation at ground. Furthermore, it gives as by-product estimates of the cloud cover and also maps of ground albedo [START_REF] Moussu | A method for the mapping of the apparent ground brightness using visible images from geostationary satellites[END_REF]). The latter have been employed to study the changes in albedo in the Western Africa during the whole year 1984 (Diabaté et al. 1989) or the hydrological regime of Lake Chad during the past years, including the 1970's drought [START_REF] Wald | Monitoring the decrease of Lake Chad from space[END_REF].

Satellite data

Albedo of the ground ρ(i,j)

Mean value of the thick cloud top albedo

ρ c Cloud index n t (i,j) = [ρ t (i,j) -ρ (i,j)] / [ρ c -ρ (i,j)] Clearness index K t (i,j) = a (i,j) n t (i,j) + b(i,j)
Shortwave global solar radiation at ground level G t (i,j) = K t (i,j) G 0 t (i,j)

Albedo of the ground ρ (i,j)

Apparent albedo at time t and pixel (i,j) ρ t (i,j)

Figure 1. Diagram of the Heliosat method A model has been proposed by [START_REF] Diabaté | Détermination du rayonnement solaire à l'aide d'images satellitaires[END_REF] for the assessment of the monthly mean of daily sums. An analytical law has been fitted onto measurements taken by Météo-France for 10 years with a relative deviation (rms.) less than 1 %. This model has then be applied to hourly values derived from satellite data through the Heliosat method. Only three values are

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 available per day. When compared to ground measurements, the relative error (rms.) in reconstruction is about 10 %. The larger the number of images used per day, the lower the level of error. The error depend also of the size of the pixel. [START_REF] Stuhlmann | An improvement of the IGMK model to derive total and diffuse solar radiation at the surface from satellite data[END_REF] applied their IGMK model to satellite images having a resolution of about 50 km (called B2-type data). Having five images per day, they found a similar error, i.e. 10 %.

Though the algorithm exists for about fifteen years, developments are still made. For example, Beyer et al. (1996) proposed some changes which may result into an easier use and installation of the Heliosat method and a better accuracy if confirmed by more experiments.

Many comparisons (several thousands) between Heliosat, other methods and ground measurements have been made by several independent research teams (see e.g. [START_REF] Diabaté | Détermination du rayonnement solaire à l'aide d'images satellitaires[END_REF][START_REF] Diabaté | Estimating incident solar radiation at the surface from images of the Earth transmitted by geostationary satellites: the Heliosat Project[END_REF][START_REF] Grüter | Determination of solar radiation at ground level from images of the earth transmitted by meteorological satellites[END_REF]Solar radiation atlas for Africa, 1991;Zelenka et al., 1991). The results are independent of season -except in seasonally snow-covered areas -, of geographical areas and of satellites, type of data, and the quality (even the absence) of the calibration of the satellite data. Some very recent works have shown that merging a few ground stations measurement into the satellite-derived maps, make the errors decrease by a few per cent [START_REF] Beyer | Merging ground-measurements and satellite-derived data for the construction of global radiation map[END_REF]Zelenka et al., 1991). The error is now a function of the distance to the closest station. The standard Heliosat method ranks as one of the most accurate. At pixel level (10x10 km 2 ) the relative error (rms.) is about

• 15 % or better for the assessment of the hourly value,

• 10 % or better for the monthly mean for a given hour,

• 10 % or better for the monthly mean of daily sums.

Heliosat also means a software, the Sun-UNIX version of it made at Armines / Ecole des mines de Paris being in public-domain and available on an Internet server (http://wwwcenerg.cma.fr/tele). A PC-based package including a satellite data receiver has also been developed and is marketed and sold by a French company. The method is currently used by several institutes in Europe and elsewhere with geostationary satellites like Meteosat (Europe), GOES (USA) or GMS (Japan). A scientific network ensures collaboration between

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 these institutes and improvements in the method.

LIMITATIONS IN ASSESSING ADVANCED SOLAR ENERGY PARAMETERS

Splitting the global radiation into its direct and diffuse components is not currently made on an operational basis. This requires additional information, such as turbidity in clear skies or geometrical and optical properties of the clouds, which is not available from the current geostationary satellites. However, some methods have been proposed which make use of the sole satellite data and which rely on assumptions replacing the missing information. But first of all, one should take care of the space-time scales he is dealing with in assessing the components of the global radiation. Such scales are of paramount importance in designing a method, including its usefulness, as well as in the evaluation of its accuracy.

The typical size of a pixel within images from geostationary satellites is about 10 km. Images are acquired every half-hour or every hour. It is then obvious that no one can expect to derive directly from such images parameters having smaller space-time scales, such as for example, the luminance entering a window facing a certain direction. Satellite images are nothing else that measurements taken by a radiometer. As such they obey the theory of signal processing, particularly to space-time sampling constraints. The application of such images and of their processing is limited to time scales equal or greater than 1 hour, and to space scale equal or greater than two pixels (about 20 km). It follows that for example, we cannot treat the case of fragmented cloud coverage or provide a detailed description of the cloud cover surrounding a peculiar building, unless additional external information is available.

Of course practical problems to be solved are strongly dependent upon the particular applications, with major effects of space and time samplings. For example, monthly means of daily sums of diffuse radiation over large areas are much easier to assess in an accurate way than the same radiation hour per hour for these places, and peculiarly if aerosols loading is highly variable. In daylighting for a peculiar building, detailed luminance distribution is

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 required for a very accurate assessment of the luminance. The large size of a pixel prevents from having this information, and the best and most useful information that can be got is likely a class of skies, together with some relevant probabilities.

One of the major points when designing or validating methods which derive parameters from satellite data is the link between these parameters and the measurements of these same parameters by standard procedures at ground level (pyranometers, for example). The latter are used either for validation of the derived parameters and the assessment of their accuracy, or for calibration of the method, possibly on a routinely basis, or for both. Several problems arise. They are usually resolved by calling upon theories of atmospheric turbulence. I discuss briefly these problems and their effects on assessment of the accuracy of a method.

An important aspect to be taken into account when satellite-derived and ground-measured information are to be compared, either for calibration or validation, is the fact that satellite information is a snapshot over a large area, while ground information is a time-integrated pinpoint measurement. The first question is: should the ground information be similar to the satellite-derived information if the method were with no error ? What are the origins of the possible discrepancies and their level of magnitude ? Second question: taking into account that the model is not perfect, can we assess precisely the error only due to the model ?

Mixed to the previous aspect, is the accuracy of the geocoding of the pixels within the satellite image. Typical accuracy is 0.3 -0.5 pixel for very well geocoded images. For the images of interest here, that means that the geographical location of a pixel is known with an error (rms.) of about 3 to 5 km. It follows that the exact position of the ground station is unknown. One may hesitate between several pixels when being deciding which pixel contain the ground station (Figure 2). Related to that point is the question of the variability of the parameter under concern within a pixel. If the parameter is homogeneous, and more exactly has an uniform value over the pixel, then the ground measurement has the same value than any other pinpoint measurement that would be made over that pixel. That is the ground measurement is representative of the parameter. has to construct an one-hour synthetic value by the means of interpolation using time-adjacent measurements made by the e.g. pyranometer. Indeed the justification in doing so is done exactly in the same way than for the space domain (i.e. the pixels). The same hypotheses are to be applied. The most common one is the stationarity of increments of the parameter in space and time. Let consider the parameter as a random variable in space. Let consider its difference between two points arbitrarily remote. This difference is also a random variable.

Stationarity of increments means that the statistical properties of this random variable are independent in space and time.

It is assumed furthermore that the optical properties of interest are passive tracers of atmospheric velocity, and that their turbulent properties can be derived from that of the velocity. This is only fairly true for clouds since they have their own dynamics which may differ strongly from the wind dynamics. Such a hypothesis allow us to make use of wellknown theories of turbulence.

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996

Time-average, as performed by pyranometers, should be replaced by average in space, as performed by satellite sensor. In turbulence theory, Taylor proposed in 1938 the so-called hypothesis of 'frozen turbulence', according to which one can consider that the aggregates of turbulent eddies which govern oscillations of optical properties at a fixed point are translated without change with the mean velocity of wind. By this hypothesis, satellite-derived values averaged over several pixels within the neighborhood of the pyranometer can be compared to the ground measurements. More exactly the statistics of the satellite-derived parameter can be compared to the statistics of the ground measurements. This hypothesis is very convenient and often used. But still it remains a working hypothesis which is not always verified when possible. It may be valid for very small intervals of time relative to the variation of the turbulence, which is obviously not the case here.

The size of the pixel (~ 10 km) as well as the measurement lapse time (1 hour) are well within the critical range intermediate between small-scale and meso-scale turbulence. Within this range, there is generally no strong links between the fluctuations observed at one scale (e.g. 10 km) and another (e.g. 1 km). The statistical properties cannot be transposed from one scale to another as one can do in the so-called 'inertial' ranges in small-or meso-scale turbulence. It follows that we cannot claim that the satellite-derived information, averaged over a block of pixels or not, should match the ground measurement. A discrepancy is expected because of the natural variability of the radiation which cannot be predicted nor assessed in the general case.

Assuming a mean velocity of 10 m/s, one sees that satellite-derived values must be averaged over about 4 pixels in order to be compared to the 1-hour averaged ground measurement. This number of pixels depend strongly upon the wind velocity which is variable in space (x, y) and also with the altitude z. The latter problem may be solved by the computation of an average of the vertical profile of mean velocity weighted by the profile of the optical properties, as far as such information is available. This is barely the case. For the sake of the simplicity, one often averages the satellite-derived values over a square of 3x3 pixels centered on the location of Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 the pyranometer. In doing so, one assumes the homogeneity of the random variable made up from the fluctuations of the velocity around the mean value for this block of pixels. As said before, this is only fairly true for several tens of kilometers, including the large variability of the optical properties in the lower part of the troposphere. Furthermore, it does not account for the prevailing direction of the wind. Taking a square means that the wind is blowing from all directions towards the central pixel or inversely! Putting it differently, this way of doing may be read as if some clouds which never passed in the field-of-view of the pyranometer during the 1-hour measurement influence this measurement. Of course, changing the size of the square to e.g. 7x7 or 11x11 pixels significantly change the results, the magnitude of it depending upon the case. Under uniform conditions, the results are the same. In the heterogeneous case, the results may differ significantly in an unpredictable way. [START_REF] Pinker | Effects of spatial sampling of satellite data on derived surface solar irradiance[END_REF] studied the effect of different spatial sampling of satellite observations on retrieved surface global radiation using two different resolutions: 8 and 50 km. They found that, on the average, the results differed by about 8 -9 %. Several other attempts, not published in international journals, found similar conclusions and demonstrated that there is not an unique size of pixel aggregate giving the best results. It is possible at one time to get better agreement with one resolution and at other times better agreement with a different resolution. [START_REF] Beyer | Utilization of satellite data for the assessment of large scale PV grid integration[END_REF] suggested that the local variance may used as a measure of the spatial heterogeneity and may serve to determine the most appropriate size.

From this discussion, some conclusions are drawn, which are valid only for the scales involved here:

• it is not true that the satellite-derived information should exactly match the ground measurement,

• the natural variability of the radiation may be important and induce a large discrepancy between assessed and measured radiation,

• turning spatial average into temporal average by the means of the Taylor hypothesis is not justified in the general case,

• however it greatly ease the burden in image processing complexity,

• it may have sensible effects on the results of the comparison between satellite-derived

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 parameters and ground measurements,

• the magnitude of these effects are difficult to predict.

ASSESSING DIFFUSE RADIATION

In daylighting as well as in many other applications in solar energy, it is necessary to split the global radiation into its diffuse and direct components in order for example to be able to compute values on tilted surfaces. Keeping in mind the above-mentioned limitations, some works have been made to infer diffuse radiation from satellite images.

One obvious way is to start from the satellite-derived global radiation and to apply a standard algorithm as in the case of ground measurement. In the framework of the European Solar Radiation Atlas, 2nd edition, several algorithms were tested by a group of experts. The algorithms of [START_REF] Erbs | Estimation of the diffuse radiation fraction for hourly, daily and monthly-average global radiation[END_REF] have been selected. The first algorithm performs the assessment of the daily diffuse horizontal irradiation from the daily global horizontal irradiation. Typical relative rms. is about 15 % or less when entries are measured radiation. In the case of satellite-derived global radiation, one has to add the associate error. I assume that a crude assessment of the rms. may be given by the root of the quadratic sum of each rms., and thus we obtain a typical relative rms. of about 20 %. The second algorithm performs the same task but for monthly average of daily sums. It is applied to maps of global radiation obtained by the merging of ground-measurements and satellite-derived information, to provide maps of monthly means of diffuse radiation averaged over 10 years (1981)(1982)(1983)(1984)(1985)(1986)(1987)(1988)(1989)(1990). Typical relative rms.

is about 8 % or less when entries are measured radiation. In the case of satellite-derived radiation, it is estimated to about 13 %. Though crudely assessed, these rms. form a reference.

Given the complexity of the processing of satellite data, a model can only be justified on an operational basis if the resulting errors are less than these references. An attempt was made by [START_REF] Diabaté | An attempt to estimate the diffuse component of solar radiation on horizontal plane from satellite images[END_REF] (see also [START_REF] Diabaté | Détermination du rayonnement solaire à l'aide d'images satellitaires[END_REF] to assess the hourly diffuse radiation through the Heliosat method. An empirical relationship was seek between the Heliosat cloud index n and the diffuse radiation measured at eleven stations in France during 1984 and 1985. This relationship was a second-order polynomial function of n. According to the linear relationship between n and KT, this is equivalent to seek a relationship between clearness index KT and diffuse radiation. The task was very difficult since it was dealing with hourly values and not averages. Relative uncertainties (rms.) were about 38 % for both years.

The larger errors were encountered for clear skies and very thick clouds. In both cases KT and the solar elevation are not sufficient to determine the diffuse radiation. The influence of the turbidity is predominant for clear skies (low cloud index, n < 0.1, KT > 0.6) and becomes negligible for cloudy skies (n > 0.5, KT < 0.4). For very thick clouds, it was found that additional information describing the type of cloud is required in order to gain accuracy. [START_REF] Stuhlmann | An improvement of the IGMK model to derive total and diffuse solar radiation at the surface from satellite data[END_REF] introduced a model to assess the daily sum of the diffuse component into the IGMK model. The IGMK model was developed concurrently with Heliosat. In essence, both models are very alike and lead to similar results [START_REF] Grüter | Determination of solar radiation at ground level from images of the earth transmitted by meteorological satellites[END_REF]Solar radiation atlas for Africa, 1991). Using climatological monthly means of the optical thickness for the atmospheric ozone, water vapor, and surface albedo, and prescribed values for aerosols type and loading, they computed the daily diffuse radiation for 31 stations for 1985 and 1986, by the processing of Meteosat B2-type images (every 3 hours, pixel size is about 50 km). Copied from [START_REF] Stuhlmann | An improvement of the IGMK model to derive total and diffuse solar radiation at the surface from satellite data[END_REF].

From the analysis of such works, I believe that a formal description of different optical processes within the atmosphere is a key to success in assessing advanced solar energy parameters. This is illustrated by the modified IGMK model which provides fairly acceptable results though crude approximations are made in optical properties of the atmosphere. Several models have been popularized like Lowtran, Modtran or 5S-6S. They have different purposes

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 which differ from those pursued here. However they form the basis from which one can cautiously extract the various sub-models describing the fundamental processes. By bringing more physics into consideration, one expects to improve the accuracy in retrieving the diffuse radiation as well as the spectral information required for illuminance assessment.

However the major limit to these sophisticated models are the physical parameters to be input.

Usually, these parameters are very difficult to know. I think that their knowledge is the second key to success.

Using models detailing the fundamental processes leads to:

• complexity increases

• number of input parameters increases,

• accuracy of input parameters should be high,

• whole system should be coherent, i.e. each piece (sub-model plus associated inputs) should have the same level of knowledge and accuracy than the others.

For example, one may use detailed description of the Rayleigh scattering and of aerosol scattering. Rayleigh scattering is a function of the air pressure at ground level. A relative change of 10 % in pressure induces a relative change of 1 % in radiation in the blue range. As for the aerosol scattering, assuming one type of aerosol instead of another leads to relative changes of 1 -2 % in the same range. These errors may partly compensate or cumulate. In this example, we have increased the description of the processes, we have increased the complexity, we have increased the number of inputs but the lack of knowledge about these inputs leaves a possible relative error of several per cent.

The work of [START_REF] Stuhlmann | An improvement of the IGMK model to derive total and diffuse solar radiation at the surface from satellite data[END_REF] or maps), which are overall poor in accuracy because they do not correspond to the current conditions. This lead to an accuracy which is not better than simpler models, which are using statistical relationship between ground measurements and satellite-derived parameters. This limit in accuracy due to the poor accuracy of the input parameters is illustrated in Figure 3.

One can see that for clear-skies there is a bias (difference between mean values) in KT between the observations and the estimates. This bias amounts to 0.04 in absolute value, which is about 10 % of the mean KT. It is mostly induced by the use of prescribed values for the aerosol properties (no seasonal nor geographical variation) or of climatological values for water vapor.

The previous works as well as runs of numerical models describing the radiative transfer within a cloudy or cloud-free atmosphere show that in a first approximation

• there are two difficult cases to solve: the clear-skies, and the overcast skies, including the case of superimposed layers of cloud, and the broken fields,

• in clear-sky, the main parameters are the aerosol loading and the water vapor content, or the visibility which is a more global parameter,

• in overcast skies, the most important parameters are the optical thickness, and the altitude of the cloud top.

According to the past experience, the following approach should be used in the Satellight program. This approach should be understood as one of the several steps towards a very accurate assessment of the diffuse component, not as a definite one. The Satellight program is sponsored by the European Commission, and aims at the retrieval of the diffuse component as well as improving the assessment of the illuminance. The approach is the following. One may Then there is one degree of freedom: the optical thickness of the cloud. It is adjusted in an iterative way so that the reflectance output from the numerical model matches the reflectance observed by Meteosat. More precisely, this minimization problem is performed on a function of the distance between measured and assessed parameters. Attention should be paid on this parameter (or these parameters). For example, if the parameter is the reflectance observed by Meteosat, one should take into account the poor accuracy of the calibration of the sensors.

This peculiar point can be solved by using reflectances relative to an arbitrary reference. For example, one can define a model cloud index in a similar way than for Heliosat. The matching is then performed on the cloud indexes. Compared to the previous works, one can expect better results because of this degree of freedom. Adjusting the optical thickness of the cloud to the observations allows to compensate for the errors arising from elsewhere. It is likely that the error on the optical thickness will be large, but the error of the whole approach to the diffuse radiation will be better. Of course the error in clear-skies is expected to be close to that observed by Stuhlmann et al. since the processing will be similar.

MERGING DATA FROM OTHER SATELLITES

However better accuracy is required for global radiation applications and also other parameters are required for several uses of in several domains: global, diffuse, direct, illuminance, APAR, cloud cover surrounding a spot, spectral composition of the radiation.

According to the previous discussion, it follows that better accuracy is required on the input parameters, including their space and time distribution.

This can only be achieved by the means of space-borne sensors. Some may help in producing

Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 more detailed assessment of these input parameters. These satellites are future programs, some are current. For example, NOAA data are acquired in two visible and near-infrared bands. [START_REF] Darnell | Estimation of surface insolation using sun-synchronous satellite data[END_REF] used such data in a very satisfying way regarding accuracy. The multispectral capabilities permit a characterization of the optical properties of the atmosphere, including aerosols loading for clear skies. However the processing of such images is much more complicated than the Meteosat data. Furthermore, there is only one to three usable images per day as an average, at the beginning of the afternoon in mean solar time. This is not sufficient to derive daily sums. It follows that the NOAA imagery cannot be used alone for the assessment of solar energy parameters. When combined to geostationary images, it greatly improves the retrieval of these parameters, but at the expense of a much more complicated processing.

Future programs such as the European MeRIS, PolDER, and GOMOS and the USA EOS initiatives will better characterize and map the optical properties of the atmosphere. We can expect to have within a few years a more accurate description of the parameters to be input to the sophisticated models retrieving the direct or diffuse radiation. An approach such as the one envisioned for Satellight will be still valid, with possibly a minimization of a quantity which is now a function of several inputs allowed to slightly fluctuate.

When calling upon several sources of data, several problems arise, including the problem of data fusion. Some satellites like the Meteosat Second Generation program will give a large number of the required information. However it is likely that in order to increase our knowledge, we have to increase the number of relevant information. Therefore we have to deal with other satellites and sensors. These satellite data are of different types, different resolutions in space, different sampling in time, different geographical coverage, and then we enter a very difficult field of image processing called data fusion. That means that an advanced analysis of satellite data will require a close cooperation between people involved in optics of the atmosphere, image processing, applied mathematics, decision theory and so on.

Advanced fusion techniques may call upon data assimilation and numerical models for predicting temporal changes of optical properties. Most of the work will be done by the space Workshop on Satellites for Solar Energy Resource Information -Washington, DC, April 10-11, 1996 agencies but the solar energy community has a fundamental role to play. As today the solar energy community has to show that it is convinced about the potentials of the satellite data in order to foster the studies the space agencies may launch in that direction.

CONCLUSION

I have discussed the state-of-the-art in assessing diffuse and direct components of the radiation. Some methods are currently available but gain in accuracy is needed for solar energy applications. Discrepancies between ground measurements and satellite observations with respect to space and time characteristics are key issues. The variation in space and time of the radiation should be better understood in order to modelize it and furthermore to be able to compare (or merge) these different types of data in a more accurate way.

Some properties, such as turbidity, geometrical and optical properties of the clouds, are predominant for the assessment of the diffuse and direct components. It has been shown that advanced models should be employed for the radiative transfer but then the main limitation is the poor accuracy of the input parameters. These parameters are, or will be, best estimated by some other satellites and it is recommended to use them when possible in order to gain accuracy. However this leads to a large increase in the complexity of the processing chain and requires a better understanding of the fundamental problems to be solved with respect to the space-time characteristics.

6.

  Heliosat project has been developed at Ecole des Mines de Paris under the auspices of both the Commission of the European Union (DG XII-F) and the French Agency of Energy, beginning in 1978. It has two purposes: the estimation of incident solar radiation at ground level from images of the earth acquired by geostationary satellites, and the production of detailed maps of the spatial distribution of the global radiation (and of its components, if possible) in real time. A large number of works from Ecole des Mines de Paris (six Ph.D. theses), and also other institutes, have assessed many times the good accuracy of the Heliosat method by the means of comparison with ground-based pyranometers. They have also shown its simplicity, its reduced computing-time, its possible levels of automation, its acceptance of different kinds of geostationary satellites (Meteosat, GOES, GMS) and of data (raw data, B2 data, PDUS data and digitized WEFAX data), and its relevance in real-time and operational constraints.

Figure 2 .

 2 Figure 2. Location of a pyranometer within a pixel

Figure 3

 3 Figure 3 is copied from this work and displays the ratio of daily diffuse to daily global radiation versus the clearness index KT for January 1985 and 1986. The relative error (rms.)in reconstructing the daily sum is about 25 % and is reduced to about 15 % for the monthly mean of daily sum of diffuse radiation. Differently to the work of Diabaté, Wald, one observe a large scatter for medium and small KT. The fact that these authors used low resolution data together with ground stations located in several different climates, is in perfect agreement with the introduction of climatological knowledge in the IGMK model. In the case of both an area of smaller extension and higher resolution satellite data, one would likely obtain larger errors.

Figure 3 .

 3 Figure 3. Ratio of daily sum of diffuse to daily sum of global radiation versus daily clearness index, for January 1985 and 1986. (a) measurements (31 stations); (b) IGMK model results.

  use climatological or standard values for aerosol and water vapor and more generally for all parameters of interest. Cloud top height is assessed by the means of imagery taken in the thermal infrared band, providing measurements of the temperature of the targets. Given a standard vertical profile of temperature, one can derive the cloud top height. The profiles may possibly be supplied by the European Center for Medium Range Weather Forecast (ECMWF).This allows to take into account the current conditions, though cloud top height determinationWorkshop on Satellites for Solar Energy Resource Information -Washington,DC, April 10-11, 1996 is limited by the fact that the vertical temperature profile may change rapidly within a ECMWF grid mesh, at least in the boundary layer. If the ECMWF profiles are used, account should be taken of the size of the grid mesh (about 0.6° at best, i.e. about 70 km) compared to the pixel size.

Table 1

 1

	summarizes the

Workshop on Satellites for Solar Energy Resource Information -Washington,

DC, April 10-11, 1996

Table 1 .

 1 Summary of the errors (in relative rms.) that are currently attained by the processing of satellite images.

  illustrates this point. Having designed a model requiring several input parameters, they affect crude values to them by lack of knowledge. In a certain way it is in contradiction with the sophistication of the model. For example, special treatment can be done for aerosols, but nobody knows the optical thickness, type and loading for the current conditions. They are using climatological data or simply archives (past measurements

Workshop on Satellites for Solar Energy Resource Information -Washington,

DC, April 10-11, 1996

Workshop on Satellites for Solar Energy Resource Information -Washington,DC, April 10-11, 1996

Workshop on Satellites for Solar Energy Resource Information -Washington,DC, April 10-11, 1996 7.

ACKNOWLEDGMENTS

Fruitful discussions with Hans-Georg Beyer help me in writing this document.