Universal Weak Variable-Length Source Coding on Countable Infinite Alphabets
Jorge F. Silva Pablo Piantanida





Universal Weak Variable-Length Source Coding
 on  Countably Infinite Alphabets
    Jorge F. Silva and Pablo Piantanida

This article has been accepted for publication by IEEE. Digital Object Identifier 10.1109/TIT.2019.2941895. Link: https://ieeexplore.ieee.org/document/8840879.
(c) 2019 IEEE. Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
J. F. Silva was supported in part by CONICYTChile, Fondecyt, under Grant 1170854 and in part by the Advanced Center for Electrical and Electronic Engineering, Basal Project, under Grant FB0008. 

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 792464.
This work was presented in part at the 2016 and 2017 IEEE International Symposium on Information Theory (ISIT) [1], [2].

J. F. Silva is with the Information and Decision Systems (IDS) Group, University of Chile, Santiago 412-3, Chile (e-mail: josilva@ing.uchile.cl).
P. Piantanida is with the Laboratoire des Signaux et Systèmes (L2S).
P. Piantanida is with the Laboratoire des Signaux et Systèmes (L2S), CentraleSupélec-CNRS-Université Paris-Sud, 91190 Gif-sur-Yvette, France, and also with the Montreal Institute for Learning Algorithms (Mila), Université de Montréal, Montréal, QC H3T 1J4, Canada (e-mail: pablo.piantanida@centralesupelec.fr).

    December 30, 2023
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






Motivated from the fact that universal source coding on countably infinite alphabets (∞-alphabets) is not feasible, this work introduces the  notion of “almost lossless source coding”. Analog to the weak variable-length source coding problem studied by Han (IEEE TIT, 2000, 46, 1217-1226), 
almost lossless source coding aims at relaxing the lossless block-wise assumption to allow an average per-letter distortion that vanishes asymptotically as the block-length tends to infinity. In this setup,  we show on one hand  that Shannon entropy characterizes the minimum achievable rate (similarly to the case of finite alphabet sources) while on the other that almost lossless universal source coding becomes feasible for the family of finite-entropy stationary memoryless sources with ∞-alphabets.  
Furthermore, we study a stronger notion of almost lossless universality that demands uniform convergence of the  average per-letter distortion to zero, where we establish a necessary and sufficient condition for the so-called family of “envelope distributions” to achieve it. Remarkably, this condition is the same necessary and sufficient condition needed for the existence of a strongly minimax (lossless) universal source code for the family of envelope distributions. Finally,  we show that an almost lossless coding scheme offers faster rate of convergence for the (minimax) redundancy compared to the well-known information radius developed for the lossless case at the expense of tolerating a non-zero distortion that vanishes to zero as the block-length grows. This shows that even when lossless universality is feasible, an almost lossless scheme can offer different regimes on the rates of convergence of the (worst case) redundancy versus the (worst case) distortion.



Universal source coding,  countably infinite alphabets (∞-alphabets), weak source coding, envelope distributions, information radius (i-radius), metric entropy analysis. 








§ INTRODUCTION


The problem of Universal Source Coding (USC) has a long history on information theory <cit.>. This topic started with the seminal work of Davisson <cit.> that formalizes the variable-length lossless coding and introduces relevant information quantities (mutual information and channel capacity <cit.>).  In lossless variable-length source coding,  it is well-known  that if we know the statistics of a source (memoryless or stationary and ergodic) the Shannon entropy (or Shannon entropy rate) provides the minimum achievable rate <cit.>. However, when the statistics of the source is not known  but it belongs to family of distributions Λ, then the problem reduces to characterize the worst-case expected overhead  (or worse-case redundancy) that a pair of encoder and decoder experiences due to the lack of knowledge about true distribution governing the source samples to be encoded <cit.>.

A seminal information-theoretic result states that the least worst-case overhead (or minimax redundancy of Λ) is fully characterized by the information radius of Λ <cit.>.  The information radius (i-radius) has been richly studied by the community and there are 
numerous contributions <cit.>, including applications to universal prediction of individual sequences <cit.>. In particular,  it is well-known  that the  i-radius growths sub-linearly for the family of finite alphabet stationary and memoryless sources <cit.>, which implies the existence of an universal source code that achieves Shannon entropy for every distribution in  this family provided that the block length tends to infinity.

What is intriguing in this positive result obtained for finite alphabet memoryless sources is that it does not longer extend to the case of stationary and memoryless sources on countably infinite alphabets (∞-alphabets), as was clearly shown in <cit.>. From an information complexity perspective,  this infeasibility result implies that the i-radius of this family is unbounded for any finite block-length and, consequently,   lossless universal source coding for ∞-alphabet stationary and memoryless sources is an intractable problem.


In this regard, the proof presented by Györfi et al. <cit.> is constructed over a connection between variable-length prefix-free codes and  distribution estimators, and the fact that  the redundancy of a given code upper bounds the expected divergence  between the true distribution and the induced  (through the code) estimate of the distribution. Then, the existence of an universal source code implies the existence of an universal estimator in the sense  of expected information divergence <cit.>.[Distribution estimator  consistent  in information divergence and reversed order information divergence were introduced by Barron et al. in <cit.>. The connection between distribution estimation consistent in expected information divergence and universal source coding can be found in <cit.> and <cit.>.] The impossibility of achieving this learning objective for the family of finite entropy memoryless sources <cit.> 
motives the main question addressed in this work that is, the study of a “weak notion” of universal variable-length source coding. 

In this framework, we propose to address the problem of universal source coding for ∞-alphabet stationary and memoryless sources by studying a weaker (lossy) notion of coding instead of the classical lossless definition <cit.>. This  
notion borrows ideas from the seminal work by Han <cit.> that allows reconstruction errors but assuming known statistic. In this paper, we investigate the idea of relaxing the lossless block-wise assumption with the goal that the corresponding weak universal source coding formulation will be reduced to a learning criterion that becomes feasible for the  whole family finite entropy stationary and memoryless sources on countably infinite alphabets. 
In particular,  we move from lossless coding to an  asymptotic vanishing distortion fidelity criterion based on the Hamming distance  as a fidelity metric. 




 §.§ Contributions


Assuming that the distribution of the source is known, we first introduce the problem of “almost lossless source coding” for memoryless sources defined on countably infinite alphabets. Theorem <ref> shows that Shannon entropy  characterizes the minimum achievable rate for this problem. The proof of this theorem adopts a result from Ho et al. <cit.> that provides a closed-form expression for the rate-distortion function R_μ(d) on ∞-alphabets. From this characterization, we show that lim_d → 0 R_μ(d)=ℋ(μ) which is essential to prove this result[This result is well-known for finite alphabets, however the extension on countably infinite alphabets is not straightforward due to the  discontinuity of the entropy <cit.>.].  


Then, we address the problem of almost lossless universal source coding. The main difficulty arises in finding a lossy coding scheme that achieves asymptotically zero distortion, i.e.,  point-wise over the family, while guaranteeing that the worst-case average redundancy –w.r.t. the minimum achievable rate– vanishes with the block-length <cit.>. The proof of existence of an universal code with the desired property relies on a two-stage coding scheme that first quantizes (symbol-by-symbol) the ∞-alphabet and then applies a lossless variable-length code over the resulting quantized symbols. Our main result, stated in Theorem <ref>, shows that almost lossless universal source coding is feasible for the family of finite entropy stationary and memoryless sources.

We further  study the possibility of obtaining rates of convergence for the worst-case distortion and the worst-case redundancy. To this end, we restrict our analysis to the family of stationary and memoryless sources with 1D-densities dominated by an envelope function f, which was previously studied in <cit.>. Theorem <ref> presents a necessary and sufficient condition on f to achieve an uniform convergence (over the family) of the distortion to zero and, simultaneously, a vanishing worst-case average redundancy. Remarkably, this condition (f being a summable function) is the same necessary and sufficient condition needed for the existence of a strongly minimax (lossless) universal source code <cit.>. 

Finally, we provide an analysis of the potential benefit of an almost lossless two-stage coding scheme by exploring the family of  envelope distributions that admits strong minimax universality in lossless source coding <cit.>.  In this  context,  Theorem <ref> shows that we can have an almost lossless approach that offers a non-trivial reduction to the rate of convergence of the worst-case redundancy, with respect to the well-known i-radius developed for the lossless case,  at the expense of tolerating a non-zero distortion that vanishes with the blocklength. This result provides evidence that even in the case where lossless universality is feasible, an almost lossless scheme can reduce the rate of the worst-case redundancy and consequently, it offers ways of achieving different regimes for the rate of convergence of the redundancy versus the distortion. The proof of this result uses advanced tools by Haussler and Opper  <cit.> to relate the minimax redundancy of a family of distributions with its metric entropy with respect to the Hellinger distance. Indeed, this metric entropy approach has shown to be instrumental to derive tight bounds on the i-radius for summable envelope distributions in <cit.>. We extended this metric entropy approach to our almost lossless coding setting with a two-stage coding scheme to characterize the precise regime in which we can achieve gains in the rate of convergence of the redundancy.



 §.§ Organization of the Paper

The rest of the paper is organized as follows. Section <ref> introduces  some definitions and preliminary results. 
Section <ref> introduces our main weak source coding problem and shows that Shannon entropy is the minimum achievable rate  
provided that the statistics of the source is known. Section <ref> presents the problem of almost lossless universal source coding and proves its feasibility for the family of finite entropy memoryless distributions on ∞-alphabets. Section <ref> elaborates a result for a stronger notion of almost lossless universality, and Section <ref> studies the gains in the rate of convergence of the minimax-redundancy that can be obtained with an almost lossless scheme  for families of distributions that admit lossless USC.  Finally, Section <ref>  concludes with a summary of the work. 
The proofs of the main results of this paper are presented in Section <ref>, while some supporting results are relegated to the Appendix section.



 §.§ Basic Notation

The following notations and conventions are used throughout this article: 
 (x_n)_n will denote an infinite dimensional sequence in ℝ^ℕ; 
 (x_n)_n ≪ (y_n)_n or,  alternatively,  (x_n)_n being o(y_n),  means that  lim_n →∞x_n/y_n=0;
 (x_n)_n being o(1) means that  lim_n →∞x_n=0;
  (x_n)_n ≤ (y_n)_n  means that  x_n≤ y_n for all n≥ 1; 
  (x_n)_n ≤ (y_n)_n eventually in n means that there exists N>1 such that  x_n≤ y_n for all n≥ N; 
  (x_n)_n ∼ (y_n)_n means that lim_n →∞x_n/y_n=1; 
  𝒳 will denote the countably infinite alphabet and 𝒫(𝒳) the collection of
  probability measures in   𝒳;
  for any function f:𝒳⟶ℝ, f is said to be summable (denoted by f∈ℓ_1(𝒳)) if ∑_n∈𝒳| f(x)| < ∞; 
 and for μ, v∈𝒫(𝒳),  μ≪ v means that 
 if v(B)=0 then μ(B)=0 for any B⊂𝒳.





§ PRELIMINARIES
 


This section introduces some useful concepts, definitions and results that will be needed across the paper. Let X= {X_i }_i=1^∞ be a stationary and memoryless process (or i.i.d. source) with values in a countably infinite alphabet (∞-alphabets) 𝒳 equipped with a probability measure μ defined on the measurable space (𝒳, ℬ(X))[ℬ(𝒳) denotes the power set of 𝒳.].  Let X^n=(X_1,…,X_n) denote a finite block of length n of the process following the product  measure μ^n on (𝒳^n, ℬ(X^n))[The product measure satisfies the memoryless condition for all ℬ_1×⋯×ℬ_n ∈𝒳^n then μ^n(ℬ_1×⋯×ℬ_n)=μ( ℬ_1)⋯μ( ℬ_n).].  
Let us denote by 𝒫(𝒳) the family of probability measures in (𝒳, ℬ(X)), where for every μ∈𝒫(𝒳), we understand f_μ(x) d μ/dλ(x) = μ(  { x}) to be a short-hand for its probability mass function (pmf). Let supp(f)= {x ∈𝒳: | f(x)|>0} and let 𝒫_ℋ(𝒳){μ: H(μ)<∞}⊂𝒫(𝒳) denote the collection of finite Shannon entropy probabilities <cit.> where


    H(μ) = -∑_x∈𝒳 f_μ(x) log f_μ(x),

with log function on base 2.  


Given an i.i.d. source X= {X_i }_i=1^∞  with distribution μ∈𝒫(𝒳),  let us consider a (variable length) lossless code  f_n  of length n as a prefix-free mapping from 𝒳^n to finite sequences of symbols in {0, 1 } <cit.>.
It is well-known that 𝔼_X^n{ℒ (f_n(X^n)) }≥ H(μ^n) <cit.>, where ℒ(·) indicates the functional that returns the length of binary sequences in {0,1}^⋆∪_k ≥ 1{0, 1 }^k.
Then, the average length (in bits) used to encode X^n with f_n  can be measured relative to H(μ^n),  which motivates the introduction of the 
average redundancy (or redundancy) of f_n by the expression: 𝔼_X^n{ℒ (f_n(X^n)) } - H(μ^n). When μ is known,  
the Huffman code uses that information to offer an optimal prefix-free mapping (minimizing the average code-length)  
whose redundancy is upper bound by 1 <cit.>.





 §.§ Strong Minimax Universality, Information Radius and Envelope Families


In universal source coding (USC), we need to encode a stationary memoryless source X with an unknown probability μ that belongs to 
a class of models Λ⊂𝒫(𝒳).  In this context,  a natural performance for a prefix-free encoder f_n:𝒳^n →{0,1}^⋆ is the worse-case  (over the family Λ) redundancy expressed by:  


    R(f_n, μ^n) sup_μ^n ∈Λ^n(  𝔼_X^n∼μ^n {ℒ (f_n(X^n)) } - H(μ^n) ),
  
where Λ^n {μ^n, μ∈Λ}⊂𝒫(𝒳^n) is a short-hand for the family of n-fold (product) distributions
induced by Λ. 
This worse-case performance indicator motivates the adoption of the minimax design principle:  
 min_f_n R(f_n, μ^n) frequently used in USC <cit.>, where the optimization is carried over the family of prefix-free codes. 

Importantly, there is a 
well-documented correspondence between prefix-free codes for 𝒳^n and probabilities in 𝒫(𝒳^n) <cit.>.
In fact, the Kraft-MacMillan inequality defines a probability in  𝒫(𝒳^n) from a prefix-free code of length n <cit.>,
and conversely arithmetic coding provides a prefix-free code for  𝒳^n from a probability v∈𝒫(𝒳^n),
where the length of this code  (in bits) is ⌈ -log v(x^n)  ⌉  + 1 for any x^n∈𝒳^n <cit.>. Then  
the minimax redundancy problem for USC reduces to the solution of the i-radius problem <cit.>[In fact, it follows that R^+(Λ^n) +2 ≥min_f_n R(f_n, μ^n) ≥ R^+(Λ^n) <cit.>.]:


    R^+(Λ^n) inf_v ∈𝒫(𝒳^n)sup_μ^n ∈Λ^n𝒟(μ^n | v)

