Shannon Entropy Estimation in $\infty$-Alphabets from Convergence Results
Jorge F. Silva


 




Shannon Entropy Estimation in ∞-Alphabets from Convergence Results
    Jorge F. Silva josilva@ing.uchile.cl 

       Department of Electrical Engineering

       Information and Decision System Group

       University of Chile

       Santiago, Chile, Off. 508, Ph. 56-2-9784090 
       
    December 30, 2023
=============================================================================================================================================================================================================================




The problem of Shannon entropy estimation in countable infinite alphabets is addressed from the study and use of convergence results of the entropy functional,  which is known to be discontinuous  with respect to the total variation distance in ∞-alphabets. Sufficient conditions for the  convergence of the entropy are used,  including scenarios with both finitely and infinitely supported assumptions on the distributions. From this new perspective,  four plug-in histogram-based estimators are studied showing that convergence results are instrumental to derive new strong consistency and rate of convergences results.  Different scenarios and conditions are used on both the  estimators and the underlying distribution, considering for example  finite and unknown supported assumptions and summable tail bounded conditions. 



Shannon entropy, infinite alphabets, convergence properties, histogram-based estimators, data-driven partitions, Barron estimator.






§ INTRODUCTION


The problem of Shannon entropy estimation has a long history in information theory, statistics and computer science <cit.>. 
This problem belongs to the category of scalar functional estimation that has been richly studied in non-parametric statistics. Starting with the  finite size alphabet scenario,  the classical plug-in estimate (i.e., the empirical distribution evaluated on the functional) is well known to be consistent, minimax optimal and asymptotically efficient <cit.> when the number of samples n goes to infinity.
In the finite alphabet setting, more recent research has been interested in looking at the called large alphabet regime,  meaning a non-asymptotic under-sampling regime where the numbers of samples n is on the order of, or even smaller than, the size of the alphabet  denoted by k. In this 
context,  it has been shown that the classical plug-in estimator is sub-optimal as it suffers from severe bias <cit.>. 
For characterizing optimality in this high dimensional context,  a non-asymptotic minimax mean square error analysis under a finite n and k has been conducted by several authors <cit.> considering the minimax risk R^*(k,n)[R^*(k,n) = inf_Ĥ(·)sup_μ∈𝒫(k)𝔼_X_1,..X_n∼μ^n{( Ĥ(X_1,..,X_n) - H(μ) )^2 } where 𝒫(k) denotes the collection of probabilities on [k] ≡{1,..,k }.]. <cit.> first showed that it was possible to construct an entropy estimator that uses a sub-linear sampling size to achieve minimax consistency when k goes to infinity,  in the sense that there is a sequence (n_k)=o(k) where R^*(k,n_k) ⟶ 0 as k goes to infinity.  A 
set of results by <cit.> show that the optimal scaling of the sampling size with respect to k to achieve the aforementioned asymptotic consistency for entropy estimation is O(k/log(k)).  A refined set of results for the complete characterization of R^*(k,n),  the specific scaling of the sampling complexity, and  the achievability of the obtained minimax L_2 risk for the family {𝒫(k): k≥ 1} with practical estimators have been presented in <cit.>.


Contrasting this set of results, it is well-known that the equivalent problem of estimating the distribution consistently (in total variation) in finite alphabet requieres a sampling complexity that scales like O(k).  Consequently, the large alphabet results for entropy estimation 
show that the task of entropy estimation in finite alphabets is simpler than estimating the high dimensional distribution in terms of sampling complexity.  These findings are consistent with the observation that the entropy is a continuous functional of the space of distributions (in the total variational distance sense) for the finite alphabet case <cit.>. 





 §.§ Infinite Alphabets

In this work we are interested in the infinite alphabet scenario, i.e., on the
estimation of the entropy when the alphabet is countable infinite and we have a finite number of samples. 

This problem is an infinite alphabet regime as the size of the alphabet goes unbounded and n 
is kept finite for the analysis,  which contrasts with the large and finite alphabet regime elaborated above.  
As argued in <cit.>,  this is a challenging non-parametric learning problem  because some of the  finite alphabet properties of the entropy do not extend to this infinite dimensional problem.  


Notably, it has been shown that the Shannon entropy is not a continuous functional with respect to the total variational distance in infinite alphabets <cit.>. 
In  particular,  Ho et al.  <cit.> showed concrete examples where convergence in χ^2-divergence and in direct information  divergence  (I-divergence), 

both stronger than total variational convergence <cit.>, 
do not imply  convergence of the entropy functional. In addition, <cit.>   showed  the discontinuity  of the entropy with respect to the reverse  I-divergence <cit.>,  and consequently,  with respect to the total variational distance[The  distinction between reverse and direct I-divergence was pointed out in the work of Barron et al. <cit.>,  in the context of distribution estimation.]. 



In entropy estimation,  the discontinuity of the entropy with respect to the divergence implies that the minimax mean square error is  unbounded[ R^*_n = inf_Ĥ(·)sup_μ∈ℍ(𝕏) 𝔼_X_1,..X_n∼μ^n{( Ĥ(X_1,..,X_n) - H(μ) )^2 }=∞, where ℍ(𝕏) denotes the family of finite entropy distribution over the countable alphabet set 𝕏. The proof of this result  
follows from <cit.> and  the Le Cam's two point method <cit.>. The argument is presented in Appendix <ref>.]. Consequently, there is no universal minimax  consistent estimator (in the mean square error over sense) of the entropy over the family of finite entropy distributions.



Considering  a point-wise or sample wise convergence to zero of the estimation error (instead of the  worse case expected error analysis mentioned above), <cit.> showed the remarkable result that the classical plug-in estimate is strongly consistent and consistent in the mean square error sense for any finite entropy distribution, i.e., the simpler  and straightforward  plug-in estimator of entropy is universal, where convergence to the right limiting value is achieved almost surely despite  the discontinuity of the  entropy functional. Moving on the analysis of the (point-wise) rate of convergence of the estimation error,  they presented a finite length lower bound for this error of any arbitrary estimation scheme <cit.> showing as a corollary that no universal rate of convergence (to zero) can be achieved for entropy estimation in infinite alphabets <cit.>. Finally constrained the problem to a family of distributions with some specific power tail bounded conditions, <cit.> show a sharp finite length expression for the rate of convergence of the estimation error of the classical plug-in estimate.






 §.§ From convergence  to Entropy estimation

Considering the discontinuity of the entropy in ∞-alphabets, this work looks at the problem of point-wise almost sure entropy estimation from the new angle of  studying and applying some recent entropy convergence results and their derived bounds in ∞-alphabets <cit.>.
Entropy convergence results have stablished concrete conditions on both the limiting distribution μ and the way a sequence of distributions {μ_n: n≥ 0} convergence to μ such that  lim_n →∞  H(μ_n )=H(μ) is satisfied. The conjecture that motivates this research is that putting these conditions  in the context of a learning task,  i.e., where {μ_n: n≥ 0} is a random sequence of distributions driven by the classical empirical process,  will offer the possibility to study new family of plug-in estimates with the objective to derive new strong consistency and rate of convergence results under some regularity conditions on μ.  On the practical side, this work explores a data-driven histogram based estimator as a key case of study,  because this approach offers the flexibility to adapt to learning task when appropriate bounds for the estimation and approximation error are derived from the analysis of the problem. 

On the specifics, we begin revisiting the classical plug-in entropy estimator considering the un-explored and relevant scenario where μ (the data-generated distribution)  has a finite but arbitrary large and unknown support.  This was declared to be a challenging problem in <cit.> because of the discontinuity of the entropy.
Finite-length (non-asymptotic) deviation inequalities and intervals of confidence are derived
extending the results presented in <cit.>. Here it is shown that the classical 
plug-in estimate achieves optimal rates of convergences.  
Relaxing the finite support restriction on μ, we present two histogram-based plug-in estimates, 
one based on 
the celebrated Barron-Györfi-van der Meulen estimate <cit.>;
and the other on a data-driven partition of the space <cit.>. 
For the Barron plug-in estimate almost sure consistency is shown for entropy estimation and distribution estimation in direct I-divergence under some mild support conditions on μ.
On the other hand for the data-driven partition scheme,  we show that the estimator is strongly consistent distribution-free,  matching the universal result obtained for the classical plug-in estimate in <cit.>. Furthermore, new almost sure rate of convergence results (in the estimation error) are obtained for distributions with finite but unknown support and families of distributions with power and exponential tail dominating conditions. In this context, our result shows that this  adaptive scheme offers optimal and near optimal rate of convergences,  as it approaches arbitrary closely the rate of convergence O(1/√(n)) that is optimal for the finite alphabet problem <cit.>.

The rest of the paper is organized as follows.  Section <ref> introduces some basic concepts,  notation and summarizes the entropy convergence results used in this study. Sections <ref>, <ref> and <ref> state  the main results of this work. The main technical derivation are presented in Section <ref>, Finally summary and final discussion are given in Section <ref>. The proof of some technical auxiliary results are relegated to the Appendix section.





§ PRELIMINARIES


Let 𝕏 be a countably  infinite set, without loss of generality the integers, 
and let 𝒫(𝕏) denote the collection of probability measures 
in 𝕏. 
For μ and v in 𝒫(𝕏), 
and μ  absolutely continuous with respect to v (i.e., μ≪ v) [if  v(A)=0 implies that μ(A)=0 for any event A∈ℬ(𝕏).],  dμ/d v(x) denotes the  Radon-Nikodym (RN) derivative  of μ with respect to v. 
Every μ∈𝒫(𝕏) is absolutely continuous 
with respect to the counting measure λ (or the Lebesgue measure)[λ(A)=|A| for all A ⊂𝕏.], where its RN derivate is the probability mass function (pmf), 


f_μ(x)≡d μ/d λ(x)=μ({x}), ∀ x ∈𝕏.  

Finally for any μ∈𝒫(𝕏), A_μ≡{x∈𝕏:  f_μ(x) >0} denotes its support and


    ℱ(𝕏) ≡{μ∈𝒫(𝕏): λ(A_μ) < ∞}
  
denotes the collection of  probabilities with finite support.

Let μ and v in 𝒫(𝕏), the total variation distance of μ and v is 
given by <cit.>


    V(μ,v) ≡sup_A ∈ℬ(𝕏)|v(A)-μ(A)|,

where ℬ(𝕏) is a short-hand for the subsets of 𝕏. 
The Kullback-Leibler divergence or I-divergence of μ with respect to v is given by


    D(μ||v) ≡∑_x ∈ A_μ f_μ(x) logf_μ(x)/f_v(x),

when μ≪ v, and D(μ||v) is  set to infinite, otherwise <cit.>[The well-known Pinsker`s inequality offers a relationship 
between the I-divergence and the variational distance 
<cit.>:  
∀μ,v ∈𝒫(𝕏), 


	2 ln 2·  V(μ,v)^2 ≤ D(μ,v).

].

The Shannon entropy of μ∈𝒫(𝕏) is 
given by <cit.>: 


    H(μ) ≡  - ∑_x ∈ A_μ f_μ(x)  log f_μ(x).

In this context, it is useful to denote by ℍ(𝕏) ⊂𝒫(𝕏)
the collection of probabilities where (<ref>) is well defined,  by 
𝒜𝒞(𝕏|v) ≡{μ∈𝒫(𝕏):  μ≪ v }
the collection of measures absolutely continuous with respect to v ∈𝒫(𝕏), and  by 
ℍ(𝕏|v) ⊂𝒜𝒞(𝕏|v) the collection of probabilities 
where  (<ref>) is well defined for v∈𝒫(𝕏).

Concerning convergence,  a sequence {μ_n: n ∈ℕ}⊂𝒫(𝕏)  is said to converge in total variation to μ∈𝒫(𝕏) if 
 
 
    lim_n →∞  V(μ_n,μ)=0.

For countable alphabets,  <cit.>  shows that the convergence in total variation is equivalent to the weak convergence[{μ_n: n ∈ℕ}⊂𝒫(𝕏)  is said to converge  weakly to μ∈𝒫(𝕏) if for any bounded function g(·): 𝕏→ℝ,  lim_n →∞∑_x∈𝕏 g(x) f_μ_n(x)= ∑_x ∈𝕏g(x) f_μ(x).],
 which is denoted here by μ_n ⇒μ, and the point-wise convergence of the  pmf's.  
Furthermore from (<ref>),  the convergence in total variation implies the uniform convergence 
of the pmf's, i.e,   lim_n →∞sup_x ∈𝕏| μ_n({x})- μ({x})|=0.  Therefore in this countable case,  all the four previously mentioned notions of convergence are equivalent:  total variation; weak convergence; point-wise convergence of the pmf`s; 
and uniform convergence of the pmf's. 
 
We conclude with the convergence in I-divergence  introduced by 
<cit.>. We say that {μ_n: n ∈ℕ}
converges to μ in direct and reverse I-divergence if
lim_n →∞  D(μ || μ_n)=0 and lim_n →∞  D(μ_n || μ)=0, 
respectively.  From Pinsker's inequality, the convergence in 
I-divergence implies the  weak convergence in (<ref>), where
it is known that the converse 
is not  true <cit.>.




 §.§ Convergence results for the Shannon entropy


The discontinuity of the entropy rises the problem of finding conditions under which convergence of the entropy can be obtained 
in infinite alphabets. On this topic, Ho et al. <cit.> have studied the interplay between the entropy and the  total variation distance stipulating conditions for convergence  by assuming a finite support on the involved distributions.   On the other hand,  <cit.>  obtained convergence of the entropy by imposing a power dominating condition <cit.>  on the limiting probability measure μ, for all the sequences {μ_n: n≥ 0} converging in reverse I-divergence to μ <cit.>. More recently,   <cit.> have addressed the entropy convergence studying a number of new settings that involve  conditions on the limiting measure μ,  as well as the way the sequence {μ_n: n≥ 0} convergences to μ in the space of distributions.
This convergence results offer sufficient conditions where the entropy evaluated in a sequence of distribution convergences to the entropy of its limiting distribution and, consequently,  the possibility of applying these results when analyszng plug-in entropy estimator.  The results used in this work are summarized in the rest of this section.  







Let us begin with the case when μ∈ℱ(𝕏), i.e.,  
the support of the limiting measure is finite and unknown.  



 
Let us assume that μ∈ℱ(𝕏) and {μ_n: n ∈ℕ}⊂𝒜𝒞(𝕏|μ). 
	If μ_n ⇒μ,  then lim_n →∞  D(μ_n || μ)=0
	and lim_n →∞  H(μ_n )=H(μ).


This result is well-known because when A_μ_n⊂ A_μ for all n the scenario
reduces to the finite alphabet case, in which the entropy is known to be continuous 
<cit.>. 
Because  we obtain two inequalities used in the rest of the exposition,  a proof is provided here.

	μ and μ_n belong to ℍ(𝕏) from the 
	finite-supported assumption. The same reason can be used to show that 
	D(μ_n||μ)<∞,  since μ_n ≪μ for all n. Let us consider the following identity: 
	
	
    H(μ )- H(μ_n) = ∑_x ∈ A_μ (f_μ_n(x)-f_μ(x)) log f_μ(x) + D(μ_n||μ).

	The first term on the right hand side (RHS) of (<ref>) is upper bounded 
	by 𝐌_μ· V(μ_n,μ)  where
	
	
    𝐌_μ = log1/𝐦_μ≡sup_x ∈ A_μ| logμ({x})| < ∞.

	For the second term,  we have that
	
	
    D(μ_n||μ)    ≤log e ·∑_x ∈ A_μ_n   f_μ_n(x) |f_μ_n(x)/f_μ(x)-1| 
       ≤log e/𝐦_μ·sup_x∈ A_μ|f_μ_n(x) - f_μ(x)| 
    				      ≤log e/𝐦_μ· V(μ_n,μ).

	and, consequently,  
	
	
    |H(μ )- H(μ_n)| ≤[ 𝐌_μ+log e/𝐦_μ] · V(μ_n,μ).
 	


Under the assumptions of Proposition <ref>, we note that
the reverse I-divergence and  the entropy difference
are bounded by the total variation by  (<ref>) and (<ref>), respectively. Note however that these bounds are distribution dependent function of 𝐦_μ(𝐌_μ) in (<ref>).[It is simple to note that 𝐦_μ(𝐌_μ)<∞ if,  and only if, μ∈ℱ(𝕏).] The next result relaxes the assumption that  μ_n ≪μ 
and offers 
a necessary and sufficient condition for the convergence of the entropy.



 <cit.>
	Let μ∈ℱ(𝕏) and {μ_n: n ∈ℕ}⊂ℱ(𝕏).   	If 
	μ_n ⇒μ,  then
		there exists N>0 such that μ≪μ_n 
		∀ n≥ N,
		 and
		
		
    lim_n →∞  D(μ || μ_n)=0.

		
		Furthermore, lim_n →∞  H(μ_n )=H(μ), if and only if [μ(· |B) in (<ref>) denotes the conditional probability 
	of μ given the event B ⊂𝕏], 
		
		
    lim_n →∞μ_n (A_μ_n∖ A_μ)  · H(μ_n(· |A_μ_n∖ A_μ))=0  ⇔lim_n →∞∑_x∈ A_μ_n∖ A_μ f_μ_n(x) log1/f_μ_n(x)=0.


	Lemma <ref> tells us that  in order to achieve entropy convergence (on top of the weak convergence), it is necessary and sufficient to ask for a vanishing  expression (with n) of the entropy of μ_n restricted to the elements of the set A_μ_n∖ A_μ.  

	Two remarks about this result: 
	
	1) The convergence in direct I-divergence 
	does not imply the convergence of the entropy[Concrete examples are presented 
	in <cit.> and <cit.>.].
	2) Under the assumption that μ∈ℱ(𝕏),  μ is eventually 
	absolutely  continuous with respect to μ_n, and the convergence in total variations is equivalent to the convergence in direct I-divergence.
	






