Senior Member, IEEE Jorge F Silva
email: josilva@ing.uchile.cl

Senior Member, IEEE Pablo Piantanida
email: pablo.piantanida@centralesupelec.fr

On Universal D-Semifaithful Coding for Memoryless Sources with Infinite Alphabets

Keywords: Lossy compression, variable length source coding, D-semifaithful code, universal source coding, infinite alphabets, strong minimax universality, information radius, universal quantization, envelope families. I

The problem of variable length and fixed-distortion universal source coding (or D-semifaithful source coding) for stationary and memoryless sources on countably infinite alphabets (1-alphabets) is addressed in this paper. The main results of this work offer a set of sufficient conditions (from weaker to stronger) to obtain weak minimax universality, strong minimax universality, and corresponding achievable rates of convergences for the worst-case redundancy for the family of stationary memoryless sources whose densities are dominated by an envelope function (or the envelope family) on 1-alphabets. An important implication of these results is that universal D-semifaithful source coding is not feasible for the complete family of stationary and memoryless sources on 1-alphabets.

To demonstrate this infeasibility, a sufficient condition for the impossibility is presented for the envelope family. Interestingly, it matches the well-known impossibility condition in the context of lossless (variable-length) universal source coding. More generally, this work offers a simple description of what is needed to achieve universal D-semifaithful coding for a family of distributions ⇤. This reduces to finding a collection of quantizations of the product space at different block-lengths -reflecting the fixed distortion restriction -that satisfy two asymptotic requirements: the first is a universal quantization condition with respect to ⇤, and the second is a vanishing information radius (I-radius) condition for ⇤ reminiscent of the condition known for lossless universal source coding.

coding with respect to those redundancies. 1In lossless variable-length source coding, it is well-known that if we know the statistics of a stationary and memoryless source, the Shannon entropy of the 1D marginal of the process characterizes the minimum achievable rate [START_REF] Cover | Elements of Information Theory[END_REF]. However, when the statistics of the source are not known but the source belongs to a family of stationary and memoryless distributions ⇤, the problem reduces to characterizing the worst-case expected overhead (or worst-case redundancy) that an encoderdecoder pair exhibit due to the lack of knowledge about true distribution [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Gassiat | Universal Coding and Order Identification by Model Selection Methods[END_REF]. In fact, a seminal information-theoretic result states that the least worst-case overhead (or minimax redundancy of ⇤) is fully characterized by the information radius of ⇤ [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF].

The information radius (I-radius) has been richly studied by the community, and there are numerous contributions [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]- [START_REF] Merhav | A strong version of the redundancy-capacity theorem of universal coding[END_REF]. In particular, it is well-known that the I-radius grows sub-linearly for the family of finite alphabet stationary and memoryless sources [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], which implies the existence of a universal source code that achieves Shannon entropy for every distribution in this family provided that the block length tends to infinity. Unfortunately, this positive result does not extend to the case of stationary and memoryless sources on countably infinite alphabets (1-alphabets) [START_REF] Gyorfi | There is no universal source code for an infinite source alphabet[END_REF], [START_REF] Kieffer | Block coding for an ergodic source relative to a zero-one valued fidelity criterion[END_REF], [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. From an information complexity perspective, this infeasibility result means that the I-radius of this family is unbounded for any finite block-length; consequently, lossless universal source coding for 1-alphabet stationary and memoryless sources is an intractable problem.

There has been renewed interest in USC with infinite alphabets in recent year [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF], [START_REF] Boucheron | About adaptive coding on countable alphabets: Max-stable envelope classes[END_REF]- [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]. Restricting the study to the case of memoryless sources with marginal densities dominated by an envelope function f (or the envelope family ⇤ f ), a series of new results have been presented in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF], [START_REF] Boucheron | About adaptive coding on countable alphabets: Max-stable envelope classes[END_REF], [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]. Remarkably, [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]Theorems 3 and 4] show that f being summable (over the infinite alphabet) is a necessary and sufficient condition to guarantee strong minimax universality for the envelope family ⇤ f . Consequently, universality can be achieved for a non-trivial (infinite dimensional) collection of distributions with infinite support. Furthermore, the specific rate of convergence for the worse-case redundancy (i.e., the information radius of ⇤ f ) has been derived for exponential and power law (envelope) families in 1-alphabets as well the construction of coding schemes that achieve optimal worstcase redundancies (information limits) [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF], [START_REF] Boucheron | About adaptive coding on countable alphabets: Max-stable envelope classes[END_REF], among other interesting results.

Complementing the previous results on infinity alphabet sources and using ideas from weak source coding by Han [START_REF] Han | Weak variable-length source coding[END_REF], almost lossless universal source coding was introduced in [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF], [START_REF] Silva | Almost lossless variable-length source coding on countably infinite alphabets[END_REF]. The general idea of this approach is to relax the lossless assumption by introducing a non-zero distortion that tends to zero with the block-length (asymptotic zero distortion), with the intention of achieving weak universality over the entire collection of memoryless sources on 1-alphabets [START_REF] Silva | The redundancy gains of almost lossless universal source coding over envelope families[END_REF], [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]. Results in this weak setting demonstrate that almost lossless USC is feasible for the entire family of stationary and memoryless distributions [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]Th. 4] on 1-alphabets, and the sensitive role that the vanishing distortion plays on the analysis of the problem when moving from a point-wise to a uniform convergence to zero [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]Th. 5].

A. Contributions

In this paper, we investigate the problem introduced by Ornstein and Shields in [START_REF] Ornstein | Universal almost sure data compression[END_REF] of fixed-distortion and variable length universal source coding-or universal D-semifaithful coding-for 1-alphabet sources. Following the line of work of the seminal paper by Boucheron et al. [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], among others [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF], [START_REF] Boucheron | About adaptive coding on countable alphabets: Max-stable envelope classes[END_REF], [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF], we study the family of stationary and memoryless sources whose probability mass functions are dominated by an envelope function f by adopting the criterion of strong minimax universality [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF]. The redundancy in this case should be measured with respect to the ratedistortion function lower bound [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Berger | Rate Distorsion Theory[END_REF], [START_REF] Gray | Source Coding Theory[END_REF]. Our main results (cf. Theorems 2 and 3) parallel the results presented in the lossless problem [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]Theorems 3 and 4] and offer a set of conditions on the envelope function to obtain weak minimax universality, strong minimax universality as well as an achievable rate of convergence for the worse-case redundancy. Conversely, Theorem 2 shows that if the envelope function is not summable, then strong minimax universality is not feasible, i.e., an impossible result. Indeed, this result matches the infeasibility condition known for the case of lossless USC [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. More generally, we present a simple result that captures what is needed (necessary and sufficient conditions) to achieve universal D-semifaithful source coding in terms of some asymptotic properties imposed on a collection of partitions of the source alphabet (Lemma 1).

A central technical contribution of this paper relies on the derivation of a lower bound for the minimax redundancy of a D-semifaithful code, operating at a given distortion level, which is obtained using a redefined expression of the I-radius for the family of sources. The resulting I-radius expression is based on the information divergence restricted to quantization cells (or bins) induced by the D-semifaithful code. This lower bound represents the central ingredient to derive the impossibility argument over envelope families. On the other hand, achievable results are obtained for summable envelope functions, similarly to the case of lossless source coding [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]. For this, a two-stage constructive coding scheme is employed (operating at a fixed distortion) for which results are adopted from universal D-semifaithful coding on finite alphabets (Lemma 5) and universal lossless source coding on 1-alphabets [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]. To the best of our knowledge, our results are the first that explore universal D-semifaithful coding for stationary and memoryless sources on 1-alphabets using the criterion of strong minimax universality. A preliminary version of this paper was presented in [START_REF] Silva | Universal d-semifaithful coding for countably infinite alphabets[END_REF] where some of the results were introduced without a complete presentation of their proofs.

B. Related Work on Universal D-semifaithful for Finite Alphabet Sources

Relevant results on universal D-semifaithful coding have been presented for finite alphabet sources [START_REF] Ornstein | Universal almost sure data compression[END_REF], [START_REF] Yu | A rate of convergence result for a universal dsemifaithful code[END_REF], [START_REF] Kontoyiannis | Pointwise redundancy in lossy data compression and universal lossy data compression[END_REF]. Ornstein and Shields [START_REF] Ornstein | Universal almost sure data compression[END_REF] proposed a universal D-semifaithful code for finite alphabet ergodic sources deriving almost-sure convergence of the rate of the code to the rate-distortion function (a sample-wise analysis). Complementing this analysis, Yu and Speed [START_REF] Yu | A rate of convergence result for a universal dsemifaithful code[END_REF] proposed a two-stage universal Dsemifaithful code for the family of finite alphabet stationary and memoryless sources with some added regularity conditions. They showed that the average rate of this D-semifaithful code achieves (uniformly over this family) the rate-distortion function at a rate of convergence that is O(n 1 log n). On the optimality of this last constructive result, it is showed in [START_REF] Merhav | A comment on "a rate of convergence result for a universal d-semifaithful code[END_REF] that the rate O(n 1 log n) is optimal for the Hamming distortion measure. This optimality was showed more generally in [START_REF] Zhang | The redundancy of source coding with a fidelity criterion -part one: Known statistics[END_REF], [START_REF] Yang | The redundancy of source coding with a fidelity criterion -part ii: Coding at a fixed rate level with unkown statistics[END_REF] and they also presented new schemes that achieve the optimal rate of convergence of O(n 1 (log n + o(log n))) for finite alphabet stationary and memoryless sources. Results of the same nature were obtained in [START_REF] Ishii | The redundancy of universal coding with a fidelity criterion[END_REF].

Revisiting the sample-wise redundancy analysis of lossy source coding operating at a fixed distortion, Kontoyiannis [START_REF] Kontoyiannis | Pointwise redundancy in lossy data compression and universal lossy data compression[END_REF] showed that the best (sample-wise) redundancy rate (in bits per sample) of a code that knows the model is O(1/ p n) (a converse result). The analysis was then extended to a universal setting, where for finite alphabet memoryless sources the same redundancy rate (sample-wise) of O(1/ p n) is shown. Surprisingly in terms of sample wise redundancy, this work showed that no penalization is observed when moving from an optimal code that knows the model to a universal setting for finite alphabet memoryless sources. This matching condition on the sample-wise redundancy is non-observed when the analysis is based on the average redundancy of a code [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF].

Finally, adopting a refined angle for the sample-wise redundancy analysis, Kontoyiannis and Zhang [START_REF] Kontoyiannis | Arbitrary source models and bayesian codebooks in rate-distortion theory[END_REF] proposed a lossy version of the Kraft inequality to connect D-semifaithful codes (operating at a fixed distortion) with probability measures (in the reproduction alphabet) [START_REF] Kontoyiannis | Arbitrary source models and bayesian codebooks in rate-distortion theory[END_REF]Theorem 1]. This novel connection (codes-measures correspondence in lossy compression) leads to an alternative non-asymptotic formulation of the rate-distortion question in the form of an optimization problem. More precisely, they introduced the optimal code length valid for any finite block length [34, Eq.( 2)], which can be interpreted as the best code length (probability on the reproduction alphabet) for the D-semifaithful coding task, see [START_REF] Kontoyiannis | Pointwise redundancy in lossy data compression and universal lossy data compression[END_REF]Corollary 1]. Using this optimal code-length representation (non-asymptotic and sample-wise), the problem of universal D-semifaithful coding is addressed by looking at the redundancy of a universal D-semifaithful code with respect to the best code length (a sample-wise redundancy analysis).