and 


    𝒟(μ^n | v) = ∑_x^n∈𝒳^n f_μ^n(x^n) logf_μ^n(x^n) /f_v(x^n)

is the divergence of μ^n with respect to v <cit.>. 
Again using this connection between codes and distributions, a class Λ⊂𝒫(𝒳)
of i.i.d. sources will be said to be weakly universal if there is a sequence of probabilities (v_n)_n (where v_n∈𝒫(X^n) for all n)
such that sup_μ∈Λlim_n →∞1/n𝒟(μ^n | v_n)=0, and  it will be strongly
universal (or strongly minimax universal) if  lim_n →∞sup_μ∈Λ1/n𝒟(μ^n | v_n)=0.
For the last stringent USC objective,  the minimax redundancy sequence (R^+(Λ^n))_n of Λ in (<ref>) 
determines if the family is strongly minimax universal <cit.>. For ∞-alphabets i.i.d. sources, it is known that R^+(𝒫(X)^n)=∞ and, furthermore,  weak minimax universality is not feasible <cit.>. This motivates the study of strong minimax universality over  sub-collections  of distributions whose 1D densities are dominated by an envelope function <cit.>: 


	Given a non-negative function f:𝒳⟶ℝ^+, the envelope family indexed by f is given by:
	
	
    Λ_f{μ∈𝒫(𝒳): f_μ(x)≤ f(x),  for  x∈𝒳}.


The next result by Boucheron et al. <cit.> establishes a necessary and sufficient condition to 
make Λ_f strongly minimax universal:


 
	<cit.>
	Let us consider f: 𝒳→ℝ^+, with 𝒳 an ∞-alphabet, and the family of i.i.d. envelope distributions {Λ^n_f, n≥ 1 }. It follows that: 
	
	
  i) If f is summable, i.e., f∈ℓ_1(𝒳),  then R^+(Λ_f^n)<∞ for all n ≥ 1, and furthermore (R^+(Λ_f^n))_n is o(n). 
	
  ii) Otherwise, R^+(Λ_f^n)=∞ for all n≥ 1.
	
 
Therefore for any envelope family in an ∞-alphabet,  either it is strongly minimax universal (i.e.,(R^+(Λ_f^n))_n is o(n)) 
or its  i-radius in (<ref>) is unbounded for any finite block-length. The last unbounded scenario means that for any n  and any prefix-free code f_n there is a distribution μ in the family 
where the average redundancy of f_n (with respect to the entropy H(μ^n)) is unbounded. Furthermore for a summable envelope function f, 
a series of relevant results stipulate the way (R^+(Λ_f^n)/n)_n tends to zero function of specific tail attributes of f <cit.>. We select a result here that will be important for our exposition, for  which some definitions are needed:

  (Bontemps et al.<cit.>) 

For a non-negative envelope function f∈ℓ_1(𝒳) with  |supp(f)|=∞,  we can determine 


    l_fmax{k: ∑_j≥ k f(j) ≥ 1}
 
and the associated envelope probability μ_f ∈Λ_f by: 


    μ_f( { k}) {[                 0,                for              k<l_f;              f(k),                for              k>l_f; 1- ∑_j > l_f f(j),                for             k=l_f. ].
 


(Bontemps et al.<cit.>) 

If we denote by F_f(u) μ_f( {1,…, u}) the envelope distribution and by  F̅_f(u)  1- F_f(u)  the tail function of f (for all u≥ 1), we can define the quantile of order 1/n of μ_f as the solutions of <cit.>:


    u^*_f(n) min{ u≥ 1:  F̅_f(u) <1/n} for all  n ≥ 1.



  <cit.>&<cit.>
	Let us consider the envelope family  {Λ^n_f, n ≥ 1 } in Def. <ref>  with f∈ℓ_1(𝒳). 
	Then there is a sequence (ξ_n)_n being o(1) such that
	
	
    (1+ ξ_n)  (u^*_f(n)-1) /4log n    ≤ R^+(Λ_f^n) 
       ≤ 2+ log e + (u^*_f(n)-1)/2log n

	holds eventually with n. 
 
It has been shown that when f∈ℓ_1(𝒳) then (u^*_f(n) log n)_n is o(n) <cit.>, therefore Theorem <ref>  
is consistent with Theorem <ref>. Importantly, (u^*_f(n))_n captures the complexity of the envelope family by 

determining the worse-case redundancy (and its velocity of convergence to zero with n) that an optimal universal code can achieve 
in compressing (losslessly) a stationary and memoryless source in this family.
 





§ ALMOST LOSSLESS SOURCE CODING


We now introduce the notion of a lossy variable-length coding of n source symbols, which consists of a pair  (f_n, g_n) where f_n: 𝒳^n ⟶{0,1}^⋆ is a prefix free variable-length code (encoder) <cit.> and g_n: {0,1}^⋆⟶𝒳^n is the inverse mapping from bits to source symbols (decoder). Inspired by the weak coding setting introduced by Han <cit.>, the possibility that {x^n: g_n(f_n(x^n))≠ x^n }≠∅ is allowed. In order to quantify the loss induced by this encoding process, a per letter distortion measure characterization ρ:𝒳×𝒳: ⟶ℝ^+ is considered <cit.>, where  for x^n,y^n∈𝒳^n the distortion is given by


    ρ_n(x^n, y^n)1/n∑_i=1^n ρ(x_i,y_i).


Given an information source 𝐗={X_i }_i=1^n, the average 
distortion induced  by the pair (f_n, g_n) is


    d(f_n, g_n,μ^n) 𝔼_X^n∼μ^n{ρ_n(X^n, g_n(f_n(X^n))) }.

For the rest of the paper, we will focus on the special case where ρ(x,y)=1_{ x≠ y }. 
Then, ρ_n(x^n, y^n) is the normalized Hamming distance between the sequences (x^n, y^n). 

On the other hand, the rate of the pair (f_n,g_n) (in bits per sample) is


    r(f_n, μ^n) 1/n𝔼_X^n∼μ^n{ℒ(f_n(X^n)) }.


At this stage,  we can 
introduce the almost-lossless source coding problem and with this,  the standard notion of minimum achievable rate. 



	Given an information source  𝐗= {X_i }_i=1^∞, we say that a rate R>0 is achievable
	for almost-losslessly encoding 𝐗, i.e., with zero asymptotic distortion, if there exists a sequence of encoder and decoder mappings { (f_n, g_n)}_n≥ 1 satisfying: 
	
	rCl
		lim sup_n ⟶∞ r(f_n, μ^n)    ≤    R, 
 
		lim_n ⟶∞ d(f_n, g_n,μ^n)    =   0.
	
	The minimum achievable rate is then defined as: 
	
	
    R_al(𝐗)min{ R: R   is achievable for 𝐗}.




Let R_al(μ)  denotes the minimum achievable rate of a stationary and memoryless source driven by μ∈𝒫(𝒳). The next theorem characterizes R_al(μ) provided that the source statistics is known. 




 
Given a stationary and memoryless source on a ∞-alphabet 
driven by the probability measure μ∈𝒫_ℋ(𝒳), it follows that R_al(μ)=H(μ).	


The proof is presented in Section <ref>. 



As it is expected, Shannon entropy characterizes the minimum achievable rate for the almost lossless source coding problem formulated in Definition <ref>. In the proof of  Theorem <ref>, we adopt a result from Ho et al. <cit.> that provides a closed-form expression for the rate-distortion function R_μ(d) of μ on ∞-alphabet 
through a tight upper bound on the conditional entropy for a given minimal error probability <cit.>. 
From this characterization, we show that lim_d → 0 R_μ(d)=H(μ), which is essential to show the  
result[Theorem <ref> is well-known for finite alphabet stationary memoryless sources, however its extension to countably infinite alphabets is not straightforward  due to the discontinuity of the entropy. The interested reader may be refer to <cit.> for further details.].  




 §.§ A Two-Stage Source Coding Scheme
 
In this section, we consider a two-stage source coding scheme that first applies a lossy  (symbol-wise)  reduction of the alphabet, and second a variable-length lossless source code over the restricted alphabet.
Let us define the finite set Γ_k {1,…,k}.   We say that a two-stage lossy code of block-length n  and size k is the composition of:  a lossy mapping of the alphabet, represented by a pair of functions  (ϕ_n, ψ_n), where ϕ_n:𝒳⟶Γ_k and ψ_n: Γ_k ⟶𝒳, and a fixed to variable-length prefix-free pair of lossless encoder-decoder (𝒞_n, 𝒟_n), where 𝒞_n:Γ_k^n ⟶{0,1}^⋆ and 𝒟_n: {0,1}^⋆⟶Γ_k^n.
 
Given a source 𝐗= {X_i }_i=1^∞ and an (n,k_n)-lossy source encode (ϕ_n, ψ_n,𝒞_n, 𝒟_n)[For brevity, the decoding function 𝒟_n: {0,1}^⋆⟶Γ_k^n will be omitted and considered implicit in the rest of the exposition.], the lossy encoding of 𝐗 induced by (ϕ_n, ψ_n,𝒞_n) is a two-stage process where first a quantization of size k_n over 𝒳^n is made (letter-by-letter) to generate a finite alphabet random sequence Y^n  (ϕ_n(X_1),…, ϕ_n(X_n)) and then, a variable-length coding is applied to produce 𝒞_n(Y^n).  Associated to the pair (ϕ_n, ψ_n), there is an induced partition of 𝒳 given by: 

    π_n{𝒜_n,iϕ_n^-1({ i}) |   i ∈Γ_k_n}⊂ℬ(𝒳),

and a collection of prototypes[Without loss of generality, we assume that y_n,i∈𝒜_n,i.] {y_n,iψ_n(i)∈𝒜_n,i |   i ∈Γ_k_n}⊂𝒳. 

The resulting distortion incurred by this code is given by


    d(ϕ_n, ψ_n,μ^n) 𝔼_X^n∼μ^n{ρ_n(X^n, Ψ_n(Φ_n(X^n))) },

where X̂^n = Ψ_n(Φ_n(X^n)) is a short-hand to denote (ψ_n(ϕ_n(X_1)),…, ψ_n(ϕ_n(X_n))).


On the other hand, the coding rate is:


    r(ϕ_n, 𝒞_n, μ^n) 1/n𝔼_X^n∼μ^n{ℒ(𝒞_n(Φ_n(X^n))) },

with Φ_n(X^n) denoting (ϕ_n(X_1),…,ϕ_n(X_n)). An illustration of this two-stage process is presented 
in Figure <ref>.







At this point, it is worth mentioning some basic properties on the partitions induced by (ϕ_n, ψ_n,𝒞_n) on 𝒳.


	A sequence of partitions {π_n}_ n ≥ 1 of 𝒳 is said to 
	be asymptotically sufficient with respect to μ∈𝒫(𝒳), if for all x∈supp(μ)
	
	
    lim_n →∞π_n(x)=   { x},  μ-almost everywhere,

	where π_n(x)⊂𝒳 denotes the cell in π that contains x and
	the almost-sure limit with respect to μ stated in (<ref>) 
	refers to the condition: 
	
	
    μ(lim sup_n →∞π_n(x) ∖{ x})=0,
 
	which is equivalent to lim_n  →∞μ(⋃_k≥ nπ_k(x) ∖{ x})=0.


Consider now almost lossless coding for which we can state the following.


	Let 𝐗 be a stationary and memoryless source  driven by μ. A necessary and sufficient condition 
	for { (ϕ_n, ψ_n,𝒞_n): n≥ 1}  to have that 
	
	
		lim_n →∞ d(ϕ_n, ψ_n,μ^n) =0
	
	is that {π_n }_n≥ 1 in (<ref>) is asymptotically sufficient for μ.



The proof of Lemma <ref> is presented in Appendix <ref>.


Studying the minimum achievable rate for zero-distortion coding requires the following definition.



	For μ∈𝒫_ℋ(𝒳) and a partition π of  
	𝒳, the entropy of μ restricted to the sigma-field induced by  π, 
	which is denoted by σ(π), is given by  
	
	
    H_σ(π)(μ)     - ∑_𝒜∈πμ(𝒜) logμ(𝒜).


A basic  inequality <cit.> shows that if σ(π) ⊂σ(π̅), then H_σ(π)(μ) ≤ H_σ(π̅)(μ) for every μ. In particular, H_σ(π)(μ) ≤ H(μ), where it is simple to show that H(μ)=sup_π∈Π(𝒳) H_σ(π)(μ)  with Π(𝒳) representing the collection of finite partitions of 𝒳. 
Furthermore, it is possible to state the following result.


	If a sequence of partitions {π_n}_n ≥ 1 of 𝒳 is asymptotically 
	sufficient with respect to μ (Def. <ref>), then 
	
	
    lim_n ⟶∞ H_σ(π_n)(μ)=H(μ).




The proof of this result is presented in Appendix <ref>.


This implies that if a two-stage scheme { (ϕ_n, ψ_n,𝒞_n): n≥ 1} achieves zero distortion, then   

    {π_n={ϕ_n^-1({ i}): i ∈Γ_k }: n≥ 1 }

is asymptotically sufficient for μ (cf. Lemma <ref>). From the well-known result in lossless variable-length source coding <cit.>, we have that:

	rCl
		r(ϕ_n, 𝒞_n, μ^n)    ≥   1/n H(Φ_n(X^n)) 

		   =    H_σ(π_n)(μ)

and consequently, Lemma <ref> implies that


		lim inf_n →∞ r(ϕ_n, 𝒞_n, μ^n) ≥ H(μ).



Hence, letting R̅_al(μ) to be the minimum achievable rate w.r.t. the family of two-stage lossy schemes in  Definition <ref>, we obtain that  R̅_al(μ) ≥  R_al(μ) =H(μ). 


The next result shows that there is no additional  overhead  (in terms of bits per sample),  if we restrict the problem to the family of two-stage lossy schemes.

 
For a stationary and memoryless source 𝐗={X_i }_ i=1^∞ driven by μ∈𝒫_ℋ(𝒳), 
	
	
    R̅_al(μ)=R_al(μ) =H(μ).




The proof is presented in Appendix <ref>.







§ UNIVERSAL  ALMOST LOSSLESS SOURCE CODING



Consider a stationary and memoryless source {X_n}_n=1^∞  on a ∞-alphabet  
with unknown distribution but belonging to a family Λ⊂𝒫(𝒳).
The main question to address here is if there exists a lossy coding scheme whose rate achieves the minimum feasible rate in Theorem <ref>,  for every possible distribution in   
Λ, while the  distortion goes to zero as the block-length tends to infinity as defined below.


	
	A family of distribution Λ is said to admit an almost lossless USC
	scheme, if there is a lossy source code { (f_n, g_n)}_n≥ 1 simultaneously satisfying:
	
	
    sup_μ∈Λlim_n →∞ d(f_n, g_n,μ^n) =0,

and

    lim_n →∞sup_μ∈Λ(r(f_n, μ^n) -H(μ))=0.


An almost lossless universal code provides a point-wise convergence of the distortion to zero for every μ∈Λ while constraining the worst-case expected redundancy to vanish as the block length tends to infinity. It is obvious from Definition <ref> that if Λ  admits a classical lossless universal source code <cit.>, i.e., the worst-case average redundancy vanishes with zero distortion for every finite n, then it admits an almost lossless USC. 
The next result shows that there is a richer family of distributions that admits an almost lossless USC scheme:

 
	The family 𝒫_ℋ(𝒳) admits an almost lossless USC scheme.


The proof  is presented in Section <ref>.




Remarkably,  Theorem <ref> shows that a weak notion of universality allows to code the complete collection of finite entropy stationary memoryless sources defined on ∞-alphabets. 
Since the same result for lossless source coding is not possible <cit.>, an interpretation of Theorem <ref> is that a non-zero distortion (for any finite block-length) is strictly needed to make the average redundancy of an universal coding scheme vanishing with the block-length. To obtain this result,  the two-stage approach  presented in Section <ref> was considered. 


If we restrict the family of two-stage schemes to have an exhaustive first-stage mapping, i.e., π_n(x)= { x } for all x ∈𝒳 and n ≥ 1,  then we reduce the approach to the lossless setting (i.e.,  zero distortion for every finite block-length).  In this case, if we apply the condition to obtain Theorem <ref> (stated in Lemma <ref> in Section <ref>), 
this reduces to verify 
that the i-radius of the family grows sub-linearly with the block-length (more details presented in  Sections <ref>
 and <ref>), which is the condition known  for a family of distributions to have a nontrivial minimax redundancy rate <cit.>.
 
 


 §.§ Entropy Estimation with an Almost Lossless Universal Code: A Side Comment


In the lossless case, the existence of a weak minimax source coding scheme {f_n: 𝒳^n  →{ 0,1}^*, n≥ 1 } for a family of distribution Λ implies that 
sup_μ∈Λlim_n →∞(r(f_n, μ^n) -H(μ))=0 <cit.>. Consequently,  the average length of the code r(f_n, μ^n)=𝔼{ℒ(𝒞_n(Φ_n(X^n))) }/n is a weak consistent estimator of the entropy distribution-free in  μ∈Λ <cit.>.  For the family of finite entropy stationary and memoryless sources, we have that it is not feasible to have a weak minimax USC scheme in ∞-alphabets.   
In fact, <cit.> says that for every code f_n and n≥ 1, there exists μ∈𝒫_ℋ(𝒳) such that r(f_n, μ^n)=∞. In other words, there is no lossless variable-length source coding scheme that offers a weakly consistent estimator of the entropy using its average block-length (per letter).

In contrast, Theorem <ref> shows that there is an almost lossless 
USC scheme {(ϕ_n, ψ_n, 𝒞_n, 𝒟_n): n≥ 1 } with an average length that offers a distribution-free weakly consistent estimation of the entropy in 𝒫_ℋ(𝒳). In fact from the proof of Lemma <ref> (Sec.<ref>), we have that 


    lim_n →∞sup_μ∈𝒫_ℋ(𝒳)(r(ϕ_n, 𝒞_n, μ^n) -H_σ(π_n)(μ))=0,

and from the fact that {π_n: n≥ 1} is asymptotically  sufficient for 𝒫_ℋ(𝒳) (Definition <ref> in Section <ref>), it follows that:  lim_n →∞ r(ϕ_n, 𝒞_n, μ^n) = H(μ), for all μ∈𝒫_ℋ(𝒳). Then, by relaxing the lossless block-wise assumption (introducing a  non-zero distortion), we control the worse-case redundancy, which  is bounded by the i-radius of 𝒫_ℋ(𝒳) restricted to a sub-sigma field (see (<ref>)). This flexibility enables the capacity to balance two sources of errors: 
 r(ϕ_n, 𝒞_n, μ^n) -H_σ(π_n)(μ) (a kind of estimation error)  and H(μ)-H_σ(π_n)(μ) (an approximation error),  that at the end offers an distribution-free estimate of the entropy (point-wise) using the average length of the code.








§ UNIFORM CONVERGENCE OF THE DISTORTION
 

In this section, we further focus on a stronger notion of universal weak source coding.   We study whether is possible to achieve an  uniform convergence of the distortion to zero (over the entire family Λ), instead of the point-wise convergence stated in Definition <ref>. To this end, we restrict the analysis to the rich family of envelope distributions introduced in Section <ref>. 
We can state the following dichotomy: 

 
	Let us consider the family of envelope distributions Λ_f.  
	
		
		
  i) If f∈ℓ_1(𝒳), then there is a two-stage coding scheme 
		{ (ϕ_n, ψ_n,𝒞_n): n≥ 1 } with | π_n| < ∞ (finite size) such that
		
		
    lim_n →∞sup_μ∈Λ_f d(ϕ_n, ψ_n,μ^n) = 0,  and 
       lim_n →∞sup_μ∈Λ_f(r(ϕ_n, 𝒞_n, μ^n) -H(μ))=0.

		
		
		
		
  ii) Otherwise, i.e., f∉ℓ_1(𝒳), for any two-stage 
		code (ϕ_n, ψ_n,𝒞_n) of length n with | π_n| < ∞  it follows that 
		
		
    sup_μ∈Λ_f d(ϕ_n, ψ_n,μ^n) = 1,

		while if | π_n| = ∞, then 
		
		
    sup_μ∈Λ_f (r(ϕ_n, 𝒞_n, μ^n) -H(μ) )= ∞.

		More generally, for a lossy code (f_n,g_n) of length n, provided that 
		
		
    sup_μ∈Λ_f d(f_n,g_n,μ^n)<1,

		then
		
    sup_μ∈Λ_f(r(f_n,μ^n) -H(μ))=∞.

	