We conclude this section with the case when the support of μ is
infinite and unknown, i.e., |A_μ|=∞.  
In this context, we highlight two results:
 
 
<cit.> 
	Let us consider that  μ∈ℍ(𝕏) and  
	{μ_n: n≥ 0}⊂𝒜𝒞(𝕏|μ).
	If μ_n ⇒μ and 
	
	
    M ≡sup_n≥ 1sup_x∈ A_μf_μ_n(x)/f_μ(x) < ∞,

	then, μ_n ∈ℍ(𝕏) ∩ℍ(𝕏|μ) for all n and
	it follows that
	
	
    lim_n →∞  D(μ_n || μ)=0  and lim_n →∞  H(μ_n )=H(μ).



Interpreting Lemma <ref>, we have that to obtain the convergence of the entropy functional without imposing a finite support assumption on μ,  a uniform bounding condition (UBC) μ-almost everywhere was added in (<ref>).  This UBC allows the use of  the dominated convergence theorem <cit.>,  and it is strictly needed in that sense <cit.>.
Finally by adding this UBC,  the convergence on reverse I-divergence is also obtained as a byproduct.  

Finally,  when μ≪μ_n for all n, we consider the following result:
 
 
 <cit.> 
	Let μ∈ℍ(𝕏) and a  sequence of measures 
	{μ_n: n≥ 1 }⊂ℍ(𝕏) such that 
	μ≪μ_n for all n ≥ 1. If μ_n ⇒μ
	and 
	
	
    sup_n≥ 1sup_x∈ A_μ|logf_μ_n(x)/f_μ(x)|  < ∞

	then, μ∈ℍ(𝕏|μ_n) for all n≥ 1, and
	
	
    lim_n →∞  D(μ || μ_n)=0.

	Furthermore, lim_n →∞  H(μ_n )=H(μ), if and only if,  
	
	
    lim_n →∞∑_x ∈ A_μ_n∖ A_μ f_μ_n(x) log1/f_μ_n(x)=0.


	This result shows again the non-sufficiency  
	of the convergence in direct I-divergence to achieve entropy convergence in the regime 
	when μ≪μ_n. In fact, 
	Lemma <ref> may be interpreted as an extension of 
	Lemma <ref> when we relax the finite support assumption on μ. 





§ SHANNON ENTROPY ESTIMATION


Let μ be a probability  in ℍ(𝕏), and 
let us denote by X_1,X_2,X_3,… the empirical process induced 
from i.i.d. realizations  of a random variable driven by μ, 
i.e., X_i ∼μ, for all i≥ 0.  
Let ℙ_μ denote the distribution of the empirical
process in (𝕏^∞,ℬ(𝕏^∞))
and ℙ^n_μ denote the finite block distribution of X^n_1≡ (X_1,..., X_n)
in the product space (𝕏^n,ℬ(𝕏^n)).
Given a realization of X_1,X_2,X_3, …, X_n, we can construct an 
histogram-based estimator like classical empirical probability given by:


    μ̂_n(A) ≡1/n∑_k=1^n 1_A(X_k),  ∀ A ⊂𝕏,

with pmf denoted by f_μ̂_n(x) 
= μ̂_n({x}) for all x ∈𝕏.
A natural estimator of the entropy  is the plug-in estimate 
of μ̂_n given by 


    H(μ̂_n) = - ∑_x ∈𝕏 f_μ̂_n(x) log f_μ̂_n(x),

which is a measurable function of X_1, …, X_n.[This dependency on the data will be 
implicit for the rest of the exposition.]

For the rest of the exposition, we use the convergence results in Section <ref> to derive 
strong consistency results for plug-in histogram-based estimates, 
like H(μ̂_n) in (<ref>), as well as finite length concentration inequalities 
to obtain almost-sure rate of convergence for the estimation error  |H(μ̂_n)  - H(μ) |. 
 




 §.§ Revisiting the classical  Plug-in estimator for finite and unknown supported distributions


We start analyzing the case where μ has a finite and unknown support. 
A  consequence of the strong law of large numbers <cit.> 
is  that ∀ x ∈𝕏, lim_n  →∞μ̂_n({x})= μ({x}), ℙ_μ-almost surely (a.s.), 
hence lim_n  →∞ V(μ̂_n, μ)=0,  ℙ_μ-a.s. 
On the other hand,  it is clear that A_μ̂_n⊂ A_μ with probability one.
Then adopting  Proposition <ref> it follows that


    lim_n →∞  D(μ̂_n  || μ)=0  and lim_n →∞  H(μ̂_n )=H(μ),   ℙ_μ-a.s.,

i.e., μ̂_n is a strongly consistent estimator of μ in reverse I-divergence 
and H(μ̂_n) is a strongly consistent estimate of H(μ) distribution-free in ℱ(𝕏). 
Furthermore, we can state the following: 



Let μ∈ℱ(𝕏)  and μ̂_n be  in (<ref>).
Then μ̂_n ∈ℋ(𝕏) ∩ℋ(𝕏|μ), 
ℙ_μ-a.s and ∀ n ≥ 1,
∀ϵ>0,
	
	
    ℙ^n_μ(D(μ̂_n || μ) > ϵ) ≤ 2^|A_μ|+1· e^- 2 𝐦_μ^2 ·  n ϵ^2/log  e ^2 , 
       ℙ^n_μ( |H(μ̂_n)  - H(μ) |  > ϵ) ≤ 2^|A_μ| +1· e^-2 n ϵ ^2/(𝐌_μ + log e/𝐦_μ)^2.

	Moreover, D(μ||μ̂_n)  is eventually well-defined with probability one, 
	and ∀ϵ>0, and for any n ≥ 1, 
	
	
    ℙ^n_μ(D(μ || μ̂_n) > ϵ) ≤
    		2^|A_μ|+1·[   e^-2 n ϵ^2/log e^2  ·(1/𝐦_u+1)^2
    		+ e^- n 𝐦_μ^2 ].