Following ideas used in lossless compression [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF], the authors explored the performance of a mixture codebook (generated by a mixture of i.i.d. distributions using a prior probability over the simplex). Sufficient conditions on the prior were developed to show that the proposed mixture codebook scheme is universal over the class of finite alphabet memoryless sources [START_REF] Kontoyiannis | Arbitrary source models and bayesian codebooks in rate-distortion theory[END_REF]Th.6]. Furthermore, some regularities on the prior were established in [START_REF] Kontoyiannis | Arbitrary source models and bayesian codebooks in rate-distortion theory[END_REF]Th.7] guaranteeing that the mixture codebook offers a universal D-semifaithful code with a sample-wise redundancy, relative to the mentioned optimal code length, that does not exceed (d 1)/2 log(n)/n bits per sample. This last result is obatined almost surely when the block length tends to infinity where d denotes the cardinality of the reproduction alphabet. The achieved 1/2•log(n)/n samplewise redundancy per degrees of freedom and per sample agrees with results known for lossless universal source coding: the minimax average redundancy is O((d 1) log(n)/n) for the class of finite alphabet memoryless sources [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Gassiat | Universal Coding and Order Identification by Model Selection Methods[END_REF]. In addition, known converse results for D-semifaithful coding in [START_REF] Merhav | A comment on "a rate of convergence result for a universal d-semifaithful code[END_REF]- [START_REF] Yang | The redundancy of source coding with a fidelity criterion -part ii: Coding at a fixed rate level with unkown statistics[END_REF] might indicate that this mixture codebook scheme has an optimal (sample-wise) redundancy per dimension.

C. Paper Organization

The rest of the paper is organized as follows. Section II introduces some definitions and basic elements for the formalization of the problem. Section III presents the universal D-Semifaithful source coding problem and introduces a general result (Lemma 1). Section IV presents results for the family of envelope distributions (Theorems 2 and 3). Final remarks and directions for future work are presented in Section V. The arguments used to prove the main results, Theorems 2 and 3 are presented in Section VII. Finally, supporting results and technical derivations are relegated to the Appendix sections.

II. MAIN DEFINITIONS AND PRELIMINARIES

Let us denote by X a countably infinite alphabet: the integers without loss of generality. The space is equipped with a distortion function ⇢ : X ⇥ X ! R + , and the non-trivial scenario is assumed where ⇢(x, x) > 0 if, and only if, x 6 = x. For any n 1, we have ⇢ n : X n ⇥ X n ! R + of block length n to be the standard single letter construction obtained from ⇢ [START_REF] Berger | Rate Distorsion Theory[END_REF], [START_REF] Gray | Source Coding Theory[END_REF], where for any

x n = (x 1 , .., x n ) and xn = (x 1 , .., xn ) in X n ⇢ n (x n , xn ) ⌘ 1 n n X i=1 ⇢(x i , xi ). (1)
A D-semifaithful code of length n operating at a distortion d > 0 is a variable length coding scheme operating at a fixed distortion [START_REF] Ornstein | Universal almost sure data compression[END_REF], [START_REF] Kontoyiannis | Pointwise redundancy in lossy data compression and universal lossy data compression[END_REF]. More precisely, we consider the following definition:

Definition 1: A D-semifaithful code of length n operating at distortion d > 0 is defined/denoted by a triplet ⇠ n = ( n , C n , D n ), where • n : X n ! B n ⇢ X n is a quantizer, • C n : B n ! {0, 1} ⇤ ⌘ [ k 1 {0, 1}
k is a lossless binary (variable length) encoder, and

• D n : {0, 1} ⇤ ! B n is a binary decoder, satisfying that for any x n 2 X n ⇢ n (x n , n (x n ))  d. (2)
The set

B n = { n (x n ), x n 2 X n
} contains the prototypes of ⇠ n in X n . In this construction, the binary encoder C n , which is variable length, is prefix-free [START_REF] Cover | Elements of Information Theory[END_REF] implying that it satisfies the Kraft-MacMillan inequality:

X i2Bn 2 L(Cn(i))  1, (3)
where

L : {0, 1} ⇤ ! N \ {0}
is the function that returns the length (number of bits) of a vector in {0, 1}

⇤ .

Importantly for the analysis presented in this paper, the code

⇠ n = ( n , C n , D n ) induces a partition in X n given/denoted by ⇡ n ⌘ A n,y n ⌘ 1 n ({y n }), y n 2 B n ⇢ 2 X n . (4)

A. The Source Coding Problem

Let us consider an information source (a random sequence) X = (X n ) n 1 with values in X and process distribution denoted by µ = {µ n 2 P(X n ), n 1}, where for any n 1 X n = (X 1 , .., X n ) ⇠ µ n , and P(X n ) denotes the collection of probabilities in X n . Then, the rate (in bits per sample) for encoding X n with a D-semifaithful code ⇠ n of length n operating at distortion d > 0 is given by

R(⇠ n , µ n ) ⌘ 1 n E X n ⇠µn {L(C n ( n (X n )))} . (5)
Using the source model µ, the variable length fixed distortion lossy source coding problem reduces to minimizing R(⇠, µ n ) in (5) over the family of D-semifaithful codes (operating at distortion d) for any n 1 [START_REF] Kieffer | Block coding for an ergodic source relative to a zero-one valued fidelity criterion[END_REF], [START_REF] Kieffer | Sample converses in source coding theory[END_REF]. It is wellknown that for any D-semifaithful code ⇠ n [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Cover | Elements of Information Theory[END_REF]

nR(⇠, µ n ) H(v µn ), (6)
where v µn denotes the probability induced by µ n and n in the reproducible alphabet B n , i.e., v µn (y n ) = µ n ( 1 n ({y n })) for any y n 2 B n , and

H(v µn ) ⌘ X y n 2Bn v µn (y n ) log(v µn (y n )) (7)
is the Shannon entropy of v µn 2 P(B n ) [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Gray | Source Coding Theory[END_REF] and the log function is base 2. Furthermore, fixing n (the quantizer) and optimizing over the encoder-decoder pairs (C n , D n ) (the prefix-free mappings from B n to {0, 1} ⇤ ), we have that [START_REF] Cover | Elements of Information Theory[END_REF],

[27]

H(v µn ) + 1 n min Cn R(( n , C n , D n ), µ n ) H(v µn ) n , (8)
considering in this last optimization that D n is a deterministic function of C n .

A convenient way to write the entropy of the induced distribution v mn in ( 8) is as the entropy of µ n but projected over quantization (or a sub-sigma field of the measurable space (X n , 2 X n )). Given a partition ⇡ = {A i , i 2 I} (countable or finite) of X n and a probability µ 2 P(X n ), we introduce the entropy of µ restricted over the sub-sigma field (⇡) by

H (⇡) (µ) ⌘ X i2I µ(A i ) log µ(A i )  H(µ) = X x n 2X n µ(x n ) log µ(x n ), (9)
where the last inequality follows from basic information inequalities [START_REF] Cover | Elements of Information Theory[END_REF]. Then, H(v µn ) is equal to H (⇡ n ) (µ n ) and ( 8) can be re-written by

H (⇡ n ) (µ n ) + 1 n min Cn R(( n , C n , D n ), µ n ) H (⇡ n ) (µ n ) n .
(10) From [START_REF] Babkin | Method of universal coding for an independent message source with non-exponential computational complexity[END_REF], the source coding (operational) problem is

R n (d, µ n ) ⌘ min ⇠n R(⇠ n , µ n ), (11)
where ⇠ n is running over the family of D-semifaithful codes of length n operating at distortion d (Def.1). This operational problem can be considered equivalent to solve2

R n (d, µ n ) ⌘ min ⇡2Qn(d) H (⇡) (µ n ) n , (12)
where Q n (d) denotes the collection of partitions of X n where any ⇡ in Q n (d) satisfies that 8A 2 ⇡, 9y n 2 A such that sup

x n 2A ⇢ n (x n , y n )  d, i.e., any ⇡ 2 Q n (d) offers a d-covering of X n with respect to ⇢ n .
For stationary and memoryless sources, it is well known that R n (d, µ n ) converges (as n tends to infinity) to the celebrated rate-distortion function [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Gray | Source Coding Theory[END_REF], which is a function of µ 1 2 P(X) [START_REF] Kieffer | Block coding for an ergodic source relative to a zero-one valued fidelity criterion[END_REF], [START_REF] Kieffer | Sample converses in source coding theory[END_REF]. For completeness, we briefly revisit this result here.

B. The Source Coding Theorem

Let us consider (X n ) n 1 to be a stationary and memoryless source characterized by µ 1 2 P(X). The rate distortion function of µ = {µ n , n 1} relative to ⇢ is given by [START_REF] Kieffer | Block coding for an ergodic source relative to a zero-one valued fidelity criterion[END_REF]:

inf n 1 R ⇤ (d, µ n ) = lim n!1 R ⇤ (d, µ n ), (13)
where

R ⇤ (d, µ n ) ⌘ 1 n inf U,V I(U; V). (14)
The infimum in ( 14) is taken with respect to the collection of joint random vectors (U, V) in X n ⇥ X n satisfying that U ⇠ µ n and P(⇢ n (U, V)  d) = 1 [START_REF] Kieffer | Block coding for an ergodic source relative to a zero-one valued fidelity criterion[END_REF]. By the definitions of these objects, it is simple to verify that

R n (d, µ n ) R n (d, µ n ) R ⇤ (d, µ n ) for
R n (d, µ n ) = lim n!1 R ⇤ (d, µ n ) = R ⇤ (d, µ 1 ).
(15) The last expression in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] is the single letter information theoretic limit of this problem [START_REF] Kieffer | Block coding for an ergodic source relative to a zero-one valued fidelity criterion[END_REF]. The expression in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] is equal to the standard rate distortion function of the source that uses the expected distortion criterion [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Berger | Rate Distorsion Theory[END_REF].

III. A SOFT RESULT ON UNIVERSAL D-SEMIFAITHFUL CODING

In universal source coding, the objective is to find a coding scheme that achieves the performance limit in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] without knowledge of the underlying source distribution [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Gassiat | Universal Coding and Order Identification by Model Selection Methods[END_REF]. To formalize this problem in the context of D-semifaithful coding, let (X n ) n 1 be a stationary and memoryless source with values in X, where we impose that µ 1 belongs to ⇤ ⇢ P(X). Let {⇠ n = ( n , C n , D n ), n 1} be a D-semifaithful coding scheme operating at distortion d > 0 with respect to the single letter distortions {⇢ n , n 1}. Following the definitions used in universal lossless source coding [START_REF] Davisson | Universal noiseless coding[END_REF], we say that Definition 2: A coding scheme {⇠ n , n 1} (operating at distortion d > 0) is strongly minimax universal for ⇤ at distortion d if

lim n!1 sup µ n 2⇤ n [R(⇠ n , µ n ) R n (d, µ n )] | {z } worst-case redundancy over ⇤ n of ⇠n = 0, (16)
where ⇤ n ⌘ {µ n , µ 2 ⇤} ⇢ P(X n ), and µ n is the product (i.i.d.) distribution induced by µ 2 P(X).

By definition of R n (d, µ n ) in ( 12), we have that R(⇠ n , µ n ) R n (d, µ n ) 0 and, consequently, this last expression can be interpreted as the redundancy (in bits per sample) we have to accept for not knowing the distribution of X n and using a distribution independent lossy encoder. Therefore, if {⇠ n , n 1} is strongly minimax universal, it means that as the block length tends to infinity (and uniformly over the family of hypotheses in ⇤), the scheme achieves the best performance obtained by a scheme that knows the distribution of the source previous to encoding. Similarly, we can use the following definition: Definition 3: A scheme {⇠ n , n 1} (operating at distortion d > 0) is weakly minimax universal for ⇤ at distortion d if [START_REF] Davisson | Universal noiseless coding[END_REF],

lim n!1 [R(⇠ n , µ n ) R n (d, µ n )] = 0, 8µ 2 ⇤. (17)
In contrast to Definition 2, being weakly minimax universal imposes a point-wise convergence of the redundancy over the collection of hypotheses in ⇤.

In this redundancy analysis, we use R n (d, µ n ) instead of the asymptotic limit R ⇤ (d, µ 1 ) stated in Theorem 1. Indeed, R n (d, µ n ) is a tighter finite-length lower bound (a nonasymptotic performance limit) of the optimal rate (in bits per sample) that can be achieved in the operational problem in [START_REF] Cover | Enumerative source coding[END_REF] when the distribution of the source is available 3 . For the lossless case (i.e., d = 0), R n (d, µ n ) reduces to the entropy of µ and, consequently, R(⇠ n , µ n ) R n (d, µ n ) can be seen also as an extension of the redundancy term used for the analysis of universal variable length lossless source coding [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Davisson | Universal noiseless coding[END_REF], [START_REF] Gassiat | Universal Coding and Order Identification by Model Selection Methods[END_REF].

Before we move to the presentation of the main context of study of this work, we present a general analysis for the worst-case redundancy in [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF].

A. Minimax Redundancy Analysis

Let ⇠ n = ( n , C n , D n ) be a D-semifaithful code of length n operating at distortion d > 0, and µ be a distribution in ⇤ ⇢ P(X). Then, the average redundancy of ⇠ n (in bits per sample) can be expressed by

R(⇠ n , µ n ) R n (d, µ n ) =  R(⇠ n , µ n ) H (⇡ n ) (µ n ) n +  H (⇡ n ) (µ n ) n R n (d, µ n ) , (18)
where ⇡ n is the partition of X n induced by n (see Eq.( 4)) for the n-fold distribution induced by µ. In particular, the first term on the right-hand side (RHS) of ( 18) is non-negative from [START_REF] Babkin | Method of universal coding for an independent message source with non-exponential computational complexity[END_REF] and the second term is non-negative from the definition in [START_REF] Fitingof | The compression of discrete information[END_REF].

1) The Projected Information Radius of ⇤ n with Respect to ⇡ ⇡n : For the moment, let us concentrate on the analysis of [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF]. From a well-known correspondence between distributions and prefix-free codes [START_REF] Cover | Elements of Information Theory[END_REF], the encoder C n can be associated with a distribution

⇥ R(⇠ n , µ n ) H (⇡ n ) (µ n )/n ⇤ in (
v Cn 2 P(B n ) 4 and R(⇠ n , µ n ) H (⇡ n ) (µ n )/n is lower bounded by 1 n D(v µ n kv Cn ) = 1 n X y n 2Bn v µ n (y n ) log v µ n (y n ) v Cn (y n ) 0,
where v µ n 2 P(B n ) is a short-hand for the distribution induced by µ n and n in the reproducible space B n . Then, we can adopt a lower bound of the worst-case (over ⇤) discrepancy by the expression

R + n (⇤, ⇠ n ) ⌘ 1 n sup µ2⇤ D(v µ n kv Cn ) 0, (19)
where

⇠ n = ( n , C n , D n ).
For the rest of the analysis, we fix the quantization n (i.e., B n and its associated partition ⇡ n ), and we optimize the prefix-free mapping (denoted by C n ) from

B n to {0, 1}
⇤ with respect to the lower bound divergence term in ( 19) 5 . The solution of this problem introduces the information radius of the family ⇤ n projected over the sigma field induced by the partition ⇡ n [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF]. More precisely, we obtain the following:

min Cn sup µ2⇤  R(⇠ n = ( n , C n , D n ), µ n ) H (⇡ n ) (µ n ) n min Cn R + n (⇤, ⇠ n = ( n , C n , D n )) (20)
1 n R + (⇤ n , (⇡ n )), (21)
where

R + (⇤ n , (⇡ n )) ⌘ min v2P(Bn) sup µ n 2⇤ n D(v µ n kv) = min v2P(X n ) sup µ n 2⇤ n D (⇡ ) (µ n kv). ( 22
) 4 v Cn (y n ) = 2 L(Cn(y n )) /C for all y n 2 B, where C = P y n 2Bn 2 L(Cn(y n ))  1 [3]. 5
Dn is a deterministic function of Cn and, therefore, it is omitted in the optimization in [START_REF] Boucheron | About adaptive coding on countable alphabets: Max-stable envelope classes[END_REF].

The inequality in [START_REF] Silva | The redundancy gains of almost lossless universal source coding over envelope families[END_REF] follows from the observation that {v Cn ; C n is prefix-free mapping} ⇢ P(B n ). The expression in [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF] is the information radius of ⇤ n projected on ⇡ n that is written in terms of the divergence between distributions on the original sample space X n but restricted over the cells of ⇡ n using that

D (⇡) (µkv) ⌘ X A2⇡ µ(A) log µ(A) v(A)  D(µkv), (23)
for any ⇡ partition of X n and µ, v 2 P(X n ). Finally, the lower bound in ( 21) is tight (up to a discrepancy of 1/n). More precisely, we have that 6min

Cn sup µ2⇤  R(( n , C n , D n ), µ n ) H (⇡ n ) (µ n ) n  1 n (R + (⇤ n , (⇡ n )) + 1). (24)
In summary for a fixed quantizer n , optimizing the secondstage (over the collection of prefix-free encoder-decoder pairs) reduces to the information radius problem in [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]. This problem finds the distribution that is closest to the entire family ⇤ n (or the centroid of the family) using the divergence restricted over the sub-sigma field (⇡ n ) in [START_REF] Han | Weak variable-length source coding[END_REF]. Naturally, this is the same information radius characterization used in universal (variable length) lossless source coding [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF].

2) Universal Quantization over ⇤ n : Let us now concentrate on the analysis of the other term in [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF] ⇥

H (⇡ n ) (µ n )/n R n (d, µ n ) ⇤ ,
which depends exclusively on the quantizer n (or equivalently on ⇡ n 2 Q n (d), see ( 12)). Then considering the universal setting, we can optimize ⇡ n 2 Q n (d) in the following worst-case sense:

min ⇡2Qn(d) sup µ n 2⇤ n  H (⇡) (µ n ) min ⇡2Qn(d) H (⇡) (µ n ) . ( 25
)
This problem can be interpreted as the universal minimax counterpart of the problem presented in [START_REF] Fitingof | The compression of discrete information[END_REF].

B. Strong-Minimax Universality

From the analysis made on the two terms in [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF], it is observed that everything reduces to the selection of the firststage of the encoding process (the quantization). The following result formalizes this observation:

LEMMA 1: A necessary and sufficient condition for the existence of a strongly universal D-semifaithful code operating at distortion d > 0 for ⇤ (Def. 2) is that there is a sequence of partitions {⇡ n , n 1} satisfying the following:

i) ⇡ n 2 Q n (d) for all n 1, (the fixed distortion requirement) ii) lim n!1 1 n R + (⇤ n , (⇡ n )) = 0, and iii) lim n!1 1 n sup µ n 2⇤ n ⇥ H (⇡n) (µ n ) min ⇡2Qn(d) H (⇡) (µ n ) ⇤ = 0.
From this result achieving strong minimax universality for ⇤ at distortion d requires meeting two conditions: on the one hand, that a universal quantizer can be found that approximates the best performance stated in [START_REF] Fitingof | The compression of discrete information[END_REF] as the blocklength tends to infinity (the approximation criterion in iii), and, on the other hand, that the resulting information radius of the projected family grows sub-linearly with the block-length (the complexity criterion in ii). This result captures the information radius condition known in the lossless universal source coding problem but adds another component making the problem conceptually more difficult to address, which is the existence of a universal quantization for the family {⇤ n , n 1} in the sense of condition iii).