The proof is presented in Section <ref>.

	
	Theorem <ref> states that if the envelope function is summable, there is a two-stage coding scheme of finite size 
	that offers a uniform convergence of the distortion to zero (over Λ_f), while ensuring that the worst-case average 
	redundancy (over Λ_f) vanishes with the block-length. 
	On the negative side, for all stationary memoryless sources indexed by a non-summable envelope function, it is not possible to achieve an uniform 
	convergence of the distortion to zero with  
	a finite size two-stage coding rule. An infinite size rule is indeed needed, 
	i.e., | π_n| = ∞, eventually with n, that on the down-side it has an unbounded i-radius 
	(details presented in Lemmas <ref> and <ref> at Section <ref>). 
	Importantly, this impossibility result remains when enriching the analysis with the adoption of general lossy coding rules (details in Sec. <ref>).
	
	
	Finally, it worths noting that the family Λ_f with f∈ℓ_1(𝒳) has a 
	finite regret and redundancy in the context of lossless universal source coding <cit.>. Furthermore,  summability is the necessary and sufficient condition on f that makes this collection strongly minimax universal 
	in  lossless source coding <cit.>. Then, based on this strong almost lossless source coding criterion
	(with a uniform convergence to zero of the distortion and the redundancy) 
	it is not possible to code (universally) a richer family of distributions when restricting the analysis to envelope families.





§ REDUNDANCY GAINS FOR SUMMABLE ENVELOPE FAMILIES



Theorem <ref> states that we can achieve a uniform convergence 
of the distortion to zero while the worst-case redundancy vanishes with a two-stage lossy scheme if,  and only if, Λ_f has a summable envelope function. On the lossless variable-length source coding side,  if f∈ℓ_1(𝒳) we know from Theorem <ref> that the i-radius of the family


    R^+(Λ_f^n) =   min_v^n ∈𝒫(𝒳^n)sup_μ^n ∈Λ_f^n𝒟(μ^n | v^n),

is o(n)  <cit.>, 
which is equivalent to state that Λ_f  
is strongly minimax universal <cit.>. Therefore, under the assumption that  f∈ℓ_1(𝒳), the lossy approach with asymptotic vanishing distortion may appear to not be useful if no gains are observed in the way the worst-case redundancy approaches zero in (<ref>), with respect  to the normalized i-radius sequence (R^+(Λ_f^n)/n)_n≥ 1 that governs minimax redundancy in the lossless case <cit.>.

This section explores the feasibility of obtaining gains in terms of the minimax redundancy of a  two-stage lossy approach tends to zero, when compared to the minimax redundancy (of the lossless scenario) for Λ_f when f∈ℓ_1(𝒳). We focus on the finite size tail-based partition scheme used to prove Theorem <ref> and the achievability part of Theorem <ref>.







 §.§ Preliminaries

Let us consider a positive and non-decreasing sequence of integers (k_n)_n and the collection of tail partitions induced by: 

    π̃_k_n{{ 1}, ⋯,  { k_n-1}, Γ_k_n-1^c },  ∀ n≥ 1,

where Γ_k= {1,… ,k}. Note that π̃_k_n resolves all the elements of Γ_k_n-1= {1,…,k_n-1 } and consequently,  there is a pair (ϕ̃_n, ψ̃_n) associated with π̃_k_n such that ∀μ∈Λ_f, 

rCl
	d(ϕ̃_n, ψ̃_n,μ^n)    ≤    μ(Γ_k_n-1^c) 
	
≤∑_x≥k_n f(x). 
	
Consequently, it follows that 

    sup_μ∈Λ_f d(ϕ̃_n, ψ̃_n,μ^n) ≤∑_x ≥ k_n f(x)<∞.

It is then easy to verify that (1/k_n)_n being  o(1) is the necessary and sufficient condition for the tail-based scheme to have the uniform convergence (over Λ_f)  of the distortion to zero. 


Concerning the worst-case minimax redundancy of the two-stage scheme induced by {π̃_k_n} in (<ref>), 
we can consider a lossy mapping  (ϕ̃_n, ψ̃_n) consistent with π̃_k_n (first-stage), where it is clear 
that the entropy of Y^n=(ϕ̃_n (X_1),..,ϕ̃_n(X_n)), which is H(Φ̃_n(X^n))=n H_σ(π̃_k_n)(μ) ≤ n H(μ),  
is a  
lower bound for the performance of any prefix-free code acting on  Y^n. Then given the first-stage (ϕ̃_n, ψ̃_n),   
we define the worse-case redundancy of  any 𝒞_n:Γ_k_n^n →{0,1}^* as follows: 


    R̅(Λ_f^n,  π̃_k_n, 𝒞_n) 
    	sup_μ∈Λ_f(r(ϕ̃_n,𝒞_n, μ^n ) - H_σ(π̃_k_n)(μ)).

Therefore for any finite n and first-stage 
partition π̃_k_n,  the minimax redundancy of the second-stage is: 


    min_𝒞_n: Γ^n_k_n→{0,1}^*R̅(Λ_f^n,  π̃_k_n, 𝒞_n).

For the second stage, we can use again the connection between prefix-free codes and distributions to map  𝒞_n to a probability v in 
𝒫(Γ_k_n^n),  where the redundancy r(ϕ̃_n,𝒞_n, μ^n ) - H_σ(π̃_k_n)(μ) can be expressed as 
one over n the divergence restricted to the cells of π̃_k_n <cit.>, more precisely as 1/n 𝒟_σ(π̃_k_n×⋯×π̃_k_n)(μ^n | v) where: 


    𝒟_σ(π̃_k_n×⋯×π̃_k_n)(μ^n | v) ∑_𝒜∈π̃_k_n×⋯×π̃_k_nμ^n(𝒜)logμ^n(𝒜)/v(𝒜),

with π̃_k_n×⋯×π̃_k_n being a short-hand for the product partition of 𝒳^n induced by π̃_k_n.
Consequently, the USC problem of the second-stage in (<ref>) given the first stage, i.e., given π̃_k_n in (<ref>), 
can be expressed by 1/n R^+(Λ_f^n, σ(π̃_k_n)) where:


    R^+(Λ_f^n, σ(π̃_k_n)) min_v ∈𝒫(𝒳^n)sup_μ^n ∈Λ_f^n𝒟_σ(π̃_k_n×⋯×π̃_k_n)(μ^n | v).

R^+(Λ_f^n, σ(π̃_k_n)) can be interpreted as the i-radius of Λ_f^n restricted to the events of the sub-sigma field σ(π̃_k_n×⋯×π̃_k_n).[More details are presented in (<ref>) and (<ref>) in Sec. <ref>.] 





 §.§ Redundancy Gain Analysis


Returning to our question, in the context of Eq. (<ref>) we know that 𝒟_σ(π̃_k_n×⋯×π̃_k_n)(μ^n|v) ≤𝒟(μ^n|v) <cit.>, therefore  for any sequence (k_n)_n of positive integers, it follows that R^+(Λ_f^n)≥ R^+(Λ_f^n, σ(π̃_k_n)) for all n,  Consequently, we have that  


    lim inf_n →∞R^+(Λ_f^n)/R^+(Λ_f^n, σ(π̃_k_n))≥ 1.

In particular, we want to determine regimes on (k_n)_n that guarantee an asymptotic gain in minimax redundancy in the sense that


    lim_n →∞R^+(Λ_f^n, σ(π̃_k_n))/R^+(Λ_f^n) =0,

subject to the condition that (1/k_n)_n is  o(1).  If (k_n)_n offers an asymptotic gain on minimax redundancy in the sense of Eq. (<ref>), then any sequence where (k̃_n)_n such that 
(k̃_n)_n ≤ (k_n)_n  eventually in n  
offers a gain in the minimax redundancy[This is a simple consequence of the fact that k≥k̃ implies σ(π̃_k̃) ⊂σ(π̃_k).]. Therefore it is important to determine  the largest size sequence  for the tail partition such that  (<ref>) is satisfied.

Note that any sequence (k_n)_n offers a non-zero worst-case distortion for a finite block-length,  and if (1/k_n)_n is o(1) this worst case distortion goes to zero at rate function of (k_n)_n and  the envelope function f. From this, one could suspect a gain in the minimax redundancy,  in the sense established by (<ref>), no matter how fast (k_n)_n tends to infinity with the block-length as long as k_n<∞ for any n.  In other words, one simple conjecture is that the complexity of a family of distributions with infinite degrees of freedom, measured in terms of the rate of convergence to zero of the minimax redundancy per sample (R^+(Λ_f^n)/n)_n, cannot be reached by projecting this family into  finite but dynamic (with the block-length) alphabets. However, the following result refutes this initial guess and determines a non-trivial regime for (k_n)_n with no minimax redundancy gain. Importantly, this regime is fully determined by (u^*_f(n))_n (see Def.<ref> in Section <ref>), which can be interpreted as a sequence of critical dimensions for Λ_f that was introduced by Bontemps et al. <cit.> in the context of lossless USC.



 
	Let Λ_f ⊂𝒫(𝒳) be an envelope family with f∈ℓ_1(𝒳) and  |supp(f)|=∞. 
	In addition, let {π̃_k_n: n≥ 1 }  be the collection of tail-based partitions  in (<ref>) 
	driven by a positive non-decreasing sequence (k_n)_n. It follows that:
	
		
  i) If (k_n)_n ≥ (u^*_f(n))_n eventually in n, then there is no gain in minimax redundancy in the sense that: 
		
		
    lim_n →∞R^+(Λ_f^n, σ(π̃_k_n))/R^+(Λ_f^n) =1.

		
  ii) Conversely, if (k_n)_n is o(u^*_f(n)), i.e., lim_n →∞k_n/u^*_f(n)=0, 
		then we have a minimax redundancy gain:
		
		
    lim_n →∞R^+(Λ_f^n, σ(π̃_k_n))/R^+(Λ_f^n) =0.

		