This result  implies that  for any τ∈ (0,1/2) and μ∈ℱ(𝕏), |H(μ̂_n)  - H(μ) |,  D(μ̂_n ||μ ) and  D(μ || μ̂_n) goes to zero as o(n^-τ) ℙ_μ-a.s.  Furthermore,   𝔼_ℙ^n_μ( |H(μ̂_n)  - H(μ) | ) and  𝔼_ℙ^n_μ(D(μ̂_n || μ))  behave like O(1/√(n)) for all μ∈ℱ(𝕏) from  (<ref>) in Sec. <ref>, which is the optimal  rate of convergence of the finite alphabet scenario.  As a direct corollary of (<ref>), 
it is possible to derive intervals of confidence for the estimation error 
|H((μ̂_n)- H(μ_n)|:  for all δ>0 and n≥ 1,  


    ℙ_μ( |H((μ̂_n)- H(μ_n)| ≤(𝐌_μ + log e/𝐦_μ)  √(1/2nln2^| A_μ| + 1/δ))  ≥ 1-δ.

This confidence interval 
behaves like O(1/√(n)) as a function of n, and like O(√(ln 1/δ)) as a function of  δ, which are the same optimal asymptotic trend that can be  obtained for V(μ, μ̂_n) in (<ref>).

To conclude,  we note that A_μ̂_n⊂ A_μ ℙ^n_μ-a.s. where for any  n≥ 1, 


	ℙ^n_μ (A_μ̂_n≠ A_μ)>0  

implying that 𝔼_ℙ^n_μ(D(μ||μ̂_n))=∞, ∀ n. 
Then even in the finite and unknown supported scenario, μ̂_n is not  consistent 
in expected direct I-divergence, which is congruent with the result in  <cit.>.
Besides this negative result,  strong consistency in direct I-divergence can be obtained from 
(<ref>), in the sense that lim_n →∞ D(μ || μ̂_n)=0, ℙ_μ-a.s.





 §.§ A simplified version of the Barron estimator for finite supported measures


It is well-understood  that consistency in  expected direct  I-divergence is  of critical importance 
for the construction of a lossless universal source coding scheme <cit.>. 
Here we explore an estimator that achieves this learning objective in addition to entropy estimation.

For that, let μ∈ℱ(𝕏) and let us assume that 
we know a measure v∈ℱ(𝕏) such that 
μ≪ v. <cit.> proposed a modified version 
of the empirical measure in (<ref>) to estimate μ
from i.i.d. realizations,  adopting a mixture estimate of the form 


    μ̃_n(B) = (1-a_n)·μ̂_n(B) + a_n · v(B),

for all B⊂𝕏, and with (a_n)_n∈ℕ a sequence of real
numbers in (0,1).
Note that supp(μ̃_n)=A_v then μ≪μ̃_n for all n[From 
the finite support assumption H(μ̃_n) <∞ and D(μ || μ̃_n) < ∞, ℙ_μ-a.s.]. 
The following result derives from the convergence result in Lemma <ref>.



	Let  v ∈ℱ(𝕏) and μ∈𝒜𝒞(𝕏| v), and let  us 
	consider μ̃_n  in (<ref>), with respect to v, 
	induced from i.i.d. realizations of μ.
	
	
  i) If  (a_n) is o(1), then  
	
	
		lim_n →∞  H(μ̃_n )=H(μ),  
 		lim_n →∞  D(μ || μ̃_n)=0, ℙ_μ-a.s., and 
		lim_n →∞𝔼_ℙ_μ(D(μ || μ̃_n))=0. 
	
	
  ii) Furthermore, if (a_n) is O(n^-p) with p > 2, then for all τ∈ (0,1/2),  | H(μ̃_n)-H(μ) |  and  D(μ||μ̃_n) are o(n^-τ) ℙ_μ-a.s,
	and  𝔼_ℙ_μ( | H(μ̃_n)-H(μ) |) and 
	𝔼_ℙ_μ(D(μ||μ̃_n)) are O(1/√(n)).
	





§ THE BARRON-GYÖRFI-VAN DER MEULEN ESTIMATOR


The celebrated Barron estimate was  proposed by Barron, Györfi and van der Meulen <cit.> in the context of an abstract and in general continuous measurable space. It was designed as a variation of the classical histogram-based scheme to achieve a consistent estimate of the distribution in 
direct I-divergence <cit.>.[As mentioned before,  consistency in expected direct I-divergence is an important learning topic because  of its connection with lossless universal  source coding <cit.>, 
where it is well-known that there is no distribution-free consistent estimate in direct I-divergence 
in the  infinite alphabet case <cit.>.] 
Here we revisit the Barron estimate in our countable alphabet scenario,  with the objective of estimating the Shannon entropy consistently, which to the best of our knowledge has not been previously addressed in the literature. For that purpose, Lemma <ref> will be used as a key result.

Let v ∈𝒫(𝕏) of infinite support (i.e., 𝐦_v=inf_x∈ A_v v({x})=0).
We want  to construct a strongly consistent estimate of the entropy 
restricted to the collection of probabilities in  ℍ(𝕏|v). For that, let us consider a sequence (h_n)_n≥ 0 with values in (0,1) and let us denote by π_n={A_n,1,A_n,2,…, A_n,m_n} the finite partition of 𝕏  with maximal cardinality satisfying that


    v(A_n,i) ≥ h_n,  ∀ i ∈{1,..,m_n}.

Note that m_n=|π_n|≤ 1/h_n for all n≥ 1, 
and because of  the fact that inf_x∈ A_v v({x})=0
it is simple to verify that  if (h_n) is o(1) and then lim_n →∞ m_n=∞.
Note that π_n offers an approximated statistically equivalent partition of 𝕏 with respect to the reference measure v. 
In this context,  given X_1,…,X_n,  i.i.d. realizations of 
μ∈ℍ(𝕏|v),  
the idea proposed by <cit.> was to estimate the RN derivative d μ/d v(x) 
by the following  histogram-based construction: 


    d μ^*_n/d v (x) = (1-a_n) ·μ̂_n(A_n(x))/v(A_n(x)) + a_n,  ∀ x ∈ A_v,

where a_n is a real number in (0,1), A_n(x) denotes the cell in π_n
that contains the point x, and μ̂_n is the  empirical measure in (<ref>).
Note that 
    f_μ^*_n(x)=d μ^*_n/d λ(x)=f_v(x)·[(1-a_n) ·μ̂_n(A_n(x))/v(A_n(x)) + a_n],
 ∀ x ∈𝕏, 
and, consequently,  ∀ B ⊂𝕏


    μ^*_n(B)=(1-a_n) ∑_i=1^m_nμ̂_n(A_n,i)·v(B∩ A_n,i)/v(A_n,i) 
    			+  a_n  v(B).

By construction A_μ⊂ A_v ⊂ supp(μ^*_n) and, consequently, 
μ≪μ^*_n for all n≥ 1.
The next result shows sufficient conditions on the sequences (a_n) and (h_n) 
to guarantee a strongly consistent estimate  of the entropy H(μ) and of μ in direct I-divergence,  distribution  free in ℍ(𝕏|v).  The proof is based on verifying that the sufficient conditions of Lemma <ref> are satisfied ℙ_μ-a.s. 


	Let v be in  𝒫(𝕏) ∩ℍ(𝕏) 
	with infinite support,  and let us consider μ in ℍ(𝕏|v). 
	If we have that:
	
		
  i)  (a_n) is o(1) and (h_n) is o(1),
		
  ii) ∃τ∈ (0,1/2), such that the sequence  (1/a_n· h_n) is o(n^τ),
	
	then μ∈ℍ(𝕏) ∩ℍ(𝕏|μ^*_n) 
	for all n≥ 1 and
	
	
    lim_n →∞  H( μ^*_n)=H(μ)   and lim_n →∞  D(μ || μ^*_n)=0,  ℙ_μ-a.s..



The Barron estimator <cit.>  was originally proposed 
in the context of distributions defined in an abstract measurable space.  Then if we restrict <cit.> to our countable alphabet case, the following result is  obtained:

 <cit.>

Let  us consider v ∈𝒫(𝕏) and  μ∈ℍ(  𝕏|v).  If (a_n) is o(1), (h_n) is o(1) and  limsup_n →∞1/n a_n h_n≤ 1 
then 

    lim_n →∞ D(μ ||μ^*_n)=0, ℙ_μ-a.s.

  
Therefore, when the objective is the estimation of distributions consistently in direct I-divergence,  Corollary <ref> should be considered to be a better result[Corollary <ref> offers weaker conditions than Theorem <ref> (in particular condition ii)).]. On the other hand, the proof of Theorem <ref> is based on verifying the sufficient conditions of Lemma <ref>,  where the objective is to achieve the convergence of the entropy,  and as a consequence, the  convergence in direct I-divergences. Therefore,  we can say that the stronger conditions of Theorem <ref> are needed when the objective is entropy estimation. This can be justified from the fact that convergence in direct I-divergence does not imply entropy convergence in the countable case,  as was discussed in Section <ref> (see, Lemmas <ref> and <ref>).





§ A DATA-DRIVEN HISTOGRAM-BASED ESTIMATOR



Data-driven partitions can approximate better the nature of the empirical distribution in the sample space with few quantization bins <cit.>. They has the flexibility to improve the approximation quality of histogram-based estimates and from that obtain better  performances in different non-parametric learning tasks <cit.>.  
One of the basic principle of this approach  is to partition 𝕏 into data-dependent cells in order to preserve a critical number of samples per cell. This last condition will be crucial  to derive a compromise between an estimation and approximation error that will be used in the proof of two of the main results of this section (Theorems <ref> and <ref>).
 
Given X_1,..,X_n i.i.d. realizations driven by μ∈ℍ(𝕏) and ϵ>0, 
let us define the data-driven set


    Γ_ϵ≡{x ∈𝕏: μ̂_n( {x })≥ϵ},

and ϕ_≡Γ_ϵ^c. Let Π_ϵ≡{{x }: x ∈Γ_ϵ}∪{ϕ_ϵ}⊂ℬ(𝕏) be a data-driven partition  with maximal resolution in Γ_ϵ, and σ_ϵ≡σ(Π_ϵ) be the smallest sigma field that contains  Π_ϵ
 [As Π_ϵ is a finite partition,  σ_ϵ is the collection of sets that are union of elements  of Π_ϵ.]. We propose  the conditional 
empirical measure restricted to  Γ_ϵ by:


    μ̂_n,ϵ≡μ̂_n(· |Γ_ϵ).

Note that by construction supp(μ̂_n,ϵ)=Γ_ϵ⊂ A_μ, ℙ_μ-a.s. and  consequently μ̂_n,ϵ≪μ for all n≥ 1. Furthermore, 
| Γ_ϵ| ≤1/ϵ  and importantly in the context of the entropy functional we have that


    𝐦_μ̂_n^ϵ≡inf_x∈Γ_ϵμ̂_n({x })≥ϵ.



The next result establishes a mild sufficient condition on (ϵ_n) 
 for which the plug-in estimate H(μ̂_n,ϵ_n) is strongly consistent distribution-free in  ℍ(𝕏).  Considering that  we are in the regime where μ̂_n,ϵ_n≪μ, ℙ_μ-a.s.,  the proof  uses Lemma <ref> as a  central result.



	 If (ϵ_n) is O(n^-τ) with τ∈ (0,1), then for all μ∈ℍ(𝕏)
	
	
    lim_n →∞  H(μ̂_n,ϵ_n)=H(μ), 
    	
    	 ℙ_μ-a.s.


This theorem tells us that this construction offers a universal estimation of the entropy in the strong 
almost sure sense,  as long as the design parameter τ belongs to (0,1). 

Complementing Theorem <ref>, 
the next result offers almost sure rates of converge for a  family of distributions with a power tail bounded condition (TBC).  
In particular, we consider the family of distributions studied by <cit.> in the context of characterizing the rate of convergences for the classical plug-in estimate.


	 Let us assume that for some p>1 there are two constants
	0<k_0 ≤ k_1 such that k_0· x^-p≤μ ( { x})≤ k_1 x^-p for all x∈𝕏. If we consider that (ϵ_n)=(n^-τ^*) for τ^*=1/2+1/p, then 
	
	
    |  H(μ) - H(μ̂_n,ϵ_n)  |   is  O(n^- 1-1/p/2+1/p),  ℙ_μ-a.s.



This result states that under the  mentioned p-power TBC on f_μ(·), the plug-in estimate H(μ̂_n,ϵ_n)  can offer a rate  of convergence to the true limit that is O(n^- 1-1/p/2+1/p) with probability one.  
The proof of this results set the approximation sequence (ϵ_n) function of p,  by finding an optimal tradeoff between estimation and approximation errors while performing a finite length (non-asymptotic) analysis of the expression |  H(μ) - H(μ̂_n,ϵ_n)  | (the details of this analysis are presented in Section <ref>). It is insightful to look at two extreme regimes in this result:  p approaching 1, in which the rate is arbitrarily slow (approaching a non-decaying behavior); and  p →∞, where |  H(μ) - H(μ̂_n,ϵ_n)  | is O(n^-q)  for all q∈ (0,1/2) ℙ_μ-a.s..
 This last power decaying range q∈ (0,1/2) matches what can be achieved for the finite alphabet scenario in Theorem <ref> (see  Eq.(<ref>)) which it is known to be optimal rate  for finite alphabets. 