In this fixed-distortion setting, we could move to the extreme of asking for a zero distortion (d = 0), where for any reasonable distortion, the quantizer n needs to be the identity to meet the distortion criterion in i). In this context, condition iii) is trivially met and minimax universality reduces to verifying the information radius condition of the un-projected family, i.e., R

+ (⇤ n ) = min v2P(X n ) sup µ n 2⇤ n D (⇡ ) (µ n kv).
Then, in the zero distortion regime, Theorem 1 recovers the necessary and sufficient condition known for lossless minimax universal source coding [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Gassiat | Universal Coding and Order Identification by Model Selection Methods[END_REF], [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF].

In the next section, we will use these conditions implicitly and explicitly to study strong minimax universality for the family of envelope distributions on infinite alphabets.

C. Proof of Lemma 1

Proof: For the direct part, for any n 1 and d > 0, let us consider a lossy code

⇠ ⇤ n = ( ⇤ n , C ⇤ n , D ⇤ n ) of length n such that ⇤ n is determined from ⇡ n , i.e. ⇡ ⇤ n = ⇡ n .
From this, ⇠ n is a Dsemifaithful code operating at distortion d from the assumption that ⇡ n 2 Q n (d). 7 For the second stage (the variable length encoder-decoder of B n ), let us consider the pairs (C ⇤ n , D ⇤ n ) as a solution of the minimax operational problem presented in the LHS of (20), i.e.,

min Cn sup µ2⇤ " R(( ⇤ n , C n , D n ), µ n ) H (⇡ ⇤ n ) (µ n ) n # .
Then we know from (24) that

sup µ2⇤ " R(⇠ ⇤ n , µ n ) H (⇡ ⇤ n ) (µ n ) n #  1 n R + (⇤ n , (⇡ ⇤ n )) + 1 n = 1 n R + (⇤ n , (⇡ n )) + 1 n .
(26) 7 To achieve this, it is sufficient to have that y n 2 ⇤ n 1 ({y n }) for any y n 2 Bn.

Finally using [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF], it follows that

sup µ2⇤ [R(⇠ ⇤ n , µ n ) R n (d, µ n )]  sup µ2⇤ " R(⇠ ⇤ n , µ n ) H (⇡ ⇤ n ) (µ n ) n # + sup µ2⇤ " H (⇡ ⇤ n ) (µ n ) n R n (d, µ n ) #  1 n R + (⇤ n , (⇡ n )) + 1 + 1 n sup µ n 2⇤ n  H (⇡n) (µ n ) min ⇡2Qn(d) H (⇡) (µ n ) , (27)
which concludes the proof from the assumptions on {⇡ n , n 1} in ii) and iii). For the other implication (i.e., the necessary condition), let us assume that there is a D-semifaithful coding scheme

{⇠ ⇤ n = ( ⇤ n , C ⇤ n , D ⇤ n ), n 1} operating at distortion d > 0 such that lim n!1 sup µ n 2⇤ n [R(⇠ ⇤ n , µ n ) R n (d, µ n )] = 0. (28)
From ( 2), we have that ⇡ ⇤ n 2 Q n (d) for all n 1 (condition i). Concerning the information radius, using [START_REF] Silva | The redundancy gains of almost lossless universal source coding over envelope families[END_REF] it follows that sup

µ n 2⇤ n " R(( ⇤ n , C ⇤ n , D ⇤ n ), µ n ) H (⇡ ⇤ n ) (µ n ) n # min Cn sup µ n 2⇤ n " R(( ⇤ n , C n , D n ), µ n ) H (⇡ ⇤ n ) (µ n ) n # 1 n R + (⇤ n , (⇡ ⇤ n )). (29)
Then using the decomposition of the average redundancy in [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF], it follows that

sup µ n 2⇤ n (R(⇠ ⇤ n , µ n ) R n (d, µ n )) sup µ n 2⇤ n " R(⇠ ⇤ n , µ n ) H (⇡ ⇤ n ) (µ n ) n # 1 n R + (⇤ n f , (⇡ ⇤ n )), (30)
which proves that condition ii) is satisfied from [START_REF] Yu | A rate of convergence result for a universal dsemifaithful code[END_REF]. Using again [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF], it follows that

8µ n 2 ⇤ n R(⇠ ⇤ n , µ n ) R n (d, µ n ) H (⇡ ⇤ n ) (µ n ) n R n (d, µ n ). ( 31
)
Verifying condition iii) follows from [START_REF] Yu | A rate of convergence result for a universal dsemifaithful code[END_REF] and the definition of R n (d, µ n ) in [START_REF] Fitingof | The compression of discrete information[END_REF].

IV. RESULTS FOR ENVELOPE FAMILIES

The results for envelope distributions on 1-alphabets are presented in this section. Let us first introduce some definitions that will be needed for the statement of results. We begin introducing the family of models: Definition 4: Let f : X ! R + be a function. We define the envelope family induced by f as

⇤ f ⌘ {µ 2 P(X) : µ(x)  f (x), 8x 2 X} , (32)
where (µ(x)) x2X is a short-hand notation for the probability mass function (pmf) of µ. Definition 5: Let H(X) ⇢ P(X) denote the set of all probabilities (source) with finite entropy in X.

In addition, we need to introduce a notion of regularity for the distortion function. We consider the Euclidean norm between two points in X denoted by |i j| for any i, j 2 X. With this, the ball of radius ✏ and centered at i is denoted by B ✏ (i) ⌘ {j 2 X, |i j| < ✏} for any ✏ > 0 and i 2 X.

Definition 6: An unbounded distortion function ⇢ : X ⇥ X ! R + is said to be consistent with respect to the Euclidean norm if for any K > 0, there exists ✏ > 0 such that for any i 2 X if j / 2 B ✏ (i) then ⇢(i, j) K. The condition on ⇢ stated in Definition 6 implies that for any arbitrarily large K > 0, there is a sufficiently large ✏ > 0 (only function of K) where the condition ⇢(i, j) < K implies that |i j| < ✏. In other words, a fixed distortion condition ⇢(i, j) < d (for any d > 0) would be violated eventually by making i and j progressively far apart in terms of the Euclidean norm (restricted over X). An implication of this condition is that any partition of X with cells that meet a fixed-distortion requirement (i.e., elements of Q 1 (d) for any d > 0) requires an infinite number of cells 8 . In other words, a d-covering of X with cells that meet a fixed-distortion requirement retains the infinite cardinality of the lossless problem (the cardinality of X). In summary, the condition in Definition 6 is relevant as we are interested in problems where D-semifaithful source coding do not reduce to an equivalent finite alphabet coding task.

A. Main Results