The proof is presented in Section <ref>.





Analysis and interpretation of Theorem <ref>:

	
	
  * First, we note that the sequence (u^*_f(n))_n in (<ref>) defines a notion of critical dimension (or cardinality) for the family Λ_f,  as it characterizes a boundary (or phase transition) on the size of the tail-based two-stage coding schemes above from which no gains in terms of the rate of minimax redundancy are obtained.
	
	
	
  * If we consider the regime of redundancy gain, i.e., where (k_n)_n is  o(u^*_f(n)),   it is simple to note that any arbitrary partition 
	scheme {π_n: n≥ 1 } such that | π_n |= | π̃_k_n| =k_n satisfies:
	
	
    lim_n →∞R^+(Λ_f^n, σ(π_n))/R^+(Λ_f^n) =0.

	Then, this scenario of redundancy gain can be extended to any finite alphabet partition strategy, and consequently, we can say that 
	the condition (k_n)_n is o(u^*_f(n)) offers a trivial  regime of minimax redundancy gain. However, what is not evident is the fact that the tail-based partition offers a non-trivial regime of redundancy gain, in the sense that the condition (k_n)_n ≥ (u^*_f(n))_n eventually with n suffices  to guarantee that: 
	
	
    lim_n →∞R^+(Λ_f^n, σ(π̃_k_n))/R^+(Λ_f^n) =1.

	From this angle, the tail-based partition is efficient (or sufficient) to capture the asymptotic complexity of Λ_f with a minimum alphabet size. Complementing this richness property of {π̃_k_n}, it is simple to verify that the  tail partition is an optimal solution when the objective is to minimize the worst-case distortion of a two-stage lossy coding scheme restricting the finite size k>0 on the quantization.
	
	
	
  * From a complexity view-point, R^+(Λ_f^n) measures the complexity of the lossless coding task. 
	Then, for a given finite partition π_n ∈ℬ(𝒳),  R^+(Λ_f^n)- R^+(Λ_f^n, σ(π_n)) ≥ 0 can be interpreted as the reduction on complexity by the process of projecting Λ^n_f into a finite alphabet, i.e.,  
	
	
    Λ_f^n/σ(π_n) {μ^n/σ(π_n×⋯×π_n):μ∈Λ_f }

	where μ/σ(π){μ(𝒜): 𝒜∈σ(π)}∈𝒫(𝒳, σ(π)) is a short-hand for the probability μ  restricted to the sub-sigma field induced by π (details presented in Section <ref>).
	Then, it is interesting to know if the i.i.d. family of envelope distributions {Λ^n_f: n≥ 1} with f∈ℓ_1(𝒳) 
	admits a finite but dynamic alphabet reduction that captures its complexity asymptotically with n. For that question, we can introduce the following: 
	
	
	
	
	
	We say that Λ⊂𝒫(𝒳) has a finite alphabet reduction, if there exists a partition scheme {π_n: n≥ 1 } with | π_n |=k_n<∞ such that lim_n →∞R^+(Λ^n, σ(π_n))/R^+(Λ^n) =1, or, equivalently, that {Λ^n: n≥ 1} is equivalent to {Λ^n/σ(π_n): n≥ 1 }  in terms of asymptotic information complexity. In this case, we  say that (k_n)_n 
	is a sequence  of sufficient sizes (or sufficient) to represent Λ.
	
	
	 
	We say that  (k^*_n)_n is the critical (or minimal) size to represent Λ_ f, if  (k^*_n)_n is a  sequence of sufficient size to represent Λ (Def. <ref>), and no sequence (l_n)_n exists such that: (l_n)_n is sufficient to represent Λ and (l_n)_n ≪ (k^*_n)_n. 
	
	
	In this context,  the proof of Theorem <ref> shows as a corollary that (u^*_f(n))_n is the critical size to represent Λ_ f.  The achievability part is obtained using the tail-based partition and some metric entropy lower bound  
	for the i-radius extended from <cit.>.  On the other hand, the converse argument derives from  basic i-radius results for i.i.d. sources over finite alphabets <cit.> and results for envelope families on countably infinite alphabets <cit.>.
	
	Finally, from  Boucheron et al. <cit.>,  
	we have that Λ_f has either a finite alphabet reduction with a sub-linear critical size sequence given by (u^*_f(n))_n (if  f∈ℓ_1(𝒳)), or infinite minimax redudancy for all n≥ 1. 
	
	
  * To illustrate the result, let us consider the exponentially decreasing envelope class studied in <cit.>: 
	
	
    Λ_f_Ce^-α={μ∈𝒫(𝒳), f_μ(x) ≤ f_Ce^-α(x)= C e^-α x},

	where C>0 and α>0. It has been shown in <cit.> that
	
	
    1/αln(C x) ≤ U_f_Ce^-α(x) +1 ≤1/αln(κ C x)

	where κ = 1/(1-e^-α) and U_f(x) is defined in Def. <ref> (see Section <ref> for details). 
	Importantly for our analysis, it follows that  u^*_f_Ce^-α(n)-1 ≤ U_f_Ce^-α(n) <  u^*_f_Ce^-α(n) (see  Section <ref>), therefore we have that for all n≥ 1
	
	
    1/αln(C n) +1 <  u^*_f_Ce^-α(n) ≤1/α (ln (κ) +ln(C n) ).

	Consequently,  the critical dimension of this exponential family, which determines the regime of redundancy gain, 
	scales like ∼ (1/αln n)_n. Similar analysis can be conducted on the power-law envelopes and sub-exponential envelopes  classes
	studied in <cit.>. See also an excellent exposition of these last results in <cit.>.






§ SUMMARY AND CONCLUDING REMARKS
 

The problem of almost lossless universal source coding for countably infinite alphabet sources is introduced in this work. 
Our main result  shows that a weak notion of universal (variable length) source coding is feasible for the entire 
class of finite entropy stationary memoryless sources. This result is obtained by  tolerating a (non-zero) single-letter distortion in the encoding process 
that vanishes asymptotically with the block-length. To this end, one key idea is an induced sequence of partitions of the  ∞-alphabet, which offers a way to control the  worst-case average redundancy associated with the i-radius of a class of distributions restricted to a subsigma-field. 
We have also studied a stronger almost losses condition, asking for uniform convergence of the distortion to zero (over the family of distributions), where it turns out that this variation of weak universality can be achieved  for the same class of envelope distributions that is strong minimax universal in the lossless case.  This last result suggests that asking for a non-zero distortion that convergence to zero point-wise (over the family of distributions) is the strongest relaxation from the lossless criterion 
that allows us to control the  worst-case redundancy of the problem. 
Finally,  we show that it is possible  to obtain gains in the rate of convergence of the worst-case redundancy  of an almost lossless scheme,  with respect to the worst-case redundancy of the lossless case, by tolerating a non-zero distortion that tends to zero with the block-length. In this context,  we fully characterize the regime of  gains for a two-stage lossy scheme induced by tail based partitions. 




§ PROOFS OF THE MAIN RESULTS
 








 §.§ Theorem <ref>



First, we introduce a 
result and some definitions that will be used in the proof. 



  §.§.§ Preliminaries


 
For 
μ∈𝒫(𝒳) its rate distortion function  is given by <cit.>: 


    R_μ(d)inf_P(X̃|X)  st.  ℙ(X̃≠ X) ≤ d I(X; X̃).





For any μ∈𝒫(𝒳) and θ>0, let us define μ̃_θ∈𝒫(𝒳)
by: μ̃_θ({i }) min{θ, μ({i }) } for all i>1 and 
μ̃_θ({1 })   1-κ_θ where  κ_θ∑_i>1μ̃_θ({i }). 



 (Ho et al.<cit.>) 

Let us consider μ∈𝒫(𝒳), where 𝒳 is an ∞-alphabet, then there is d_0>0 such that ∀ d ≤ d_0 


    R_μ(d) = H(μ) -  H(μ̃_θ(d))

with μ̃_θ introduced in Def.<ref> 
and θ(d) > 0 being the solution of the condition κ_θ = ∑_i>1μ̃_θ({i })=d. 






  §.§.§ Proof of Theorem <ref>

We consider the non-trivial case where μ has infinite support over 𝒳, i.e., inf_x∈𝒳 f_μ(x)=0,  otherwise the problem reduces to a finite alphabet scenario where this result is known <cit.>. 

We begin with the converse argument. This reduces to prove that any lossy coding scheme with zero asymptotic distortion 
has a rate that convergences to a limit that is grater or equal to H(μ) (see Def. <ref>). 
For that, let us assume that we have a lossy scheme { (f_n, g_n): n≥ 1} such that


    lim_n ⟶∞ d(f_n, g_n,μ^n) =0 ⇔
       lim_n ⟶∞1/n∑_i=1^n ℙ{  X_i≠ (g_n(f_n(X^n)))_i } =0.

If we denote by X̂^n  g_n(f_n(X^n)) the reconstruction,  from lossless variable length source coding  it is well-known that <cit.>:

rCl 	
	r(f_n, μ^n)    ≥     1/n I(X^n, X̂^n) 

				
			       ≥   1/n ∑_i=1^n I(X_i;X̂_i) 
			    
			     ≥1/n ∑_i=1^n R_μ(ℙ{X_i≠X̂_i})
			    
			    

			       ≥    R_μ  ( 1/n ∑_i=1^n ℙ  {  X_i≠X̂_i }) 

			    
			    
			       =    R_μ (d(f_n, g_n,μ^n)), 

where for the inequalities in (<ref>), we use that 𝐗 is memoryless, the non-negativity of the conditional mutual information <cit.>, and the convexity of the rate-distortion function of μ  <cit.>.  

For the rest we assume that μ is organized  in decreasing order in the sense that f_μ(1) ≥ f_μ(2)≥⋯ [We note that  for the
charcaterization of R_μ(d) as d → 0 this assumption implies no loss of generality.] and that we are in the regime where d≤ d_o (introduced in Lemma <ref>). 
Using Lemma <ref>, we have that R_μ(d) = H(μ) -  H(μ̃_θ(d)),  where if we consider


    K_μ(d) min{ k>1:
    								f_μ(k+1) ≤θ(d) },

it is simple to verify that:


    H(μ̃_θ(d)) = (1-κ_θ(d))log1/1-κ_θ(d)
       + (K_μ(d)-1)·θ(d) log1/θ(d) + ∑_i>K_μ(d) f_μ(i) log1/f_μ(i).


From (<ref>) and (<ref>), we focus on exploring H(μ̃_θ(d_n)) when d_n → 0.  First,  it is simple to verify that d → 0 implies that θ(d) → 0 by definition.  Then, for a fix μ∈𝒫_ℋ(𝒳) with infinite support, the problem reduces to chacaterize lim_θ→ 0 H(μ̃_θ).  Note that μ̃_θ converges point-wise to the degenerate probability μ^*=(1,0,⋯) as θ vanishes [In the  ∞-alphabet 
the point-wise convergence of probabilities to a limit is equivalent to the weak convergence and the convergence in total variations <cit.>.]. 
However, by the entropy discontinuity <cit.>, the convergence of the measure to μ^* is not sufficient to guarantee  that  lim_θ→ 0 H(μ̃_θ)=H(μ^*)=0.

First, it is simple to note that κ_θ→ 0, as θ→ 0 considering that μ̃_θ(i) → 0 for all i≥ 1,  μ∈𝒫_ℋ(𝒳), and 
the dominated convergence theorem <cit.>. 
Then, lim_θ→ 0 (1-κ_θ)log1/1-κ_θ=0, which is the limit of the first term in the RHS of (<ref>). For the rest, we define the self-information function i_μ̃_θ(i) μ̃_θ({i }) log 1/ μ̃_θ({i })>0, for all i>1, and i_μ̃_θ(1)  0. By definition lim_θ→ 0 i_μ̃_θ(i)=0 point-wise in 𝒳, noting that lim_θ→ 0 K_μ(θ) = ∞ and H(μ)<∞. Furthermore, there is θ_0>0 such that for all  θ< θ_0, 0≤ i_μ̃_̃θ̃(i) ≤ i_μ̃_θ_0(i) for all [This follows from the fact that the function θlog1/θ is monotonically increasing in the range of (0,θ_0) for some θ_0>0.] i≥ 1, where  from the  assumption that H(μ)<∞, and the fact that K_μ(θ_0)<∞, then  (i_μ̃_̃θ̃_̃0̃(i)) ∈ℓ_1(𝒳).  Again by the dominated convergence theorem <cit.>,  lim_θ→ 0∑_i≥ 1 i_μ̃_̃θ̃(i) =0 and consequently, lim_θ→ 0 H(μ̃_θ)=0 from (<ref>).

Returning to (<ref>), it follows that for all n≥ 1,

rCl 
	r(f_n, μ^n)    ≥    R_μ (d(f_n, g_n,μ^n)_d_n ) 

	   =   H(μ) - H(μ̃_θ(d_n)). 

Finally, as d_n → 0, 

rCl 
	lim inf_n →0 r(f_n, μ^n)    ≥    H(μ) - lim sup_d_n →0 H(μ̃_θ(d_n)) 

	   =    H(μ) - lim_θ→0 H(μ̃_θ)

	   =   H(μ)  . 

Therefore, the inequality in (<ref>) implies that R_al(μ)≥ H(μ) from Definition <ref>.  

The achievability part (i.e., R_al(μ)≤ H(μ)) follows from the proof of Proposition <ref> in Appendix <ref>.

 








 §.§ Theorem <ref>




For the proof of Theorem <ref>, we  first introduce some definitions and an achievability result:


  §.§.§ Preliminaries

Regarding the distortion,  we need the following definition: 

	A sequence of partitions {π_n: n ≥ 1} of 𝒳 is 
	asymptotically sufficient for Λ⊂𝒫(𝒳), if  it is 
	asymptotically sufficient for every measure μ∈Λ (cf. Definition <ref>). 


Concerning the analysis of the worst-case average redundancy in a lossy context,  it is instrumental to introduce the divergence restricted to a sub-sigma field <cit.>. 


Let π be a  partition of 𝒳 and σ(π) ⊂ℬ(𝒳) its induces sigma-field. Then, for every μ,  v ∈𝒫(𝒳),  the divergence of μ with respect to v restricted to σ(π) is <cit.>:


    𝒟_σ(π)(μ|v) ∑_𝒜∈πμ(𝒜)logμ(𝒜)/v(𝒜).