Extending Theorem <ref>, the following result addresses  the more
constrained case of distributions with an exponential TBC.


Let us consider α>0 and let us assume that there are k_0,k_1 with 0<k_0 ≤ k_1 and N>0 such that  k_0 · e^-α x≤μ ( { x})≤ k_1 · e^-α x for all x ≥ N.  If we consider (ϵ_n)=(n^-τ) with  τ∈ (0,1/2), then

    |  H(μ) - H(μ̂_n,ϵ_n)  |   is  O(n^-τlog n),  ℙ_μ-a.s.




Under this stringer TBC on f_μ(·),  we note that 


	|  H(μ) - H(μ̂_n,ϵ_n)  |   is  o(n^-q)  ℙ_μ-a.s.,  

for any arbitrary q ∈ (0,1/2),  by selecting (ϵ_n)=(n^-τ) with  q<τ<1/2. This last condition on τ is universal over α>0.
Remarkably for any distribution with this exponential TBC, we can approximate (arbitrarely closely)  the optimal almost sure rate of convergence achieved for the finite alphabet scenario.  

Finally,  we revisit the finite and unknown supported scenario,  where we show that the data-driven estimate exhibit the same optimal almost sure convergence rate performance of the classical plug-in entropy estimate studied in  Sec. <ref>.


	Let us assume that μ∈ℱ(𝒳) and (ϵ_n) being o(1).  
	Then for all ϵ>0 there is N>0 such that  ∀ n≥ N
	
	
    ℙ^n_μ( |H(μ̂_n,ϵ_n)  - H(μ) |  > ϵ) ≤ 2^|A_μ|+1·[   e^-2 n ϵ ^2/(𝐌_μ + log e/𝐦_μ)^2
    		+ e^- n 𝐦_μ^2/4].


The proof of this result reduces to verify that μ̂_n,ϵ_n detects A_μ almost surely when n goes to infinity and from this, it follows that H(μ̂_n,ϵ_n) matches the optimal almost sure performance of H(μ̂_n) under the assumption that μ∈ℱ(𝒳).  In particular,  (<ref>) implies that |H(μ̂_n,ϵ_n)  - H(μ) | is o(n^-q) almost surely for all q∈ (0,1/2) as long as ϵ_n → 0  with n. 





§ PROOFS OF THE MAIN RESULTS





 §.§ Theorem <ref>:




	Let  μ be in ℱ(𝕏),  then |A_μ|  ≤ k for some k>1.  
	From  Hoeffding's inequality  <cit.> 
	 ∀ n≥ 1, and for any ϵ>0, 
	
	
    ℙ^n_μ(V(μ̂_n, μ) > ϵ) ≤ 2^k+1· e^- 2n ϵ^2 and 𝔼_ℙ^n_μ(V(μ̂_n, μ)) ≤ 2 √((k+1)log 2/n).

	Considering that μ̂_n≪μ ℙ_μ-a.s, we can use 
	Proposition <ref> to obtain that
	
	
    D(μ̂_n||μ) ≤log e/𝐦_μ· V(μ̂_n,μ),  and 
    		|H((μ̂_n)- H(μ_n)|  ≤[ 𝐌_μ+log e/𝐦_μ] · 	V(μ̂_n,μ).

	Hence,  (<ref>) and (<ref>) derive from (<ref>). 
	
	
	For the direct I-divergence, let us consider a sequence (x_i)_i≥ 1 and the following 
	function (a stopping time):
	
	
    T_o(x_1,x_2,…) ≡inf{n≥ 1: A_μ̂_n(x^n_1)=A_μ},

	i.e, T_o(x_1,x_2,…) is the point where the support of μ̂_n(x^n_1) is equal to A_μ
	and, consequently, the direct I-divergence is well-defined (since μ∈ℱ(𝕏)).
	[By the uniform convergence of μ̂_n to μ_n (ℙ_μ-a.s.) 
	and the finite support assumption of μ,  it  is  simple to verify that  
	ℙ_μ(T_o(X_1,X_2,…) < ∞)=1.] 
	Let us define the event: 
	
	
    ℬ_n ≡{x_1,x_2,..:T_o(x_1,x_2,..)≤ n}⊂𝕏^ℕ,

 	i.e.,  the collection of sequences in 𝕏^ℕ where at time n,
	A_μ̂_n=A_μ and, consequently, D(μ||μ̂_n) < ∞. 
	Restricted to this set, 
	
	
    D(μ || μ̂_n)    ≤∑_x ∈ A_μ̂_n||μ f_μ̂_n(x) logf_μ̂_n(x)/f_μ(x)
    				+ ∑_x ∈ A_μ∖ A_μ̂_n || μ f_μ̂_n(x) logf_μ(x)/f_μ̂_n(x)
       ≤log e ·∑_x ∈ A_μ̂_n||μ  f_μ̂_n(x) ·(f_μ̂_n(x)/f_μ(x) -1)
       + log e ·[μ(A_μ∖ A_μ̂_n || μ) - μ̂_n((A_μ∖ A_μ̂_n || μ))]
       ≤log e  ·(1/𝐦_u+1) V(μ, μ̂_n),

	where in the first inequality  A_μ̂_n||μ≡{x ∈ A_μ̂_n:  f_μ̂_n(x) > f_μ(x) }, 
	and the last is obtained by the definition of the total variational distance. 
	In addition,  let us  define the ϵ-deviation set 
	𝒜^ϵ_n ≡{x_1,x_2,...:D(μ||μ̂_n(x^n_1))>ϵ}⊂𝕏^ℕ. Then by additivity and monotonicity of ℙ_μ,  we have that 
	
	
    ℙ_μ(𝒜^ϵ_n) ≤ℙ_μ(𝒜^ϵ_n ∩ℬ_n) + ℙ_μ (ℬ_n^c).

	By definition of ℬ_n,  (<ref>)
	and (<ref>)  
	
	
    ℙ_μ(𝒜^ϵ_n ∩ℬ_n)    ≤ℙ_μ (V(μ||μ̂_n) log e  ·(1/𝐦_u+1) >ϵ)
       ≤ 2^|A_μ| +1· e^-2 n ϵ^2/log e^2  ·(1/𝐦_u+1)^2.

	On the other hand,  ∀ϵ_o ∈ (0,𝐦_μ)
	if V(μ, μ̂_n) ≤ϵ_o then T_o≤ n. 
	Consequently ℬ^c_n ⊂{x_1,x_2,..:V(μ, μ̂_n(x^n_1))>ϵ_o}, 
	and again from (<ref>)  
	
	
    ℙ_μ(ℬ_n^c)    ≤ 2^|A_μ|+1· e^-2 n ϵ_o^2,

	for all n≥ 1 and ∀ϵ_o∈ (0,𝐦_μ).
	Integrating the results in  (<ref>) and (<ref>)
	and considering ϵ_0 =𝐦_μ/√(2),  suffices to show  (<ref>).  





 §.§ Theorem <ref>


As (a_n) is o(1),  it is simple to verify that 
lim_n →∞V(μ̃_n, μ)=0, ℙ_μ-a.s.
Also note that the support disagreement between μ̃_n and μ
is bounded by the hypothesis, then 


    lim_n →∞μ̃_n (A_μ_n∖ A_μ) ·log|A_μ̃_n∖ A_μ| 
    	≤lim_n →∞μ̃_n (A_μ_n∖ A_μ) ·log|A_v|=0, 
    	 ℙ_μ-a.s.

Therefore from Lemma <ref>,  

we have the strong consistency of  H(μ̃_n) and the almost sure convergence of D( μ||μ̃_n) to zero. Note that D( μ||μ̃_n)
is uniformly upper bounded by log e · (1/𝐦_μ+1) V(μ, μ̃_n) 
(see (<ref>) in the proof of Theorem <ref>). 
Then the convergence in probability of D( μ||μ̃_n) implies the 
convergence of its mean <cit.>,
which concludes the proof of the first part.  

Concerning rate of convergences, we use the following: 


    H(μ )- H(μ̃_n)    = ∑_x ∈ A_μ∩ A_μ̃_n[f_μ̃_n(x)-f_μ(x)]  log f_μ(x)
    	 + ∑_x∈ A_μ∩ A_μ̃_n f_μ̃_n(x) logf_μ̃_n(x)/f_μ(x)
       -∑_x∈ A_μ̃_n∖ A_μ f_μ̃_n(x) log1/f_μ̃_n(x).

The absolute value of the first term in the right hand side (RHS) of (<ref>) is 
bounded by 𝐌_μ· V(μ̃_n,μ) and the second term is bounded 
by log e/𝐦_μ· V(μ̃_n,μ), from the assumption that μ∈ℱ(𝕏). For the last term, note that f_μ̃_n(x)=a_n· v({ x}) for all 
x ∈ A_μ̃_n∖ A_μ and that A_μ̃_n =A_v, then 

    0≤∑_x∈ A_μ̃_n∖ A_μ f_μ̃_n(x) log1/f_μ̃_n(x)≤ a_n· (H(v) + log1/a_n· v(A_v∖ A_μ)).

On the other hand, 


    V(μ̃_n,μ)   =1/2∑_x∈ A_μ| (1-a_n)μ̂_n({ x}) +a_n v({ x})  - μ({ x})| + ∑_x ∈ A_v∖ A_μ a_n v({ x}).
       ≤ (1-a_n)· V(μ̂_n, μ) +a_n.

Integrating these bounds in (<ref>), 


    |  H(μ )- H(μ̃_n)|     ≤ (𝐌_μ + log e/𝐦_μ) · ((1-a_n)· V(μ̂_n, μ) +a_n) + a_n · H(v) + a_n·log1/a_n
       = K_1· V(μ̂_n, μ) + K_2· a_n + a_n·log1/a_n,

for  constants K_1>0 and K_2>0 function of μ and v.

Under the assumption that μ∈ℱ(𝕏),  the Hoeffding's inequality <cit.> tells us that 
ℙ_μ(V(μ̂_n, μ) >ϵ) ≤ C_1 · e^-C_2 n ϵ^2
(for some distribution free constants C_1>0 and C_2>0). From this inequality,  
 V(μ̂_n, μ) goes to zero as o(n^-τ) ℙ_μ-a.s. ∀τ∈ (0,1/2) and 
 𝔼_ℙ_μ(V(μ̂_n, μ)) is O(1/√(n)). On the other hand,  
under the assumption in ii) (K_2· a_n + a_n·log1/a_n) is O(1/√(n)), which from (<ref>) proves the convergence rate results for |  H(μ )- H(μ̃_n)|.

Considering the direct I-divergence, D(μ|| μ̃_n) ≤log e ·∑_x ∈ A_μ   f_μ(x) |f_μ(x)/f_μ̃_n(x)-1| ≤log e/𝐦_μ̃_n· V(μ̃_n,μ),  then the uniform convergence of  μ̃_n({x}) to μ({x}) ℙ_μ-a.s. in A_μ, and the fact that |A_μ|<∞, imply that  for an arbitrary small 
ϵ>0 (in particular smaller than 𝐦_μ),  


    lim_n ⟶∞ D(μ|| μ̃_n)    ≤log e/𝐦_μ-ϵ·lim_n ⟶∞V(μ̃_n,μ),  ℙ_μ-a.s.,