THEOREM 2: Let ⇤ f ⇢ P(X) be induced by a nonnegative function f and ⇢ be an unbounded distortion consistent with respect to the Euclidean norm (Def. 6). We have the following results: i) If f / 2 `1(X), then for any d > 0 and any D-semifaithful coding scheme {⇠ n , n 1} operating at distortion d:

sup µ2⇤f [R(⇠ n , µ n ) R n (d, µ n )] = 1, 8n 1.
ii) If f 2 `1(X), then for any distortion d > 0, there exists a D-semifaithful coding scheme {⇠ n , n 1} operating at distortion d -with respect to {⇢ n , n 1} -that is weakly minimax universal, i.e., 9 then the same construction presented in ii) is strongly minimax universal, i.e.,

lim n!1 [R(⇠ n , µ n ) R n (d, µ n )] = 0, for any µ 2 ⇤ f \ H(X). iii) If ⇤ f ⇢ H(X),
lim n!1 sup µ2⇤f [R(⇠ n , µ n ) R n (d, µ n )] = 0.
The proofs of these results are presented in Section VII. Some remarks about Theorem 2:

1: The result in part i) implies that achieving strongminimax universality is not feasible for the entire collection of stationary memoryless sources in 1-alphabets. This is a direct implication of this result using f (i) = 1 for all i 2 X.

2: Interestingly, part i) matches the impossibility condition known for the lossless case in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. Therefore, in the context of infinite alphabet stationary and memoryless sources, a nonzero distortion does not help making feasible the task of universal source coding as we move from the lossless to the lossy (fixed-distortion) setting of the variable length coding problem.

3: The argument used for the impossibility part relies on the proof of Lemma 1 and in particular on bounding from below the worst-case redundancy by the I-radius of ⇤ f projected over the cells induced by a D-semifaithful code (operating at distortion d). Then, the proof reduces to show that this redefined I-radius (see [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF]) is unbounded for any partition of X that belongs to Q n (d) and for any d > 0.

4: On the other hand, assuming that f 2 `1(X), the result in part ii) shows that there is a D-semifaithful scheme that achieves weak minimax universality for any d > 0. This result is strengthened in part iii) showing that the same Dsemifaithful construction is strongly minimax universal provided that ⇤ f ⇢ H(X).

5: The constructive (achievability) argument used for the proof of Theorem 2 (part iii) is based on a two-stage (lossylossless) scheme (see Figure 1 in Section VII). The basic idea of this construction is to consider a specific two-stage lossy coding scheme. In the first-stage of this scheme, the problem is projected (loosely) to a finite alphabet task for which results for finite alphabet universal source coding are adopted (see Lemma 5 in Section VII). The second-stage, on the other hand, is addressed as a lossless source coding problem over a transformed infinite alphabet, where results from lossless universal source coding for envelope families are used (see Lemma 6 in Section VII).

6: An important result used in the proof of Theorem 2 (part iii) is that the so called envelope distribution μf derived from f by

μf (x) ⌘ 8 < : f (x) if x ⌧ f 1 P x ⌧f f (x) if x = ⌧ f 1 0 if x < ⌧ f 1, , with ⌧ f ⌘ min n k 1, P x k f (x)  1 o
, is the probability in ⇤ f that achieves maximum entropy under some mild considerations. The statement of this result is presented in Lemma 7 (in Sect VII-B). Therefore, the condition ⇤ f ⇢ H(X) reduces to the verification of H(μ f ) < 1 and, consequently, that the function (f (x) log 1/f (x)) x2X is summable 10 . Complementing this observation, we obtain the following implication: 11 COROLLARY 1:

⇤ f ⇢ H(X) is equivalent to sup µ2⇤f H(µ) < 1.
7: Finally, Theorem 2 can be extended to the scenario of a bounded distortion if it is consistent with the Euclidean norm in the following sense: 10 (f (x) log 1/f (x)) x2X being summable implies that f 2 `1(X). 11 The proof is presented in Appendix VI-D. Definition 7: A bounded distortion function ⇢ : X ⇥ X ! [0, ⇢ max ], with ⇢ max > 0, is said to be consistent with respect to the Euclidean norm if for any K 2 (0, ⇢ max ), there is ✏ > 0 such that for any i 2 X if j / 2 B ✏ (i) then ⇢(i, j) K. The statement of that result would be the same as the statement of Theorem 2 but restricting d to the range (0, ⇢ max ). The proof argument follows directly from the proof of Theorem 2, consequently, both the statement and the proof are omitted. Finally, it is worth noting that the Hamming distance satisfies Def. 7 as many other regular distortions, e.g., ⇢ M (i, j) ⌘ K min {|i j| , M} for any K 2 R + \ {0} and M > 1.

B. Rate of Convergence

The next result complements Theorem 2 by providing an upper bound on the rate of convergence for the worst-case overhead for the case of summable envelope families.

THEOREM 3: Under the setting of Theorem 2, if ⇤ f ⇢ H(X), and we add the condition that

lim sup k!1 P i k f (i) log 1/f (i) μf (T k ) log 1/μ f (T k ) < 1 with T k ⌘ {k, k + 1, . . .} ⇢ X, then for any distortion d > 0, there is a D-semifaithful coding scheme {⇠ ⇤ n , n 1} operating at distortion d -with respect to {⇢ n , n 1} -such that sup µ2⇤f [R(⇠ ⇤ n , µ n ) R n (d, µ n )]  C 0 u f (n) log n n + C 1 log n n + C 2 1 n ,
where C 0 , C 1 and C 2 are constants and

u f (n) ⌘ min {k 1 such that μf (T k+1 ) < 1/n} . ( 33
)
The proof is presented in Section VII.

This last result adds a regularity assumption on the way the tail component of the entropy of μf tends to zero, which is sufficient to obtain a rate of convergence for the worstcase overhead that is O(u f (n) log(n)/n). Importantly, it can be verified that polynomial envelope families (with f p (x) = K/x p for some p > 1 and K > 0) and exponential envelope families (with f p (x) = Ke ↵x with K > 0 and ↵ > 0) satisfy the tail conditions stated in this result, and, consequently, they are both strongly minimax universal. In fact, we have the following:

LEMMA 2: Let us consider a polynomial function given by (f p (i)) i 1 = (K/i p ) i 1 . For any K > 0 and p > 1 it follows that

lim sup k!1 P i k f p (i) log 1/f p (i) μfp (T k ) log 1/μ fp (T k ) < 1.
LEMMA 3: Let us consider an exponential function given by (f ↵ (i)) i 1 = (Ke ↵i ) i 1 . For any K > 0 and ↵ > 0 it follows that lim sup k!1

P i k f ↵ (i) log(1/f ↵ (i)) μf↵ (T k ) log(1/μ f↵ (T k )) < 1.
The proofs of these Lemmas are presented in Appendices I and II, respectively.

Finally, the sequence (u f (n)) n 1 in (33) was introduced by Bontemps et al. in [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF] for the lossless source coding problem, where the same rate O(u f (n) log(n)/n) was obtained for the redundancy of the best (lossless) universal scheme with f 2 `1(X), see [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]Th. 4] and [16, Th.2 and Prop. 5] 12 . For the exponential envelope family of parameter ↵ in Lemma 3, it was shown in [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]Prop. 6] and [22,

Sect. VI.B.4)] that 1 ↵ ln(Kn)+ 1 < u f↵ (n)  1
↵ ln(CKn) where C = 1/(1 e ↵ ). Consequently, from Theorem 3, there is

{⇠ ⇤ n , n 1} (operating at distortion d) such that sup µ2⇤f ↵ [R(⇠ ⇤ n , µ n ) R n (d, µ n )] is O( (log n) 2 n
). For the power law envelope family of parameter p in Lemma 2, the same method used to bound u f↵ (n) for the exponential family in [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]Prop.6] can be adopted to show that (KS)

1/p •n 1/p 2 < u fp (n)  (KS) 1/p •n 1/p +1, where S = P k 1 1/k p < 1 (as (f p (i)) i 1 2 `1(X) for p < 1). Conse- quently, from Theorem 3, there is {⇠ ⇤ n , n 1} (operating at distortion d) such that sup µ2⇤f p [R(⇠ ⇤ n , µ n ) R n (d, µ n )] is O( (n 1/p log n n ).

V. CONCLUDING REMARKS AND FUTURE WORK

On the analysis of universal D-semifaithful source coding on envelope families, Theorem 2 offers a necessary and sufficient condition to achieve minimax universality (in the sense introduced in Section III) for ⇤ f in 1-alphabets. Interestingly, the condition matches the summability condition over f known for the lossless (variable length) coding setting [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF].

On future work, it remains an open problem to evaluate if the rate of convergence for the worst-case overhead obtained in Theorem 3 can be improved. It is intriguing that this result does not show a faster rate of convergence to zero with n (because of the non-zero distortion) with respect to its lossless counterpart that has the same rate [START_REF] Gassiat | Universal Coding and Order Identification by Model Selection Methods[END_REF]- [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF], [START_REF] Boucheron | About adaptive coding on countable alphabets: Max-stable envelope classes[END_REF]. In fact, the result is insensitive to the value of d, which is something that requires a more careful analysis. In favor of the potential tightness of this part, we note that the non-zero distortion did not show an effect on the impossibility part (part i) of Theorem 2) with respect to its counterpart in the lossless problem [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF]. On the other hand, it is clear that the distortion reduces the information radius of the projected family, in the sense that R + (⇤ n f , (⇡ n ))  R + (⇤ n f ) (see the definition in Eq.( 22)). Then, the non-zero distortion does reduce this information radius complexity indicator. However, it is unclear that this gain in information radius translates into a gain in the overall minimax overhead expression in the lossy setting (with respect to its counterpart in the lossless setting) because the information radius captures only one of the two expressions of redundancy in [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF]. The other non-negative term is captured by the role of the universal quantization discrepancy mentioned in [START_REF] Kieffer | Sample converses in source coding theory[END_REF]. To conclude this discussion, we realize (from the expression in [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF] and the analysis in Section III-A.1) that a concrete way to prove that the result in Theorem 3 is optimal is to show that any sequence of partitions

{⇡ n , n 1} such that ⇡ n 2 Q n (d) satisfies that lim inf n!1 R + (⇤ n f , (⇡ n )) R + (⇤ n f ) > 0. (34)
At a first glance, this result does not appear intuitive, but we could conjecture that it is true. Indeed, a related non-zero gain (information radius) result has been obtained by the authors of this work in [START_REF] Silva | The redundancy gains of almost lossless universal source coding over envelope families[END_REF], [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF] but in a simpler context involving a tail-based scalar quantization and a distortion that is not fixed and tends to 0 with n. We believe that some of the tools used in this analysis can be adopted to derive [START_REF] Kontoyiannis | Arbitrary source models and bayesian codebooks in rate-distortion theory[END_REF], but the extension to analyze the object in ( 34) is not direct. This is a relevant direction for future work on universal source coding on infinite alphabets. Finally, on the general analysis of universal D-semifaithful coding presented in Section III of this work, Lemma 1 tells us that meeting minimax universality for a given non-zero distortion d > 0 and a family of distributions ⇤ implies the existence of a universal sequence of D-semifaithful quantizers for ⇤. Consequently, if the minimax redundancy criterion in ( 16) is met, for some d > 0, then there exists a sequence of partitions {⇡ n , n 1}, such that ⇡ n 2 Q n (d) (introduced in ( 12)), satisfying that