Let Λ⊂𝒫(𝒳) and π be a partition of 𝒳. 
Fot any n≥ 1, the information radius of Λ^n ⊂𝒫(𝒳^n) 
restricted to 
σ(π) is given by: 


    R^+(Λ^n, σ(π)) min_v^n ∈𝒫(𝒳^n)sup_μ^n ∈Λ^n𝒟_σ(π×⋯×π)(μ^n | v^n),

 where π×⋯×π denotes the product partition of 𝒳^n, 𝒫(𝒳^n) is the set of probability measures in (𝒳^n, ℬ(𝒳^n)),  and Λ^n denotes the collection of all i.i.d (product) probabilities measures in (𝒳^n, ℬ(𝒳^n)) induced by Λ. 
 



	Let us consider Λ⊂𝒫(𝒳). 
	If there is a sequence of partitions {π_n: n ≥ 1} of 𝒳 such that:
	
	
  * {π_n: n ≥ 1} is asymptotically sufficient  for Λ (Def. <ref>),  and 
	
  * (R^+(Λ^n, σ(π_n)))_n is o(n), 
	
	then the family of stationary and memoryless sources with marginal distribution in Λ admits 
	an almost lossless source coding scheme. 



The proof 
is presented in Section <ref>.




  §.§.§ Proof of Theorem <ref>

Let us consider a collection of finite size partitions {π_n: n ≥ 1}⊂ℬ(𝒳) 
with  k_n=| π_n|<∞ for all n.  
We note that if 


    ⋂_m≥ 1⋃_l≥ mπ_l(x)= { x},  for all   x∈𝒳

then, this partition scheme is asymptotically sufficient for 𝒫(𝒳).  
Concerning the information radius,  we have that k_n = | π_n| <∞, which reduces the analysis to the finite alphabet case. In this context, it is well-known that <cit.>:


    k_n-1/2log n -K_1 ≤ R^+(𝒫(𝒳^n), σ(π_n)) ≤k_n-1/2log n + K_2,

for some universal constants K_1 and K_2. Then, provided that  (k_n)_n is  o(n/log n)  it follows that  (R^+(𝒫(𝒳^n), σ(π_n)))_n is  o(n). 
There are numerous finite partition sequences that satisfy the  conditions stated in (<ref>) and (k_n)_n being o(n/log n).  For example, the tail partition family given by π̅_k_n{{1 }, {2 }, ⋯, { k_n-1}, Γ_k_n-1^c }, where Γ_k{1,⋯,k} and Γ_0∅, considering that  (1/k_n)_n is o(1) and (k_n)_n is o(n/log n).  
Finally, for all  Λ^n ⊂𝒫(𝒳^n)   we have by definition that R^+(Λ^n, σ(π_n))≤ R^+(𝒫(𝒳^n), σ(π_n)), which proves the result by applying Lemma <ref>. 

 







 §.§ Proof of Lemma <ref>



First note that if {π_n: n ≥ 1} is asymptotically sufficient for the family Λ, 
it means that for all μ∈Λ, lim_n →∞μ(∪_k≥ nπ_k(x) ∖{ x})=0 (Def. <ref>).  If we denote  by k_n=| π_n | and π_n={𝒜_n.i: 1≤ i ≤ k_n }, then we can construct ϕ_n:𝒳^n →{ 1,…, k_n} such that ϕ^-1_n(i)=𝒜_n,i for all 1≤ i ≤ k_n. On the other hand, we can choose an arbitrary y_n,i∈𝒜_n.i for each i∈Γ_k_n, and the mapping ψ:Γ_k_n→𝒳 in the way ψ(i)=y_n,i.   
At this point, we observe:

rCl
	d(ϕ_n, ψ_n,μ^n)   =    ℙ(X≠ψ_n(ϕ_n(X))) 

	   =    ∑_i=1^k_n ∑_x∈𝒜_n,i f_μ(x) ρ_0,1(x, y_n, i) 

	   =    ∑_i=1^k_n μ(𝒜_n,i ∖{ y_n,i }) 

	   =    μ(𝒳∖⋃_i=1^k_n { y_n,i }).
	

Then, from the hypothesis that {π_n: n ≥ 1} is asymptotically sufficient for μ, and the use of bounded convergence theorem, it is simple to verify that the RHS of (<ref>) goes to zero (see Section <ref>). Therefore, this convergence happens point-wise  ∀μ∈Λ.



It worth mentioning that (<ref>) tends to zero,  if and only if,  lim_n →∞∪_k≥ nπ_k(x)= { x} μ-almost surely (cf. Lemma <ref>). Hence, to achieve a point-wise convergence to zero of the distortion over Λ, for this two-stage scheme, it is necessary and sufficient that 
{π_n: n ≥ 1} is asymptotically sufficient for Λ. 



Regarding the second coding stage, we ideally need to  find a lossless code with the least worst-case average
redundancy over the family 


    Λ^n/σ(π_n)    {μ^n/σ(π_n ×⋯×π_n):μ∈Λ}
       ⊂𝒫(𝒳^n, σ(π_n ×⋯×π_n)),

where μ/σ(π)∈𝒫(𝒳, σ(π)) is a short hand for the probability μ restricted to the sub-sigma field induced by π [Note that if μ∈𝒫(𝒳), then the restriction μ/σ(π) ∈𝒫(𝒳, σ(π)) reduces to the evaluation of μ over the cells of π. In fact, {μ(B): B∈π} plays the role of the probability mass function of μ/σ(π) on the measurable space (𝒳, σ(π)).],   and P(𝒳, σ) denotes the collection of probabilities restricted to the events of the sub-sigma field σ⊂ℬ(𝒳). 

In fact, for a lossless prefix-free code 𝒞_n:Γ_k_n^n →{0,1}^*, associated to the first stage ϕ_n, its worst-case average redundancy over Λ^n 
is given by:


    R(Λ^n, 
    	ϕ_n, 𝒞_n) sup_μ∈Λ(r(ϕ_n,𝒞_n, μ^n ) - H(μ)).

For any fixed μ∈Λ, it is clear that the entropy of Φ_n(X^n) is a lower bound for the average rate of the code, i.e., r(ϕ_n,𝒞_n, μ^n)≥1/nH(Φ_n(X^n))=H_σ(π_n)(μ), then constraining to the events of σ(π_n), we are interested in controlling the following stringer worst-case overhead:


    R̅(Λ^n,
    	ϕ_n,
    	𝒞_n) sup_μ∈Λ(r(ϕ_n,𝒞_n, μ^n ) - H_σ(π_n)(μ)).

Note that H_σ(π_n)-H(μ)≤ 0 
and thus, R̅(Λ^n, ϕ_n,  𝒞_n)≥ R(Λ^n, ϕ_n, 𝒞_n). 
Then, we can choose a code solution to the following mini-max problem:


    𝒞^*_n min_𝒞^n: Γ^n_k_n→{0,1}^*R̅(Λ^n, 
    	ϕ_n, 𝒞_n),  for all  n≥ 1.


From the close connection between probabilities and prefix free codes <cit.>,   
the performance of the optimal code in (<ref>) is  tightly related to the i-radius of the family Λ^n/σ(π_n)  in (<ref>), in the sense that  ∀ n≥ 1:


    R^+(Λ^n, σ(π_n))/n≤R̅(Λ^n,
    	ϕ_n, 𝒞^*_n) ≤R^+(Λ^n, σ(π_n))+2/n.

Finally,  from the hypothesis on the information radius and (<ref>),  we have that:
rCl
lim_n →∞ R(Λ^n, ϕ_n, 𝒞^*_n) ≤lim_n →∞ R̅(Λ^n, ϕ_n, 𝒞^*_n) =0.



The inequalities in (<ref>) states that the sub-linear trend (with the block-length) on the i-radius of {Λ^n/σ(π_n): n≥ 1 }  is a necessary 
and sufficient condition for the existence of a strongly minimax universal  code for {Λ^n/σ(π_n): n≥ 1 }.










 §.§ Theorem <ref>


Let us first introduce some notations, definitions and results that will be used in the proof of Theorem <ref>. 



	For Λ⊂𝒫(𝒳) its i-radius is given and denoted by:
	
    R^+(Λ) inf_v ∈𝒫(𝒳)sup_μ∈Λ𝒟(μ | v).





	For a function ϕ: 𝒳→ℐ  (where ℐ is either a finite 
	or a countably infinite set) and μ∈𝒫(𝒳), let us denote by v_μ∈𝒫(ℐ)
	the distribution induced by ϕ in ℐ trough the standard construction[There is no question about the measurability
of ϕ(·) as  we consider that ℬ(𝒳) is the power set.]: v_μ(B) μ(ϕ^-1(B)) for all 
B⊂ℐ.





	Let  ϕ: 𝒳→ℐ be a mapping where ℐ is a countably infinite set.
	Then for any non-negative envelope function f: 𝒳→ℝ^+, 
	there is f̃:ℐ→ℝ^+ given by[A_iϕ^-1({ i }) for any i∈ℐ.]
	
	
    f̃(i) min {∑_x∈𝒜_i f(x), 1 },

	such that {v_μ: μ∈Λ_f } =Λ̃_f̃{ v∈𝒫(ℐ): f_v(i)≤f̃(i) for all i ∈ℐ}. 


The proof of this result is presented in Appendix <ref>.

Lemma <ref> implies that envelope families on 𝒳 map to envelope families on ℐ through the mapping ϕ. 
In this context, the result by Boucheron et al. <cit.> in Theorem <ref> (in Section <ref>) 
is instrumental to prove Theorem <ref>.


Proof of Theorem <ref>:



  §.§.§ Achievability

If f∈ℓ_1(𝒳), the fact that Λ_f has a uniform bound on the tails of the distributions suggests
that a family of tail truncating partitions should be considered to achieve the claim i). Let us define


    π̃_k_n{{ 1}, ⋯,  { k_n}, Γ_k_n^c },

which resolves  the elements of Γ_k_n= {1,…,k_n } and, consequently,  
there is a pair (ϕ̃_n, ψ̃_n) associated with π̃_k_n such that ∀μ∈Λ_f:

    d(ϕ̃_n, ψ̃_n,μ^n) ≤μ(Γ_k_n^c) ≤∑_x>k_n f(x).

In fact, sup_μ∈Λ_f d(ϕ̃_n, ψ̃_n,μ^n) ≤∑_x>k_n f(x)<∞, and 
(1/k_n)_n being  o(1) is a sufficient condition to satisfy the uniform convergence of the distortion to zero.  Furthermore, 
from the proof of Lemma <ref> (Eq.(<ref>)) and (<ref>),  there is a lossless coding scheme {𝒞̃_n:Γ_k_n+1^n  →{0,1}^*: n≥ 1} such that sup_μ∈Λ_f(r(ϕ_n, 𝒞̃_n, μ^n) -H(μ)) ≤ k_n·log√(n)/n + O(1/n). Therefore,  we can consider (k_n)_n being O(n^τ) with τ∈ (0,1) to conclude the achievability part.  




  §.§.§ Converse for Two-Stage Lossy Coding Schemes
[We first present this preliminary converse argument, as it provides the ground to explore the redundancy gain analysis presented in Section <ref>.]
For the converse part,  let us first consider an arbitrary two-stage lossy rule  (ϕ_n, ψ_n, 𝒞_n) with a finite partition k_n =| π_n| < ∞. If we denote its prototypes by 𝒴_n {ψ(i): i ∈Γ_k_n}, it is clear that  there exists μ∈Λ_f such that supp(μ) ⊂𝒴_n^c, and consequently,  d(ϕ_n, ψ_n,μ^n)=1 for all n.  Therefore, for any finite size partition rule (ϕ_n, ψ_n, 𝒞_n) it follows that  sup_μ∈Λ_f d(ϕ_n, ψ_n,μ^n)=1 for all n≥ 1 and hence, when f∉ℓ_1(𝒳) no uniform convergence on the distortion can be achieved  with a finite size lossy rule.

On the other hand, for the family of infinite size partition rules, i.e., (ϕ_n, ψ_n, 𝒞_n) such that | π_n|= ∞,  we focus our analysis on R^+(Λ^n_f, σ(π_n)) in (<ref>).  Let us fix a block-length n>0 and a rule (ϕ_n,ψ_n, 𝒞_n)
of infinite size. For sake of clarity, we consider that ϕ_n: 𝒳→ℐ, where ℐ is a ∞-alphabet.  
For any μ∈Λ_f, v_μ denotes the induced measure in ℐ
by the mapping ϕ_n trough the standard construction (see Def. <ref>).  
In addition,  it is simple to verify 
that for any pair μ_1,μ_2 ∈𝒫(𝒳) 

rCl
		𝒟_σ(π_n)(μ_1 | μ_2)    =    𝒟(v_μ_1|v_μ_2)

		   =   ∑_i∈ℐ f_v_μ_1(i) f_v_μ_1(i) /f_v_μ_2(i) , 

where π_n={𝒜_n,i=ϕ_n^-1({i }): i∈ℐ} and f_v_μ(i) μ(𝒜_n,i)
 ∀ i denotes the pmf of v_μ on ℐ. Then, 

rCl
	R^+(Λ^n_f, σ(π_n))    =    R^+({v^n_μ: μ∈Λ_f }) 

where v^n_μ denotes de product probability on ℐ^n with marginal v_μ and 
𝒫(ℐ^n) is the collection of probability measures on ℐ^n. Then,  
the i-radius of Λ_f^n restricted to the product sub-sigma field σ(π_n×⋯×π_n)
is equivalent to the information radius of {v^n_μ: μ∈Λ_f }⊂𝒫(ℐ^n) (Def. <ref>).  
From Lemma <ref>,  {v^n_μ: μ∈Λ_f } is an envelope family with envelope function  
given by (<ref>).  It is simple to verify that f∉ℓ_1(𝒳) 
implies that f̃∉ℓ_1(ℐ),  then Theorem <ref> and (<ref>) tell us
that  R^+(Λ^n_f, σ(π_n))=∞. 
Finally, since the i-radius in (<ref>) tightly bounds the least-worst expected redundancy for the second lossless coding stage (see  (<ref>) and (<ref>)), this implies that: 


    sup_μ∈Λ_f (r(ϕ_n, 𝒞_n, μ^n) -H(μ)) = ∞,

which concludes the argument.  





  §.§.§ Converse for general variable-length lossy codes


Let us consider a general lossy code (f_n,g_n) of length n>0 introduced in Section <ref>. Without loss of generality we can decouple  
f_n as the composition of a vector quantizer ϕ_n:𝒳^n →ℐ_n, where 
ℐ_n is an index set, and a prefix-free losses mapping 𝒞_n: ℐ_n  →{0,1}^*, 
where f(x^n)=𝒞_n(ϕ_n(x^n)) for all x^n∈𝒳^n. From this, we characterize
the vector quantization induced by  (f_n,g_n) as follows:


    π_n {ϕ_n^-1({ i }): i ∈ℐ_n }⊂ℬ(𝒳^n).