which suffices to obtain the convergence results for the I-divergence. 







 §.§ Theorem <ref>


	Let us define the oracle Barron measure μ̃_n by:
	
	
    f_μ̃_n(x) = d μ̃_n/d λ(x) = f_v(x) [(1-a_n) ·μ(A_n(x))/v(A_n(x)) + a_n],

	where we consider the true measure instead of its empirical version in (<ref>). 
	Then, the following convergence results can be obtained (see Proposition <ref> in Appendix <ref>), 
	
	
    lim_n →∞sup_x∈ A_μ̃_n|d μ̃_n/d μ^*_n(x)-1|=0,  ℙ_μ-a.s.

	Let 𝒜 denote the collection   of sequences x_1,x_2,.... where the convergence in 
	(<ref>) is holding[This set is almost-surely typical meaning that ℙ_μ(𝒜)=1.].
	The rest of the proof reduces to show that for any arbitrary (x_n)_n≥ 1∈𝒜, 
	its respective sequence of induced measures  {μ^*_n: n≥ 1 }[For simplicity, the
	 dependency of μ^*_n  on the sequence (x_n)_n≥ 1 will be considered implicit for the rest of the
	 proof.] satisfies the sufficient conditions  of Lemma <ref> for entropy convergence.
	 
	 Let fix an arbitrary (x_n)_n≥ 1∈𝒜:

	
	
	Weak convergence μ^*_n ⇒μ:
	Without  loss of generality  we consider that A_μ̃_n=A_v for all n≥ 1. 
	
	Since a_n → 0 and h_n → 0,
	f_μ̃_n(x) →μ({x}) ∀ x ∈ A_v,  
	we got the weak 
	convergence of μ̃_n to μ.  On the other hand by definition of  𝒜,  
	lim_n →∞sup_x∈ A_μ̃_n|f_μ̃_n(x)/f_μ^*_n(x)-1| =0
	that implies that lim_n →∞| f_μ^*_n(x) - f_μ̃_n(x)|=0
	for all x ∈ A_v, and consequently  μ^*_n ⇒μ. 

	
	
	The condition in (<ref>):
	By construction μ≪μ^*_n,  μ≪μ̃_n and μ̃_n ≈μ^*_n  for all n, 
	then we will use the following equality: 
	
	
    logd μ/d μ^*_n (x) = logd μ/d μ̃_n(x)  + logd μ̃_n/d μ^*_n (x),


	for all x ∈ A_μ. Concerning the approximation error term of (<ref>), i.e.,  logd μ/d μ̃_n(x), 
	 ∀ x∈ A_μ, 
	
	
	
    d μ̃_n/d μ(x)= (1-a_n) [μ(A_n(x))/μ({x})v({x})/v(A_n(x))] + a_n v({x})/μ ({x}).

	Given that μ∈ℍ(𝕏|v) this is equivalent to state that 
	 log (d μ/d v(x)) is bounded  μ-almost everywhere, 
	which is equivalent to say that  𝐦≡inf_x∈ A_μd μ/d v(x) >0
	and M ≡sup_x∈ A_μd μ/d v(x) < ∞. From this,  
	
	∀ A ⊂ A_μ, 
	
	
    𝐦   v(A) ≤μ(A)≤ M  v(A).

	Then we have that, ∀ x ∈ A_μ
	
	
		𝐦/M≤[μ(A_n(x))/μ({x})v({x})/v(A_n(x))] ≤M/𝐦.
	
	Therefore  for n sufficient large,   0<1/2𝐦/M≤d μ̃_n/d μ(x) ≤M/𝐦 + M < ∞ for all x in  A_μ. Hence,  there exists N_o>0
	such that sup_n≥ N_osup_x ∈ A_μ|logd μ̃_n/d μ(x)| < ∞.

	For the estimation error term of (<ref>), i.e., logd μ̃_n/d μ^*_n (x),  note that from the fact that  (x_n)∈𝒜, 
	and the convergence in (<ref>),  there exists N_1>0 such that for all n≥ N_1   sup_x∈ A_μ|logd μ̃_n/d μ^*_n(x)| < ∞,  given that A_μ⊂ 	A_μ̃_n=A_v. Then using (<ref>), 
	for all n ≥max{N_0,N_1 }   sup_x∈ A_μ| logd μ^*_n/d μ(x)| < ∞, 
	which verifies (<ref>).

	
	
	The condition in (<ref>):
	Defining the function ϕ^*_n(x) ≡ 1_A_v∖ A_μ(x) · f_μ^*_n(x) log (1/f_μ^*_n(x)), we want to verify that  lim_n →∞∫_𝕏ϕ^*_n(x) d λ(x)=0. 
	Considering that (x_n)∈𝒜, for all ϵ>0 there exists N(ϵ)>0, 
	such that sup_x∈ A_μ̃_n|f_μ̃_n(x)/f_μ^*_n(x)-1|<ϵ, then
	
	
    (1-ϵ) f_μ̃_n(x) < f_μ^*_n(x) < (1+ ϵ) f_μ̃_n(x),  for all  x ∈ A_v.

	From (<ref>),  0 ≤ϕ^*_n(x) ≤ (1+ ϵ) f_μ̃_n(x) log (1/(1- ϵ) f_μ̃_n(x)) for all n ≥ N(ϵ).  Analyzing f_μ̃_n(x) in (<ref>) 	there are two scenarios: if A_n(x)∩ A_μ = ∅   then f_μ̃_n(x)=a_n f_v(x), and otherwise f_μ̃_n(x)=f_v(x)(a_n+(1-a_n)μ(A_n(x)∩ A_μ)/v(A_n(x))).  Let us define: 
	
	
    ℬ_n ≡{x ∈ A_v∖ A_μ: A_n(x)∩ A_μ = ∅} and 𝒞_n ≡{x∈ A_v∖ A_μ: A_n(x)∩ A_μ∅}.

	Then for all n≥ N(ϵ), 
	
	
    ∑_𝕏ϕ^*_n(x) 
    		    ≤∑_A_v∖ A_μ (1+ ϵ) f_μ̃_n(x) log 1/((1- ϵ) f_μ̃_n(x)) 
    		 
       = ∑_ℬ_n (1+ϵ) a_n f_v(x) log1/(1-ϵ)a_n f_v(x) + ∑_𝕏ϕ̃_n(x),

	with ϕ̃_n(x) ≡ 1_𝒞_n(x) · (1+ϵ) f_μ̃_n(x)  log1/(1-	ϵ)f_μ̃_n(x).  The left term in (<ref>) is upper bounded by 
	a_n(1+ϵ) (H(v) + log (1/a_n)) which goes to zero with n from (a_n) being o(1) 
	and the fact that v∈ℍ(𝕏).  For the right term in (<ref>), (h_n) being o(1) implies that  ∀ x∈ A_v∖ A_μ,  x belongs to ℬ_n eventually in n, then  ϕ̃_n(x) 
	tends to zero point-wise as n goes to infinity. On the other hand, for all x ∈𝒞_n 
	(see 	(<ref>)),  we have that
	
	
    1/1/m + 1≤μ(A_n(x) ∩ A_μ )/v(A_n(x) ∩ A_μ) +  v(A_v∖ A_μ)≤μ(A_n(x))/v(A_n(x))≤μ(A_n(x)∩ A_μ)/v(A_n(x)∩ A_μ)≤ M.

	These inequalities derive from (<ref>). Consequently for all x∈𝕏,  
	if  n sufficiently large such that a_n<0.5, then 
	
	
    0≤ϕ̃_n(x)    ≤ (1+ϵ)(a_n+(1-a_n)M)f_v(x) log1/(1-ϵ)(a_n+(1-a_n)m/(m+1))
       ≤ (1 + ϵ)(1+M)f_v(x)   [ log2(m+1)/(1-ϵ) + log1/f_v(x)] .

	Hence from (<ref>), ϕ̃_n(x) is  bounded by a  fix function that is l_1(𝕏) by the assumption that v∈ℍ(𝕏). Then by the dominated convergence theorem <cit.> and (<ref>),   
	
	
    lim_n →∞∑_𝕏ϕ^*_n(x) 
    	≤lim_n →∞∑_𝕏ϕ̃_n(x).
 
	
	In summary, we have shown that for any arbitrary  (x_n)∈𝒜 the sufficient conditions of Lemma <ref> are satisfied, which proves the result in (<ref>) reminding that ℙ_μ(𝒜)=1. 





 §.§ Theorem <ref>


	Let us  first introduce the oracle measure 
	
	
    μ_ϵ_n≡μ(· |Γ_ϵ_n) ∈𝒫(𝕏).

	Note that μ_ϵ_n is a random probability measure (function of the i.i.d sequence X_1,..,X_n) as Γ_ϵ_n is a data-driven set (<ref>).  We will first show that: 
	
	
    lim_n →∞  H(μ_ϵ_n)=H(μ) 
    	 and lim_n →∞  D(μ_ϵ_n|| μ)=0,  ℙ_μ-a.s.

	Under the assumption on (ϵ_n) of Theorem <ref>,    
	lim_n →∞| μ(Γ_ϵ_n)- μ̂_n(Γ_ϵ_n) |=0,  
	ℙ_μ-a.s.[This result derives from the fact that lim_n →∞ V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n) =0,  ℙ_μ-a.s. , from (<ref>).]  
	In addition,  since (ϵ_n) is o(1) then lim_n →∞μ̂_n(Γ_ϵ_n) =1,  
	which implies that lim_n →∞μ(Γ_ϵ_n)=1 ℙ_μ-a.s.  
	From this μ_ϵ_n⇒μ, ℙ_μ-a.s.  
	
	Let us  consider a sequences (x_n) where 
	lim_n →∞μ(Γ_ϵ_n)=1.  Constrained to that 
	
	
    limsup_n →∞sup_x∈ A_μf_μ_ϵ_n(x) /f_μ(x) = limsup_n 			→∞1/μ(Γ_ϵ_n) < ∞,

	then there is N>0 such that sup_n>Nsup_x∈ A_μf_μ_ϵ_n(x) /f_μ(x) <∞. 
	Hence from Lemma  <ref>,   lim_n →∞ D(μ_ϵ_n || μ)=0 and 
	lim_n →∞| H(μ_ϵ_n) - H(μ) |=0.  Finally,  the set of sequences (x_n) 
	where lim_n →∞μ(Γ_ϵ_n)=1 has probability one with respect 
	to ℙ_μ, which proves (<ref>).
	
	For the rest of the proof,  we concentrate on the analysis of  
	|H(μ̂_n,ϵ_n)- H(μ_ϵ_n) | 
	that can be attributed to the estimation error aspect of the problem. 
	It is worth noting that by construction  supp(μ̂_n,ϵ_n)=supp(μ_ϵ_n)=Γ_ϵ_n, ℙ_μ-a.s., consequently we can use
	
	
    H(μ̂_n,ϵ_n)- H(μ_ϵ_n) = ∑_x∈Γ_ϵ_n[ μ_ϵ_n ({x })- μ̂_n,ϵ_n ({x }) ] logμ̂_n,ϵ_n ({ x }) + D(μ_ϵ_n || μ̂_n,ϵ_n).

		
	
	
	The first term on the RHS  of (<ref>) is upper bounded  by 
	log 1/ 𝐦_μ̂_n^ϵ_n· V(μ_ϵ_n, μ̂_n,ϵ_n) ≤log 1/ϵ_n · V(μ_ϵ_n, μ̂_n,ϵ_n). Concerning the second term on the RHS  of (<ref>), it is possible to show  (details presented in Appendix <ref>) that
	 
	
    D(μ_ϵ_n || μ̂_n,ϵ_n) ≤2 loge/ϵ_n/μ(Γ_ϵ_n)· V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n),

	where 
	
	
    V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n) ≡sup_A ∈σ_ϵ_n| μ(A) - μ̂_n(A)|.

	In addition, it can be verified  (details presented in Appendix <ref>) that
 	
	
    V(μ_ϵ_n, μ̂_n,ϵ_n) ≤ K ·  V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n),

	for some universal constant K>0.  Therefore from (<ref>), (<ref>) and (<ref>), there is C>0 such that:
	 
	
    |  H(μ̂_n,ϵ_n)- H(μ_ϵ_n)|  ≤C/μ(Γ_ϵ_n)log1/ϵ_n·  V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n).

	As mentioned before,  μ(Γ_ϵ_n) goes to 1 almost surely,  then we need to concentrate 
	on the analysis of the asymptotic behavior of log1/ϵ_n  · V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n).
	From Hoeffding's inequality <cit.>, we have that ∀δ>0
	
	
    ℙ^n_μ(  log1/ϵ_n  · V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n)  >δ) ≤ 2^| Γ_ϵ_n|+1· e^- 2n δ^2/(log 1/ϵ_n)^2,

	considering that by construction | σ_ϵ_n| ≤ 2^| Γ_ϵ_n|+1≤  2^1/ϵ_n +1.
	Assuming that (ϵ_n) is O(n^-τ), 
	
	
    lnℙ^n_μ( log 1/ϵ_n  · V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n)  >δ) ≤  (n^τ+1) ln 2 -2nδ^2/τlog n.
 
	Therefore for all τ∈ (0,1), δ>0 and any arbitrary l∈ (τ, 1)
	
	
    limsup_n →∞1/n^l·lnℙ^n_μ( log 1/ϵ_n  · V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n)  >δ) < 0.

	This is sufficient to  show that ∑_n≥ 1ℙ^n_μ(  log1/ϵ_n  · V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n)  >δ) < ∞ that concludes the argument 
	from the  Borel-Cantelli Lemma.







 §.§ Theorem <ref>



	We  consider 
	
	
    | H(μ) - H(μ̂_n,ϵ_n) | ≤| H(μ) - H(μ_ϵ_n) | +  | H(μ_ϵ_n) - H(μ̂_n,ϵ_n) |

	to analize the approximation  and the estimation error terms separately. 
	


  §.§.§ Approximation error analysis:
 
	 Note that 
	 | H(μ) - H(μ_ϵ_n) |  is a random object
	  as μ_ϵ_n in (<ref>) is a function  of the data-dependent partition 
	  and, consequently, a function of X_1,..,X_n. In the  following,  
	  we consider the oracle set
	  
	  
    Γ̃_ϵ_n≡{x ∈𝕏:  μ( {x })≥ϵ_n},

	   and the oracle conditional measure[Γ̃_ϵ_n is a deterministic function of (ϵ_n) and so is  the measure μ̃_ϵ_n in (<ref>).]
	  
	  
    μ̃_ϵ_n≡μ(· | Γ̃_ϵ_n) ∈𝒫(𝕏).
 
	   
	   From  definitions and triangular inequality:
	    
	  
    | H(μ) - H( μ̃_ϵ_n) |     ≤∑_x∈Γ̃^c_ϵ_nμ ( {x }) log1/μ ( {x })  + log1/μ (Γ̃_ϵ_n)
       + (1/μ (Γ̃_ϵ_n)  - 1 ) ·∑_x∈Γ̃_ϵ_nμ ( { x}) log1/μ ( {x }),
 
	   and, similarly,  the approximation error is bounded by
	   
	  
    | H(μ) - H(μ_ϵ_n) |     ≤∑_x∈Γ^c_ϵ_nμ ( {x }) log1/μ ( {x }) 
       + log1/μ (Γ_ϵ_n) +  (1/μ (Γ_ϵ_n)  -1 ) ·∑_x∈Γ_ϵ_nμ ( { x}) log1/μ ( {x }).
 
	   We denote the RHS of (<ref>) and (<ref>) by a_ϵ_n and b_ϵ_n(X_1,..,X_n), respectively. 
	   
	   We can show that if (ϵ_n) is O(n^-τ) and τ∈ (0,1/2), then 
	   
		
    limsup_n →∞ b_ϵ_n(X_1,..,X_n) - a_2 ϵ_n≤ 0,  ℙ_μ-a.s.,

	 which from (<ref>)   implies that | H(μ) - H(μ_ϵ_n) | 
	   is O(a_2 ϵ_n), ℙ_μ-a.s.
	   The proof of (<ref>) is presented in Appendix <ref>.
	   
	   Then, we  need to analyze the rate of convergence of the deterministic sequence (a_2ϵ_n).
	   Analyzing the RHS of (<ref>), we recognize two independent terms: 
	   the partial entropy sum ∑_x∈Γ̃^c_ϵ_nμ ( {x }) log1/μ ( {x }) and the rest that is bounded asymptotically by   μ(Γ̃^c_ϵ_n) (1+H(μ)), using the fact that ln x ≤ x-1 for x≥ 1. Here is where the tail condition on μ plays a  role. 
	   
	   From the tail condition, we have that 
	   
	   
    μ(Γ̃^c_ϵ_n)    ≤μ( { (k_o/ϵ_n)^1/p+1,  (k_o/ϵ_n)^1/p+2,  (k_o/ϵ_n)^1/p+3, …})  = ∑_x≥  (k_o/ϵ_n)^1/p+1μ({x }) 
       ≤ k_1 ·𝒮_ (k_o/ϵ_n)^1/p+1,
 
	  where 𝒮_x_o≡∑_x≥ x_o x^-p.  Similarly as {0,1,.., (k_o/ϵ_n)^1/p}⊂Γ̃_ϵ_n, then
	   
	   
    ∑_x∈Γ̃^c_ϵ_nμ ( {x }) log1/μ ( {x })   ≤∑_x≥  (k_o/ϵ_n)^1/p+1μ ( {x }) log1/μ ( {x })≤∑_x≥  (k_o/ϵ_n)^1/p+1 k_1 x^-p·log1/k_0 x^-p
       ≤ k_1log p ·ℛ_(k_o/ϵ_n)^1/p+1 + k_1 log 1/k_0 ·𝒮_(k_o/ϵ_n)^1/p+1,
 
	  where  ℛ_x_o≡∑_x≥ x_o x^-plog x.   
	  
	  In Appendix <ref>, 
	  it is shown that 𝒮_x_o≤ C_0· x_o^1-p and ℛ_x_o≤ C_1 · x_o^1-p for constants  C_1>0 and C_0>0. Integrating these results in the RHS of (<ref>) and (<ref>) and considering that (ϵ_n) is O(n^-τ), we have that 
	   both μ(Γ̃^c_ϵ_n) and ∑_x∈Γ̃^c_ϵ_nμ ( {x }) log1/μ ( {x }) are  O(n^-τ(p-1)/p). This implies that our oracle sequence (a_ϵ_n) is O(n^-τ(p-1)/p). 
	   
	   In conclusion, if ϵ_n is O(n^-τ) for τ∈ (0,1/2), it follows that 
	   
	   
    | H(μ) - H(μ_ϵ_n) |   is  O(n^-τ(p-1)/p), ℙ_μ-a.s.
 



  §.§.§ Estimation error analysis:
 