lim n!1 1 n sup µ n 2⇤ n f  H (⇡n) (µ n ) min ⇡2Qn(d) H (⇡) (µ n ) = 0, (35)
where H (⇡n) (µ n ) is the entropy of µ n restricted to the sub-sigma field induced by ⇡ n (see Eq.( 9)), and min ⇡2Qn(d) H (⇡) (µ n ) is the quantizer in Q n (d) that minimizes the entropy given the distribution µ n and d. For obvious reasons, this representation dimension of the problem in [START_REF] Kieffer | Sample converses in source coding theory[END_REF] is not part of the lossless setting and requires a special treatment in this lossy case. In principle, it is not obvious that the criterion in [START_REF] Kieffer | Sample converses in source coding theory[END_REF] can be achieved for any family of stationary memoryless distributions in 1-alphabets. Then, a direct implication of Theorem 2 for envelope families (the achievability part in iii)) is that there is a universal quantization scheme in the sense presented in [START_REF] Kieffer | Sample converses in source coding theory[END_REF] for ⇤ f when f 2 `1(X). The proof of Theorem 2 in Section VII-B offers a concrete construction for this universal quantization scheme based on the two-stage quantization approach illustrated in Figure 1.

VI. ENTROPY AND DISTRIBUTION ESTIMATION FOR INFINITE ALPHABETS: DISCUSSION ON RELATED IMPOSSIBILITY AND ACHIEVABILITY RESULTS

It is worth mentioning that a minimax universal (variable length) source code (Definition 3) can be used to determine (estimate) the rate-distortion function R ⇤ (d, µ 1 ) and the entropy of a distribution µ 2 H(X) as a special case (d = 0). Given this capability, it is interesting to mention some results for entropy estimation and distribution estimation for infinite alphabets. We focus on the lossless coding setting (d = 0) as this regime offers a connection with the problems of entropy estimation and distribution estimation in information divergence [START_REF] Gyorfi | There is no universal source code for an infinite source alphabet[END_REF], [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF], [START_REF] Antos | Convergence properties of functionals estimates for discrete distributions[END_REF], [START_REF] Silva | Shannon entropy estimation in 1-alphabets from convergence results: Studying plug-in estimators[END_REF].

In the lossless setting (d = 0), the existence of a weak minimax coding scheme f n :

X n ! {0, 1} ⇤ (Def. 3) im- plies that sup µ2⇤ lim n!1 (r(f n , µ n ) H(µ)) = 0 where r(f n , µ n ) = E(L(f n (X n )))
/n is the average rate in bits per sample of f n . Consequently, under this (weak) minimax property, the average length of the code offers a consistent estimator of the entropy for all members of ⇤. Unfortunately, for the family of finite entropy stationary and memoryless sources, there is no variable-length code that achieves this weak minimax criterion (point-wise convergence to the entropy over the members of H(X)). This impossibility result was presented in [4, Theorem 3]. The authors of this result showed that for any block-length n and prefix-free code f n , there exists a model µ 2 H(X) where r(f n , µ n ) = 1. 13 . This negative result comes from the impossibility of estimating distributions in H(X) in the expected direct information divergence and the fact that the redundancy r(f n , µ n ) H(µ) is lower bounded by the expected divergence between µ and an estimator of µ constructed from the code f n [4, Theorem 2]. Consequently, the impossibility of distribution estimation for infinite alphabets implies the impossibility of estimating the entropy using the average length of a variablelength lossless (prefix-free) code. This impossibility result is consistent with Theorem 2 i), where based on the average length of a (D-semifaithful) code, we cannot estimate the rate-distortion function for the entire class of stationary and memoryless sources. Indeed, we show that for any d > 0, any n 1, any (D-semifaithful) code ⇠ n operating at distortion d and any L > 0, there is a distribution

µ 2 P (X) such that R(⇠ n , µ n ) R ⇤ (d, µ 1 ) > L.
Breaking from the lossless coding structure, we presented in [START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF] an almost lossless (variable length) coding strategy for infinite alphabet memoryless sources with the capacity to estimate the entropy over the family H(X) by tolerating a non-zero but vanishing distortion. The proposed lossy scheme (with a vanishing distortion) does not induce an estimate of the distribution in expected information divergence. Consequently, the impossibility result in [START_REF] Gyorfi | There is no universal source code for an infinite source alphabet[END_REF] does not contradict the fact that the average rate of this almost lossless source coding strategy provides a consistent estimation of the entropy distributionfree in H(X). More discussion on the use of this coding strategy for entropy estimation is presented in [22, Section IV.A].

Going beyond the use of source codes, there are other strategies and results for entropy estimation for infinite alphabets worth mentioning. These results, however, do not have an evident connection with the results presented in this paper and are relevant in their own merit. Regarding this, Antos and Kontoyiannis [36, Theorem 2 and Corollary 1] showed the remarkable result that the classical plug-in estimate of the entropy is strongly consistent 14 and consistent in the mean square error sense for any finite entropy distribution in H(X). On the analysis of the point-wise convergence of the estimation error, [36, Theorem 3] showed a finite length lower bound for this estimation error valid for any estimation scheme (impossibility result). This result implies (asymptotically) that no universal rate of convergence (to zero) can be achieved for the entropy estimation over the family of infinite alphabet memoryless sources. On the constructive side, constraining the problem to a family of distributions with specific power tail-bounded conditions, Antos et al. [START_REF] Antos | Convergence properties of functionals estimates for discrete distributions[END_REF]Theorem 7] presented a finite length expression for the rate of convergence of the estimation error of the classical plug-in estimator. Similar results -strong consistency distribution-free in H(X) and (almost sure) rate of convergence for the estimation error under some tail bounded conditions -have been obtained for a datadriven partition scheme in [START_REF] Silva | Shannon entropy estimation in 1-alphabets from convergence results: Studying plug-in estimators[END_REF]. 15 .

VII. PROOFS OF THE MAIN RESULTS OF SECTION IV

A. Theorem 2 -Part i): f / 2 `1(X) Proof: Let us consider d > 0 and arbitrary D-semifaithful coding scheme {⇢ n = ( n , C n , D n ), n 1}, such that ⇢ n (x n , n (x n ))  d, (36)
for all n 1 and x n 2 X n . We denote by

B n = { n (x n ), x n 2 X n
} the range of n and by ⇡ n the partition of X n induced by n (see Eq.( 4)). From the decomposition in [START_REF] Clarke | Information-theoretic asymptotics of Bayes methods[END_REF], for any

µ n 2 ⇤ n f R(⇠ n , µ n ) R n (d, µ n )  R(⇠ n , µ n ) H (⇡ n ) (µ n ) n . (37)
From ( 37) and the analysis presented in Sec.III-A.1, the worstcase overhead over ⇤ f is bounded by

sup µ n 2⇤ n f R(⇠ n , µ n ) R n (d, µ n ) 1 n sup µ2⇤f D(v µ n kv Cn ) 1 n min v2P(X n ) sup µ n 2⇤ n f D (⇡ ) (µ n kv) = 1 n R + (⇤ n f , (⇡ n )), (38)
where R + (⇤ n f , (⇡ n )) is the information radius of the family ⇤ n f restricted to the sub-sigma field induced by ⇡ n . The rest of the proof will show that R (⇤ n f , (⇡ n )) = 1, for any n 1. Using that f / 2 `1(X), i.e., P x2X f (x) = 1, we can use the method presented in [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF] to show that there is a countable collection of distributions ⇤ = {μ j , j 2 J } ⇢ ⇤ f with |J | = 1, where if we denote by A j = support(μ j ) ⌘ {x 2 X, μj (x) > 0} , then |A j | < 1 for each j 2 J and for any i, j 2 J i 6 = j A i \A j = ;. For completness, a construction of ⇤ is presented in Appendix VI-B. Then, we can consider the n-fold family ⇤n = μn j , j 2 J where support(μ n j ) = A n j = A j ⇥ ... ⇥ A j ⇢ X n . Using the consistency of ⇢ with respect to the Euclidean norm (in Def.6), Proposition 2 (in Appendix VI-C) shows that to achieve the fixed distortion criterion in [START_REF] Antos | Convergence properties of functionals estimates for discrete distributions[END_REF], it is necessary that the range of n has an infinite number of prototypes: i.e., we have that

|B n | = 1.
For any j 2 J , let us consider a covering of the support of μn j by cells of ⇡ n by

C(A n j ) ⌘ [ B2⇡n(A n j )
B, (39) 15 As a side comment, the mentioned tail bounded conditions used in [START_REF] Antos | Convergence properties of functionals estimates for discrete distributions[END_REF], [START_REF] Silva | Shannon entropy estimation in 1-alphabets from convergence results: Studying plug-in estimators[END_REF] to obtain rate of convergence for entropy estimation are stronger than the condition used in our work to define the envelope families (Definition 4) -used in our achievability results in Theorems 2 and 3 where ⇡ n (A n j ) ⌘ B 2 ⇡ n , A n j \ B 6 = ; . At this point, we can show that C(A n j ) < 1, 8j 2 J . This follows from the construction of A n j , j 2 J and the observation that any cell B in ⇡ n is a finite set from the hypothesis that ⇡ n 2 Q n (d) and the consistency assumption on ⇢ n (Def. 6). Therefore, we get that C(A n j ) in (39) is a finite set for any j. Let us consider a countably infinite sub-collection of disjoint sets in C(A n j ), j 2 J by the following approach:

j 1 ⌘ 1, j 2 ⌘ min j > j 1 , such that C(A n j ) \ C(A n j1 ) = ; , . . . j k ⌘ min ( j > j k 1 , such that C(A n j ) \ k 1 [ l=1 C(A n jl ) = ; ) . . . . (40)
For any finite k, the solution in ( 40) is guaranteed to be achieved with a finite integer; then, we have an infinite new collection of probabilities ⇤n ⌘ μn jk , k 1 ⇢ ⇤n ⇢ ⇤ n f . Based on the construction of μn jk , the family ⇤n is composed of a collection of probabilities with disjoint support in X n . Then, we consider the following partition of

X n ⌘ n ⌘ C(A n jk ), k 1 [ X n \ 1 [ k=1 C(A n jk ) ! , ( 41
)
where it is clear that (⌘ n ) ⇢ (⇡ n ) and for any µ, v 2

P(X n ), D (⌘n) (µkv)  D (⇡ n ) (µkv).
The important point here is that ⇤n contains an infinite set of distributions with disjoint support when restricted to the cells of ⌘ n in (41) and, thus, from the known connection between information radius and channel capacity [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], the following can be obtained: LEMMA 4: R + ( ⇤n , (⌘ n )) = 1. The proof of Lemma 4 is presented in Appendix V.

Therefore, we have that

R + (⇤ n f , (⇡ n )) R + ( ⇤n , (⇡ n )) R + ( ⇤n , (⌘ n )) = 1, (42)
from the fact that by construction ⇤n ⇢ ⇤ n f and (⌘ n ) ⇢ (⇡ n ). Finally (42) and (38) prove the impossibility part (Theorem 2 i)). 16

B. Theorem 2 -Part iii

): f 2 `1(X) and ⇤ f ⇢ H(X)
To organize the proof of this part, let us first introduce preliminary results and definitions that will be used in the main argument.

Definition 8: The distribution induced by the tail function f is given by

μf (x) ⌘ 8 < : f (x) if x ⌧ f 1 P x ⌧f f (x) if x = ⌧ f 1 0 if x < ⌧ f 1, (43)
where

⌧ f ⌘ min n k 1, P x k f (x)  1 o .
Note that by construction, we have that μf (x) 2 ⇤ f and ⌧ f < 1 from the hypothesis that f 2 `1(X).

Let us consider the finite set k = {1, .., k} for any k 1. Then we have the following result for finite alphabet sources:

LEMMA 5: For any n 1, k 1, distortion d > 0 and ✏ > 0, there is a D-semifaithful code ⇠ ⇤k n = ( ⇤k n , C ⇤k n , D ⇤k n ) on k+1 , that operates at distortion d > 0 (w.r.t. ⇢n ) and verifies that

sup v2P( k+1 )  1 n E Y n ⇠v n L(C ⇤k n ( ⇤k n (Y n ))) R n (d, v n )  k log(n + 1) n + ✏,
where P( k+1 ) is the collection of probabilities on k+1 (i.e., the simplex of dimension k).

The proof of Lemma 5 is presented in Appendix III.

For envelope families on infinite alphabets, we have the following remarkable result from Bontemps et al. [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]:

LEMMA 6: [16, Prop. 5] If f 2 `1(X), then for any n 1

(1 + o(1)) u f (n) 1 4 log n  R + (⇤ n f )  2 + log e + u f (n) 1 2 log n, (44)
where

u f (n) = min {k 1 such that μf (T k+1 ) < 1/n} . ( 45
) Finally, let us consider a tail partition of X given by ⇡k ⌘ { k , {k + 1} , {k + 2} , . . .} for any k 1. The next result shows that the tail distribution μf (in Def. 43) achieves maximum entropy over the envelope family in the following sense:

LEMMA 7: If H(μ f ) < 1, it follows that eventually in k (i.e., for a sufficiently large k),

sup µ2⇤f H (⇡k) (µ) = H (⇡k) (μ f ) < 1. Otherwise, if H(μ f ) = 1, then sup µ2⇤f H (⇡k) (µ) = H (⇡k) (μ ) = 1 for any k 1.
The proof of Lemma 7 is presented in Appendix IV. Consequently, we have that ⇤ f ⇢ H(X) is equivalent to the condition sup µ2⇤f H(µ) < 1.

Proof: The basic idea of the proof is to decompose the alphabet X into two segments and use a two-stage scheme. More precisely, let us consider the following mapping S k : X ! k+1 = {1, .., k + 1} where