Using this two-stage (vector quantization-coding) view,  
it is possible to show that[The proof of (<ref>) is presented in Appendix <ref>.]: 


    R̅(Λ_f,f_n)    sup_μ∈Λ_f(r(f_n,μ^n) -1/nH_σ(π_n)(μ^n)) 
       ≥1/ninf_v∈𝒫(𝒳^n)sup_μ∈Λ_f𝒟_σ(π_n)(μ^n | v),

which means that the worst-case overhead, expressed by R̅(Λ_f,f_n),  is lower bounded by the i-radius
 of the n-fold family Λ_f^n projected into the sub-sigma field induced by π_n, i.e., a quantization of 𝒳^n. 
 
Considering that f∉ℓ_1(𝒳), we follow the construction presented in <cit.> that shows 
that there is an infinite collection of distributions Λ̃={μ̃_j ∈Λ_f, j∈𝒥} with | 𝒥| =∞, where if we denote by 


    𝒜_μ̃_jsupp( μ̃_j)=  { x ∈𝒳: f_μ̃_j(x)>0 },
 
then | 𝒜_μ̃_j| < ∞ for each j∈𝒥 and for any j_1≠ j_2, 𝒜_μ̃_j_1∩𝒜_μ̃_j_2 =∅. In this context, for each j∈𝒥 A^n_μ̃_j𝒜_μ̃_j×…×𝒜_μ̃_j∈𝒳^n is the support of μ̃^n_j.   

At this point, let us use the assumption that:  

sup_μ∈Λ_f d(f_n,g_n,μ^n)<1.
This implies that sup_μ∈Λ̃ d(f_n,g_n,μ^n)<1. From the fact that Λ̃ is an infinite collection of probabilities 
with disjoint supports and the definition of the distortion, it is simple to verify that we need to allocate at least one prototype[The prototypes of (f_n,g_n) is the set ℬ_n={g_n(f_n(x^n_1)): x^n_1∈𝒳^n }.] per cell A^n_μ̃_j, which implies that | ℐ_n | =∞,  because otherwise it follows that  sup_μ∈Λ̃ d(f_n,g_n,μ^n)=1.

Using (<ref>), we will focus on evaluating the information radius of Λ̃^n projected over the measurable space (𝒳^n,σ(π_n))
considering that by definition:   

rCl
   inf   _v∈𝒫(𝒳^n) sup_μ∈Λ̃   𝒟_σ(π_n)(μ^n | v) 

   ≤     inf_v∈𝒫(𝒳^n) sup_μ∈Λ_f   𝒟_σ(π_n)(μ^n | v). 



For every j∈𝒥, let us define the covering of the support of μ̃^n_j∈Λ̃^n by
π_n(𝒜^n_μ̃_j) { B∈π_n: 𝒜^n_μ̃_j∩ B≠∅}
and 


    ℬ(𝒜^n_μ̃_j) ⋃_B∈π_n(𝒜^n_μ̃_j) B.

By construction, we note that | 𝒜^n_μ̃_j| <∞ and consequently | π_n(𝒜^n_μ̃_j) | <∞
for all j∈𝒥. Considering that π_n has an infinite number of cells, we can choose an infinite subset 
of elements in Λ̃^n={μ̃^n_j: j∈𝒥} in the following way:  We fix j_1=1 and μ̅_1=μ̃_1∈Λ̃,  then we consider


    j_2 =  min{ j>j_1,  such that ℬ(𝒜^n_μ̃_j) ∩ℬ(𝒜^n_μ̅_1) =∅} <∞,

and we choose μ̅_2 = μ̃_j_2∈Λ̃. Iterating this rule,   
at the k-stage (k≥ 2) we solve


    j_k =  min{ j>j_k-1,  such that ℬ(𝒜^n_μ̃_j) ∩(⋃_l=1^k-1ℬ(𝒜^n_μ̅_l)) =∅}

and we take μ̅_k = μ̃_j_k∈Λ̃, for all k≥ 1.  Note that the solution of (<ref>) is guaranteed from the fact that | 𝒥| =∞ and | π_n(𝒜^n_μ̃_j) | <∞ for all j. Finally, we define  Λ̅^n {μ̅^n_l: l≥ 1}⊂Λ̃^n. Importantly (for the computation of the i-radius), this restricted family of distributions has the property that their support coverings in (<ref>) are disjoint by its construction in (<ref>). From Λ̅^n, we can induce the following partition:


    ξ_n {ℬ(A^n_μ̅_l): l≥ 1) }∪(𝒳^n∖⋃_l≥ 1ℬ(A^n_μ̅_l))  ⊂σ(π_n),

where the last identity is from the construction,  as  every cell of ξ_n is a finite union 
of cells of π_n (i.e., ξ_n ≪π_n). It is not difficult to check that for every v∈𝒫(𝒳^n),
we have that [This result follows from the fact that the elements of Λ̅^n projected into the 
sub-sigma field ξ_n degenerate, in the sense that  H_σ(ξ_n)(μ̅^n_l)=0 for all l≥ 1.]


    sup_μ̅_l∈Λ̅𝒟_σ(ξ_n)	(μ̅^n_l|v)=∞.

Consequently, we have that 


    inf_v∈𝒫(𝒳^n)sup_μ̃_j ∈Λ̃𝒟_σ(π_n)(μ̃_j^n | v)    ≥inf_v∈𝒫(𝒳^n)sup_μ̃_j ∈Λ̃𝒟_σ(ξ_n)(μ̃_j^n | v)
       ≥inf_v∈𝒫(𝒳^n)sup_μ̅_l∈Λ̅𝒟_σ(ξ_n)	(μ̅^n_l|v)=∞,

the first inequality derives from ξ_n ≪π_n and the second from  Λ̅⊂Λ̃. 
Finally (<ref>) and the relationship between  the worst-case redundancy and the information radius in (<ref>) (Prop. <ref> in Appendix <ref>) imply that
	 
	
    R̅(Λ̃,f_n)=  sup_μ̃_j ∈Λ̃(r(f_n,μ̃_j^n) -1/nH_σ(π_n)(μ̃_j^n))=∞.

	In other words, from (<ref>) there is jo∈𝒥 such that r(f_n,μ̃_jo^n) -1/nH_σ(π_n)(μ̃_jo^n)=∞, where considering that by construction 1/nH_σ(π_n)(μ̃_jo^n) ≤ H(μ̃_jo)< log| 𝒜_μ̃_jo| <∞, this implies that r(f_n,μ̃_jo^n) - H(μ̃_jo)=∞. Therefore, we have that 
	 
	
    sup_μ̃_j ∈Λ̃(r(f_n,μ̃_j^n) -H(μ̃_j^n))=∞,

	which concludes the result considering that Λ̃⊂Λ_f.
 








 §.§ Theorem <ref>





Without loss of generality,  in this section we assume that 𝒳 is the integer set ℕ∖{ 0}.  

To organize the proof, we first introduce some definitions and a series of important results that will be used in the main argument.


  §.§.§ Preliminaries




 <cit.>
	For a non-negative function f: 𝒳→ℝ^+, the hazard function of Λ_f is given by 
	
    h_f(u)     - lnF̅_f(u)
 
	for all u ∈𝒳.


<cit.>
The continuous extension of (h_f(u))_u ∈𝒳 
to the positive real line ℝ^+ is defined by means of the following linear interpolation[This idea was proposed by Bontemps et al. <cit.> following Anderson <cit.>.]:  

    h̃_f(kλ + (1-λ)(k+1)) λ h_f(k) + (1-λ) h_f(k+1)
 
for  k∈𝒳 and for all λ∈ [0,1).  


Consistently with (h̃_f(x))_x≥ 0,  in Def.<ref>, it is possible to extend (F_f(u))_u∈𝒳 to ℝ^+ using the 
relationship expressed in Def. <ref>: 


Given f: 𝒳→ℝ^+, the continuous extension of (F_f(u))_u∈𝒳 using (h̃_f(x))_x≥ 0 (Def. <ref>) is denoted by (ℱ_f(x))_x≥ 0 and called the smoothed envelope distributions of Λ_f. 


<cit.>

Under the setting of Def. <ref>, a function U_f: [1,∞]  ⟶ℝ can be defined 
as the solution of:

    U_f(t) ℱ^-1_f (1 - 1/t),

for all t≥ 1. 




	Let (f(x))_x∈𝒳 be non-negative and in ℓ_1(𝒳).  A non-decreasing continuous function can 
	be obtained as[See Eq.(<ref>).]: 
	
	
    l_f(1/ϵ) ∫^1/ϵ^2_1U_f(x)/2x∂ x,
 
	for any ϵ>0. 



	Let  (ϵ_f,n)_n≥ 1 be the sequence obtained as the solution (point-wise) of:  l_f(1/ϵ)=nϵ^2/8 for all n.


We are in the position to state two instrumental results: 
 <cit.> 
	Let {Λ^n_f, n≥ 1 } be the envelope collection of stationary and memoryless sources with f∈ℓ_1(𝒳) and tail function (F̅_f(u))_u∈𝒳. Then for any n≥ 1
	
	
    R^+(Λ_f^n) ≤inf_u≥ 1[ n F̅_f(u) log (e) + u-1/2·log n ] +2.



 <cit.> 
	Under the setting of Lemma <ref>, there is a sequence (ξ_n)_n being o(1) (and function of f) 
	such that:[Remarkably, it has been shown in <cit.> that this closed-form lower bound captures the precise asymptotic of the information radius of the envelope class, meaning that: lim_n →∞ R^+(Λ_f^n)/log (e) ∫_1^n U_f(x)/2x∂ x=1.]
	
	
    R^+(Λ_f^n) ≥ (1+ ξ_n) log (e) ∫_1^n U_f(x)/2x∂ x,  for all n≥ 1.



We also use results from the seminal work of Haussler and Opper <cit.> that we summarize here: 


	For any μ_1, μ_2 ∈𝒫(𝒳), the  Hellinger distance  is given/denoted by: d_h(μ_1.μ_2)^2 ∑_x∈𝒳 (√(f_μ_1(x))- √(f_μ_2(x)))^2.



  <cit.>
	For Λ⊂𝒫(𝒳) and ϵ>0,  let 𝒟_ϵ(Λ) be the smallest  cardinality of a partition of Λ, whose cells have a diameter smaller or equal then ϵ (with respect to d_h in 𝒫(𝒳)) or it  is infinity if no finite partition satisfies the diameter condition. Then, the metric entropy of Λ is given by: 
	
	
    ℋ_ϵ(Λ) ln (𝒟_ϵ(Λ)).
 

The following important results can be stated:


<cit.>
	
	Let us assume that Λ⊂𝒫(𝒳) is totally bounded, i.e., ℋ_ϵ(Λ)< ∞ for all ϵ>0.  
	Then, for all n≥ 1, 
	
	
    R^+(Λ^n) ≥log (e) ·sup_ϵ>0min{ℋ_ϵ(Λ),nϵ^2/8} -1.





From Lemma <ref>,  if we let ϵ^*_Λ,ninf{ϵ>0: ℋ_ϵ(Λ) ≤nϵ^2/8}, we have that ∀ n≥ 1:


    R^+(Λ^n) ≥log (e) ·ℋ_ϵ^*_Λ,n(Λ)-1,

and,  consequently, 

    liminf_n →∞ R^+(Λ^n)/log (e) ℋ_ϵ^*_Λ,n(Λ) ≥ 1.
 

It is worth noting that the metric entropy lower bound for the information radius stated in Corollary <ref> is asymptotically tight under a slowly variant condition on the behaviour of ℋ_ϵ(Λ) as ϵ goes to zero <cit.>.[More details are presented in  <cit.>.]

Importantly for envelope families,  when f∈ℓ_1(𝒳) the asymptotic of the metric entropy of  Λ_f,  
i.e., lim_ϵ→ 0ℋ_ϵ(Λ_f),  is known. More precisely, Bontemps et al.<cit.> have shown that


    ℋ_ϵ(Λ_f)= (1+o_f(1)) ∫_1^1/ϵ^2U_f(x)/2x∂ x

as ϵ tends to 0. 






  §.§.§ Proof of Theorem <ref>— Regime of Gain in Minimax Redundancy






Let us assume
that (k_n)_n is o(u^*_f(n)). This part derives directly from the tight lower and upper bounds  developed by Bontemps et al. <cit.> and Boucheron et al. <cit.> for the case of summable envelopes.  In particular, from Lemmas <ref> we have 
that 


    R^+(Λ_f^n)    ≤[ n F̅_f(u^*_f(n)) log (e) + u^*_f(n)-1/2log n ] +2 
       ≤  2+ log (e) + u^*_f(n)-1/2log n.

On the other hand,  it has been shown that [Notice that: ∫_1^n  U_f(x)/2x ∂ x=1/2∫_0^ln n U_f(e^y) ∂ y ≥U_f(n)ln n/4, the last inequality from the concavity and positivity of U_f(e^y) shown in <cit.>. On the other hand,  from their definitions ∀ n∈𝒳,  u^*_f(n)-1 ≤ U_f(n) < u^*_f(n).]
	
    ∫_1^n U_f(x)/2x∂ x ≥U_f(n)log n/4≥ (u^*_f(n)-1)/4log n.

Consequently, from Lemma <ref> we have that eventually with n:


    (1+ ξ_n)    (u^*_f(n)-1) /4log n	≤ R^+(Λ_f^n) 
       ≤ 2+ log (e) + (u^*_f(n)-1)/2log n,

which means that (R^+(Λ_f^n))_n≈ (u^*_f(n) log n). 

Moreover, it is well-known that <cit.>:


    R^+(Λ_f^n, σ(π̃_k_n)) ≤ R^+(𝒫^n(k_n)) ≤k_n-1/2log n + K,

for some K>0, where  𝒫(k_n) is a short-hand for the collection all probabilities defined on the finite alphabet Γ_k_n, i.e., the simplex of dimension k_n-1. Consequently, under the assumption that (k_n)_n is o(u^*_f(n)),  from (<ref>) and (<ref>) it follows that: 


    lim_n →∞R^+(Λ_f^n, σ(π̃_k_n))/R^+(Λ_f^n) =0.

 






  §.§.§ Proof of Theorem <ref> — Regime of No-gain in Minimax Redundancy


Let us assume that (k_n)_n ≥ (u^*_f(n))_n eventually with n.  Here we  adopt results from the seminal work of Haussler and Opper <cit.> that offers a lower bound for the mutual information and consequently,  the channel capacity that corresponds to the information radius of a family of distributions <cit.>. 

However in our problem, 
we have a dynamic collection of distributions, explained 
by the process of projecting Λ_f into the dynamic collection of sub-sigma fields {σ(π̃_k_n): n≥ 1}.  More precisely, and adopting the notation introduced  in Section <ref>, we have the collection of distributions:  


    Λ_f^n/σ(π̃_k_n)    {μ^n/σ(π̃_k_n×⋯×π̃_k_n):μ∈Λ_f }
       ⊂𝒫(𝒳^n, σ(π̃_k_n×⋯×π̃_k_n)),