Let us consider | H(μ_ϵ_n) - H(μ̂_n,ϵ_n) |, 
from the bound in (<ref>) and the fact that for any τ∈ (0,1), 
lim_n →∞μ(Γ_ϵ_n)=1 ℙ_μ-a.s. from (<ref>),   
the problem reduces to analyze the rate of convergence  of the following random object: 


    ρ_n(X_1,..,X_n) ≡log1/ϵ_n· V(μ/σ(Γ_ϵ_n), μ̂_n/σ(Γ_ϵ_n)).
 
We will analize, instead, the  oracle version of ρ_n(X_1,..,X_n) given by: 


    ξ_n(X_1,..,X_n) ≡log1/ϵ_n· V(μ/σ(Γ̃_ϵ_n/2), μ̂_n/σ(Γ̃_ϵ_n/2)),
 
where Γ̃_ϵ≡{x∈𝕏: μ({ x})≥ϵ} is the oracle counterpart of Γ_ϵ in (<ref>). To do so, we can show that if ϵ_n is O(n^-τ)  with τ∈ (0, 1/2), then 


    liminf_n →∞ξ_n(X_1,..,X_n) - ρ_n(X_1,..,X_n) ≥ 0,   ℙ_μ-a.s.

The proof of (<ref>) is presented in Appendix <ref>.

Moving to the almost sure rate of convergence  of ξ_n(X_1,..,X_n), it is simple to show 
for our p-power dominating distribution that if (ϵ_n) is O(n^-τ) and τ∈ (0,p) 
then 
    lim_n →∞ξ_n(X_1,..,X_n)=0ℙ_μ-a.s,
 and, more specifically,  


    ξ_n(X_1,..,X_n)  is  o(n^-q)  for all  q∈ (0,(1-τ/p)/2),  ℙ_μ-a.s.

The argument is presented in Appendix <ref>.

In conclusion, if ϵ_n is O(n^-τ) for τ∈ (0,1/2), it follows that 


    | H(μ_ϵ_n) - H(μ̂_n,ϵ_n) |   is  O(n^-q), ℙ_μ-a.s.,
 
for all q∈ (0,(1-τ/p)/2).




  §.§.§ Estimation vs. approximation error:
 
Coming back to (<ref>) and using (<ref>) and (<ref>),  the analysis reduces to finding the solution τ^*  in (0,1/2) that offers the 
best trade-off between the estimation and approximation error rate:


    τ^* ≡max_τ (0,1/2)min{(1-τ/p)/2, τ(p-1)/p}.
  
It is simple to verify that τ^*=1/2. Then by considering τ arbitrary close to the admissible limit 1/2,  we can 
achieve a rate of convergence for | H(μ) - H(μ̂_n,ϵ_n) |
that is arbitrary close to O(n^-1/2(1-1/p)), ℙ-a.s. 

More formally,  for any l ∈ (0,1/2(1-1/p)) we can take τ∈ (l/(1-1/p), 1/2)
where  | H(μ) - H(μ̂_n,ϵ_n) | is o(n^-l), ℙ_μ-a.s.,  
from (<ref>) and (<ref>).

Finally, a simple corollary of this analysis is to consider τ(p)=1/2+1/p<1/2 where: 


    | H(μ) - H(μ̂_n,ϵ_n) |  is  O(n^- 1-1/p/2+1/p),  ℙ_μ-a.s.,
  