S k (x) ⌘ ⇢ x if x 2 k = {1, .., k} k + 1 if x > k (46)
Applying this lossy mapping (letter by letter) to the source X n , we create a truncated version of it:

Y n 1 (k) ⌘ S k (X n ) ⌘ (S k (X 1 ), . . . , S k (X n )) 2 n k+1 .
(47) To retain the information lost from X n in Y n 1 (k), the following complementary mapping is used:

O k (x) ⌘ ⇢ 1 if x 2 k x if x > k 2 {1} [ c k , (48)
which induces

Z n 1 (k) ⌘ O k (X n ) ⌘ (O k (X 1 ), . . . , O k (X n )) 2 ({1} [ c k ) n . (49)
It is clear that for any k 1, Y n 1 (k) and Z n 1 (k) recover X n with no loss. In this context, we propose a two-stage strategy where Y n 1 (k) (a finite alphabet stationary memoryless source) is encoded with a D-semifaithful code (operating at distortion d > 0) and Z n 1 (k) (an infinite alphabet stationary memoryless source) is encoded losslessly using a variable-length code. Let us consider a distortion d > 0 and a D-semifaithful triplet

⇠ k n = ( k n , C k n , D k n )
for the source Y n 1 (k) on the alphabet k+1 , operating at distortion d > 0 with respect to a distortion ⇢ on k+1 ⇥ k+1 , where we assume that ⇢ coincides with ⇢ on k ⇥ k (the non-truncated symbols, see Eq. ( 46)). This means that for all

y n 2 n k+1 ⇢n (y n , k n (y n ))  d. (50)
On the other hand, we can consider a lossless variable-length encoder-decoder pair ( Ck n , Dk n ) for the source Z n 1 (k), where

Ck n : ({1} [ c k ) n ! {0, 1} ⇤ and Dk n : {0, 1} ⇤ ! ({1} [ c k ) n .
Then, given an input x n 2 X n the final output (after decoding) of this two-stage approach is

(ŷ n , z n ) = ( k n (S k (x n )), O k (x n )) 2 ( k+1 ) n ⇥ ({1} [ c k ) n . (51)
Finally, we recover xn from (ŷ n , z n ) by the following letterby-letter mapping

xn = ( k (ŷ 1 , z 1 ), . . . , k (ŷ n , z n )) 2 X n ,
where

k (ŷ i , z i ) ⌘ ⇢ z i if z i 2 c k ŷi if z i = 1 2 X. (52)
Then, using the condition imposed on ⇢, it follows that

⇢ n (x n , xn )  ⇢n (y n , ŷn )  d, (53)
where y n = S k (x n ) and ŷn is defined in (51). The first inequality in (53) is verified in Appendix VI-A, and the second follows from the fact that ⇠ k n is a D-semifaithful code with respect to ⇢. Therefore, this two-stage strategy produces a D-semifaithful code in X n with respect to ⇢. The encodingdecoding process is illustrated in Figure 1.

On the other hand, the length of this two-stage mapping (in bits per sample) that we denote by T k n is given by

1 n L(T k n (x n )) = 1 n h L(C k n ( k n (S k (x n )))) + L( Ck n (O k (x n ))) i . (54)
Then if X n ⇠ µ n , the average length is given by

1 n E X n L(T k n (X n )) = 1 n E Y n L(C k n ( k n (Y n ))) | {z } first-stage bit rate + 1 n E Z n n L( Ck n (Z n )) o | {z } second-stage bit rate , (55)
where

Y n = S k (X n ) and Z n = O k (X n ).
because Ck n is a variable length (prefix-free) lossless encoder of Z n [START_REF] Cover | Elements of Information Theory[END_REF]. Furthermore, it is well-known that the redundancy of Ck n is equal to (up to a discrepancy of

O(1/n)) [3] 1 n h E Z n ⇠m n µ n L( Ck n (Z n )) o H(m n µ ) i ⇡ 1 n D(m n µ km Ck n ), (63)
where m Ck

n 2 P(({1} [ c k ) n
) is the distribution associated with the prefix-free code Ck n [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Cover | Elements of Information Theory[END_REF]. From this observation, the criterion for designing the second-stage in the context of universal source coding reduces to solving the following problem 17 :

R + ( ⇤n f , k) ⌘ min m2P(({1}[ c k ) n ) sup µ2⇤f D(m n µ km), (64)
which is the information radius of the projected family ⇤n f ⌘ m n µ , µ 2 ⇤ f . In particular, associated with the solution of (64) [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], there is a lossless code C⇤k

n such that R + ( ⇤n f , k) n  sup µ2⇤f  1 n E Z n ⇠m n µ n L( C⇤k n (Z n )) o H(m µ )  R + ( ⇤n f , k) + 1 n . (65)
Importantly, using the information radius object introduced in (20), it is simple to check that

R + ( ⇤n f , k) = R + (⇤ n f , (⇡ ⇥n k )) = min m2P(X n ) sup µ2⇤f D (⇡ ⇥n k ) (µ n km), (66)
where

⇡⇥n k ⌘ { k , {k + 1} , {k + 2} , . . .} n
denotes the partition of X n induced by the lossy mapping

(O k (), O k (), .., O k ()) : X n ! ({1} [ c k ) n .
Then from ( 23) and (66)

R + ( ⇤n f , k)  R + (⇤ n f ) ⌘ min m2P(X n ) sup µ2⇤f D(µ n km). (67)
This last expression is the information radius of the unconstrained family ⇤ n f [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF]. The result by Bontemps et al. [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF] (stated in Lemma 6) for summable envelope families comes in handy here. In fact, combining Lemma 6 with (65), for any k 1 and n 1, there exists a variable-length code

C⇤k n : ({1} [ c k ) n ! {0, 1} ⇤ satisfying that sup µ2⇤f  1 n E Z n ⇠m n µ n L( C⇤k n (Z n )) o H(m µ )  u f (n) 1 2 • log n n + 2 + log e n | {z } O(1/n) . (68)
It is important to note that the bound in the RHS of (68) is valid independent of (uniform over) k.

3) Maximum Entropy analysis over the Envelope Family:

For what follows, let us consider the assumption that 18sup µ2⇤f H(µ) < 1.

(69)

Then from (68), we have that there is a coding scheme n C⇤k n , n 1

o satisfying that 8k 1: sup µ2⇤f 1 n E X n ⇠µ n n L( C⇤k n (O k (X n ))) o  u f (n) 1 2 log n n + O(1/n) + sup µ2⇤f H(m µ,k ), = u f (n) 1 2 log n n + O(1/n) + sup µ2⇤f H (⇡k) (µ), 8n 1, (70)
where in the first inequality m µ,k 2 P({1}

[ c k ) denotes the distribution of Z = O k (X) when X ⇠ µ 2 ⇤ f ,
and in the second inequality, we use the tail partition ⇡k = { k , {k + 1} , {k + 2} , . . .}. To continue with the argument, we use Lemma 7 that shows that μf in (43) achieves the maximum entropy of the problem stated in the right term of (70) (eventually in k). Then assuming (69), i.e., H(μ f ) < 1, and a sufficiently large k,

1 n sup µ2⇤f E X n ⇠µ n n L( C⇤k n (O k (X n ))) o  u f (n) 1 2 log n n + O(1/n) + μf ( k ) log 1 μf ( k ) + X i k+1 μf (i) log 1 μf (i) , 8n 1.
(71)

4) Concatenating the results in (55): From the expressions in (55), ( 61) and (71), we have that for any distortion d > 0 and threshold k 1, there is a twostage scheme

n T ⇤k n = (⇠ ⇤k n , ( C⇤k n , D⇤k n )), n 1 o where ⇠ ⇤k n = ( ⇤k n , C ⇤k n , D ⇤k n )
is the D-semifaithful code of the first stage, operating at distortion d with respect to ⇢ k n , n 1 , and ( C⇤k n , D⇤k n ) is the variable-length lossless encoder-decoder pair of the second stage, such that for any n 1 and a sufficiently large k:

sup µ2⇤f  1 n E X n ⇠µ n L(T ⇤k n (X n )) R n (d, µ n )  k log(n + 1) n + u f (n) 1 2 log n n + O(1/n) + μf ( k ) log 1 μf ( k ) + X i k+1 μf (i) log 1 μf (i) , (72)
assuming that H(μ f ) < 1. Finally it is clear in the above construction that we can take (k n ) function of n to achieve minimax universality using the fact that (u f (n)•log n/n) tends to zero with n [START_REF] Boucheron | Coding on countably infinite alphabets[END_REF], [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]. In fact, if (k n ) tends to 1 with n and lim n !1 k n log(n)/n = 0, from (72) this is sufficient to have that

lim n !1 sup µ2⇤f  1 n E X n ⇠µ n L(T ⇤kn n (X n )) R n (d, µ n ) = 0. (73)
Consequently, we achieve strong minimax universality with the construction T ⇤kn n , n 1 in the sense stated in [START_REF] Bontemps | About adaptive coding on countable alphabets[END_REF]. This concludes the proof of Part iii).

C. Theorem 2 -Part ii): f 2 `1(X) and H(μ f ) = 1

Proof: If we relax the finite entropy condition on the envelope distribution, i.e., we have that H(μ f ) = 1 from Corollary 1, the same arguments and in particular the twostage construction presented in Section VII-B can be used to show that for any µ 2 ⇤ f , such that H(µ) < 1, it follows that 19 

1 n E X n ⇠µ n L(T ⇤kn n (X n )) R n (d, µ n ) | {z } point-wise analysis  k n log(n + 1) n + u f (n) 1 2 log n n + O(1/n) + µ( k ) log 1 µ( k ) + X i k+1 µ(i) log 1 µ(i) . (74)
Then under the conditions that (k n ) tends to infinity with n and (k n ) is o(log(n)/n), for any µ 2 ⇤ f \ H(X) it follows that

lim n !1  1 n E X n ⇠µ n L(T ⇤kn n (X n )) R n (d, µ n ) = 0, (75)
which concludes the proof of Part ii).

D. Theorem 3

Proof: Let us consider the assumption that

lim sup k!1 P i k μf (i) log(1/μ f (i)) μf (T k ) log 1/μ f (T k ) < 1. ( 76
)
Notice that the expression in the numerator of ( 76) is well defined as H(μ f ) < 1 from the hypothesis that ⇤ f ⇢ H(X).

Hence, the result in (72) for the worst-case overhead can be adopted. Using a sequence (k n ) n such that k n ! 1 then the term H (⇡k n ) (μ f ) in (72) can be expressed (in the limit) by 19 For the sake of space, the steps to derive (74) are not presented as it follows directly from the argument presented in Section VII-B.

lim sup n!1 H (⇡k n ) (μ f ) = lim sup n!1 μf (T kn ) log 1/μ f (T kn )⇥  1 + P i kn μf (i) log(1/μ f (i)) μf (T kn ) log 1/μ f (T kn ) , (77)
where from (76), there are two constants K 0 > 0 and N > 0, such that for any n N :

H (⇡k n ) (μ f ) = µ( kn ) log 1 µ( kn ) + X i kn+1 µ(i) log 1 µ(i)  μf (T kn ) log 1/μ f (T kn ) • K 0 . (78)
In particular, choosing (k f n ) n = (u f (n)) n by the definition in (45) it follows that μf (T k f n +1 ) < 1/n and μf (T

k f n ) 1/n. Then for any n 1: μf (T k f n ) log 1/μ f (T k f n )  1 n log n. (79)
Therefore considering the two-stage scheme 72), ( 78) and (79), we have that eventually in n

n T ⇤k f n n , n 1 o driven by (k f n ) n 1 , from (
sup µ2⇤f  1 n E X n ⇠µ n n L(T ⇤k f n n (X n )) o R n (d, µ n )  u f (n) log(n + 1) n + u f (n) 1 2 log n n + O(1/n) + K 0 • log n n , (80)
which concludes the proof.

VIII. ACKNOWLEDGMENT The work of J.F. Silva was supported by Fondecyt 1210315 CONICYT-Chile and the Advanced Center for Electrical and Electronic Engineering, Basal Project FB0008. This project has received funding from the European Unions Horizon 2020 research and innovation programme under the Marie Skodowska-Curie grant agreement No 792464. We thank the Associate Editor and the two reviewers for the time devoted to reviewing our work. Their observations and comments were instrumental to improve this paper content. The authors thank Sebastian Espinosa for helping with the Figure . Finally, we thank Diane Greenstein for editing and proofreading all this material.

APPENDIX I PROOF OF LEMMA 2

Proof: First, it is simple to verify that if p > 1, then (f p (i) log 1/f p (i)) i 1 2 `1(X), which implies that μfp 2 H(X) (see Eq.( 43)). Let us introduce the tail series: 20

S k p ⌘ X i k μfp (i) = X i k f p (i),
where the last equality is valid eventually (for k sufficiently large). Then it follows that

S k p = k p X i k k p i p = k p ✓ 1 + 1 ((k + 1)/k) p + . . . + 1 ((k + K)/k) p + . . . ◆ = k p 0 @ 1 + X i 1 1 (1 + i/k) p 1 A .
(81) 20 For this analysis, we consider K = 1.

797805.

The term of the series in the brackets on the RHS of ( 81) is indexed by the fraction i/k, where k is fixed and i goes over the integers. Hence, this series decomposes in k-additive components as follows:

0 @ 1 + X i 1 1 (i + 1) p 1 A | {z } term with 0 offset + X i 1
1 (i + 1/k) p | {z }
term with 1/k offset + . . .

+ X i 1 1 (i + (k 1)/k) p | {z } term with (k 1)/k offset . ( 82
)
The 0-offset term in (82) equals To continue with the proof, let us analyze the following information series:

P i 1 1 i p =
I k p ⌘ X i k μfp (i) log(1/μ fp (i)) = X i k f p (i) log(1/f p (i)),
where the last equality is valid eventually (for k sufficiently large). This last expression is equal to p P i k

1 i p log i.
Therefore, we can concentrate on the series:

Ĩk p ⌘ X i k 1 i p log i = log k k p 2 4 1 + X i 1 log(k + i)/ log(k) ((k + i)/k) p 3 5 = log k k p 2 4 1 + X i 1 log(k + i)/ log(k) (1 + i/k) p 3 5 . (84)
Similarly to (82), the series on the RHS of (84) can be decomposed in 2

4 1 + X i 1 log(k + ki)/ log(k) (1 + i) p 3 5 | {z } 0-term + X i 1 log(ik + 1)/ log(k) (i + 1/k) p | {z } 1/k-offset term + . . . + X i 1 log(ik + k 1)/ log(k) (i + (k 1)/k) p | {z } (k 1)/k-offset term . ( 85
)
For the 0-offset term, we have that 2

4 1 + X i 1 log(k + ki)/ log(k) (1 + i) p 3 5  1 + X i 1 ✓ 1 1 + i ◆ p + 1 log k X i 1 log(i + 1) (i + 1) p = S 1 p + 1 log k I 2 p , (86)
while for the generic l/k-term in (85), we have that X

i 1 log(ik + l)/ log(k) (i + l/k) p  X i 1 log(ik + k)/ log(k) i p = X i 1 1 i p + 1 log k X i 1 log(i + 1) i p | {z } Īp⌘ = S 1 p + 1 log(k) Īp . (87)
Returning to (84), it follows from (85) and the posterior bounds that

I k p  p log k k p 1  S 1 p + 1 log k Īp . (88)
Then,

lim sup k!1 I k p S k p log(1/S k p )  lim sup k!1 p log k k p 1 S 1 p + p k p 1 Īp 1 k p 1 S 2 p log k p 1 S 1 p (89) = pS 1 p (p 1)S 2 p < 1, (90)
which concludes the proof as p > 1.

APPENDIX II PROOF OF LEMMA 3

Proof: If we consider the information function

(i ↵ (i)) = ( f ↵ (i) log f ↵ (i)),
I k ↵ = log(1/K)S k ↵ + K↵ log e • X i k ie ↵i | {z } Īk ↵ ⌘ (91)
where

Īk ↵ = ke ↵k S 0 ↵ (1/K + 1/k • e ↵ ). Finally, we have from (91) that I k ↵ = (log(1/K)S 1 ↵ + S 1 ↵ ) • e ↵k + (S 0 ↵ /K) • ke ↵k . With this, it is simple to verify that lim sup k!1 I k ↵ S k ↵ log(1/S k ↵ ) = S 0 ↵ KS 1 ↵ • lim sup k!1 k k↵ log e + log(1/S 1 ↵ ) = 1 Ke ↵ ↵ log e < 1, (92)
which proves the result.

APPENDIX III PROOF OF LEMMA 5

Proof: Without loss of generality, let us consider the finite alphabet A = {1, .., k}, a distortion d > 0, and the collection ⇤ = P(A). Using the non-asymptotic performance bound in [START_REF] Fitingof | The compression of discrete information[END_REF], we are interested in the following object:

min ( n ,Cn,Dn) sup µ2⇤  1 n E X n ⇠µ n {L(C n ( n (X n )))} R n (d, µ n ) , (
1 n E Y n ⇠μp L(C ⇤k n,p ( ⇤k n,p (Y n )))  R n (d, μp ) + ✏, (94)
where k > ⌧ f , see (43))

H (⇡k) (μ f ) H (⇡k) (µ) = μf ( k ) log 1 μf ( k ) + X x k+1 µ(x) log µ(x) f (x) + X x k+1 (f (x) µ(x)) log 1 f (x) µ( k ) log 1 µ( k ) μf ( k ) log 1 μf ( k ) + µ( k ) log μf ( k ) µ( k ) + µ( k ) log µ( k ) + X x k+1 (f (x) µ(x)) log 1 f (x) (99) = (μ f ( k ) µ( k )) • log 1 μf ( k ) + X x k+1 (f (x) µ(x)) log 1 f (x) , = 0 @ X x k+1 µ(x) X x k+1 μf (x) 1 A • log 1 μf ( k ) + X x k+1 (f (x) µ(x)) log 1 f (x) = X x k+1 (f (x) µ(x)) • log 1 P y k+1 f (y) f (x) . (100)
To obtain (99) we use that

P x k+1 µ(x) log µ(x) f (x) µ( k ) log µ( k ) μf ( k )
from the observation that D (⇡k) (µkμ f ) 0. At this point, we use the fact that f 2 `1(X), which means that lim k!1 P x k+1 f (x) = 0. Therefore eventually (i.e., for a sufficiently large k) we have that 1 P x k+1 f (x) > P x k+1 f (x). Assuming this large k regime, it follows from (100) that

H (⇡k) (μ f ) H (⇡k) (µ) X x k+1 (f (x) µ(x)) • log P y k+1 f (y) f (x) 0. (101)
The last inequality in (101) comes from the assumption that µ 2 ⇤ f , which means that µ(x)  f (x) for all x 2 X. On the second part of the result, we assume that H(μ f ) =

1. Here, it is clear that H (⇡k) (μ f ) = 1 for any k 1, which is sufficient to obtain the unbounded result.

APPENDIX V PROOF OF LEMMA 4

Proof: First, it is important to note that by the construction of ⇤n in (40) and the partition ⌘ n in (41), ⇤n degenerates in the probability space (X n , (⌘ n )), in the sense that for any k 1

H (⌘n) (μ n jk ) = 0. (102)
Let us consider a distribution over the indices of the family ⇤n (i.e., over the integer set N) ⇢ 2 P(N), and with this we can construct a joint distribution ⇢ ⇥ ⇤n in the product space (N, 2 N ) ⇥ (X n , (⌘ n )) in the standard way, i.e., ⇢ ⇥ ⇤n (A ⇥ B) = P a2A ⇢(a) • μn ja (B) for any A ⇢ N and B 2 (⌘ n ). Associated with this joint distribution, we can derive an expression for the mutual information of ⇢ ⇥ ⇤n [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], [START_REF] Cover | Elements of Information Theory[END_REF]:

I(⇢; ⇤n ) ⌘ X a2N ⇢(a) • D (⌘n) (μ n ja kμ) (103) = H (⌘n) (μ) X a2N ⇢(a) • H (⌘n) (μ n ja ), (104)
where μ(B) ⌘ P a2N ⇢(a)μ n ja (B) for any B 2 (⌘ n ). Using (102), it is simple to show that I(⇢; ⇤n ) = H (⌘n) (μ) = H(⇢) = P a2N ⇢(a) log ⇢(a). Finally it is well known, from the construction of the information radius of ⇤n [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF], that R + ( ⇤n , (⌘ n )) I(⇢; ⇤n ) = H(⇢) for any ⇢ 2 P(N). This last inequality proves the result as sup ⇢2P(N) H(⇢) = 1.

APPENDIX VI AUXILIARY RESULTS

A. Proposition 1 PROPOSITION 1: For all x n 2 X n , it follows that ⇢ n (x n , xn )  ⇢n (y n , ŷn ).

Proof:

⇢ n (x n , xn ) = 1 n n X i=1 ⇢(x i , xi ) = 1 n n X i=1 ⇥ ⇢(x i , xi )1 k (x i ) + ⇢(x i , xi )1 c k (x i ) ⇤ = 1 n n X i=1 2 6 4⇢(yi, ŷi )1 k (x i ) + ⇢(x i , z i ) | {z } =0 as zi=xi 1 c k (x i ) 3 7 5  1 n n X i=1 ⇢(y i , ŷi )1 k (x i ) (105)  1 n n X i=1 ⇢(y i , ŷi ) (106)
= ⇢n (y n , ŷn ).

The first inequality in (105) follows from the construction of ⇢ assuming that ⇢ coincides with ⇢ in k ⇥ k and the mild assumption that ⇢(i, k + 1)  ⇢(i, k + 1) for all i 2 k .

B. The construction of ⇤ = {μ j , j 2 J }

We know that P j 1 f (j) = 1. Let us introduce the bounded envelope function f : X ! [0, 1] given by f (i) ⌘ min {1, f(i)} for any i 2 X. It is simple to verify that P j 1 f (j) = 1 and that ⇤ f ⇢ ⇤ f . Using this bounded function, we introduce an iterative method to construct a countably infinite family ⇤ = {μ j , j 2 J } ⇢ ⇤ f as follows:

• Iteration 1: Select k1 = min n k 1, st. P k l=1 f (l) 1 o 23 .
Construct a probability μ1 2 P(X) by 24 μ1 (1) = f (1) .... From the fact that P i 1 f (i) = 1, the key step in (110) is achieved in a finite value for any j 1. In conclusion, this iterative (inductive) method shows the existence of an infinite collection of models {μ j , j 2 N} ⇢ ⇤ f ⇢ ⇤ f with disjoint support.

μ1 ( k1 1) = f ( k1 1) μ1 ( k1 ) = 1 μ1 ( n 1, .., k1 1
o )  f ( k1 ), (108)

C. Proposition 2

PROPOSITION 2: Let ⇢ : X ⇥ X ! R + be an unbounded distortion function consistent with respect to the Euclidean norm (Def. 6). For any n 1 and d > 0, if ( n , C n , D n ) is a D-semifaithful code of length n operating at distortion d (Def. 1), then |B n = { n (x n ), x n 2 X n }| = 1. 24 Here, we assume that k1 > 1, otherwise, we have the trivial case μ1 (1) = 1. 25 Here, we assume that k2 > 1, otherwise, we have the trivial case μ2 ( k1 + 1) = 1.

Proof: We prove this result by contradiction. Let us assume that |B n | < 1. We can consider the partition induced by n (•), i.e., A n y n ⌘ Let us consider K > nd and its respective ✏(K) > 0 (from Def, 6) such that for any pair i, j 2 X, if |i j| ✏(K) then ⇢(i, j) K and ⇢(j, i) K. We can select ↵ 2 I (i.e., x n ↵ 2 A n ỹn ) such that x n ↵ (l ⇤ ) 2 A n,l ⇤ ỹn \ B ✏(K) (ỹ n (l ⇤ )) c (as this last set is non-empty) 26 . By definition of B ✏ (x), we have that |x n ↵ (l ⇤ ) ỹn (l ⇤ )| ✏(K), which implies that ⇢(x n ↵ (l ⇤ ), ỹn (l ⇤ )) K. This implies that ⇢ n (x n ↵ , ỹn ) ⇢(x n ↵ (l ⇤ ), ỹn (l ⇤ ))/n K/n > d (see Eq.( 1)). On the other hand, x n ↵ 2 A n ỹn and, consequently, n (x n ↵ ) = ỹn , which implies that ⇢ n (x n ↵ , n (x n ↵ )) > d. This last result contradicts the fact that ( n , C n , D n ) is operating at distortion d. Therefore, our initial assumption that |B n | < 1 is incorrect, which concludes the proof.

D. Proof of Corollary 1

Proof: It is sufficient to show that if ⇤ f ⇢ H(X) then sup µ2⇤f H(µ) < 1. We know that μf 2 ⇤ f (see Eq.( 43)) and, consequently, H(μ f ) < 1. Let us consider µ 2 ⇤ f and an arbitrary large K > 0:

H(µ) = K X i=1 µ(i) log 1 log µ(i) µ( K ) log 1 µ( K ) + H (⇡K ) (µ) (112) = µ( K ) • K X i=1 µ(i) µ( K ) log µ( K ) µ(i) + H (⇡K ) (µ) (113)
 log K + H (⇡K ) (µ)  log K + H (⇡K ) (μ f )

 log K + H(μ f ) < 1. (114)
The first equality in (112) uses ⇡k ⌘ { k , {k + 1} , {k + 2} , . . .} and the definition of H (⇡K ) (µ) in [START_REF] Shtarkov | Combinatorial methods of universal coding for discrete stationary sources[END_REF]. The inequalities in (114) follow from Lemma 26 Considering that the ball B✏(x) ⇢ X (see Def.6) is a finite set (for any x 2 X and ✏ > 0), it follows that A n,l ⇤ ỹn \ (B✏(ỹ n (l ⇤ )) c = 1 for any ✏ > 0.

7 (using a sufficiently large K) and the fact that H (⇡K ) (μ f )  H(μ f ) < 1. Finally the last expression in (114) is independent of µ (i.e., valid for any element of ⇤ f ), which concludes the proof.

E. Proposition 3

PROPOSITION 3: R n (d, µ), defined in [START_REF] Fitingof | The compression of discrete information[END_REF], is a concave function of its second argument in P(X n ).

Proof: We assume that d > 0 and n 1 are given. Let us consider a finite collection of models {µ i , i = 1, .., L} in P(X n ) and some weights (w i ) i=1,..,L 2 [0, 1] L such that P L i=1 w i = 1. We need to verify that d,µ) where µ = P L i=1 w i •µ i 2 P(X n ) denotes the convex combination of {µ i , i = 1, .., L} using (w i ) i=1,..,L . Let us consider an arbitrary partition ⇡ 2 Q n (d). Then we have that

P L i=1 w i • R n (d, µ i )  R n (
H (⇡) (µ) n L X i=1 w i • H (⇡) (µ i ) n (115) L X i=1 w i • R n (d, µ i ) (116)
The first inequality in (115) is from the concavity of the entropy [START_REF] Cover | Elements of Information Theory[END_REF]. The second inequality comes by definition (see Eq.( 12)) using the fact that ⇡ 2 Q n (d). Finally, the lower bound in (116) is valid for every ⇡ 2 Q n (d), which concludes the proof from the definition of R n (d, µ) in [START_REF] Fitingof | The compression of discrete information[END_REF].

F. Deriving the upper bound in [START_REF] Silva | Almost lossless variable-length source coding on countably infinite alphabets[END_REF] We use the standard approach to construct a prefix-free (variable length) code from a probability in P(B n ) [START_REF] Cover | Elements of Information Theory[END_REF]. For any model v 2 P(B n ), we can construct a code C v such that for any y n 2 B n it follows that L(C v (y n )) = d log(v(y n ))e. This code satisfies the Kraft-MacMillan inequality in (3) considering that log(v(y n ))  L(C v (y n )) < log(v(y n )) + 1. Using these inequalities, we have that for any v 2 P(B n ) and µ 2 ⇤ (considering that n is given and fixed in this analysis) 27 R(

⇠ n = ( n , C v , D v ), µ n ) H (⇡ n ) (µ n ) n  1 n (D(v µ n ||v) + 1). ( 117
)
As the class of prefix-free mapping from B n to {0, 1} ⇤ contains the induced collection {C v , v 2 P(B n )}, from (117) it follows that

min Cn sup µ2⇤  R(( n , C n , D n ), µ n ) H (⇡ n ) (µ n ) n  min v2P(Bn) sup µ2⇤  R(( n , C v , D v ), µ n ) H (⇡ n ) (µ n ) n  1 n • min v2P(Bn) sup µ n 2⇤ n D(v µ n kv) + 1 n . ( 118
)
Using the definition presented in Eq.( 22), the last lower bound in ( 118) is (R + (⇤ n , (⇡ n )) + 1)/n.

.μ2 2 •

 2 By its construction in (108), we have that μ1 2 ⇤ f and A 1 = support(μ 1 P(X) by 25 μ2 ( k1 + 1) = f ( k1 + 1) ....μ2 ( k1 + k2 1) = f ( k1 + k2 1) μ2 ( k1 + k2 ) = 1 μ2 ( n k1 + 1, .., k1 + k2 1 o )  f ( k1 + k2 )(109)and μ2 (n k1 + 1, .., k1 + k2 o c ) = 0. Then, we have that μ2 2 ⇤ f and A 2 = support(μ 2 ) = n k1 + 1, .., k1 + k2 o . Iteration j: (for j > 2)The construction follows from the same steps mentioned in iteration 2, where

  .. + kj 1 + 1, ..., k1 + ... + kj 1 o , .. + kj 1 + 1, ..., k1 + ... + kj 1 o ) and A j = support(μ j ) = n k1 + ... + kj 1 + 1, ..., k1 + ... + kj o .

  it is clearly summable then μf↵ 2

	H(X) (see Eq.(43)). Let us analyze the tail of μf↵ , i.e., S k ↵ ⌘ P i k μf↵ (i) for any k 1. We have that S k ↵ = e ↵k P i 1 Ke ↵i = e ↵k ↵ . On the other hand, we • S 1 need to analyze the tail fraction of the entropy of μf↵ , i.e., I k P i k μf↵ (i) log μf↵ (i) = P i k f (i) log f (i), the ↵ ⌘ last equality holding eventually (for k sufficiently large). It is
	simple to show that

  93)where the minimum is carried over the collection of Dsemifaithful codes on A operating at distortion d.Let us fix an arbitrary ✏ > 0. For any x n 2 A n , let p x n denote the type of x n (the empirical distribution in P(A) induced by x n ), and Pn ⌘ {p x n , x n 2 A n } the collection of types obtained with sequences of length n. For any p 2 Pn , the type class of p is given by T p ⌘ {x n 2 A n : p x n = p}, where it is clear that

	n is well known that Pn  (n + 1) o T p , p 2 Pn offers a finite partition of A n . It k [3]. For any member in the type class p 2 Pn , let us choose a D-semifaithful code ⇠ ⇤k n,p = ( ⇤k n,p , C ⇤k n,p , D ⇤k n,p ) indexed by p satisfying the condition: 21

1 n

 1 ({y n }) for any y n 2 B n , where ⇡ n = A n y n , y n 2 B n is a finite partition of X n . At least one of the cells of ⇡ n should have an infinite number of elements. Let us denote this infinite cell by A n ỹn with ỹn 2 B n . If we index the elements of this cell, i.e., A n ỹn = {x n ↵ , ↵ 2 I} where I is a countably infinite set, we can create n (one dimensional) projections of A n ỹn by X denotes the i-component of the vector x n ↵ 2 A n ỹn . As we have that A n ỹn = 1, this implies that at least one of the 1D coordinate projections in (111) has infinite cardinality. Let us assume that A n,l ⇤ ỹn = 1 for some l ⇤ 2 {1, .., n} from this point on.

	A n,1 ỹn ⌘ {x n ↵ (1), ↵ 2 I} A n,2 ỹn ⌘ {x n ↵ (2), ↵ 2 I} ...
	A n,n ỹn ⌘ {x n ↵ (n), ↵ 2 I} ⇢ X	(111)
	where x n ↵ (i) 2

A nice presentation of the early history of universal coding can be found in[5, Section II] and reference therein.

Up to a discrepancy of at most 1/n in bits per sample: Rn(d, µn)  Rn(d, µn)  Rn(d, µn) + 1 n .

For completeness, the argument to derive[START_REF] Silva | Almost lossless variable-length source coding on countably infinite alphabets[END_REF] is presented in Appendix VI-F.

An extended version of this result is stated in Proposition 2. Its proof is presented in Appendix VI-C.

This condition implies that f 2 `1(X).

See also[START_REF]Universal weak variable-length source coding on countably infinite alphabets[END_REF] Th.2] for a discussion of these results.

Indeed, they show the stronger result that L(fn(X n )) = 1 almost surely, with X n ⇠ µ n .

Almost surely with respect to the empirical process distribution.

Alternatively, this result can be derived from (42) (Lemma 4) and Lemma 1.

Using the correspondence between prefix-free codes and perfect (dyadic) distributions.

This condition is equivalent to the condition ⇤ f ⇢ H(X) used in statement of Theorem 2 -part iii). See Corollary 1.

The concavity of Rn(d, µ) is stated and proved in Proposition 3 at Appendix VI-E.

This problem has a (finite) solution form the fact that P j 1 f (j) = 1.

Dv denotes the decoder of Cv.

)) 2 {0, 1} ⇤ first-stage bits second-stage bits 1) Analysis of the first-stage bits in (55): For the first term on the RHS of (55), it will be useful to consider the following truncated distortion ⇢ k on X ⇥ X, (8x, x 2 X)

to specify ⇢ in k+1 ⇥ k+1 , used in the first-stage of the construction. It follows that

for any x n and xn in X n . For the rest of the argument, we fix ⇢n (y n , ȳn ) to be ⇢ k n (y n , ȳn ) for any y n , ȳn

where

Then from the definition in (12), we have that

for any d > 0, any n 1, any k 1 and any µ 2 P(X).

On the other hand, if we consider the distribution of Y n = S k (X n ) 2 k+1 (assuming that X n ⇠ µ n for some marginal µ 2 P(X)) and in particular its marginal distribution v µ in P( k+1 ), we can use the operational finite-length rate-

for any d > 0, any n 1, any k 1 and any µ 2 P(X).

Finally, for any D-semifaithful code

. ⇢n , we have from (59), [START_REF] Babkin | Method of universal coding for an independent message source with non-exponential computational complexity[END_REF] and ( 12) that

At this point, we can use the result in Lemma 5 for finite alphabet sources. In particular, from Lemma 5 (choosing ✏ = 1/n) and the expressions in (60) and (59), we have that for any n 1, k 1 and distortion d > 0, there is a D-semifaithful code ⇠ ⇤k n for the first-stage such that

2) Analysis of the second-stage bits in (55): Considering the second term on the RHS of (55), let m µ 2 P({1}

where μp 2 P(A n ) in ( 94) is a short-hand for the uniform distribution over

With this, we consider a simple two-stage universal strategy, inspired by the two-stage scheme used in lossless universal source coding [START_REF] Csiszar | Information Theory and Statistics: A Tutorial[END_REF]. For encoding x n there is fixed-rate function f n : Pn ! {0, 1} kdlog(n+1)e for indexing (encoding) the type of x n , and conditioning on this information, the secondstage encodes x n lossily with ⇠ ⇤k n,p x n . Then the variable length representation of x n operating at distortion d is given by

From this construction, it is simple to check that this scheme is a D-semifaithful code of A n with respect to ⇢ n .

Let us analyze its worst-case overhead in ⇤. Let us consider µ 2 ⇤, then if we denote by T k n = (f n , (⇠ ⇤k n,p ; p 2 Pn )) the two-stage scheme and (with small abuse of notation) we use T k n as a short-hand for the encoding mapping (from source symbols to binary sequences) then

8x n 2 A n . At this point, if we introduce Y ⌘ p X n 2 Pn (the type of X n ⇠ µ n ), it follows that for any p 2 Pn , P(Y = 21 This selection can be accomplished from [START_REF] Fitingof | The compression of discrete information[END_REF].

p) = µ n (T p ) and

The expression in (96) follows from (95) and the observation that conditioning to the event Y = p, for some p 2 Pn , X n ⇠ μp independent of µ [START_REF] Cover | Elements of Information Theory[END_REF]. To obtain (97), we include the term P p2 Pn µ n (T p )R n (d, μp ) in (96) to then use the inequality in (94). Finally to obtain (98), we use the fact that µ n (B) = P p2 Pn µ n (T p )μ p (B) [START_REF] Cover | Elements of Information Theory[END_REF] and that R n (d, µ) is a concave function of the second argument from its construction in [START_REF] Fitingof | The compression of discrete information[END_REF]. 22 Finally, the inequality in (98) is valid distribution free (independent of µ), which concludes the proof.

APPENDIX IV PROOF OF LEMMA 7

Proof: Let us assume that H(μ f ) < 1, where μf 2 ⇤ f is the tail distribution introduced in (43). Let us consider an arbitrary µ 2 ⇤ f . Then we have that (assuming the regime