for all  n≥ 1, where μ/σ(π){μ(𝒜): 𝒜∈σ(π)}∈𝒫(𝒳, σ(π)) denotes the probability μ  restricted to the sub-sigma field induced by π and  𝒫(𝒳, σ) denotes the collection of probabilities restricted to the events of the sub-sigma field σ⊂ℬ(𝒳). Furthermore, associated to π̃_k_n= {𝒜_k_n,i: i=1,..,k_n} there is a lossy mapping  ϕ_n: 𝒳^n ⟶Γ_k_n where ϕ_n^-1(i)=𝒜_k_n,i for i∈Γ_k_n.  
Consequently through ϕ_n,  every μ∈𝒫(𝒳) induces a probability in Γ_k_n, which we denote by  ρ_μ,k_n∈𝒫(Γ_k_n), by the standard construction: ρ_μ,k_n(B)=μ(ϕ_n^-1(B)) for all B⊂Γ_k_n.  Note that ρ_μ,k_n is fully characterized by its pmf f_ρ_μ,k_n(i)=ρ_μ,k_n( { i })=μ(𝒜_k_n, i), ∀ i ∈Γ_k_n, where we have that  f_ρ_μ,k_n(i)=f_μ(i) if i<k_n and f_ρ_μ,k_n(k_n)=1-μ(Γ_k_n-1).

By letting 


    Λ̃_f,k_n{ρ_μ,k_n:μ∈Λ_f }⊂𝒫(Γ_k_n),
  
from (<ref>) we have that:


    R^+(Λ^n_f, σ(π̃_k_n)) =  R^+(Λ̃^n_f,k_n).

Consequently, the problem reduces to characterize the information radius of a family of dynamic distributions 
{Λ̃^n_f,k_n, n≥ 1 } (defined on a dynamic alphabet whose size grows with the block-length). Using the envelope conditions of Λ_f and Lemma <ref> in Section <ref>, it is simple to show that Λ̃_f,k_n satisfies an envelope condition on 𝒫(Γ_k_n), which is expressed in (<ref>). 


Then, if we consider the extended (over the integer) finite size envelope function f̃_k_n:𝒳⟶ℝ^+ given by: f̃_k_n(i) f(i) for i=[1:k_n-1], f̃_k_n(k_n) F̅_f(k_n-1) and f̃_k_n(i)  0 for i>k_n, 
Λ̃_f,k_n is equivalent to Λ_f̃_k_n⊂𝒫(𝒳) and thus, 


    R^+(Λ^n_f, σ(π̃_k_n)) =  R^+(Λ̃^n_f,k_n) = R^+( Λ^n_f̃_k_n),  ∀ n≥ 1.

Therefore, studying the minimax redundancy gain reduces to analyze the family of envelope distributions of finite size {Λ_f̃_k_n: n≥ 1 }, where supp(f̃_k_n) ⊂Γ_k_n by construction. 
If we consider, 


    ϵ^*_n,kinf{ϵ>0: ℋ_ϵ(Λ_f̃_k_n) ≤nϵ^2/8},

the straight adoption of Lemma <ref> in this dynamic context implies that 


    R^+( Λ^n_f̃_k_n) ≥log (e) ·ℋ_ϵ^*_n,k_n(Λ_f̃_k_n)-1
 
for all n and, consequently, 


    lim inf_n ⟶∞ R^+( Λ^n_f̃_k_n) ≥log (e) ·lim inf_n ⟶∞ℋ_ϵ^*_n,k_n(Λ_f̃_k_n)-1.
 
Following the approach proposed by Haussler et al. <cit.>, the idea is to obtain a tight approximation (ideally in closed-form) of the RHS of (<ref>), assuming that the function ℋ_ϵ^*_n,k_n(Λ_f̃_k_n) is 
asymptotically  lower bounded by a continuous non-decreasing function. 
With that objective in mind, the following important result (Theorem <ref> below) can be obtained.
For the statement of this result, the following definition is needed:




	Given (f(x))_x∈𝒳, non-negative and in ℓ_1(𝒳),  and a sequence of positive integers (k_n)_n, we say that (ϵ_n)_n ∈ (ℝ^+∖{ 0})^ℕ is admissible for (k_n)_n given Λ_f if
	
	
    F̅_f(k_n-1) ≤ϵ^2_n/16

	holds eventually (with n). 






Let us consider 
Λ_f ⊂𝒫(𝒳),  with f ∈ℓ_1(𝒳) and supp(f)=𝒳,  and a sequence of non-decreasing positive integers (k_n)_n such that (1/k_n)_n is o(1).

If (ϵ_f,n)_n (see Def. <ref>) is admissible for (k_n)_n given Λ_f (see Def. <ref>) 
then 

    lim inf_n →∞R^+( Λ^n_f̃_k_n)/log (e) ·∫^n_1U_f(x)/2x∂ x≥ 1




The proof of Theorem <ref> is presented in Section <ref>.

 

In general we have that  


    R^+( Λ^n_f̃_k_n) = R^+( Λ^n_f, σ(π̃_k_n)) ≤ R^+(Λ^n_f),

 the last inequality from (<ref>). On the other hand, it is known from <cit.>  
 that there is a sequence (a_n)_n being o(1)  where eventually in n
 
 
    R^+(Λ^n_f)   ≤ (1+a_n) log (e) · l_f(√(n)) 
       =(1+a_n) log (e) ·∫^n_1U_f(x)/2x∂ x.

Consequently, under the assumptions of  Theorem <ref> it follows directly from this result 
and (<ref>) that


    lim_n →∞R^+(Λ^n_f̃_k_n)/R^+(Λ^n_f)=1.



Returning to the proof, from  Theorem <ref>, Definition <ref> and Remark <ref>,  a sufficient condition to obtain (<ref>) (i.e., no gain in minimax redundancy) is that (√(F̅_f(k_n)))_n ≪ (ϵ_f,n)_n (see some remarks about this in Lemma <ref>, Section <ref> below). Furthermore from the proof of Theorem <ref>, we have that (ϵ_f,n) = (√(8/n · l(1/ϵ_f,n)))_n ∼ (√(8/n · l_f(√(n))))_n = (√(8/n ·∫_1^n U_f(x)/2x∂ x))_n, where it is known that ∫_1^n U_f(x)/2x∂ x≥U_f(n) ln n/4 <cit.>. 

From the main assumption,  which consider that there is N_o>0 such that ∀ n  ≥ N_o, k_n ≥ u^*_f(n), we note that

    ( F̅_f(k_n)/(ϵ_f,n)^2)_n  ∼( n ·F̅_f(k_n)/∫_1^n U_f(x)/2x∂ x)_n,
 
where for the second series we have that:

rCl 
	n ·F̅_f(k_n)/∫_1^n U_f(x)/2x ∂x    ≤    4 n ·F̅_f(k_n)/U_f(n) lnn 

	   ≤    4 n ·F̅_f(u^*_f(n))/U_f(n) lnn 

	   <     4/U_f(n) lnn ⟶0.  

The strict inequality in (<ref>) is by definition of u^*_f(n) in (<ref>), where 1/n ∈ (F̅_f(u^*_f(n)), F̅_f(u^*_f(n)-1)].  The last convergence in the RHS of (<ref>) is from the fact that  U_f(n)∈ [u^*_f(n)-1, u^*_f(n)) →∞ as n tends to infinity,  this follows from (<ref>) and the non-trivial assumption that | supp(f) | =∞.  

In summary, from (<ref>) we have that  (√(F̅_f(k_n)))_n ≪ (ϵ_f,n)_n, then Theorem <ref> and its corollary in  (<ref>) implies that lim_n →∞R^+(Λ^n_f̃_k_n)/R^+(Λ^n_f)=1. 
This last limit and the equalities in (<ref>) conclude the proof. 
 








 §.§ Theorem <ref>


To organize the proof of Theorem <ref>,  we present first two instrumental results: 

The first result is a simple extension of <cit.>:



	Let us consider the  dynamic collection of distributions {Λ_f̃_k_n: n≥ 1 } presented in (<ref>) where f∈ℓ_1(𝒳), and let (k_n)_n  be a non-decreasing sequence of integers. In addition, let l: ℝ^+ →ℝ^+ be a strictly increasing and unbounded continuous function. Let us denote by (ϵ_l.n)_n the solutions to the expression: l(1/ϵ)= n ϵ^2/8 for all n. 
	If there is a sequence (ϵ_n)_n such that:  
	
	
	
  * (ϵ_n)_n ≤ (ϵ_l.n)_n holds eventually with n, and 
	
	
  * lim inf_n →∞ℋ_ϵ_n( Λ_f̃_k_n)/l(1/ϵ_n)≥ 1,
	 
	then[In particular, if  lim inf_n →∞ℋ_ϵ_l,n( Λ_f̃_k_n)/l(1/ϵ_l,n)≥ 1 then lim inf_n →∞R^+( Λ^n_f̃_k_n)/log (e) · l(1/ϵ_l,n)≥ 1.] 
	
	
    lim inf_n →∞R^+( Λ^n_f̃_k_n)/log (e) · l(1/ϵ_n)≥ 1.
 



The proof is presented in Section <ref>.


The second result characterizes a sufficient condition on (ϵ_n)_n, function of (k_n)_n, i.e., the size sequence of tail based partitions, where the metric entropy of our collection of envelope distributions shares the same asymptotic than the unconstrained family determined in (<ref>).



	Let us consider a sequence of non-negative integer (k_n)_n and a sequence of non-negative reals (ϵ_n)_n, where (1/k_n)_n is  o(1) and (ϵ_n)_n is o(1).
	If f ∈ℓ_1(𝒳) and (ϵ_n)_n is admissible for (k_n)_n given Λ_f (see Def. <ref>)
	then  
	
    ℋ_ϵ_n(Λ_f̃_k_n)=(1+a_n) ∫_1^1/ϵ_n^2U_f(x)/2x∂ x
 
	for a 
	sequence (a_n)_n being o(1), and consequently,
	
	
    lim_n →∞ℋ_ϵ_n(Λ_f̃_k_n)/l_f(1/ϵ_n)= lim_n →∞ℋ_ϵ_n(Λ_f̃_k_n)/ℋ_ϵ_n(Λ_f)=1 ,

	where l_f(1/ϵ)=∫_1^1/ϵ^2U_f(x)/2x∂ x for ϵ>0 (see Def. <ref>). 


The proof of this result is presented in Section <ref>.



Comments on Lemma <ref>:



	
  * Lemma <ref> establishes concrete sufficient conditions where (ℋ_ϵ_n(Λ_f̃_k_n))_n has the same asymptotic than the metric entropy of the unconstrained family (ℋ_ϵ_n(Λ_f))_n, which is ∼ (∫_1^1/ϵ^2_nU_f(x)/2x∂ x)_n
		from (<ref>). 
	
  * The proof of this result follows the volume comparison arguments proposed by Bontemps in <cit.>. 
	
  * Note that  if 
	lim_n →∞F̅_f(k_n)/ ϵ^2_n=0 implies that (ϵ_n)_n is admissible for (k_n)_n given Λ_f. 
	
  * Given (k_n)_n and f, √(F̅_f(k_n)) offers a lower bound on the admissible regime for (ϵ_n)_n (see Def.<ref>). 
	
  * If (k̃_n)_n ≫  (k_n)_n, i.e.,  k_n/k̃_n → 0 as n→∞, then from Definition <ref> 
	(k̃_n)_n offers a bigger admissible range for the (ϵ_n)_n  
	than its counterpart for (k_n)_n.  
 


Finally, as the asymptotic of the metric entropy in (<ref>) offers a tight lower bound to the information radius of envelope families <cit.>,  Lemma <ref> in conjunction with Lemma <ref>  provide the mean to characterize a regime of no gain in minimax redundancy as presented in the proof of Theorem <ref> below.  

Proof of Theorem <ref>:



	Using the hypothesis that (ϵ_f,n)_n is admissible for (k_n)_n  given Λ_f, we have from Lemma <ref> that as n goes to infinity:
	
	
    ℋ_ϵ_f,n(Λ_f̃_k_n) ≥ (1+o(1))  · l_f(1/ϵ_f,n),

	which implies that 
	rCl
	lim inf_n →∞ ℋ_ϵ_f,n(Λ_f̃_k_n)/l_f(1/ϵ_f,n)    ≥    1.
		
	Note that l_f(x)=∫_1^x^2U_f(x̅)/2x̅∂x̅ on [1,∞) (Def.<ref>) is strictly increasing,  continuous and unbounded, consequently applying Lemma <ref> it follows that:
	
	
    lim inf_n →∞R^+( Λ^n_f̃_k_n)/log (e) · l_f(1/ϵ_f,n)≥ 1
    ⇔   lim inf_n →∞R^+( Λ^n_f̃_k_n)/log (e) · n ϵ^2_f,n/8≥ 1,

	where the last identity follows from the definition of ϵ_f,n in Def. <ref>.
	
	At this point we use the result in <cit.> that shows 
	that the function (l_f(x)) is very slowly variant <cit.>, in the sense that ∀η≥ 0 and κ>0, 
	
	
    lim_x →∞l_f(κ  x l_f(x)^η)/l_f(x)=1.

	This slowly variant condition implies that (ϵ_f,n)_n, as a (point-wise) solution of the condition l_f(1/ϵ)=n ϵ^2/8,  
	satisfies asymptotically (the argument  is presented in  the proof of <cit.>) that: 
	
	
    ( ϵ_f,n^2/8 )_n ∼( l_f(√(n))/n)_n = ( 1/n∫_1^nU_f(x)/2x∂x̅) )_n.

	Consequently  (<ref>) and (<ref>) prove the result. 
 






 §.§ Proof of Lemma <ref>



	From Lemma <ref> it follows that R^+( Λ^n_f̃_k_n)/l(1/ϵ_l,n)≥ 
	
	
    log (e) min{ℋ_ϵ_l,n (Λ_f̃_k_n)/l(1/ϵ_l,n),nϵ^2/8 · l(1/ϵ_l,n)} -1/l(1/ϵ_l,n),
       = log (e) min{ℋ_ϵ_l,n (Λ_f̃_k_n)/l(1/ϵ_l,n), 1 } -1/l(1/ϵ_l,n)

	for all n. 
	As (ϵ_l,n) ≥ (ϵ_n), without loss of generality we assume that there is a mapping 
	τ:ℕ⟶ℕ such that ϵ_l,n=ϵ_τ(n) for every  n, 
	where τ(n) ≤ n eventually with n. From construction (ϵ_l,n) is o(1) and thus, 
	l(1/ϵ_l,n) ⟶∞. Then,
	
	rCl
		   lim    inf_n ⟶∞ R^+( Λ^n_f̃_k_n)/l(1/ϵ_l,n) ≥log(e) min{ lim inf_n ⟶∞ ℋ_ϵ_τ(n) (Λ_f̃_k_n)/l(1/ϵ_τ(n)), 1 }

		   =    log(e) ·min{ lim inf_n ⟶∞ ℋ_ϵ_n ( Λ_f̃_k_τ^-1(n) )/l(1/ϵ_n), 1 } 

		
		   ≥    log(e) ·{ lim inf_n ⟶∞ ℋ_ϵ_n ( Λ_f̃_k_n )/l(1/ϵ_n), 1 } 

		
		   ≥    log(e),
	
	where the  inequality in (<ref>) follows from the fact that ℋ_ϵ( Λ_f̃_k) ≤ℋ_ϵ( Λ_f̃_k̅) if k̅≥ k and that  τ^-1(n) ≥ n, and (<ref>) from the main hypothesis of Lemma <ref>.







 §.§ Proof of Lemma <ref>