which concludes the argument. 






 §.§ Theorem <ref>



	The argument follows the proof of Th. <ref>. 
	In particular, we use the estimation-approximation error bound: 
	
	
    | H(μ) - H(μ̂_n,ϵ_n) | ≤| H(μ) - H(μ_ϵ_n) | +  | H(μ_ϵ_n) - H(μ̂_n,ϵ_n) |,
 
	and the following two results derived in the proof of Th. <ref>: If (ϵ_n) is O(n^-τ) with τ∈ (0,1/2) then (for the approximation error)
	
	
    | H(μ) - H(μ_ϵ_n) |  is   O(a_2ϵ_n) ℙ_μ-a.s.,

	with a_ϵ_n = ∑_x∈Γ̃^c_ϵ_nμ ( {x }) log1/μ ( {x })  + μ(Γ̃^c_ϵ_n) (1+H(μ)),
	while (for the estimation error)
	
	
    | H(μ_ϵ_n) - H(μ̂_n,ϵ_n) |  is  O (ξ_n(X_1,..,X_n))  ℙ_μ-a.s.,

	with ξ_n(X_1,..,X_n) = log1/ϵ_n· V(μ/σ(Γ̃_ϵ_n/2), μ̂_n/σ(Γ̃_ϵ_n/2)).
	
	
	
	For the estimation error,  we need to bound the rate of convergence of ξ_n(X_1,..,X_n) to zero almost surely.  We first note that {1,..,x_o(ϵ_n) }=Γ̃_ϵ_n with x_o(ϵ_n)= ⌊  1/αln (k_0/ϵ_n)⌋.  Then from Hoeffding's inequality we have that
	
	
    ℙ^n_μ(  {ξ_n(X_1,..,X_n) > δ})    ≤ 2^| (Γ̃_ϵ_n/2) |·  e^-2n δ^2/log(1/ϵ_n)^2
       ≤ 2^1/αln (2k_0/ϵ_n)+1· e^-2n δ^2/log(1/ϵ_n)^2.

	Considering ϵ_n=O(n^-τ),  an arbitrary sequence (δ_n) being o(1) and l>0, 
	it follows from (<ref>) that 
	
	
    1/n^l·lnℙ^n_μ(  {ξ_n(X_1,..,X_n) > δ_n  })    ≤1/n^lln(2)  [ 1/αln (2k_0/ϵ_n)+1 ] - n^1-lδ_n^2/log(1/ϵ_n)^2.

	We note that the first term in the RHS of (<ref>) 
	is O(1/n^llog n) and goes to zero for all l>0, while the second term is O(n^1-lδ_n^2/log n^2).  
	If  we consider δ_n=O(n^-q), this second term is O(n^1-2q-l·1/log n^2). Therefore, 
	for any q∈ (0,1/2) we can take an arbitrary l∈ (0,1-2q] such that 
	ℙ^n_μ(  {ξ_n(X_1,..,X_n) > δ_n  }) is O(e^-n^l) from (<ref>). This result implies,  from the 
	Borel-Cantelli Lemma, that ξ_n(X_1,..,X_n) is o(δ_n), ℙ_μ-a.s, which in summary shows that | H(μ_ϵ_n) - H(μ̂_n,ϵ_n) | is O(n^-q) for all q∈ (0,1/2).
	
	
	
	For the approximation error, it is simple to verify that: 
	
	
    μ(Γ̃^c_ϵ_n) ≤ k_1 ·∑_x  ≥ x_o(ϵ_n)+1 e^-α x  = k_1  ·𝒮̃_x_o(ϵ_n)+1

	and 
	
	
    ∑_x∈Γ̃^c_ϵ_nμ ( {x }) log1/μ ( {x })   ≤∑_x  ≥ x_o(ϵ_n)+1 k_1 e^-α xlog1/k_0 e^-α x = k_1 log1/k_0·𝒮̃_x_o(ϵ_n)+1
       + αlog e · k_1  ·ℛ̃_x_o(ϵ_n)+1,

	where 𝒮̃_x_o≡∑_x  ≥ x_o e^-α x  and ℛ̃_x_o≡∑_x  ≥ x_o x· e^-α x. At this point, it is not difficult to show that 𝒮̃_x_o≤ M_1 e^-α x_o and  
	ℛ̃_x_o≤ M_2 e^-α x_o· x_o for some constants M_1>0 and M_2>0. Integrating these 
	partial steps,  we have that
	
	
    a_ϵ_n≤ k_1 (1+H(μ)+log1/k_0) ·𝒮̃_x_o(ϵ_n)+1 + αlog e · k_1  ·ℛ̃_x_o(ϵ_n)+1≤ O_1·ϵ_n + O_2·ϵ_n log1/ϵ_n

	for some constant O_1>0 and O_2>0. 
	The last step is from the evaluation of x_o(ϵ_n)= ⌊  1/αln (k_0/ϵ_n)⌋. 
	Therefore from (<ref>) and (<ref>), it follows that | H(μ) - H(μ_ϵ_n) | 
	is O(n^-τlog n)  ℙ_μ-a.s. for all τ∈ (0,1/2). 
	
	The argument concludes by integrating in (<ref>) the almost sure convergence results obtained for the estimation and approximation in errors. 





 §.§ Theorem <ref>



	Let us define the event 
	
	
    ℬ^ϵ_n  =  {x^n_1 ∈𝕏^n: Γ_ϵ(x^n_1)=A_μ},

	that represents the detection of the support of μ from the data for a given ϵ>0 in (<ref>). 
	Note that the dependency on the data for Γ_ϵ  is made explicit in this notation. 

	In addition, let us consider the deviation event
	
	
    𝒜^ϵ_n(μ)= { x^n_1 ∈𝕏^n: V(μ,μ̂_n) >ϵ}.

	By the hypothesis that | A_μ|<∞, then 𝐦_μ=min_x∈ A_μ f_μ(x)>0.  
	Therefore if  x^n_1∈ (𝒜^𝐦_μ/2_n(μ))^c  then μ̂_n( { x }) ≥𝐦_μ/2  for  all x∈ A_μ, which implies that  (ℬ^ϵ_n)^c⊂𝒜^𝐦_μ/2_n(μ) as long as 0<ϵ≤𝐦_μ/2. 
	Using the hypothesis that ϵ_n → 0,  there is N>0 such that for all n≥ N (ℬ^ϵ_n_n)^c⊂𝒜^𝐦_μ/2_n(μ) and, consequently, 
	
	
    ℙ^n _μ ((ℬ^ϵ_n_n)^c) ≤ℙ^n _μ (𝒜^𝐦_μ/2_n(μ)) ≤ 2^k+1· e^- n 𝐦_μ^2/4,

	the last from Hoeffding's inequality considering k=| A_μ| <∞.

	If we consider the events:
	
	
    𝒞^ϵ_n(μ)    ={ x^n_1 ∈𝕏^n:  |H(μ̂_n,ϵ_n)  - H(μ) |  >ϵ} and 
    𝒟^ϵ_n(μ)    ={ x^n_1 ∈𝕏^n: |H(μ̂_n)  - H(μ) |  >ϵ}

	and we use the fact that by definition μ̂_n,ϵ_n=μ̂_n conditioning on  ℬ^ϵ_n_n,  it follows that 𝒞^ϵ_n(μ) ∩ℬ^ϵ_n_n ⊂𝒟^ϵ_n(μ).  	
	Then,  for all ϵ>0 and n≥ N
	
	
    ℙ^n_μ(𝒞^ϵ_n(μ))    ≤ℙ^n_μ(𝒞^ϵ_n(μ) ∩ℬ^ϵ_n_n) + ℙ^n _μ ((ℬ^ϵ_n_n)^c)
       ≤ℙ^n_μ(𝒟^ϵ_n(μ)) + ℙ^n _μ ((ℬ^ϵ_n_n)^c)
       ≤ 2^k+1[ e^-2 n ϵ ^2/(𝐌_μ + log e/𝐦_μ)^2 + e^- n 𝐦_μ^2/4],

	the last inequality from Theorem <ref> and (<ref>).
	
	





§ SUMMARY AND FINAL REMARKS


In this work we show that entropy convergence results  
are instrumental to derive new (strongly consistent) estimation results for the Shannon entropy in infinite alphabets, and as a byproduct,  distribution estimators that are strongly consistent in direct and reverse  I-divergence.  
Adopting a set of sufficient conditions for entropy convergences in the context of four plug-in histogram-based schemes, we show concrete conditions where strong consistency for entropy estimation in ∞-alphabets can be obtained (Theorems <ref>, <ref> and <ref>). In addition,  we explore the relevant  case where the target distribution has a finite but unknown support,  deriving for the overall estimation error 
almost sure rate of convergence results (Theorems <ref> and <ref>) that match the optimal asymptotic rate that can be obtained in the finite alphabet version of the problem. Finally, we focus on the case of a data-driven plug-in estimate that restricts the support where we estimate the distribution. The basic idea was to have design parameters to control estimation error effects in the context of entropy estimation. The conjecture was that this approach will offers degrees of freedom to restrict the learning complexity while introducing an approximation error and, consequently, the possibility to find an adequate balance between these two learning components.  Adopting a entropy convergence result (Lemma <ref>), we show that this data-driven scheme offers the same universal estimation attributes than the classical plug-in estimate under some mild conditions on its threshold design parameter (Theorem <ref>). In addition,  by addressing the  technical task of deriving concrete closed-form expressions for the estimation 
and approximation error in this adaptive data-driven context (where a subset of the space is selected adaptively from the data to restrict the estimation of the distribution), we show a solution were  almost sure rate of convergence of the overall estimation error are obtained over a family of distribution with some concrete tail bounded conditions (Theorems <ref> and <ref>). These results show the potential that  data-driven frameworks has to adapt to the complexity of entropy estimation in unbounded alphabets by restricting the inference to a finite but dynamic subset of the space that scales with the amount of data and the distribution of the data in the sampling space. 

Concerning the classical plug-in estimate presented in Section <ref>, it is important to mention that the  work of  <cit.>  shows that lim_n →∞  H(μ̂_n )=H(μ) almost surely  distribution-free and,  furthermore, it provides rates of convergences for families with specific  
tail-bounded conditions <cit.>. On this context, Theorem <ref>  focuses on the case when μ∈ℱ(𝕏), where  new finite-length deviation inequalities and confidence intervals were derived.  From that perspective,  it complements the result presented in <cit.> in the non-explored scenario when μ∈ℱ(𝕏). It is also important to mention two results by <cit.> for the plug-in estimate in (<ref>). They derive bounds for the object ℙ_μ^n(|H(μ̂_n)  - H(μ) |≥ϵ) 
and from this determine confidence intervals under a finite and known support restriction on the distribution μ.
In contrast, our result in Theorem <ref>  resolves the case for a  finite and unknown supported distribution,   that was declared to be a challenging problem based on the arguments presented in <cit.> concerning the discontinuity of the entropy.



The work is supported by funding from FONDECYT Grant 1170854, CONICYT-Chile
and the Advanced Center for Electrical and Electronic Engineering (AC3E), Basal Project FB0008.  The author is grateful to Patricio Parada for his insights and stimulating discussion in the initial stage of this work.







§ MINIMAX RISK FOR FINITE ENTROPY DISTRIBUTIONS IN INFINITE ALPHABETS


 R^*_n =∞.

For the proof, we use the following lemma that follows from <cit.>. 

  
Let us fix two arbitrary real numbers δ>0 and ϵ>0. Then there are P, Q two finite supported distributions on ℍ(𝕏)  that satisfy that D(P||Q)<ϵ while H(Q)-H(P)>δ. [The proof of Lemma <ref> derives from the same construction presented in the proof of <cit.>, i.e., P=(p_1,..,p_L) and a modification of it Q_M=(p_1· (1-1/√(M)), p_2+p_1/M√(M),..., p_L+p_1/M√(M),p_1/M√(M),...,p_1/M√(M)) both of finite support and consequently in ℍ(𝕏). It is simple to verify that as M goes to infinity D(P||Q_M) ⟶ 0 while H(Q_M)-H(P)⟶∞.] 



	For any pair of distribution P, Q in ℍ(𝕏), Le Cam's two point method <cit.> shows that:   
	
	
    R^*_n ≥1/4( H(Q)-H(P) )^2 exp^-n D(P||Q).
	
	 Adopting Lemma <ref> and (<ref>), for any n and any arbitrary ϵ>0 and δ>0, we have that R^*_n> δ^2exp^-nϵ/4. Then exploiting the discontinuity of the entropy in infinite alphabets, we can fix ϵ and make δ arbitrar large. 





§ PROPOSITION <REF>


 
	Under the assumptions of Theorem <ref>: 
	
	
    lim_n →∞sup_x∈ A_μ̃_n|d μ̃_n/d μ^*_n(x)-1|=0,  ℙ_μ-a.s.



First note that supp(μ̃_n)=supp(μ^*_n), then d μ̃_n/d μ^*_n(x) is well-defined and ∀ x ∈ A_μ̃_n


    d μ̃_n/d μ^*_n(x)= (1-a_n)·μ(A_n(x)) +a_n v(A_n(x))/(1-a_n)·μ̂_n(A_n(x)) +a_n v(A_n(x)).

Then by construction, 


    sup_x∈ A_μ̃_n|d μ̃_n/d μ^*_n(x)-1| ≤sup_A∈π_n|μ̂_n(A)-μ(A)|/a_n· h_n.

From Hoeffding's inequality we have that  ∀ϵ>0


    ℙ^n_μ( sup_A ∈π_n|μ̂_n(A) - μ(A)| > ϵ)
    ≤ 2 ·|π_n| ·exp ^- 2n ϵ^2.

By condition ii),  given that (1/a_nh_n) is o(n^τ)
for some τ∈ (0,1/2), then there exists τ_o ∈ (0,1)
such that, 


    lim_n →∞1/n^τ_olnℙ^n_μ(sup_x∈ A_μ̃_n|d μ̃_n/d μ^*_n(x)-1| > ϵ) ≤
    	lim_n →∞1/n^τ_oln (2 |π_n| ) - 2· (n^1-τ_o/2 a_n h_n ϵ)^2= - ∞.

This implies that ℙ^n_μ(sup_x∈ A_μ̃_n|d μ̃_n/d μ^*_n(x)-1| > ϵ) is eventually dominated by a constant time (e^-n^τ_o)_n≥ 1, 
which from the Borel-Cantelli lemma <cit.> implies that 


    lim_n →∞sup_x∈ A_μ̃_n|d μ̃_n/d μ^*_n(x)-1|=0,  ℙ_μ-a.s.