Following the lower bound for 𝒟_ϵ(Λ_f) elaborated in <cit.>, 
which is based on a  covering argument and volume based inequality, 
we have that  for all m≥ 1  and any arbitrary k such that m+l_f ≤ k (see Def. <ref>), 

rCl
	𝒟_ϵ(Λ_f̃_k)     ≥   Vol ( ∏_i=l_f+1^l_f+m [0,√(f̃_k(i))] )/Vol ( ℬ_m(ϵ) )

	    =    ∏_i=l_f+1^l_f+m √(f̃_k(i) ) /ϵ^m Vol(ℬ_m), 

where ℬ_m(ϵ) denotes the ball in ℝ^m of radius ϵ, and ℬ_m ℬ_m(1).

If we consider 


    N_ϵinf{m≥ 1: F̅_f(m) <  ϵ^2/16}

 and let Ñ^k_ϵmin{ N_ϵ , k }, and we evaluate (<ref>) with m=Ñ^k_ϵ - l_f  it follows that  


    ℋ_ϵ(Λ_f̃_k) = ln𝒟_ϵ (Λ_f̃_k)  ≥
       ∑_i=l_f+1^Ñ^k_ϵln√(f̃_k(i)) - lnVol (ℬ_Ñ^k_ϵ-l_f) -   (Ñ^k_ϵ-l_f) ln 1/ϵ.

On the other hand,  we can adopt the upper bound in <cit.> that is based on another 
volume comparison argument, leading to 

rCl
	𝒟_ϵ(Λ_f̃_k)    ≤    Vol (∏_i=1^Ñ^k_ϵ [-ϵ/8, √(f̃_k(i)) + ϵ/8] )/Vol(ℬ_Ñ^k_ϵ(ϵ/8) )  

	   =   ∏_i=1^Ñ^k_ϵ (√(f̃_k(i)) + ϵ/4)/ (ϵ/8)^Ñ^k_ϵ ·Vol(ℬ_Ñ^k_ϵ).

This inequality reduces to <cit.>

rCl
	ℋ_ϵ(Λ_f̃_k)    ≤   ∑_i=1^l_f ln(√(f̃_k(i)) + ϵ/4) + ∑_i=l_f+1^Ñ^k_ϵ ln(√(f̃_k(i))) 

	   -    ln( Vol (ℬ_Ñ^k_ϵ) ) + Ñ^k_ϵ-l_f/√(1-e^-b) + Ñ^k_ϵln8/ϵ,

for b=-lnF̅(l_f)>0.

	If we consider the regime where N_ϵ< k, then it follows that  N_ϵ=Ñ^k_ϵ and  { l_f+1,…,N_ϵ}⊂{1,…,k-1}. Therefore f̃_k(i)=f(i) for all i∈{ l_f+1,..,N_ϵ}. In this scenario, we have that:
	
	
    ℋ_ϵ(Λ_f̃_k)    ≥∑_i=l_f+1^N_ϵln√(f(i)) - lnVol (ℬ_N_ϵ-l_f) 
       -   (N_ϵ-l_f) ln 1/ ϵ

	and
	
    ℋ_ϵ(Λ_f̃_k)    ≤∑_i=1^l_fln (√(f(i)) + ϵ/4) + ∑_i=l_f+1^N_ϵln (√(f(i))) 
       - ln( Vol (ℬ_N_ϵ) ) + N_ϵ-l_f/√(1-e^-b) + N_ϵln 8/ϵ.

	We point out that the RHS expression of (<ref>) and  (<ref>) are the very same lower and upper bounds derived in <cit.> for ℋ_ϵ(Λ_f), respectively. 
	Consequently in this regime, we obtain the lower and upper bound expressions of the unconstrained (i.e., lossless) problem.
	
	By definition N_ϵ< k is equivalent to the condition that  F̅_f(k-1) ≤ϵ^2/16.  Using the hypothesis that (k_n) and (ϵ_n) are such that  the condition in Eq.(<ref>) (in Def.<ref>) 
	is satisfied eventually with n, it follows that
	
	
    lim inf_n →∞ℋ_ϵ_n(Λ_f̃_k_n) ≥
       lim inf_n →∞{∑_i=l_f+1^N_ϵ_nln√(f(i)) - lnVol (ℬ_N_ϵ_n-l_f). 
       .-   (N_ϵ_n-l_f) ln1/ϵ_n},

	and
	
    lim sup_n →∞ℋ_ϵ_n(Λ_f̃_k_n) ≤
       lim sup_n →∞{∑_i=1^l_fln(√(f(i)) + ϵ/4) + ∑_i=l_f+1^N_ϵln(√(f(i))). 
       .- ln( Vol (ℬ_N_ϵ) ) + N_ϵ-l_f/√(1-e^-b) + N_ϵln8/ϵ}.



To conclude, it has been shown in <cit.> that  the RHS of both (<ref>) and (<ref>) behaves asymptotically  as (1+o(1))∫_1^1/ϵ^2U_f(x)/2x∂ x when ϵ goes to zero. Consequently given that by hypothesis ϵ_n ⟶ 0,  this fact implies that  ℋ_ϵ_n(Λ_f̃_k_n)=(1+o(1)) ∫_1^1/ϵ_n^2U_f(x)/2x∂ x  as n tends to infinity. Finally  (<ref>) follows from (<ref>), (<ref>) and <cit.>.






§ SUPPORTING RESULTS





 §.§ Proof of Lemma <ref>



	Let first prove the sufficient condition. Let us assume that {π_n: n≥ 1 }
	is asymptotically sufficient for μ. The induced distortion is given by 
	
	
    d(ϕ_n, ψ_n,μ^n) = ∑_x∈𝒳f_μ(x) ·ρ (x,ψ_n(ϕ_n(x)))_ g_n(x) .

Considering that μ(limsup_nπ_n(x))= f_μ(x) for all x∈supp(μ), then it follows 
that lim_n →∞ψ_n(ϕ_n(x)))=x, μ-almost everywhere and lim_n →∞g_n(x)=0, μ-almost surely. Furthermore,  g_n(x) is a bounded function by definition, then the bounded convergence theorem <cit.> implies that lim_n →∞∫_𝒳 g_n(x)dμ(x)=0 ⇔lim_n →∞ d(ϕ_n, ψ_n,μ^n)=0.

For the converse, let us assume that ∩_n≥ 1∪_m≥ nπ_m(x) ≠{x }, μ-almost surely. In other words, ∃ x,x_o∈supp(μ) with x≠ x_o such that {x,x_o}⊂lim_n →∞∪_m≥ nπ_m(x). Consequently, there exists N such that for all n≥ N, d(ϕ_n, ψ_n,μ^n) ≥min{f_μ(x), f_μ(x_o) }·min{ρ(x,x_o), ρ(x_o,x) } >0. 






 §.§ Proof of Lemma <ref>


For the proof we need the following definitions: 

	Let us consider μ∈𝒫(𝒳) and a function g:𝒳→ℝ. 
	g is said to be integrable with respect to μ if ∑_x∈𝒳|  g(x) |   f_μ(x) < ∞. 
	Finally, ℓ_1(μ) denotes the collection of all integrable functions with respect to μ. 



	Let us consider: 
	
	
    H(μ) - H_σ(π_n) (μ) = ∑_x∈𝒳 f_μ(x) ·logμ(π_n(x))/f_u(x)_g̃_n(x) .

From the assumption that H(μ)<∞, then g̃_n(x) ∈ℓ_1(μ). Furthermore, under
the assumption that {π_n:n ≥ 1 } is asymptotically sufficient, we have that lim_n →∞μ(π_n(x))=f_μ(x) for all x∈supp(μ) and thus, lim_n →∞g̃_n(x) = 0 μ-almost everywhere. 
Finally considering that g̃_n(x) ≤log  1/f_μ(x) ∈ℓ_1(μ), the dominated convergence theorem 
implies that lim_n →∞∑_x∈𝒳 f_μ(x) ·g̃_n(x)=0.






 §.§ Proof of Proposition <ref>:
 


The argument reduces to verify the achievability of the entropy using a two-stage lossy construction.   
For that we consider the tail partition 


    π_n={{1 },…,{n }, {n+1,…,}},

associated to ϕ_n(x)=x if x∈{1,..,n} and otherwise ϕ_n(x)=0. 
It is simple to verify that this scheme satisfies the zero distortion condition. 
For the lossless coding of Y^n=Φ_n(X^n)∈{0,1,…,n}^n, we can 
consider the prefix-free Shannon code <cit.>, whose rate is at most two bits away from the 
entropy of  Y^n.  Hence,  there is 𝒞_n:{0,1,..,n}^n ⟶{ 0,1}^*
such that: 

    r(ϕ_n, 𝒞_n, μ^n) ≤H(Y^n) +1/n = H_σ(π_n)(μ) +1/n,

which suffices to show that 

    lim sup_n ⟶∞ r(ϕ_n, 𝒞_n, μ^n) ≤ H(μ),

and therefore R_al(μ) ≤R̅_al(μ)≤ H(μ).





 §.§ Proof of Lemma <ref>



	First, it is direct to show that {v_μ: μ∈Λ_f }⊂Λ̃_f̃. 
	
	 Then, it remains to prove that for any v∈Λ̃_f̃  there is μ∈Λ_f
	such that v_μ=v, in total variations. Let us fix an arbitrary i∈ℐ.  
	
	If we first assume that  | 𝒜_n,i|< ∞,  we propose the following  approach: 
	
	
    x̂_1=min_x∈𝒜_n,i f(x),      ŵ_x_1 =f(x̂_1)/∑_x∈𝒜_n,if(x),
       x̂_2=min_x∈𝒜_n,i∖{x̂_1 } f(x),     ŵ_x_2 =f(x̂_2)/∑_x∈𝒜_n,if(x),
       ,… ,

	where finally  x̂_| 𝒜_n,i|∈𝒜_n,i∖{x̂_i:i=1,…, | 𝒜_n,i|-1 }      and  ŵ_x_| 𝒜_n,i| =f(x̂_| 𝒜_n,i|)/∑_x∈𝒜_n,if(x). With this we define μ( {x̂_i })=ŵ_x_1· v({ i } ) for each i∈{1,…, | 𝒜_n,i| }. Note that μ( {x̂_i }) ≤ f( x̂_i )  and ∑_x∈𝒜_n,i f_μ(x)=v({ i } ) by construction. 
	
	If | 𝒜_n,i|= ∞ and ∑_x∈𝒜_n,if(x) < ∞, we can follow the same inductive approach than in (<ref>) to construct μ({ x}) for all  x∈𝒜_n,i.  
	
	On the other hand, if | 𝒜_n,i|= ∞ and ∑_x∈𝒜_n,if(x) = ∞, then f̃(i)=1 by definition, and we can always  find μ_i ∈Λ_f such that supp(μ_i) ∈𝒜_n,i.  Then, we construct μ({x }) = μ_i (x) · v({ i }), where it is clear that μ(𝒜_n,i)=v({ i }) and  f_μ(x) ≤ f(x) for all x∈𝒜_n,i provided by  μ_i ∈Λ_f. 






 §.§ Proposition <ref>





	Let us consider a lossy code (f_n,g_n) and a family of distributions Λ⊂𝒫(𝒳). 
	If we denote by v_μ^n the probability in ℐ_n induced by μ^n∈Λ^n (the n-fold distributions with marginal in Λ) and ϕ_n, by v_μ^n({ i })=μ^n(ϕ_n^-1({ i })) ∀ i ∈ℐ_n,  then
	
	rCl
		R̅(Λ,f_n)    =       sup_μ∈Λ (r(f_n,μ^n) -1/nH_σ(π_n)(μ^n)) 

		   ≥   1/n R^+({v_μ^n: μ∈Λ}) 

		    =       1/n inf_v∈𝒫(ℐ_n) sup_μ∈Λ  𝒟(v_μ^n|v) 

		   =    1/n inf_v∈𝒫(𝒳^n) sup_μ∈Λ 𝒟_σ(π_n)(μ^n | v).
	



	By definition r(f_n,μ^n)=1/n𝔼_X^n_1∼μ^n{ℒ(𝒞_n(ϕ_n(X^n_1)))}.  Consequently,  if we let Y_n=ϕ_n(X^n) in ℐ_n we have that Y_n∼ v_μ^n, where 
	v_μ^n denote the probability induced by μ^n and ϕ_n in 𝒫(ℐ_n). We will consider r(𝒞_n, v_μ^n)= 𝔼_Y_n ∼ v_μ^n{ℒ(𝒞_n(Y_n))} =n · r(f_n,μ^n), and as r(𝒞_n, v_μ^n)≥ H(Y_n) <cit.>, 
	for the rest we  focus on a refined worst-case redundancy, attributed to the second stage of f_n, given by
	
	
    R̅(Λ, 𝒞_n) sup_μ∈Λ(r(𝒞_n, v_μ^n) - H(v_μ^n)).

	We note that H(v_μ^n) = H_σ(π_n)(μ^n), therefore R̅(Λ,f_n)= 1/nR̅(Λ, 𝒞_n). Considering (<ref>) we have that
	
	rCl
		R̅(Λ, 𝒞_n)    ≥   min_𝒞̃_n:ℐ_n  →{ 0,1}^* sup_μ∈Λ (r(𝒞̃_n, v_μ^n) - H(v_μ^n))

									   ≥    inf_v ∈𝒫(ℐ_n) sup_μ∈Λ 𝒟(v_μ^n | v) 

									   =    R^+({v_μ^n: μ∈Λ})

									   =    inf_v ∈𝒫(𝒳^n) sup_μ∈Λ 𝒟_σ(π_n)(μ^n | v).
	
	The first inequality in (<ref>) is because we are solving the least worst-case redundancy (fixing the first stage of f_n), the  second is from the tight connection between prefix-free mappings and probabilities in 𝒫(ℐ_n) and the role of the information divergence in lossless variable length prefix-free coding <cit.>, and the last equalities are from the definition of the induced probabilities in 𝒫(ℐ_n) and the identity in (<ref>).  We note that the expression in (<ref>) is the information radius of our n-fold family Λ^n projected into the sub-sigma field induced by π_n, i.e., first stage of f_n.

	


IEEEtran				
			