§ PROPOSITION <REF>


 
	
	
    D(μ_ϵ_n || μ̂_n,ϵ_n) ≤2 loge/ϵ_n/μ(Γ_ϵ_n)· V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n)



	From definition, 
	
	
    D(μ_ϵ_n || μ̂_n,ϵ_n) = 1/μ(Γ_ϵ_n)∑_x ∈Γ_ϵ_n f_μ(x) logf_μ(x)/f_μ̂_n(x) + logμ̂_n(Γ_ϵ_n) /μ(Γ_ϵ_n).

	For the right term in the RHS of (<ref>): 
	
	
    logμ̂_n(Γ_ϵ_n) /μ(Γ_ϵ_n)≤log(e) /μ(Γ_ϵ_n)|  μ̂_n(Γ_ϵ_n)-μ(Γ_ϵ_n) |.

	For the left term in the RHS of (<ref>): 
	
	
    | ∑_x ∈Γ_ϵ_n f_μ(x) logf_μ(x)/f_μ̂_n(x)| 
    			   = | ∑_ x ∈Γ_ϵ_n
     f_μ(x)≤ f_μ̂_n(x) f_μ(x) logf_μ(x)/f_μ̂_n(x) + ∑_ x ∈Γ_ϵ_n
      f_μ(x) > f_μ̂_n(x) ≥ϵ_n f_μ(x) logf_μ(x)/f_μ̂_n(x)| 
       ≤∑_ x ∈Γ_ϵ_n
     f_μ(x)≤ f_μ̂_n(x) f_μ(x) logf_μ̂_n(x) /f_μ(x) + ∑_ x ∈Γ_ϵ_n
      f_μ(x) > f_μ̂_n(x) ≥ϵ_n  f_μ̂_n(x) logf_μ(x)/f_μ̂_n(x)
       + ∑_ x ∈Γ_ϵ_n
      f_μ(x) > f_μ̂_n(x) ≥ϵ_n  ( f_μ(x)-f_μ̂_n(x)) ·logf_μ(x)/f_μ̂_n(x)
       ≤log e [ ∑_ x ∈Γ_ϵ_n
     f_μ(x)≤ f_μ̂_n(x) (f_μ̂_n(x)-f_μ(x)) + ∑_ x ∈Γ_ϵ_n
      f_μ(x) > f_μ̂_n(x) (f_μ(x)- f_μ̂_n(x))  ] 
       + log1/ϵ_n·∑_ x ∈Γ_ϵ_n
      f_μ(x) > f_μ̂_n(x)   ( f_μ(x)-f_μ̂_n(x))
       ≤  (log e+ log1/ϵ_n) ·∑_x∈Γ_ϵ_n| f_μ(x)- f_μ̂_n(x) |.

	The first inequality in (<ref>) is by triangular inequality,  the second in (<ref>) is from the fact that ln x≤ x-1 for x>0. 
	Finally from definition of the total  variational distance over σ_ϵ_n in (<ref>)
	we have that 
	
	
    2 · V(μ/σ_ϵ_n, μ̂_n/σ_ϵ_n)=  ∑_x∈Γ_ϵ_n| f_μ(x)- f_μ̂_n(x) | + |  μ̂_n(Γ_ϵ_n)-μ(Γ_ϵ_n) |,

	 which concludes the argument from (<ref>), (<ref>) and (<ref>).






§ PROPOSITION <REF>



	Considering that (k_n) →∞, 
	there exists K>0 and N>0 such that ∀ n ≥ N, 
	
	
    V(μ̃_k_n, μ̂^*_k_n,n )  ≤ K · V(μ/σ_k_n, μ̂_n/σ_k_n).


 


    V(μ̃_k_n, μ̂^*_k_n,n )   = 1/2∑_x ∈ A_μ∩Γ_k_n|μ{x}/μ(Γ_k_n)- μ̂_n{x}/μ̂_n(Γ_k_n)|
       ≤1/2μ(Γ_k_n)[∑_x ∈ A_μ∩Γ_k_n|μ̂_n{x}- μ{x}| + ∑_x ∈ A_μ∩Γ_k_nμ̂_n{x}| μ(Γ_k_n)/μ̂_n(Γ_k_n)-1| ] 
       = 1/2μ(Γ_k_n)[ 2 · V(μ/σ_k_n, μ̂_n/σ_k_n) + | μ(Γ_k_n)  - μ̂_n(Γ_k_n) | ]
       ≤3 · V(μ/σ_k_n, μ̂_n/σ_k_n)/2μ(Γ_k_n)

By the hypothesis  μ(Γ_k_n) → 1, which concludes the proof.






§ PROPOSITION <REF>



	If ϵ_n is O(n^-τ)  with τ∈ (0, 1/2), then 
	
	
    limsup_n →∞ b_ϵ_n(X_1,..,X_n) - a_2 ϵ_n≤ 0,  ℙ_μ-a.s.



	Let us define the set 
	  
	  
    ℬ_n=  {(x_1,..,x_n):  Γ̃_2 ϵ_n⊂Γ_ϵ_n}⊂𝕏^n.
  
	  From definition  every sequence (x_1,..,x_n) ∈ℬ_n  is such that   
	  b_ϵ_n(x_1,..,x_n) ≤ a_2ϵ_n and, consequently,  we just need to prove that 
	   ℙ_μ(liminf_n →∞ℬ_n) = ℙ_μ (∪_n≥ 1∩_k≥ nℬ_k)=1 <cit.>. 
	   Furthermore, if sup_x∈Γ̃_2ϵ_n| μ̂_n({x })- μ({x }) | ≤ϵ_n, then by definition of Γ̃_2 ϵ_n in (<ref>),  we have that μ̂_n ({ x})  ≥ϵ_n for all x∈Γ_2 ϵ_n (i.e., Γ̃_2 ϵ_n⊂Γ_ϵ_n).  From this 
	   
	   
    ℙ^n_μ (ℬ^c_n)     ≤ℙ^n_μ( sup_x∈Γ̃_2ϵ_n| μ̂_n({x })- μ({x }) | > ϵ_n )  ≤| Γ̃_2ϵ_n| · e^-2n ϵ_n^2≤1/2ϵ_n· e^-2n ϵ_n^2 ,
 
	   from the Hoeffding's inequality <cit.>, the union bound and the fact that 
	   by construction | Γ̃_2 ϵ_n| 
	   ≤1/2ϵ_n.
	   If we consider ϵ_n=O(n^-τ) and l>0, we have that: 
	   
	   
    1/n^l·lnℙ^n_μ (ℬ^c_n) ≤1/n^lln (1/2 · n^τ) - 2n^1-2τ -l.

	   From (<ref>) for any  τ∈ (0,1/2) there is l ∈ (0,1-2τ]
	   such that ℙ^n_μ (ℬ^c_n) is bounded by a term O(e^-n^l). 
	   This implies that ∑_n≥ 1ℙ^n_μ (ℬ^c_n) <∞, that suffices to  show that  ℙ_μ (∪_n≥ 1∩_k≥ nℬ_k)=1. 





§ AUXILIARY RESULTS FOR THEOREM <REF>


Let us first consider the series 


    𝒮_x_o= ∑_x≥ x_o x^-p   =x_o^-p·( 1+  ( x_o/x_o+1)^p+ (x_o/x_o+2)^p + …) 
       =x_o^-p·( 𝒮̃_x_o,0+  𝒮̃_x_o,1 + …  + 𝒮̃_x_o,x_o-1),

where 𝒮̃_x_o,j≡∑_k=0^∞( k· x_o +j/x_o)^-p for all 
j∈{0,..,x_o-1 }. It is simple to verify that for all 
j∈{0,..,x_o-1 }, 𝒮̃_x_o,j≤𝒮̃_x_o,0 =∑_k≥ 0 k^-p <∞ given that  by hypothesis p>1. Consequently, 
𝒮_x_o≤ x_o^1-p·∑_k≥ 0 k^-p.

Similarly, for the second series we have that:


    ℛ_x_o = ∑_x≥ x_ox^-plog x    = x_o^-p·(log (x_o)+  (x_o/x_o+1) log (x_o+1) +  (x_o/x_o+2) log (x_o+2) + …)  
       =x_o^-p·( ℛ̃_x_o,0+  ℛ̃_x_o,2 + …  +ℛ̃_x_o,x_o-1),

where ℛ̃_x_o,j≡∑_k=1^∞( k· x_o +j/x_o)^-p·log (kx_o+j)  for all  j∈{0,..,x_o-1 }. 
Note again that  ℛ̃_x_o,j≤ℛ̃_x_o,0 <∞ for all j∈{0,..,x_o-1 }, and, consequently, ℛ_x_o≤ x_o^1-p·∑_k≥ 1 k^-plog k from (<ref>).





§ PROPOSITION <REF>



	If ϵ_n is O(n^-τ)  with τ∈ (0, 1/2), then 
	
	
    liminf_n →∞ξ_n(X_1,..,X_n) - ρ_n(X_1,..,X_n) ≥ 0,   ℙ_μ-a.s.



	By definition if σ(Γ_ϵ_n)⊂σ( Γ̃_ϵ_n/2) then 
	ξ_n(X_1,..,X_n) ≥ρ_n(X_1,..,X_n). Consequently,  if we define the set: 
	
	
    ℬ_n= { (x_1,..,x_n): σ(Γ_ϵ_n)⊂σ( Γ̃_ϵ_n/2)},

	then the proof reduced to verify that ℙ_μ(liminf_n  →∞ℬ_n) = ℙ_μ( ∪_n≥ 1 ∩_k≥ nℬ_k)=1.
	
	On the other hand, if sup_x∈Γ_ϵ_n|  μ̂_n({ x})  -  μ ( { x } ) | ≤ϵ_n/2 then by definition of Γ_ϵ, for all x∈Γ_ϵ_n μ ({ x}) ≥ϵ_n/2, i.e., Γ_ϵ_n⊂Γ̃_ϵ_n/2.  In other words, 
	
	
    𝒞_n= { (x_1,..,x_n): sup_x∈Γ_ϵ_n|  μ̂_n({ x})  -  μ ( { x } ) | ≤ϵ_n/2 }⊂ℬ_n.

	Finally, 
	
	
    ℙ^n_μ (𝒞^c_n)      = ℙ^n_μ( sup_x∈Γ_ϵ_n|  μ̂_n({ x})  -  μ ( { x } ) | > ϵ_n/2 ) ≤| Γ_ϵ_n| ·  e^-n ϵ^2/2≤1/ϵ_n·  e^-n ϵ^2/2.

	In this context, if we consider ϵ_n=O(n^-τ) and l>0, then we have that: 
	   
	   
    1/n^l·lnℙ^n_μ (𝒞^c_n) ≤τ·ln n/n^l - n^1-2τ -l/2.

	   Therefore, we have that for any  τ∈ (0,1/2) we can take l ∈ (0,1-2τ]
	   such that ℙ^n_μ (𝒞^c_n) is bounded by a term O(e^-n^l).  Then, 
	  the Borel Cantelli lemma tells us that 
	   ℙ_μ( ∪_n≥ 1 ∩_k≥ n𝒞_k)=1, which concludes the proof from (<ref>).







§ PROPOSITION <REF>


 
For the p-power tail dominating distribution stated in Theorem <ref>, 
if (ϵ_n) is O(n^-τ) with τ∈ (0,p) then

ξ_n(X_1,..,X_n)  is  o(n^-q)  for all  q∈ (0,(1-τ/p)/2), ℙ_μ-a.s.


	From the Hoeffding's inequality we have that
	
	
    ℙ^n_μ(  { x_1,..,x_n:   ξ_n(x_1,..,x_n) > δ})    ≤| σ(Γ̃_ϵ_n/2) | ·  e^-2n δ^2/log(1/ϵ_n)^2
       ≤ 2^(2k_o/ϵ_n)^1/p+1· e^-2n δ^2/log(1/ϵ_n)^2,

	the second inequality using that Γ̃_ϵ≤ (k_0/ϵ) ^1/p+1  from the definition 
	of Γ̃_ϵ in (<ref>) and the tail bounded assumption on μ.
	If we consider ϵ_n=O(n^-τ) and l>0, then we have that: 
	
	
    1/n^l·lnℙ^n_μ(  { x_1,..,x_n:   ξ_n(x_1,..,x_n) > δ}) 
    			   ≤ln 2  · (C n^τ/p-l+n^-l) -  2δ^2/τ^2·n^1-l/log n^2

	for some constant C>0. Then in order to obtain that ξ_n(X_1,..,X_n) converges almost surely to zero from (<ref>),  it is sufficient that l>0, l<1, and l>τ/p. This implies that if τ<p, 
	there is l∈ (τ/p,1) such that such that ℙ^n_μ (ξ_n(x_1,..,x_n) > δ ) is bounded 
	by a term O(e^-n^l) and, consequently,  lim_n →∞ξ_n(X_1,..,X_n)=0, ℙ_μ-a.s.[Using the same steps used in Appendix <ref>.]
	
	Moving to the rate of convergence of ξ_n(X_1,..,X_n) (assuming that τ<p), 
	let us consider δ_n=n^-q for some q≥ 0.  From (<ref>): 
	
	
    1/n^l·lnℙ^n_μ(  { x_1,..,x_n:   ξ_n(x_1,..,x_n) > δ_n  }) 
    			   ≤ln 2  · (C n^τ/p-l+n^-l) -  2δ^2/τ^2·n^1-2q-l/log n^2.

	To make ξ_n(X_1,..,X_n) being o(n^-q) ℙ-a.s., a sufficient condition is that 
	l>0, l>τ/p, and l<1-2q. Therefore (considering that τ<p),  the admissibility condition on the existence of a exponential rate of convergence O(e^-n^l) for l>0 for the deviation event { x_1,..,x_n:   ξ_n(x_1,..,x_n) > δ_n  } is that τ/p < 1-2q, which is equivalent to 0<q<1-τ/p/2.







			

