Shannon Entropy Estimation in ∞-Alphabets from Convergence Results: Studying Plug-In Estimators

Abstract

This work addresses the problem of Shannon entropy estimation in countably infinite alphabets studying and adopting some recent convergence results of the entropy functional, which is known to be a discontinuous function in the space of probabilities in ∞-alphabets. Sufficient conditions for the convergence of the entropy are used in conjunction with some deviation inequalities (including scenarios with both finitely and infinitely supported assumptions on the target distribution). From this perspective, four plug-in histogram-based estimators are studied showing that convergence results are instrumental to derive new strong consistent estimators for the entropy. The main application of this methodology is a new data-driven partition (plug-in) estimator. This scheme uses the data to restrict the support where the distribution is estimated by finding an optimal balance between estimation and approximation errors. The proposed scheme offers a consistent (distribution-free) estimator of the entropy in ∞-alphabets and optimal rates of convergence under certain regularity conditions on the problem (finite and unknown supported assumptions and tail bounded conditions on the target distribution).

1. Introduction

Shannon entropy estimation has a long history in information theory, statistics, and computer science [1]. Entropy and related information measures (conditional entropy and mutual information) have a fundamental role in information theory and statistics [2,3] and, as a consequence, it has found numerous applications in learning and decision making tasks [4,5,6,7,8,9,10,11,12,13,14,15]. In many of these contexts, distributions are not available and the entropy needs to be estimated from empirical data. This problem belongs to the category of scalar functional estimation that has been thoroughly studied in non-parametric statistics.

Starting with the finite alphabet scenario, the classical plug-in estimator (i.e., the empirical distribution evaluated on the functional) is well known to be consistent, minimax optimal, and asymptotically efficient [16] (Section 8.7–8.9). More recent research has focused on looking at the so-called large alphabet (or large dimensional) regime, meaning a non-asymptotic under-sampling regime where the number 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 [17,18]. For characterizing optimality in this high dimensional context, a non-asymptotic minimax mean square error analysis (under a finite n and k) has been explored by several authors [17,18,19,20,21] considering the minimax risk

$$R^{*}(k,n)=\underset{\widehat{H}(·)}{inf}\underset{\mu \in \mathcal{P}(k)}{sup}{\mathbb{E}}_{X_1,\dots X_n\sim {\mu }^n}\left\{{\left(\widehat{H}(X_1,\dots ,X_n)-H(\mu )\right)}^2\right\}$$

where $\mathcal{P}(k)$ denotes the collection of probabilities on $\left[k\right]\equiv \left\{1,\dots ,k\right\}$ and $H(\mu )$ is the entropy of $\mu$ (details in Section 2). Paninski [19] 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 Valiant et al. [20,21] shows that the optimal scaling of the sampling size with respect to k is O(k/$\log (k$)), to achieve the aforementioned asymptotic consistency for entropy estimation. 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 $\left\{\mathcal{P}(k):k\ge 1\right\}$ with practical estimators have been presented in [17,18]. On the other hand, it is well-known that the problem of estimating the distribution (consistently in total variation) in finite alphabets requires a sampling complexity that scales as $O(k)$ [22]. Consequently, in finite alphabets the task of entropy estimation is simpler than estimating the 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 [2,23,24,25].

1.1. The Challenging Infinite Alphabet Learning Scenario

In this work, we are interested in the countably infinite alphabet scenario, i.e., on the estimation of the entropy when the alphabet is countably infinite and we have a finite number of samples. This problem can be seen as an infinite dimensional regime as the size of the alphabet goes unbounded and n is kept finite for the analysis, which differs from the large dimensional regime mentioned above. As argued in [26] (Section IV), 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 context. Notably, it has been shown that the Shannon entropy is not a continuous functional with respect to the total variational distance in infinite alphabets [24,26,27]. In particular, Ho et al. [24] (Theorem 2) showed concrete examples where convergence in ${\chi }^2$-divergence and in direct information divergence (I-divergence) of a set of distributions to a limit, both stronger than total variational convergence [23,28], do not imply the convergence of the entropy. In addition, Harremoës [27] showed the discontinuity of the entropy with respect to the reverse I-divergence [29], 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. [29]). In entropy estimation, the discontinuity of the entropy implies that the minimax mean square error goes unbounded, i.e.,

$$R_n^{*}=\underset{\widehat{H}(·)}{inf}\underset{\mu \in \mathcal{H}(\mathbb{X})}{sup}{\mathbb{E}}_{X_1,\dots X_n\sim {\mu }^n}\left\{{\left(\widehat{H}(X_1,\dots ,X_n)-H(\mu )\right)}^2\right\}=\infty ,$$

where $\mathcal{H}(\mathbb{X})$ denotes the family of finite entropy distribution over the countable alphabet set $\mathbb{X}$ (the proof of this result follows from [26] (Theorem 1) and the argument is presented in Appendix A). Consequently, there is no universal minimax consistent estimator (in the mean square error sense) of the entropy over the family of finite entropy distributions.

Considering a sample-wise (or point-wise) convergence to zero of the estimation error (instead of the minimax expected error analysis mentioned above), Antos et al. [30] (Theorem 2 and Corollary 1) show 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 (point-wise). Then, the classical plug-in entropy estimator is universal, meaning that the convergence to the right limiting value $H(\mu )$ is achieved almost surely despite the discontinuity of the entropy. Moving on the analysis of the (point-wise) rate of convergence of the estimation error, Antos et al. [30] (Theorem 3) present a finite length lower bound for the error of any arbitrary estimation scheme, showing as a corollary that no universal rate of convergence (to zero) can be achieved for entropy estimation in infinite alphabets [30] (Theorem 4). Finally, constraining the problem to a family of distributions with specific power tail bounded conditions, Antos et al. [30] (Theorem 7) present a finite length expression for the rate of convergence of the estimation error of the classical plug-in estimate.

1.2. From Convergence Results to Entropy Estimation

In view of the discontinuity of the entropy in ∞-alphabets [24] and the results that guarantee entropy convergence [25,26,27,31], this work revisits the problem of point-wise almost-sure entropy estimation in ∞-alphabets from the perspective of studying and applying entropy convergence results and their derived bounds [25,26,31]. Importantly, entropy convergence results have established concrete conditions on both the limiting distribution $\mu$ and the way a sequence of distributions $\left\{{\mu }_n:n\ge 0\right\}$ converges to $\mu$ such that ${lim}_{n\to \infty }H({\mu }_n)=H(\mu )$ is satisfied. The natural observation that motivates this work is that consistency is basically a convergence to the true entropy value that happens with probability one. Then our main conjecture is that putting these conditions in the context of a learning task, i.e., where $\left\{{\mu }_n:n\ge 0\right\}$ is a random sequence of distributions driven by the classical empirical process, will offer the possibility to study a broad family of plug-in estimators with the objective to derive new strong consistency and rates of convergence results. On the practical side, this work proposes and analizes a data-driven histogram-based estimator as a key learning scheme, since this approach offers the flexibility to adapt to learning task when appropriate bounds for the estimation and approximation errors are derived.

1.3. Contributions

We begin revisiting the classical plug-in entropy estimator considering the relevant scenario where $\mu$ (the unknown distribution that produces the i.i.d. samples) has a finite but arbitrary large and unknown support. This is declared to be a challenging problem by Ho and Yeung [26] (Theorem 13) because of the discontinuity of the entropy. Finite-length (non-asymptotic) deviation inequalities and intervals of confidence are derived extending the results presented in [26] (Section IV). From this, it is shown that the classical plug-in estimate achieves optimal rates of convergence. Relaxing the finite support restriction on $\mu$, two concrete histogram-based plug-in estimators are presented, one built upon the celebrated Barron-Györfi-van der Meulen histogram-based approach [29,32,33]; and the other on a data-driven partition of the space [34,35,36]. For the Barron plug-in scheme, almost-sure consistency is shown for entropy estimation and distribution estimation in direct I-divergence under some mild support conditions on $\mu$. For the data-driven partition scheme, the main context of application of this work, it is shown that this estimator is strongly consistent distribution-free, matching the universal result obtained for the classical plug-in approach in [30]. Furthermore, new almost-sure rates of convergence results (in the estimation error) are obtained for distributions with finite but unknown support and for families of distributions with power and exponential tail dominating conditions. In this context, our results show that this adaptive scheme has a concrete design solution that offers very good convergence rate of the overall estimation error, as it approaches the rate $O(1/\sqrt{n})$ that is considered optimal for the finite alphabet case [16]. Importantly, the parameter selection of this scheme relies on, first, obtaining expressions to bound the estimation and approximation errors and, second, finding the optimal balance between these two learning errors.

1.4. Organization

The rest of the paper is organized as follows. Section 2 introduces some basic concepts, notation, and summarizes the main entropy convergence results used in this work. Section 3, Section 4 and Section 5 state and elaborate the main results of this work. Discussion of the results and final remarks are given in Section 6. The technical derivation of the main results are presented in Section 7. Finally, proofs of auxiliary results are relegated to the Appendix Section.

2. Preliminaries

Let $\mathbb{X}$ be a countably infinite set and let $\mathcal{P}(\mathbb{X})$ denote the collection of probability measures in $\mathbb{X}$. For $\mu$ and v in $\mathcal{P}(\mathbb{X})$, and $\mu$ absolutely continuous with respect to v (i.e., $\mu \ll v$), $\frac{d\mu }{dv}(x)$ denotes the Radon-Nikodym (RN) derivative of $\mu$ with respect to v. Every $\mu \in \mathcal{P}(\mathbb{X})$ is equipped with its probability mass function (pmf) that we denote by $f_{\mu }(x)\equiv \mu \left(\left\{x\right\}\right)$, $\forall x\in \mathbb{X}$. Finally, for any $\mu \in \mathcal{P}(\mathbb{X})$, $A_{\mu }\equiv \left\{x\in \mathbb{X}:f_{\mu }(x)>0\right\}$ denotes its support and

$$\mathcal{F}(\mathbb{X})\equiv \left\{\mu \in \mathcal{P}(\mathbb{X}):\left|A_{\mu }\right|<\infty \right\}$$

(1)

denotes the collection of probabilities with finite support.

Let $\mu$ and v be in $\mathcal{P}(\mathbb{X})$, then the total variation distance of $\mu$ and v is given by [28]

$$V(\mu ,v)\equiv \underset{A\in 2^{\mathbb{X}}}{sup}\left|v(A)-\mu (A)\right|,$$

(2)

where $2^{\mathbb{X}}$ denotes the subsets of $\mathbb{X}$. The Kullback–Leibler divergence or I-divergence of $\mu$ with respect to v is given by

$$D(\mu ||v)\equiv \sum _{x\in A_{\mu }}{f}_{\mu }(x)\log \frac{f_{\mu }(x)}{f_v(x)}\ge 0,$$

(3)

when $\mu \ll v$, while $D(\mu ||v)$ is set to infinite, otherwise [37].

The Shannon entropy of $\mu \in \mathcal{P}(\mathbb{X})$ is given by [1,2,38]:

$$H(\mu )\equiv -\sum _{x\in A_{\mu }}{f}_{\mu }(x)\log f_{\mu }(x)\ge 0.$$

(4)

In this context, let $\mathcal{H}(\mathbb{X})\subset \mathcal{P}(\mathbb{X})$ be the collection of probabilities where (4) is finite, let $\mathcal{AC}(\mathbb{X}|v)\subset \mathcal{P}(\mathbb{X})$ denote the collection of probabilities absolutely continuous with respect to $v\in \mathcal{P}(\mathbb{X})$, and let $\mathcal{H}(\mathbb{X}|v)\subset \mathcal{AC}(\mathbb{X}|v)$ denote the collection of probabilities where (3) is finite for $v\in \mathcal{P}(\mathbb{X})$.

Concerning convergence, a sequence $\left\{{\mu }_n:n\in \mathbb{N}\right\}\subset \mathcal{P}(\mathbb{X})$ is said to converge in total variation to $\mu \in \mathcal{P}(\mathbb{X})$ if

$$\underset{n\to \infty }{lim}V({\mu }_n,\mu )=0.$$

(5)

For countable alphabets, ref. [31] (Lemma 3) shows that the convergence in total variation is equivalent to the weak convergence, which is denoted here by ${\mu }_n\Rightarrow \mu$, and the point-wise convergence of the pmf’s. Furthermore, from (2), the convergence in total variation implies the uniform convergence of the pmf’s, i.e, ${lim}_{n\to \infty }{sup}_{x\in \mathbb{X}}\left|{\mu }_n(\left\{x\right\})-\mu (\left\{x\right\})\right|=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 Barron et al. [29]. It is said that $\left\{{\mu }_n:n\in \mathbb{N}\right\}$ converges to $\mu$ in direct and in reverse I-divergence if ${lim}_{n\to \infty }D(\mu ||{\mu }_n)=0$ and ${lim}_{n\to \infty }D({\mu }_n\left|\right|\mu )=0$, respectively. From Pinsker’s inequality [39,40,41], the convergence in I-divergence implies the weak convergence in (5), where it is known that the converse result is not true [27].

2.1. Convergence Results for the Shannon Entropy

The discontinuity of the entropy in ∞-alphabets raises the problem of finding conditions under which convergence of the entropy can be obtained. On this topic, Ho et al. [26] have studied the interplay between entropy and the total variation distance, specifying conditions for convergence by assuming a finite support on the involved distributions. On the other hand, Harremoës [27] (Theorem 21) obtained convergence of the entropy by imposing a power dominating condition [27] (Definition 17) on the limiting probability measure $\mu$ for all the sequences $\left\{{\mu }_n:n\ge 0\right\}$ converging in reverse I-divergence to $\mu$ [29]. More recently, Silva et al. [25] have addressed the entropy convergence studying a number of new settings that involve conditions on the limiting measure $\mu$, as well as the way the sequence $\left\{{\mu }_n:n\ge 0\right\}$ converges to $\mu$ in the space of distributions. These results offer sufficient conditions where the entropy evaluated in a sequence of distributions converges to the entropy of its limiting distribution and, consequently, the possibility of applying these when analyzing plug-in entropy estimators. The results used in this work are summarized in the rest of this section.

Let us begin with the case when $\mu \in \mathcal{F}(\mathbb{X})$, i.e., when the support of the limiting measure is finite and unknown.

Proposition 1.

Let us assume that $\mu \in \mathcal{F}(\mathbb{X})$ and $\left\{{\mu }_n:n\in \mathbb{N}\right\}\subset \mathcal{AC}(\mathbb{X}|\mu )$. If ${\mu }_n\Rightarrow \mu$, then ${lim}_{n\to \infty }D({\mu }_n\left|\right|\mu )=0$ and ${lim}_{n\to \infty }H({\mu }_n)=H(\mu )$.

This result is well-known because when $A_{{\mu }_n}\subset A_{\mu }$ for all n, the scenario reduces to the finite alphabet case, where the entropy is known to be continuous [2,23]. Since we obtain two inequalities that are used in the following sections, a simple proof is provided here.

Proof. 

$\mu$ and ${\mu }_n$ belong to $\mathcal{H}(\mathbb{X})$ from the finite-supported assumption. The same argument can be used to show that $D({\mu }_n||\mu )<\infty$, since ${\mu }_n\ll \mu$ for all n. Let us consider the following identity:

$$H(\mu )-H({\mu }_n)=\sum _{x\in A_{\mu }}(f_{{\mu }_n}(x)-f_{\mu }(x))\log f_{\mu }(x)+D({\mu }_n\left|\right|\mu ).$$

(6)

The first term on the right hand side (RHS) of (6) is upper bounded by ${\mathbf{M}}_{\mu }·V({\mu }_n,\mu )$ where

$${\mathbf{M}}_{\mu }=\log \frac{1}{{\mathbf{m}}_{\mu }}\equiv \underset{x\in A_{\mu }}{sup}\left|\log \mu (\left\{x\right\})\right|<\infty .$$

(7)

For the second term, we have that

$$\begin{array}{cc}\hfill D({\mu }_n||\mu )& \le \log e·\sum _{x\in A_{{\mu }_n}}{f}_{{\mu }_n}(x)\left|\frac{f_{{\mu }_n}(x)}{f_{\mu }(x)}-1\right|\hfill \\ & \le \frac{\log e}{{\mathbf{m}}_{\mu }}·\underset{x\in A_{\mu }}{sup}\left|f_{{\mu }_n}(x)-f_{\mu }(x)\right|\le \frac{\log e}{{\mathbf{m}}_{\mu }}·V({\mu }_n,\mu ).\hfill \end{array}$$

(8)

and, consequently,

$$\begin{array}{c}\hfill \left|H(\mu )-H({\mu }_n)\right|\le \left[{\mathbf{M}}_{\mu }+\frac{\log e}{{\mathbf{m}}_{\mu }}\right]·V({\mu }_n,\mu ).\end{array}$$

(9)

☐

Under the assumptions of Proposition 1, we note that the reverse I-divergence and the entropy difference are bounded by the total variation by (8) and (9), respectively. Note, however, that these bounds are a distribution-dependent function of ${\mathbf{m}}_{\mu }$(${\mathbf{M}}_{\mu }$) in (7) (it is direct to show that ${\mathbf{m}}_{\mu }({\mathbf{M}}_{\mu })<\infty$ if, and only if, $\mu \in \mathcal{F}(\mathbb{X})$). The next result relaxes the assumption that ${\mu }_n\ll \mu$ and offers a necessary and sufficient condition for the convergence of the entropy.

Lemma 1.

Ref. [25] (Theorem 1) Let $\mu \in \mathcal{F}(\mathbb{X})$ and $\left\{{\mu }_n:n\in \mathbb{N}\right\}\subset \mathcal{F}(\mathbb{X})$. If ${\mu }_n\Rightarrow \mu$, then there exists $N>0$ such that $\mu \ll {\mu }_n$ $\forall n\ge N$, and

$$\underset{n\to \infty }{lim}D(\mu ||{\mu }_n)=0.$$

Furthermore, ${lim}_{n\to \infty }H({\mu }_n)=H(\mu )$, if and only if,

$$\underset{n\to \infty }{lim}{\mu }_n\left(A_{{\mu }_n}\backslash A_{\mu }\right)·H\left({\mu }_n\left(·|A_{{\mu }_n}\backslash A_{\mu }\right)\right)=0\iff \underset{n\to \infty }{lim}\sum _{x\in A_{{\mu }_n}\backslash A_{\mu }}{f}_{{\mu }_n}(x)\log \frac{1}{f_{{\mu }_n}(x)}=0,$$

(10)

where $\mu (·|B)$ denotes the conditional probability of μ given the event $B\subset \mathbb{X}$.,

Lemma 1 tells us that 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 ${\mu }_n$ restricted to the elements of the set $A_{{\mu }_n}\backslash A_{\mu }$. Two remarks about this result are: (1) The convergence in direct I-divergence does not imply the convergence of the entropy (concrete examples are presented in [24] (Section III) and [25]); (2) Under the assumption that $\mu \in \mathcal{F}(\mathbb{X})$, $\mu$ is eventually absolutely continuous with respect to ${\mu }_n$, and the convergence in total variations is equivalent to the convergence in direct I-divergence.

This section concludes with the case when the support of $\mu$ is infinite and unknown, i.e., $\left|A_{\mu }\right|=\infty$. In this context, two results are highlighted:

Lemma 2.

Ref. [31] (Theorem 4) Let us consider that $\mu \in \mathcal{H}(\mathbb{X})$ and $\left\{{\mu }_n:n\ge 0\right\}\subset \mathcal{AC}(\mathbb{X}|\mu )$. If ${\mu }_n\Rightarrow \mu$ and

$$M\equiv \underset{n\ge 1}{sup}\underset{x\in A_{\mu }}{sup}\frac{f_{{\mu }_n}(x)}{f_{\mu }(x)}<\infty ,$$

(11)

then ${\mu }_n\in \mathcal{H}(\mathbb{X})\cap \mathcal{H}(\mathbb{X}|\mu )$ for all n and it follows that

$$\underset{n\to \infty }{lim}D({\mu }_n\left|\right|\mu )=0\mathrm{and}\underset{n\to \infty }{lim}H({\mu }_n)=H(\mu ).$$

Interpreting Lemma 2 we have that, to obtain the convergence of the entropy functional (without imposing a finite support assumption on $\mu$), a uniform bounding condition (UBC) $\mu$-almost everywhere was added in (11). By adding this UBC, the convergence on reverse I-divergence is also obtained as a byproduct. Finally, when $\mu \ll {\mu }_n$ for all n, the following result is considered:

Lemma 3.

Ref. [25] (Theorem 3) Let $\mu \in \mathcal{H}(\mathbb{X})$ and a sequence of measures $\left\{{\mu }_n:n\ge 1\right\}\subset \mathcal{H}(\mathbb{X})$ such that $\mu \ll {\mu }_n$ for all $n\ge 1$. If ${\mu }_n\Rightarrow \mu$ and

$$\underset{n\ge 1}{sup}\underset{x\in A_{\mu }}{sup}\left|\log \frac{f_{{\mu }_n}(x)}{f_{\mu }(x)}\right|<\infty$$

(12)

then, $\mu \in \mathcal{H}(\mathbb{X}|{\mu }_n)$ for all $n\ge 1$, and

$$\underset{n\to \infty }{lim}D(\mu ||{\mu }_n)=0.$$

Furthermore, ${lim}_{n\to \infty }H({\mu }_n)=H(\mu )$, if and only if,

$$\underset{n\to \infty }{lim}\sum _{x\in A_{{\mu }_n}\backslash A_{\mu }}{f}_{{\mu }_n}(x)\log \frac{1}{f_{{\mu }_n}(x)}=0.$$

(13)

This result shows the non-sufficiency of the convergence in direct I-divergence to achieve entropy convergence in the regime when $\mu \ll {\mu }_n$. In fact, Lemma 3 may be interpreted as an extension of Lemma 1 when the finite support assumption over $\mu$ is relaxed.

3. Shannon Entropy Estimation

Let $\mu$ be a probability in $\mathcal{H}(\mathbb{X})$, and let denote by $X_1,X_2,X_3,\dots$ the empirical process induced from i.i.d. realizations of a random variable driven by $\mu$, i.e., $X_i\sim \mu$, for all $i\ge 0$. Let ${\mathbb{P}}_{\mu }$ denote the distribution of the empirical process in $({\mathbb{X}}^{\infty },\mathcal{B}({\mathbb{X}}^{\infty }))$ and ${\mathbb{P}}_{\mu }^n$ denote the finite block distribution of $X^n\equiv (X_1,\dots ,X_n)$ in the product space $({\mathbb{X}}^n,\mathcal{B}({\mathbb{X}}^n))$. Given a realization of $X_1,X_2,X_3,\dots ,X_n$, we can construct an histogram-based estimator like classical empirical probability given by:

$${\widehat{\mu }}_n(A)\equiv \frac{1}{n}\sum _{k=1}^n{\mathbf{1}}_A(X_k),\forall A\subset \mathbb{X},$$

(14)

with pmf given by $f_{{\widehat{\mu }}_n}(x)={\widehat{\mu }}_n(\left\{x\right\})$ for all $x\in \mathbb{X}$. A natural estimator of the entropy is the plug-in estimate of ${\widehat{\mu }}_n$ given by

$$H({\widehat{\mu }}_n)=-\sum _{x\in \mathbb{X}}{f}_{{\widehat{\mu }}_n}(x)\log f_{{\widehat{\mu }}_n}(x),$$

(15)

which is a measurable function of $X_1,\dots ,X_n$ (this dependency on the data will be implicit for the rest of the paper).

For the rest of this Section and Section 4 and Section 5, the convergence results in Section 2.1 are used to derive strong consistency results for plug-in histogram-based estimators, like $H({\widehat{\mu }}_n)$ in (15), as well as finite length concentration inequalities to obtain almost-sure rates of convergence for the overall estimation error $\left|H({\widehat{\mu }}_n)-H(\mu )\right|$.

3.1. Revisiting the Classical Plug-In Estimator for Finite and Unknown Supported Distributions

We start by analyzing the case when $\mu$ has a finite but unknown support. A consequence of the strong law of large numbers [42,43] is that $\forall x\in \mathbb{X}$, ${lim}_{n\to \infty }{\widehat{\mu }}_n(\left\{x\right\})=\mu (\left\{x\right\})$, ${\mathbb{P}}_{\mu }$-almost surely (a.s.), hence ${lim}_{n\to \infty }V({\widehat{\mu }}_n,\mu )=0$, ${\mathbb{P}}_{\mu }$-a.s. On the other hand, it is clear that $A_{{\widehat{\mu }}_n}\subset A_{\mu }$ holds with probability one. Then Proposition 1 implies that

$$\begin{array}{c}\underset{n\to \infty }{lim}D({\widehat{\mu }}_n\left|\right|\mu )=0\mathrm{and}\underset{n\to \infty }{lim}H({\widehat{\mu }}_n)=H(\mu ),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,\hfill \end{array}$$

(16)

i.e., ${\widehat{\mu }}_n$ is a strongly consistent estimator of $\mu$ in reverse I-divergence and $H({\widehat{\mu }}_n)$ is a strongly consistent estimate of $H(\mu )$ distribution-free in $\mathcal{F}(\mathbb{X})$. Furthermore, the following can be stated:

Theorem 1.

Let $\mu \in \mathcal{F}(\mathbb{X})$ and let us consider ${\widehat{\mu }}_n$ in (14). Then ${\widehat{\mu }}_n\in \mathcal{H}(\mathbb{X})\cap \mathcal{H}(\mathbb{X}|\mu )$, ${\mathbb{P}}_{\mu }$-a.s and $\forall n\ge 1$, $\forall ϵ>0$,

$$\begin{array}{c}{\mathbb{P}}_{\mu }^n\left(D({\widehat{\mu }}_n||\mu )>ϵ\right)\le 2^{\left|A_{\mu }\right|+1}·e^{-\frac{2{\mathbf{m}}_{\mu }^2·n{ϵ}^2}{\log e^2}},\hfill \end{array}$$

(17)

$$\begin{array}{c}{\mathbb{P}}_{\mu }^n\left(\left|H({\widehat{\mu }}_n)-H(\mu )\right|>ϵ\right)\le 2^{\left|A_{\mu }\right|+1}·e^{-\frac{2n{ϵ}^2}{{({\mathbf{M}}_{\mu }+\frac{\log e}{{\mathbf{m}}_{\mu }})}^2}}.\hfill \end{array}$$

(18)

Moreover, $D(\mu ||{\widehat{\mu }}_n)$ is eventually finite with probability one and $\forall ϵ>0$, and for any $n\ge 1$,

$$\begin{array}{cc}\hfill & {\mathbb{P}}_{\mu }^n\left(D(\mu ||{\widehat{\mu }}_n)>ϵ\right)\le 2^{\left|A_{\mu }\right|+1}·\left[e^{-\frac{2n{ϵ}^2}{\log e^2·{\left(1/{\mathbf{m}}_u+1\right)}^2}}+e^{-n{\mathbf{m}}_{\mu }^2}\right].\hfill \end{array}$$

(19)

This result implies that for any $\tau \in (0,1/2)$ and $\mu \in \mathcal{F}(\mathbb{X})$, $\left|H({\widehat{\mu }}_n)-H(\mu )\right|$, $D({\widehat{\mu }}_n||\mu )$, and $D(\mu ||{\widehat{\mu }}_n)$ goes to zero as $o(n^{-\tau })$ ${\mathbb{P}}_{\mu }$-a.s. Furthermore, ${\mathbb{E}}_{{\mathbb{P}}_{\mu }^n}\left(\left|H({\widehat{\mu }}_n)-H(\mu )\right|\right)$ and ${\mathbb{E}}_{{\mathbb{P}}_{\mu }^n}(D({\widehat{\mu }}_n\left|\right|\mu ))$ behave like $O(1/\sqrt{n})$ for all $\mu \in \mathcal{F}(\mathbb{X})$ from (30) in Section 7, which is the optimal rate of convergence of the finite alphabet scenario. As a corollary of (18), it is possible to derive intervals of confidence for the estimation error $\left|H(({\widehat{\mu }}_n)-H({\mu }_n)\right|$: for all $\delta >0$ and $n\ge 1$,

$$\begin{array}{c}\hfill {\mathbb{P}}_{\mu }\left(\left|H(({\widehat{\mu }}_n)-H({\mu }_n)\right|\le \left({\mathbf{M}}_{\mu }+\log e/{\mathbf{m}}_{\mu }\right)\sqrt{\frac{1}{2n}\ln \frac{2^{\left|A_{\mu }\right|+1}}{\delta }}\right)\ge 1-\delta .\end{array}$$

(20)

This confidence interval behaves like $O(1/\sqrt{n})$ as a function of n, and like $O(\sqrt{\ln 1/\delta })$ as a function of $\delta$, which are the same optimal asymptotic trends that can be obtained for $V(\mu ,{\widehat{\mu }}_n)$ in (30).

Finally, we observe that $A_{{\widehat{\mu }}_n}\subset A_{\mu }$ ${\mathbb{P}}_{\mu }^n$-a.s. where for any $n\ge 1$, ${\mathbb{P}}_{\mu }^n(A_{{\widehat{\mu }}_n}\ne A_{\mu })>0$ implying that ${\mathbb{E}}_{{\mathbb{P}}_{\mu }^n}(D(\mu \left|\right|{\widehat{\mu }}_n))=\infty$ for all finite n. Then even in the finite and unknown supported scenario, ${\widehat{\mu }}_n$ is not consistent in expected direct I-divergence, which is congruent with the result in [29,44]. Besides this negative result, strong consistency in direct I-divergence can be obtained from (19), in the sense that ${lim}_{n\to \infty }D(\mu ||{\widehat{\mu }}_n)=0$, ${\mathbb{P}}_{\mu }$-a.s.

3.2. A Simplified Version of the Barron Estimator for Finite Supported Probabilities

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 [2,23,29,44,45,46,47,48]. Here, we explore an estimator that achieves this learning objective, in addition to entropy estimation. For that, let $\mu \in \mathcal{F}(\mathbb{X})$ and let assume $v\in \mathcal{F}(\mathbb{X})$ such that $\mu \ll v$. Barron et al. [29] proposed a modified version of the empirical measure in (14) to estimate $\mu$ from i.i.d. realizations, adopting a mixture estimate of the form

$$\begin{array}{c}\hfill {\tilde{\mu }}_n(B)=(1-a_n)·{\widehat{\mu }}_n(B)+a_n·v(B),\end{array}$$

(21)

for all $B\subset \mathbb{X}$, and with ${(a_n)}_{n\in \mathbb{N}}$ a sequence of real numbers in $(0,1)$. Note that $A_{{\tilde{\mu }}_n}=A_v$ then $\mu \ll {\tilde{\mu }}_n$ for all n and from the finite support assumption $H({\tilde{\mu }}_n)<\infty$ and $D(\mu ||{\tilde{\mu }}_n)<\infty$, ${\mathbb{P}}_{\mu }$-a.s.. The following result derives from the convergence result in Lemma 1.

Theorem 2.

Let $v\in \mathcal{F}(\mathbb{X})$, $\mu \ll v$ and let us consider ${\tilde{\mu }}_n$ in (21) induced from i.i.d. realizations of μ.

(i) 

If $(a_n)$ is $o(1)$, then ${lim}_{n\to \infty }H({\tilde{\mu }}_n)=H(\mu )$, ${lim}_{n\to \infty }D(\mu ||{\tilde{\mu }}_n)=0$, ${\mathbb{P}}_{\mu }$-a.s., and ${lim}_{n\to \infty }{\mathbb{E}}_{{\mathbb{P}}_{\mu }}(D(\mu \left|\right|{\tilde{\mu }}_n))=0$.

(ii) 

Furthermore, if $(a_n)$ is $O(n^{-p})$ with $p>2$, then for all $\tau \in (0,1/2)$, $\left|H({\tilde{\mu }}_n)-H(\mu )\right|$ and $D(\mu ||{\tilde{\mu }}_n)$ are $o(n^{-\tau })$ ${\mathbb{P}}_{\mu }$-a.s, and ${\mathbb{E}}_{{\mathbb{P}}_{\mu }}(\left|H({\tilde{\mu }}_n)-H(\mu )\right|)$ and ${\mathbb{E}}_{{\mathbb{P}}_{\mu }}(D(\mu \left|\right|{\tilde{\mu }}_n))$ are $O(1/\sqrt{n})$.

Using this approach, we achieve estimation of the true distribution in expected information divergence as well as strong consistency for entropy estimation as intended. In addition, optimal rates of convergence are obtained under the finite support assumption on $\mu$.

4. The Barron-Györfi-van der Meulen Estimator

The celebrated Barron estimator was proposed by Barron, Györfi and van der Meulen [29] in the context of an abstract and continuous measurable space. It is designed as a variation of the classical histogram-based scheme to achieve a consistent estimation of the distribution in direct I-divergence [29] (Theorem 2). Here, the Barron estimator is revisited in the 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 literature. For that purpose, the convergence result in Lemma 3 will be used as a key result.

Let $v\in \mathcal{P}(\mathbb{X})$ be of infinite support (i.e., ${\mathbf{m}}_v={inf}_{x\in A_v}v(\left\{x\right\})=0$). We want to construct a strongly consistent estimate of the entropy restricted to the collection of probabilities in $\mathcal{H}(\mathbb{X}|v)$. For that, let us consider a sequence ${(h_n)}_{n\ge 0}$ with values in $(0,1)$ and let us denote by ${\pi }_n=\left\{A_{n,1},A_{n,2},\dots ,A_{n,m_n}\right\}$ the finite partition of $\mathbb{X}$ with maximal cardinality satisfying that

$$v(A_{n,i})\ge h_n,\forall i\in \left\{1,\dots ,m_n\right\}.$$

(22)

Note that $m_n=\left|{\pi }_n\right|\le 1/h_n$ for all $n\ge 1$, and because of the fact that ${inf}_{x\in A_v}v(\left\{x\right\})=0$ it is simple to verify that if $(h_n)$ is $o(1)$ then ${lim}_{n\to \infty }{m}_n=\infty$. ${\pi }_n$ offers an approximated statistically equivalent partition of $\mathbb{X}$ with respect to the reference measure v. In this context, given $X_1,\dots ,X_n$, i.i.d. realizations of $\mu \in \mathcal{H}(\mathbb{X}|v)$, the idea proposed by Barron et al. [29] is to estimate the RN derivative $\frac{d\mu }{dv}(x)$ by the following histogram-based construction:

$$\frac{d{\mu }_n^{*}}{dv}(x)=(1-a_n)·\frac{{\widehat{\mu }}_n(A_n(x))}{v(A_n(x))}+a_n,\forall x\in A_v,$$

(23)

where $a_n$ is a real number in $(0,1)$, $A_n(x)$ denotes the cell in ${\pi }_n$ that contains the point x, and ${\widehat{\mu }}_n$ is the empirical measure in (14). Note that

$$f_{{\mu }_n^{*}}(x)=\frac{d{\mu }_n^{*}}{d\lambda }(x)=f_v(x)·\left[(1-a_n)·\frac{{\widehat{\mu }}_n(A_n(x))}{v(A_n(x))}+a_n\right],$$

$\forall x\in \mathbb{X}$, and, consequently, $\forall B\subset \mathbb{X}$

$${\mu }_n^{*}(B)=(1-a_n)\sum _{i=1}^{m_n}{\widehat{\mu }}_n(A_{n,i})·\frac{v(B\cap A_{n,i})}{v(A_{n,i})}+a_{n}v(B).$$

(24)

By construction $A_{\mu }\subset A_v\subset A_{{\mu }_n^{*}}$ and, consequently, $\mu \ll {\mu }_n^{*}$ for all $n\ge 1$. The next result shows sufficient conditions on the sequences $(a_n)$ and $(h_n)$ to guarantee a strongly consistent estimation of the entropy $H(\mu )$ and of $\mu$ in direct I-divergence, distribution free in $\mathcal{H}(\mathbb{X}|v)$. The proof is based on verifying that the sufficient conditions of Lemma 3 are satisfied ${\mathbb{P}}_{\mu }$-a.s.

Theorem 3.

Let v be in $\mathcal{P}(\mathbb{X})\cap \mathcal{H}(\mathbb{X})$ with infinite support, and let us consider μ in $\mathcal{H}(\mathbb{X}|v)$. If we have that:

(i) 

$(a_n)$ is $o(1)$ and $(h_n)$ is $o(1)$,

(ii) 

$\exists \tau \in (0,1/2)$, such that the sequence $\left(\frac{1}{a_n·h_n}\right)$ is $o(n^{\tau })$,

then $\mu \in \mathcal{H}(\mathbb{X})\cap \mathcal{H}(\mathbb{X}|{\mu }_n^{*})$ for all $n\ge 1$ and

$$\underset{n\to \infty }{lim}H({\mu }_n^{*})=H(\mu )\mathrm{and}\underset{n\to \infty }{lim}D(\mu ||{\mu }_n^{*})=0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}..$$

(25)

This result shows an admisible regime of design parameters and its scaling with the number of samples that guarantees that the Barron plug-in entropy estimator is strongly consistent in $\mathcal{H}(\mathbb{X}|v)$. As a byproduct, we obtain that the distribution $\mu$ is estimated consistently in direct information divergence.

The Barron estimator [29] was originally proposed in the context of distributions defined in an abstract measurable space. Then if we restrict [29] (Theorem 2) to the countable alphabet case, the following result is obtained:

Corollary 1.

Ref. [29] (Theorem 2) Let us consider $v\in \mathcal{P}(\mathbb{X})$ and $\mu \in \mathcal{H}(\mathbb{X}|v)$. If $(a_n)$ is $o(1)$, $(h_n)$ is $o(1)$ and $lim{sup}_{n\to \infty }\frac{1}{n{a}_n{h}_n}\le 1$ then

$$\underset{n\to \infty }{lim}D(\mu ||{\mu }_n^{*})=0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$$

When the only objective is the estimation of distributions consistently in direct I-divergence, Corollary 1 should be considered to be a better result than Theorem 3 (Corollary 1 offers weaker conditions than Theorem 3 in particular condition (ii)). The proof of Theorem 3 is based on verifying the sufficient conditions of Lemma 3, where the objective is to achieve the convergence of the entropy, and as a consequence, the convergence in direct I-divergence. Therefore, we can say that the stronger conditions of Theorem 3 are needed when the objective is entropy estimation. This is justified from the observation that convergence in direct I-divergence does not imply entropy convergence in ∞-alphabets, as is discussed in Section 2.1 (see, Lemmas 1 and 3).

5. A Data-Driven Histogram-Based Estimator

Data-driven partitions offer a better approximation to the data distribution in the sample space than conventional non-adaptive histogram-based approaches [34,49]. They have the capacity to improve the approximation quality of histogram-based learning schemes, which translates in better performance in different non-parametric learning settings [34,35,36,50,51]. One of the basic design principles of this approach is to partition or select a sub-set of elements of $\mathbb{X}$ in a data-dependent way to preserve a critical number of samples per cell. In our problem, this last condition proves to be crucial to derive bounds for the estimation and approximation errors. Finally, these expressions will be used to propose design solutions that offer an optimal balance between estimation and approximation errors (Theorems 5 and 6).

Given $X_1,\dots ,X_n$ i.i.d. realizations driven by $\mu \in \mathcal{H}(\mathbb{X})$ and $ϵ>0$, let us define the data-driven set

$${\mathsf{\Gamma }}_{ϵ}\equiv \left\{x\in \mathbb{X}:{\widehat{\mu }}_n(\left\{x\right\})\ge ϵ\right\},$$

(26)

and ${\varphi }_{ϵ}\equiv {\mathsf{\Gamma }}_{ϵ}^c$. Let ${\mathsf{\Pi }}_{ϵ}\equiv \left\{\left\{x\right\}:x\in {\mathsf{\Gamma }}_{ϵ}\right\}\cup \left\{{\varphi }_{ϵ}\right\}\subset 2^{\mathbb{X}}$ be a data-driven partition with maximal resolution in ${\mathsf{\Gamma }}_{ϵ}$, and ${\sigma }_{ϵ}\equiv \sigma ({\mathsf{\Pi }}_{ϵ})$ be the smallest sigma field that contains ${\mathsf{\Pi }}_{ϵ}$ (as ${\mathsf{\Pi }}_{ϵ}$ is a finite partition, ${\sigma }_{ϵ}$ is the collection of sets that are union of elements of ${\mathsf{\Pi }}_{ϵ}$). We propose the conditional empirical probability restricted to ${\mathsf{\Gamma }}_{ϵ}$ by:

$${\widehat{\mu }}_{n,ϵ}\equiv {\widehat{\mu }}_n(·|{\mathsf{\Gamma }}_{ϵ}).$$

(27)

By construction, it follows that $A_{{\widehat{\mu }}_{n,ϵ}}={\mathsf{\Gamma }}_{ϵ}\subset A_{\mu }$, ${\mathbb{P}}_{\mu }$-a.s. and this implies that ${\widehat{\mu }}_{n,ϵ}\ll \mu$ for all $n\ge 1$. Furthermore, $\left|{\mathsf{\Gamma }}_{ϵ}\right|\le \frac{1}{ϵ}$ and, importantly in the context of the entropy functional, it follows that

$${\mathbf{m}}_{{\widehat{\mu }}_n}^{ϵ}\equiv \underset{x\in {\mathsf{\Gamma }}_{ϵ}}{inf}{\widehat{\mu }}_n(\left\{x\right\})\ge ϵ.$$

(28)

The next result establishes a mild sufficient condition on $({ϵ}_n)$ for which $H({\widehat{\mu }}_{n,{ϵ}_n})$ is strongly consistent distribution-free in $\mathcal{H}(\mathbb{X})$. Considering that we are in the regime where ${\widehat{\mu }}_{n,{ϵ}_n}\ll \mu$, ${\mathbb{P}}_{\mu }$-a.s., the proof of this result uses the convergence result in Lemma 2 as a central result.

Theorem 4.

If $({ϵ}_n)$ is $O(n^{-\tau })$ with $\tau \in (0,1)$, then for all $\mu \in \mathcal{H}(\mathbb{X})$

$$\underset{n\to \infty }{lim}H({\widehat{\mu }}_{n,{ϵ}_n})=H(\mu ),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$$

Complementing Theorem 4, the next result offers almost-sure rates of converge for a family of distributions with a power tail bounded condition (TBC). In particular, the family of distributions studied in [30] (Theorem 7) are considered.

Theorem 5.

Let us assume that for some $p>1$ there are two constants $0<k_0\le k_1$ and $N>0$ such that $k_0·x^{-p}\le \mu (\left\{x\right\})\le k_1{x}^{-p}$ for all $x\ge N$. If we consider that $({ϵ}_n)\approx (n^{-{\tau }^{*}})$ for ${\tau }^{*}=\frac{1}{2+1/p}$, then

$$\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\mathrm{is}O(n^{-\frac{1-1/p}{2+1/p}}),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$$

This result shows that under the mentioned p-power TBC on $f_{\mu }(·)$, the plug-in estimator $H({\widehat{\mu }}_{n,{ϵ}_n})$ can achieve a rate of convergence to the true limit that is $O(n^{-\frac{1-1/p}{2+1/p}})$ with probability one. For the derivation of this result, the approximation sequence $({ϵ}_n)$ is defined as a function of p (adapted to the problem) by finding an optimal tradeoff between estimation and approximation errors while performing a finite length (non-asymptotic) analysis of the expression $\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$ (the details of this analysis are presented in Section 7).

It is insightful to look at two extreme regimes of this result: p approaching 1, in which the rate is arbitrarily slow (approaching a non-decaying behavior); and $p\to \infty$, where $\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$ is $O(n^{-q})$ for all $q\in (0,1/2)$ ${\mathbb{P}}_{\mu }$-a.s.. This last power decaying range $q\in (0,1/2)$ matches what is achieved for the finite alphabet scenario (for instance in Theorem 1, Equation (18)), which is known to be the optimal rate for finite alphabets.

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

Theorem 6.

Let us consider $\alpha >0$ and let us assume that there are $k_0,k_1$ with $0<k_0\le k_1$ and $N>0$ such that $k_0·e^{-\alpha x}\le \mu (\left\{x\right\})\le k_1·e^{-\alpha x}$ for all $x\ge N$. If we consider $({ϵ}_n)\approx (n^{-\tau })$ with $\tau \in (0,1/2)$, then

$$\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\mathrm{is}O(n^{-\tau }\log n),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$$

Under this stringent TBC on $f_{\mu }(·)$, it is observed that $\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\mathrm{is}o(n^{-q})$ ${\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$, for any arbitrary $q\in (0,1/2)$, by selecting $({ϵ}_n)\approx (n^{-\tau })$ with $q<\tau <1/2$. This last condition on $\tau$ is universal over $\alpha >0$. Remarkably, for any distribution with this exponential TBC, we can approximate (arbitrarily closely) the optimal almost-sure rate of convergence achieved for the finite alphabet problem.

Finally, the finite and unknown supported scenario is revisited, where it is shown that the data-driven estimator exhibits the optimal almost sure convergence rate of the classical plug-in entropy estimator presented in Section 3.1.

Theorem 7.

Let us assume that $\mu \in \mathcal{F}(\mathbb{X})$ and $({ϵ}_n)$ being $o(1)$. Then for all $ϵ>0$ there is $N>0$ such that $\forall n\ge N$

$${\mathbb{P}}_{\mu }^n\left(\left|H({\widehat{\mu }}_{n,{ϵ}_n})-H(\mu )\right|>ϵ\right)\le 2^{\left|A_{\mu }\right|+1}·\left[e^{-\frac{2n{ϵ}^2}{{({\mathbf{M}}_{\mu }+\frac{\log e}{{\mathbf{m}}_{\mu }})}^2}}+e^{-\frac{n{\mathbf{m}}_{\mu }^2}{4}}\right].$$

(29)

The proof of this result reduces to verify that ${\widehat{\mu }}_{n,{ϵ}_n}$ detects $A_{\mu }$ almost-surely when n goes to infinity and from this, it follows that $H({\widehat{\mu }}_{n,{ϵ}_n})$ eventually matches the optimal almost sure performance of $H({\widehat{\mu }}_n)$ under the key assumption that $\mu \in \mathcal{F}(\mathbb{X})$. Finally, the concentration bound in (29) implies that $\left|H({\widehat{\mu }}_{n,{ϵ}_n})-H(\mu )\right|$ is $o(n^{-q})$ almost surely for all $q\in (0,1/2)$ as long as ${ϵ}_n\to 0$ with n.

6. Discussion of the Results and Final Remarks

This work shows that entropy convergence results are instrumental to derive new (strongly consistent) estimation results for the Shannon entropy in ∞-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 convergence in the context of four plug-in histogram-based schemes, this work shows concrete design conditions where strong consistency for entropy estimation in ∞-alphabets can be obtained (Theorems 2–4). In addition, the relevant case where the target distribution has a finite but unknown support is explored, deriving almost sure rates of convergence results for the overall estimation error (Theorems 1 and 7) that match the optimal asymptotic rate that can be obtained in the finite alphabet version of the problem (i.e., the finite and known supported case).

As the main context of application, this work focuses on the case of a data-driven plug-in estimator that restricts the support where the distribution is estimated. The idea is to have design parameters that control estimation-error effects and to find an adequate balance between these two learning errors. Adopting the entropy convergence result in Lemma 2, it is shown 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 4). In addition, by addressing the technical task of deriving concrete closed-form expressions for the estimation and approximation errors in this learning context a solution is presented where almost-sure rates of convergence of the overall estimation error are obtained over a family of distributions with some concrete tail bounded conditions (Theorems 5 and 6). These results show the capacity that data-driven frameworks offer for adapting aspects of their learning scheme to the complexity of the entropy estimation task in ∞-alphabets.

Concerning the classical plug-in estimator presented in Section 3.1, it is important to mention that the work of Antos et al. [30] shows that ${lim}_{n\to \infty }H({\widehat{\mu }}_n)=H(\mu )$ happens almost surely and distribution-free and, furthermore, it provides rates of convergence for families with specific tail-bounded conditions [30] (Theorem 7). Theorem 1 focuses on the case when $\mu \in \mathcal{F}(\mathbb{X})$, where new finite-length deviation inequalities and confidence intervals are derived. From that perspective, Theorem 1 complements the results presented in [30] in the non-explored scenario when $\mu \in \mathcal{F}(\mathbb{X})$. It is also important to mention two results by Ho and Yeung [26] (Theorems 11 and 12) for the plug-in estimator in (15). They derived bounds for ${\mathbb{P}}_{\mu }^n(\left|H({\widehat{\mu }}_n)-H(\mu )\right|\ge ϵ)$ and determined confidence intervals under a finite and known support restriction on $\mu$. In contrast, Theorem 1 resolves the case for a finite and unknown supported distribution, which is declared to be a challenging problem from the arguments presented in [26] (Theorem 13) concerning the discontinuity of the entropy.

7. Proof of the Main Results

Proof of Theorem 1.

Let $\mu$ be in $\mathcal{F}(\mathbb{X})$, then $\left|A_{\mu }\right|\le k$ for some $k>1$. From Hoeffding’s inequality [28], $\forall n\ge 1$, and for any $ϵ>0$

$$\begin{array}{c}\hfill {\mathbb{P}}_{\mu }^n\left(V({\widehat{\mu }}_n,\mu )>ϵ\right)\le 2^{k+1}·e^{-2n{ϵ}^2}\mathrm{and}{\mathbb{E}}_{{\mathbb{P}}_{\mu }^n}(V({\widehat{\mu }}_n,\mu ))\le 2\sqrt{\frac{(k+1)\log 2}{n}}.\end{array}$$

(30)

Considering that ${\widehat{\mu }}_n\ll \mu$ ${\mathbb{P}}_{\mu }$-a.s, we can use Proposition 1 to obtain that

$$\begin{array}{c}\hfill D({\widehat{\mu }}_n\left|\right|\mu )\le \frac{\log e}{{\mathbf{m}}_{\mu }}·V({\widehat{\mu }}_n,\mu ),\mathrm{and}\left|H(({\widehat{\mu }}_n)-H({\mu }_n)\right|\le \left[{\mathbf{M}}_{\mu }+\frac{\log e}{{\mathbf{m}}_{\mu }}\right]·V({\widehat{\mu }}_n,\mu ).\end{array}$$

(31)

Hence, (17) and (18) derive from (30).

For the direct I-divergence, let us consider a sequence ${(x_i)}_{i\ge 1}$ and the following function (a stopping time):

$$\begin{array}{c}\hfill T_o(x_1,x_2,\dots )\equiv inf\left\{n\ge 1:A_{{\widehat{\mu }}_n(x^n)}=A_{\mu }\right\}.\end{array}$$

(32)

$T_o(x_1,x_2,\dots )$ is the point where the support of ${\widehat{\mu }}_n(x^n)$ is equal to $A_{\mu }$ and, consequently, the direct I-divergence is finite (since $\mu \in \mathcal{F}(\mathbb{X})$). In fact, by the uniform convergence of ${\widehat{\mu }}_n$ to ${\mu }_n$ (${\mathbb{P}}_{\mu }$-a.s.) and the finite support assumption of $\mu$, it is simple to verify that ${\mathbb{P}}_{\mu }(T_o(X_1,X_2,\dots )<\infty )=1$. Let us define the event:

$$\begin{array}{c}\hfill {\mathcal{B}}_n\equiv \left\{x_1,x_2,\dots :T_o(x_1,x_2,\dots )\le n\right\}\subset {\mathbb{X}}^{\mathbb{N}},\end{array}$$

(33)

i.e., the collection of sequences in ${\mathbb{X}}^{\mathbb{N}}$ where at time n, $A_{{\widehat{\mu }}_n}=A_{\mu }$ and, consequently, $D(\mu ||{\widehat{\mu }}_n)<\infty$. Restricted to this set

$$\begin{array}{cc}\hfill D(\mu ||{\widehat{\mu }}_n)& \le \sum _{x\in A_{{\widehat{\mu }}_n\left|\right|\mu }}{f}_{{\widehat{\mu }}_n}(x)\log \frac{f_{{\widehat{\mu }}_n}(x)}{f_{\mu }(x)}+\sum _{x\in A_{\mu }\backslash A_{{\widehat{\mu }}_n\left|\right|\mu }}{f}_{{\widehat{\mu }}_n}(x)\log \frac{f_{\mu }(x)}{f_{{\widehat{\mu }}_n}(x)}\hfill \\ & \le \log e·\sum _{x\in A_{{\widehat{\mu }}_n\left|\right|\mu }}{f}_{{\widehat{\mu }}_n}(x)·\left(\frac{f_{{\widehat{\mu }}_n}(x)}{f_{\mu }(x)}-1\right)\hfill \end{array}$$

(34)

$$\begin{array}{c}+\log e·\left[\mu (A_{\mu }\backslash A_{{\widehat{\mu }}_n\left|\right|\mu })-{\widehat{\mu }}_n((A_{\mu }\backslash A_{{\widehat{\mu }}_n\left|\right|\mu }))\right]\hfill \end{array}$$

(35)

$$\begin{array}{c}\le \log e·\left(1/{\mathbf{m}}_u+1\right)V(\mu ,{\widehat{\mu }}_n),\hfill \end{array}$$

(36)

where in the first inequality $A_{{\widehat{\mu }}_n\left|\right|\mu }\equiv \left\{x\in A_{{\widehat{\mu }}_n}:f_{{\widehat{\mu }}_n}(x)>f_{\mu }(x)\right\}$, and the last is obtained by the definition of the total variational distance. In addition, let us define the $ϵ$-deviation set ${\mathcal{A}}_n^{ϵ}\equiv \left\{x_1,x_2,\dots :D(\mu ||{\widehat{\mu }}_n(x^n))>ϵ\right\}\subset {\mathbb{X}}^{\mathbb{N}}$. Then by additivity and monotonicity of ${\mathbb{P}}_{\mu }$, we have that

$$\begin{array}{c}\hfill {\mathbb{P}}_{\mu }({\mathcal{A}}_n^{ϵ})\le {\mathbb{P}}_{\mu }({\mathcal{A}}_n^{ϵ}\cap {\mathcal{B}}_n)+{\mathbb{P}}_{\mu }({\mathcal{B}}_n^c).\end{array}$$

(37)

By definition of ${\mathcal{B}}_n$, (36) and (30) it follows that

$$\begin{array}{cc}\hfill {\mathbb{P}}_{\mu }({\mathcal{A}}_n^{ϵ}\cap {\mathcal{B}}_n)& \le {\mathbb{P}}_{\mu }(V(\mu \left|\right|{\widehat{\mu }}_n)\log e·\left(1/{\mathbf{m}}_u+1\right)>ϵ)\hfill \\ & \le 2^{\left|A_{\mu }\right|+1}·e^{-\frac{2n{ϵ}^2}{\log e^2·{\left(1/{\mathbf{m}}_u+1\right)}^2}}.\hfill \end{array}$$

(38)

On the other hand, $\forall {ϵ}_o\in (0,{\mathbf{m}}_{\mu })$ if $V(\mu ,{\widehat{\mu }}_n)\le {ϵ}_o$ then $T_o\le n$. Consequently ${\mathcal{B}}_n^c\subset \left\{x_1,x_2,\dots :V(\mu ,{\widehat{\mu }}_n(x^n))>{ϵ}_o\right\}$, and again from (30)

$$\begin{array}{cc}\hfill {\mathbb{P}}_{\mu }({\mathcal{B}}_n^c)& \le 2^{\left|A_{\mu }\right|+1}·e^{-2n{ϵ}_o^2},\hfill \end{array}$$

(39)

for all $n\ge 1$ and $\forall {ϵ}_o\in (0,{\mathbf{m}}_{\mu })$. Integrating the results in (38) and (39) and considering ${ϵ}_0={\mathbf{m}}_{\mu }/\sqrt{2}$ suffice to show the bound in (19). ☐

Proof of Theorem 2.

As $(a_n)$ is $o(1)$, it is simple to verify that ${lim}_{n\to \infty }V({\tilde{\mu }}_n,\mu )=0$, ${\mathbb{P}}_{\mu }$-a.s. Also note that the support disagreement between ${\tilde{\mu }}_n$ and $\mu$ is bounded by the hypothesis, then

$$\begin{array}{c}\underset{n\to \infty }{lim}{\tilde{\mu }}_n\left(A_{{\mu }_n}\backslash A_{\mu }\right)·\log \left|A_{{\tilde{\mu }}_n}\backslash A_{\mu }\right|\le \underset{n\to \infty }{lim}{\tilde{\mu }}_n\left(A_{{\mu }_n}\backslash A_{\mu }\right)·\log \left|A_v\right|=0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.\hfill \end{array}$$

(40)

Therefore from Lemma 1, we have the strong consistency of $H({\tilde{\mu }}_n)$ and the almost sure convergence of $D(\mu ||{\tilde{\mu }}_n)$ to zero. Note that $D(\mu ||{\tilde{\mu }}_n)$ is uniformly upper bounded by $\log e·(1/{\mathbf{m}}_{\mu }+1)V(\mu ,{\tilde{\mu }}_n)$ (see (36) in the proof of Theorem 1). Then the convergence in probability of $D(\mu ||{\tilde{\mu }}_n)$ implies the convergence of its mean [42], which concludes the proof of the first part.

Concerning rates of convergence, we use the following:

$$\begin{array}{cc}\hfill H(\mu )-H({\tilde{\mu }}_n)& =\sum _{x\in A_{\mu }\cap A_{{\tilde{\mu }}_n}}\left[f_{{\tilde{\mu }}_n}(x)-f_{\mu }(x)\right]\log f_{\mu }(x)+\sum _{x\in A_{\mu }\cap A_{{\tilde{\mu }}_n}}{f}_{{\tilde{\mu }}_n}(x)\log \frac{f_{{\tilde{\mu }}_n}(x)}{f_{\mu }(x)}\hfill \\ & -\sum _{x\in A_{{\tilde{\mu }}_n}\backslash A_{\mu }}{f}_{{\tilde{\mu }}_n}(x)\log \frac{1}{f_{{\tilde{\mu }}_n}(x)}.\hfill \end{array}$$

(41)

The absolute value of the first term in the right hand side (RHS) of (41) is bounded by ${\mathbf{M}}_{\mu }·V({\tilde{\mu }}_n,\mu )$ and the second term is bounded by $\log e/{\mathbf{m}}_{\mu }·V({\tilde{\mu }}_n,\mu )$, from the assumption that $\mu \in \mathcal{F}(\mathbb{X})$. For the last term, note that $f_{{\tilde{\mu }}_n}(x)=a_n·v(\left\{x\right\})$ for all $x\in A_{{\tilde{\mu }}_n}\backslash A_{\mu }$ and that $A_{{\tilde{\mu }}_n}=A_v$, then

$$0\le \sum _{x\in A_{{\tilde{\mu }}_n}\backslash A_{\mu }}{f}_{{\tilde{\mu }}_n}(x)\log \frac{1}{f_{{\tilde{\mu }}_n}(x)}\le a_n·(H(v)+\log \frac{1}{a_n}·v(A_v\backslash A_{\mu })).$$

On the other hand,

$$\begin{array}{cc}\hfill V({\tilde{\mu }}_n,\mu )& =\frac{1}{2}\sum _{x\in A_{\mu }}\left|(1-a_n){\widehat{\mu }}_n(\left\{x\right\})+a_{n}v(\left\{x\right\})-\mu (\left\{x\right\})\right|+\sum _{x\in A_v\backslash A_{\mu }}{a}_{n}v(\left\{x\right\}).\hfill \\ & \le (1-a_n)·V({\widehat{\mu }}_n,\mu )+a_n.\hfill \end{array}$$

Integrating these bounds in (41),

$$\begin{array}{cc}\hfill \left|H(\mu )-H({\tilde{\mu }}_n)\right|& \le ({\mathbf{M}}_{\mu }+\log e/{\mathbf{m}}_{\mu })·((1-a_n)·V({\widehat{\mu }}_n,\mu )+a_n)+a_n·H(v)+a_n·\log \frac{1}{a_n}\hfill \\ & =K_1·V({\widehat{\mu }}_n,\mu )+K_2·a_n+a_n·\log \frac{1}{a_n},\hfill \end{array}$$

(42)

for constants $K_1>0$ and $K_2>0$ function of $\mu$ and v.

Under the assumption that $\mu \in \mathcal{F}(\mathbb{X})$, the Hoeffding’s inequality [28,52] tells us that ${\mathbb{P}}_{\mu }(V({\widehat{\mu }}_n,\mu )>ϵ)\le C_1·e^{-C_{2}n{ϵ}^2}$ (for some distribution free constants $C_1>0$ and $C_2>0$). From this inequality, $V({\widehat{\mu }}_n,\mu )$ goes to zero as $o(n^{-\tau })$ ${\mathbb{P}}_{\mu }$-a.s. $\forall \tau \in (0,1/2)$ and ${\mathbb{E}}_{{\mathbb{P}}_{\mu }}(V({\widehat{\mu }}_n,\mu ))$ is $O(1/\sqrt{n})$. On the other hand, under the assumption in ii) $(K_2·a_n+a_n·\log \frac{1}{a_n})$ is $O(1/\sqrt{n})$, which from (42) proves the rate of convergence results for $\left|H(\mu )-H({\tilde{\mu }}_n)\right|$.

Considering the direct I-divergence, $D(\mu ||{\tilde{\mu }}_n)\le \log e·{\sum }_{x\in A_{\mu }}{f}_{\mu }(x)\left|\frac{f_{\mu }(x)}{f_{{\tilde{\mu }}_n}(x)}-1\right|\le \frac{\log e}{{\mathbf{m}}_{{\tilde{\mu }}_n}}·V({\tilde{\mu }}_n,\mu )$. Then the uniform convergence of ${\tilde{\mu }}_n(\left\{x\right\})$ to $\mu (\left\{x\right\})$ ${\mathbb{P}}_{\mu }$-a.s. in $A_{\mu }$ and the fact that $\left|A_{\mu }\right|<\infty$ imply that for an arbitrary small $ϵ>0$ (in particular smaller than ${\mathbf{m}}_{\mu }$)

$$\begin{array}{cc}\hfill \underset{n⟶\infty }{lim}D(\mu ||{\tilde{\mu }}_n)& \le \frac{\log e}{{\mathbf{m}}_{\mu }-ϵ}·\underset{n⟶\infty }{lim}V({\tilde{\mu }}_n,\mu ),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}..\hfill \end{array}$$

(43)

(43) suffices to obtain the convergence result for the I-divergence. ☐

Proof of Theorem 3.

Let us define the oracle Barron measure ${\tilde{\mu }}_n$ by:

$$f_{{\tilde{\mu }}_n}(x)=\frac{d{\tilde{\mu }}_n}{d\lambda }(x)=f_v(x)\left[(1-a_n)·\frac{\mu (A_n(x))}{v(A_n(x))}+a_n\right],$$

(44)

where we consider the true probability instead of its empirical version in (23). Then, the following convergence result can be obtained (see Proposition A2 in Appendix B),

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\underset{x\in A_{{\tilde{\mu }}_n}}{sup}\left|\frac{d{\tilde{\mu }}_n}{d{\mu }_n^{*}}(x)-1\right|=0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}..\end{array}$$

(45)

Let $\mathcal{A}$ denote the collection of sequences $x_1,x_2,\dots$ where the convergence in (45) is holding (this set is typical meaning that ${\mathbb{P}}_{\mu }(\mathcal{A})=1$). The rest of the proof reduces to show that for any arbitrary ${(x_n)}_{n\ge 1}\in \mathcal{A}$, its respective sequence of induced measures $\left\{{\mu }_n^{*}:n\ge 1\right\}$ (the dependency of ${\mu }_n^{*}$ on the sequence ${(x_n)}_{n\ge 1}$ will be considered implicit for the rest of the proof) satisfies the sufficient conditions of Lemma 3.

Let us fix an arbitrary ${(x_n)}_{n\ge 1}\in \mathcal{A}$:

Weak convergence ${\mu }_n^{*}\Rightarrow \mu$: Without loss of generality we consider that $A_{{\tilde{\mu }}_n}=A_v$ for all $n\ge 1$. Since $a_n\to 0$ and $h_n\to 0$, $f_{{\tilde{\mu }}_n}(x)\to \mu (\left\{x\right\})$ $\forall x\in A_v$, we got the weak convergence of ${\tilde{\mu }}_n$ to $\mu$. On the other hand by definition of $\mathcal{A}$, ${lim}_{n\to \infty }{sup}_{x\in A_{{\tilde{\mu }}_n}}\left|\frac{f_{{\tilde{\mu }}_n}(x)}{f_{{\mu }_n^{*}}(x)}-1\right|=0$ that implies that ${lim}_{n\to \infty }\left|f_{{\mu }_n^{*}}(x)-f_{{\tilde{\mu }}_n}(x)\right|=0$ for all $x\in A_v$ and, consequently, ${\mu }_n^{*}\Rightarrow \mu$.

The condition in (12): By construction $\mu \ll {\mu }_n^{*}$, $\mu \ll {\tilde{\mu }}_n$ and ${\tilde{\mu }}_n\approx {\mu }_n^{*}$ for all n, then we will use the following equality:

$$\log \frac{d\mu }{d{\mu }_n^{*}}(x)=\log \frac{d\mu }{d{\tilde{\mu }}_n}(x)+\log \frac{d{\tilde{\mu }}_n}{d{\mu }_n^{*}}(x),$$

(46)

for all $x\in A_{\mu }$. Concerning the approximation error term of (46), i.e., $\log \frac{d\mu }{d{\tilde{\mu }}_n}(x)$, $\forall x\in A_{\mu }$

$$\frac{d{\tilde{\mu }}_n}{d\mu }(x)=(1-a_n)\left[\frac{\mu (A_n(x))}{\mu (\left\{x\right\})}\frac{v(\left\{x\right\})}{v(A_n(x))}\right]+a_n\frac{v(\left\{x\right\})}{\mu (\left\{x\right\})}.$$

(47)

Given that $\mu \in \mathcal{H}(\mathbb{X}|v)$, this is equivalent to state that $\log (\frac{d\mu }{dv}(x))$ is bounded $\mu$-almost everywhere, which is equivalent to say that $\mathbf{m}\equiv {inf}_{x\in A_{\mu }}\frac{d\mu }{dv}(x)>0$ and $M\equiv {sup}_{x\in A_{\mu }}\frac{d\mu }{dv}(x)<\infty$. From this, $\forall A\subset A_{\mu }$,

$$\mathbf{m}v(A)\le \mu (A)\le Mv(A).$$

(48)

Then we have that, $\forall x\in A_{\mu }$ $\frac{\mathbf{m}}{M}\le \left[\frac{\mu (A_n(x))}{\mu (\left\{x\right\})}\frac{v(\left\{x\right\})}{v(A_n(x))}\right]\le \frac{M}{\mathbf{m}}$. Therefore for n sufficient large, $0<\frac{1}{2}\frac{\mathbf{m}}{M}\le \frac{d{\tilde{\mu }}_n}{d\mu }(x)\le \frac{M}{\mathbf{m}}+M<\infty$ for all x in $A_{\mu }$. Hence, there exists $N_o>0$ such that ${sup}_{n\ge N_o}{sup}_{x\in A_{\mu }}\left|\log \frac{d{\tilde{\mu }}_n}{d\mu }(x)\right|<\infty$.

For the estimation error term of (46), i.e., $\log \frac{d{\tilde{\mu }}_n}{d{\mu }_n^{*}}(x)$, note that from the fact that $(x_n)\in \mathcal{A}$, and the convergence in (45), there exists $N_1>0$ such that for all $n\ge N_1$ ${sup}_{x\in A_{\mu }}\left|\log \frac{d{\tilde{\mu }}_n}{d{\mu }_n^{*}}(x)\right|<\infty$, given that $A_{\mu }\subset A_{{\tilde{\mu }}_n}=A_v$. Then using (46), for all $n\ge max\left\{N_0,N_1\right\}$ ${sup}_{x\in A_{\mu }}\left|\log \frac{d{\mu }_n^{*}}{d\mu }(x)\right|<\infty$, which verifies (12).

The condition in (13): Defining the function ${\varphi }_n^{*}(x)\equiv 1_{A_v\backslash A_{\mu }}(x)·f_{{\mu }_n^{*}}(x)\log (1/f_{{\mu }_n^{*}}(x))$, we want to verify that ${lim}_{n\to \infty }{\int }_{\mathbb{X}}{\varphi }_n^{*}(x)d\lambda (x)=0$. Considering that $(x_n)\in \mathcal{A}$ for all $ϵ>0$, there exists $N(ϵ)>0$ such that ${sup}_{x\in A_{{\tilde{\mu }}_n}}\left|\frac{f_{{\tilde{\mu }}_n}(x)}{f_{{\mu }_n^{*}}(x)}-1\right|<ϵ$ and then

$$(1-ϵ)f_{{\tilde{\mu }}_n}(x)<f_{{\mu }_n^{*}}(x)<(1+ϵ)f_{{\tilde{\mu }}_n}(x),\mathrm{for}\mathrm{all}x\in A_v.$$

(49)

From (49), $0\le {\varphi }_n^{*}(x)\le (1+ϵ)f_{{\tilde{\mu }}_n}(x)\log (1/(1-ϵ)f_{{\tilde{\mu }}_n}(x))$ for all $n\ge N(ϵ)$. Analyzing $f_{{\tilde{\mu }}_n}(x)$ in (44), there are two scenarios: $A_n(x)\cap A_{\mu }=\varnothing$ where $f_{{\tilde{\mu }}_n}(x)=a_n{f}_v(x)$ and, otherwise, $f_{{\tilde{\mu }}_n}(x)=f_v(x)(a_n+(1-a_n)\mu (A_n(x)\cap A_{\mu })/v(A_n(x)))$. Let us define:

$$\begin{array}{c}\hfill {\mathcal{B}}_n\equiv \left\{x\in A_v\backslash A_{\mu }:A_n(x)\cap A_{\mu }=\varnothing \right\}\mathrm{and}{\mathcal{C}}_n\equiv \left\{x\in A_v\backslash A_{\mu }:A_n(x)\cap A_{\mu }\ne \varnothing \right\}.\end{array}$$

(50)

Then for all $n\ge N(ϵ)$,

$$\begin{array}{cc}\hfill \sum _{x\in \mathbb{X}}{\varphi }_n^{*}(x)& \le \sum _{x\in A_v\backslash A_{\mu }}(1+ϵ)f_{{\tilde{\mu }}_n}(x)\log 1/((1-ϵ)f_{{\tilde{\mu }}_n}(x))\hfill \\ & =\sum _{x\in {\mathcal{B}}_n}(1+ϵ)a_n{f}_v(x)\log \frac{1}{(1-ϵ)a_n{f}_v(x)}+\sum _{x\in \mathbb{X}}{\tilde{\varphi }}_n(x),\hfill \end{array}$$

(51)

with ${\tilde{\varphi }}_n(x)\equiv 1_{{\mathcal{C}}_n}(x)·(1+ϵ)f_{{\tilde{\mu }}_n}(x)\log \frac{1}{(1-ϵ)f_{{\tilde{\mu }}_n}(x)}$. The left term in (51) 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\in \mathcal{H}(\mathbb{X})$. For the right term in (51), $(h_n)$ being $o(1)$ implies that x belongs to ${\mathcal{B}}_n$ eventually (in n) $\forall x\in A_v\backslash A_{\mu }$, then ${\tilde{\varphi }}_n(x)$ tends to zero point-wise as n goes to infinity. On the other hand, for all $x\in {\mathcal{C}}_n$ (see (50)), we have that

$$\begin{array}{c}\hfill \frac{1}{1/m+1}\le \frac{\mu (A_n(x)\cap A_{\mu })}{v(A_n(x)\cap A_{\mu })+v(A_v\backslash A_{\mu })}\le \frac{\mu (A_n(x))}{v(A_n(x))}\le \frac{\mu (A_n(x)\cap A_{\mu })}{v(A_n(x)\cap A_{\mu })}\le M.\end{array}$$

(52)

These inequalities derive from (48). Consequently for all $x\in \mathbb{X}$, if n sufficiently large such that $a_n<0.5$, then

$$\begin{array}{cc}\hfill 0\le {\tilde{\varphi }}_n(x)& \le (1+ϵ)(a_n+(1-a_n)M)f_v(x)\log \frac{1}{(1-ϵ)(a_n+(1-a_n)m/(m+1))}\hfill \\ & \le (1+ϵ)(1+M)f_v(x)\left[\log \frac{2(m+1)}{(1-ϵ)}+\log \frac{1}{f_v(x)}\right].\hfill \end{array}$$

(53)

Hence from (50), ${\tilde{\varphi }}_n(x)$ is bounded by a fix function that is ${\ell }_1(\mathbb{X})$ by the assumption that $v\in \mathcal{H}(\mathbb{X})$. Then by the dominated convergence theorems [43] and (51),

$$\underset{n\to \infty }{lim}\sum _{\mathbb{X}}{\varphi }_n^{*}(x)\le \underset{n\to \infty }{lim}\sum _{\mathbb{X}}{\tilde{\varphi }}_n(x).$$

In summary, we have shown that for any arbitrary $(x_n)\in \mathcal{A}$ the sufficient conditions of Lemma 3 are satisfied, which proves the result in (25) reminding that ${\mathbb{P}}_{\mu }(\mathcal{A})=1$ from (45). ☐

Proof of Theorem 4.

Let us first introduce the oracle probability

$${\mu }_{{ϵ}_n}\equiv \mu (·|{\mathsf{\Gamma }}_{{ϵ}_n})\in \mathcal{P}(\mathbb{X}).$$

(54)

Note that ${\mu }_{{ϵ}_n}$ is a random probability measure (function of the i.i.d sequence $X_1,\dots ,X_n$) as ${\mathsf{\Gamma }}_{{ϵ}_n}$ is a data-driven set, see (26). We will first show that:

$$\underset{n\to \infty }{lim}H({\mu }_{{ϵ}_n})=H(\mu )\mathrm{and}\underset{n\to \infty }{lim}D({\mu }_{{ϵ}_n}\left|\right|\mu )=0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$$

(55)

Under the assumption on $({ϵ}_n)$ of Theorem 4, ${lim}_{n\to \infty }\left|\mu ({\mathsf{\Gamma }}_{{ϵ}_n})-{\widehat{\mu }}_n({\mathsf{\Gamma }}_{{ϵ}_n})\right|=0$, ${\mathbb{P}}_{\mu }$-a.s. (this result derives from the fact that ${lim}_{n\to \infty }V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})=0$, ${\mathbb{P}}_{\mu }$-a.s. , from (63)) In addition, since $({ϵ}_n)$ is $o(1)$ then ${lim}_{n\to \infty }{\widehat{\mu }}_n({\mathsf{\Gamma }}_{{ϵ}_n})=1$, which implies that ${lim}_{n\to \infty }\mu ({\mathsf{\Gamma }}_{{ϵ}_n})=1$ ${\mathbb{P}}_{\mu }$-a.s. From this ${\mu }_{{ϵ}_n}\Rightarrow \mu$, ${\mathbb{P}}_{\mu }$-a.s. Let us consider a sequences $(x_n)$ where ${lim}_{n\to \infty }\mu ({\mathsf{\Gamma }}_{{ϵ}_n})=1$. Constrained to that

$$lim\underset{n\to \infty }{sup}\underset{x\in A_{\mu }}{sup}\frac{f_{{\mu }_{{ϵ}_n}}(x)}{f_{\mu }(x)}=lim\underset{n\to \infty }{sup}\frac{1}{\mu ({\mathsf{\Gamma }}_{{ϵ}_n})}<\infty .$$

(56)

Then there is $N>0$ such that ${sup}_{n>N}{sup}_{x\in A_{\mu }}\frac{f_{{\mu }_{{ϵ}_n}}(x)}{f_{\mu }(x)}<\infty$. Hence from Lemma 2, ${lim}_{n\to \infty }D({\mu }_{{ϵ}_n}\left|\right|\mu )=$ 0 and ${lim}_{n\to \infty }\left|H({\mu }_{{ϵ}_n})-H(\mu )\right|=0$. Finally, the set of sequences $(x_n)$ where ${lim}_{n\to \infty }\mu ({\mathsf{\Gamma }}_{{ϵ}_n})=1$ has probability one (with respect to ${\mathbb{P}}_{\mu }$), which proves (55).

For the rest of the proof, we concentrate on the analysis of $\left|H({\widehat{\mu }}_{n,{ϵ}_n})-H({\mu }_{{ϵ}_n})\right|$ that can be attributed to the estimation error aspect of the problem. It is worth noting that by construction $A_{{\widehat{\mu }}_{n,{ϵ}_n}}=A_{{\mu }_{{ϵ}_n}}={\mathsf{\Gamma }}_{{ϵ}_n}$, ${\mathbb{P}}_{\mu }$-a.s.. Consequently, we can use

$$H({\widehat{\mu }}_{n,{ϵ}_n})-H({\mu }_{{ϵ}_n})=\sum _{x\in {\mathsf{\Gamma }}_{{ϵ}_n}}\left[{\mu }_{{ϵ}_n}(\left\{x\right\})-{\widehat{\mu }}_{n,{ϵ}_n}(\left\{x\right\})\right]\log {\widehat{\mu }}_{n,{ϵ}_n}(\left\{x\right\})+D({\mu }_{{ϵ}_n}\left|\right|{\widehat{\mu }}_{n,{ϵ}_n}).$$

(57)

The first term on the RHS of (57) is upper bounded by $\log 1/{\mathbf{m}}_{{\widehat{\mu }}_n}^{{ϵ}_n}·V({\mu }_{{ϵ}_n},{\widehat{\mu }}_{n,{ϵ}_n})$ $\le \log 1/{ϵ}_n·V({\mu }_{{ϵ}_n},{\widehat{\mu }}_{n,{ϵ}_n})$. Concerning the second term on the RHS of (57), it is possible to show (details presented in Appendix C) that

$$D({\mu }_{{ϵ}_n}\left|\right|{\widehat{\mu }}_{n,{ϵ}_n})\le \frac{2\log \frac{e}{{ϵ}_n}}{\mu ({\mathsf{\Gamma }}_{{ϵ}_n})}·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n}),$$

(58)

where

$$V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})\equiv \underset{A\in {\sigma }_{{ϵ}_n}}{sup}\left|\mu (A)-{\widehat{\mu }}_n(A)\right|.$$

(59)

In addition, it can be verified (details presented in Appendix D) that

$$V({\mu }_{{ϵ}_n},{\widehat{\mu }}_{n,{ϵ}_n})\le K·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n}),$$

(60)

for some universal constant $K>0$. Therefore from (57), (58) and (60), there is $C>0$ such that

$$\left|H({\widehat{\mu }}_{n,{ϵ}_n})-H({\mu }_{{ϵ}_n})\right|\le \frac{C}{\mu ({\mathsf{\Gamma }}_{{ϵ}_n})}\log \frac{1}{{ϵ}_n}·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n}).$$

(61)

As mentioned before, $\mu ({\mathsf{\Gamma }}_{{ϵ}_n})$ goes to 1 almost surely, then we need to concentrate on the analysis of the asymptotic behavior of $\log 1/{ϵ}_n·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})$. From Hoeffding’s inequality [28], we have that $\forall \delta >0$

$${\mathbb{P}}_{\mu }^n\left(\log 1/{ϵ}_n·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})>\delta \right)\le 2^{\left|{\mathsf{\Gamma }}_{{ϵ}_n}\right|+1}·e^{-\frac{2n{\delta }^2}{{(\log 1/{ϵ}_n)}^2}},$$

(62)

considering that by construction $\left|{\sigma }_{{ϵ}_n}\right|\le 2^{\left|{\mathsf{\Gamma }}_{{ϵ}_n}\right|+1}\le 2^{1/{ϵ}_n+1}$. Assuming that $({ϵ}_n)$ is $O(n^{-\tau })$,

$$\ln {\mathbb{P}}_{\mu }^n\left(\log 1/{ϵ}_n·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})>\delta \right)\le (n^{\tau }+1)\ln 2-\frac{2n{\delta }^2}{\tau \log n}.$$

Therefore for all $\tau \in (0,1)$, $\delta >0$ and any arbitrary $l\in (\tau ,1)$

$$lim\underset{n\to \infty }{sup}\frac{1}{n^l}·\ln {\mathbb{P}}_{\mu }^n\left(\log 1/{ϵ}_n·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})>\delta \right)<0.$$

(63)

This last result is sufficient to show that ${\sum }_{n\ge 1}{\mathbb{P}}_{\mu }^n\left(\log 1/{ϵ}_n·V(\mu /{\sigma }_{{ϵ}_n},{\widehat{\mu }}_n/{\sigma }_{{ϵ}_n})>\delta \right)<\infty$ that concludes the argument from the Borel-Cantelli Lemma. ☐

Proof of Theorem 5.

We consider the expression

$$\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\le \left|H(\mu )-H({\mu }_{{ϵ}_n})\right|+\left|H({\mu }_{{ϵ}_n})-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$$

(64)

to analize the approximation error and the estimation error terms separately.

• Approximation Error Analysis

Note that $\left|H(\mu )-H({\mu }_{{ϵ}_n})\right|$ is a random object as ${\mu }_{{ϵ}_n}$ in (54) is a function of the data-dependent partition and, consequently, a function of $X_1,\dots ,X_n$. In the following, we consider the oracle set

$${\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}\equiv \left\{x\in \mathbb{X}:\mu (\left\{x\right\})\ge {ϵ}_n\right\},$$

(65)

and the oracle conditional probability

$${\tilde{\mu }}_{{ϵ}_n}\equiv \mu (·|{\tilde{\mathsf{\Gamma }}}_{{ϵ}_n})\in \mathcal{P}.(\mathbb{X}).$$

(66)

Note that ${\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}$ is a deterministic function of $({ϵ}_n)$ and so is the measure ${\tilde{\mu }}_{{ϵ}_n}$ in (66). From definitions and triangular inequality:

$$\begin{array}{cc}\hfill \left|H(\mu )-H({\tilde{\mu }}_{{ϵ}_n})\right|& \le \sum _{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}+\log \frac{1}{\mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n})}\hfill \\ & +\left(\frac{1}{\mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n})}-1\right)·\sum _{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})},\hfill \end{array}$$

(67)

and, similarly, the approximation error is bounded by

$$\begin{array}{cc}\hfill \left|H(\mu )-H({\mu }_{{ϵ}_n})\right|& \le \sum _{x\in {\mathsf{\Gamma }}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}\hfill \\ & +\log \frac{1}{\mu ({\mathsf{\Gamma }}_{{ϵ}_n})}+\left(\frac{1}{\mu ({\mathsf{\Gamma }}_{{ϵ}_n})}-1\right)·\sum _{x\in {\mathsf{\Gamma }}_{{ϵ}_n}}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}.\hfill \end{array}$$

(68)

We denote the RHS of (67) and (68) by $a_{{ϵ}_n}$ and $b_{{ϵ}_n}(X_1,\dots ,X_n)$, respectively.

We can show that if $({ϵ}_n)$ is $O(n^{-\tau })$ and $\tau \in (0,1/2)$, then

$$lim\underset{n\to \infty }{sup}{b}_{{ϵ}_n}(X_1,\dots ,X_n)-a_{2{ϵ}_n}\le 0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,$$

(69)

which from (68) implies that $\left|H(\mu )-H({\mu }_{{ϵ}_n})\right|$ is $O(a_{2{ϵ}_n})$, ${\mathbb{P}}_{\mu }$-a.s. The proof of (69) is presented in Appendix E.

Then, we need to analyze the rate of convergence of the deterministic sequence $(a_{2{ϵ}_n})$. Analyzing the RHS of (67), we recognize two independent terms: the partial entropy sum ${\sum }_{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}$ and the rest that is bounded asymptotically by $\mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c)(1+H(\mu ))$, using the fact that $\ln x\le x-1$ for $x\ge 1$. Here is where the tail condition on $\mu$ plays a role. From the tail condition, we have that

$$\begin{array}{cc}\hfill \mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c)& \le \mu \left(\left\{{(k_o/{ϵ}_n)}^{1/p}+1,{(k_o/{ϵ}_n)}^{1/p}+2,{(k_o/{ϵ}_n)}^{1/p}+3,\dots \right\}\right)=\sum _{x\ge {(\frac{k_o}{{ϵ}_n})}^{1/p}+1}\mu (\left\{x\right\})\hfill \\ & \le k_1·{\mathcal{S}}_{{(\frac{k_o}{{ϵ}_n})}^{1/p}+1},\hfill \end{array}$$

(70)

where ${\mathcal{S}}_{x_o}\equiv {\sum }_{x\ge x_o}{x}^{-p}$. Similarly as $\left\{0,1,\dots ,{(k_o/{ϵ}_n)}^{1/p}\right\}\subset {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}$, then

$$\begin{array}{cc}\hfill \sum _{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}& \le \sum _{x\ge {(\frac{k_o}{{ϵ}_n})}^{1/p}+1}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}\le \sum _{x\ge {(\frac{k_o}{{ϵ}_n})}^{1/p}+1}{k}_1{x}^{-p}·\log \frac{1}{k_0{x}^{-p}}\hfill \\ & \le k_1\log p·{\mathcal{R}}_{{(\frac{k_o}{{ϵ}_n})}^{1/p}+1}+k_1\log 1/k_0·{\mathcal{S}}_{{(\frac{k_o}{{ϵ}_n})}^{1/p}+1},\hfill \end{array}$$

(71)

where ${\mathcal{R}}_{x_o}\equiv {\sum }_{x\ge x_o}{x}^{-p}\log x$.

In Appendix F, it is shown that ${\mathcal{S}}_{x_o}\le C_0·x_o^{1-p}$ and ${\mathcal{R}}_{x_o}\le C_1·x_o^{1-p}$ for constants $C_1>0$ and $C_0>0$. Integrating these results in the RHS of (70) and (71) and considering that $({ϵ}_n)$ is $O(n^{-\tau })$, we have that both $\mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c)$ and ${\sum }_{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}$ are $O(n^{-\frac{\tau (p-1)}{p}})$. This implies that our oracle sequence $(a_{{ϵ}_n})$ is $O(n^{-\frac{\tau (p-1)}{p}})$.

In conclusion, if ${ϵ}_n$ is $O(n^{-\tau })$ for $\tau \in (0,1/2)$, it follows that

$$\left|H(\mu )-H({\mu }_{{ϵ}_n})\right|\mathrm{is}O(n^{-\frac{\tau (p-1)}{p}}),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.$$

(72)

• Estimation Error Analysis

Let us consider $\left|H({\mu }_{{ϵ}_n})-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$. From the bound in (61) and the fact that for any $\tau \in (0,1)$, ${lim}_{n\to \infty }\mu ({\mathsf{\Gamma }}_{{ϵ}_n})=1$ ${\mathbb{P}}_{\mu }$-a.s. from (63), the problem reduces to analyze the rate of convergence of the following random object:

$${\rho }_n(X_1,\dots ,X_n)\equiv \log \frac{1}{{ϵ}_n}·V(\mu /\sigma ({\mathsf{\Gamma }}_{{ϵ}_n}),{\widehat{\mu }}_n/\sigma ({\mathsf{\Gamma }}_{{ϵ}_n})).$$

(73)

We will analize, instead, the oracle version of ${\rho }_n(X_1,\dots ,X_n)$ given by:

$${\xi }_n(X_1,\dots ,X_n)\equiv \log \frac{1}{{ϵ}_n}·V(\mu /\sigma ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n/2}),{\widehat{\mu }}_n/\sigma ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n/2})),$$

(74)

where ${\tilde{\mathsf{\Gamma }}}_{ϵ}\equiv \left\{x\in \mathbb{X}:\mu (\left\{x\right\})\ge ϵ\right\}$ is the oracle counterpart of ${\mathsf{\Gamma }}_{ϵ}$ in (26). To do so, we can show that if ${ϵ}_n$ is $O(n^{-\tau })$ with $\tau \in (0,1/2)$, then

$$lim\underset{n\to \infty }{inf}{\xi }_n(X_1,\dots ,X_n)-{\rho }_n(X_1,\dots ,X_n)\ge 0,{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}..$$

(75)

The proof of (75) is presented in Appendix G.

Moving to the almost sure rate of convergence of ${\xi }_n(X_1,\dots ,X_n)$, it is simple to show for our p-power dominating distribution that if $({ϵ}_n)$ is $O(n^{-\tau })$ and $\tau \in (0,p)$ then

$$\underset{n\to \infty }{lim}{\xi }_n(X_1,\dots ,X_n)=0{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,$$

and, more specifically,

$${\xi }_n(X_1,\dots ,X_n)\mathrm{is}o(n^{-q})\mathrm{for}\mathrm{all}q\in (0,(1-\tau /p)/2),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}..$$

(76)

The argument is presented in Appendix H.

In conclusion, if ${ϵ}_n$ is $O(n^{-\tau })$ for $\tau \in (0,1/2)$, it follows that

$$\left|H({\mu }_{{ϵ}_n})-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\mathrm{is}O(n^{-q}),{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,$$

(77)

for all $q\in (0,(1-\tau /p)/2)$.

• Estimation vs. Approximation Errors

Coming back to (64) and using (72) and (77), the analysis reduces to finding the solution ${\tau }^{*}$ in $(0,1/2)$ that offers the best trade-off between the estimation and approximation error rate:

$${\tau }^{*}\equiv \arg \underset{\tau (0,1/2)}{max}min\left\{\frac{(1-\tau /p)}{2},\frac{\tau (p-1)}{p}\right\}.$$

(78)

It is simple to verify that ${\tau }^{*}=1/2$. Then by considering $\tau$ arbitrary close to the admissible limit $1/2$, we can achieve a rate of convergence for $\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$ that is arbitrary close to $O(n^{-\frac{1}{2}(1-1/p)})$, $\mathbb{P}$-a.s.

More formally, for any $l\in (0,\frac{1}{2}(1-1/p))$ we can take $\tau \in (\frac{l}{(1-1/p)},\frac{1}{2})$ where $\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$ is $o(n^{-l})$, ${\mathbb{P}}_{\mu }$-a.s., from (72) and (77).

Finally, a simple corollary of this analysis is to consider $\tau (p)=\frac{1}{2+1/p}<1/2$ where:

$$\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\mathrm{is}O\mathsf{\left(}{n}^{-\frac{1-1/p}{2+1/p}}\mathsf{\right)},{\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,$$

(79)

which concludes the argument. ☐

Proof of Theorem 6.

The argument follows the proof of Theorem 5. In particular, we use the estimation-approximation error bound:

$$\left|H(\mu )-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\le \left|H(\mu )-H({\mu }_{{ϵ}_n})\right|+\left|H({\mu }_{{ϵ}_n})-H({\widehat{\mu }}_{n,{ϵ}_n})\right|,$$

(80)

and the following two results derived in the proof of Theorem 5: If $({ϵ}_n)$ is $O(n^{-\tau })$ with $\tau \in (0,1/2)$ then (for the approximation error)

$$\left|H(\mu )-H({\mu }_{{ϵ}_n})\right|\mathrm{is}O(a_{2{ϵ}_n}){\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,$$

(81)

with $a_{{ϵ}_n}={\sum }_{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}+\mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c)(1+H(\mu )),$ while (for the estimation error)

$$\left|H({\mu }_{{ϵ}_n})-H({\widehat{\mu }}_{n,{ϵ}_n})\right|\mathrm{is}O({\xi }_n(X_1,\dots ,X_n)){\mathbb{P}}_{\mu }\text{-}\mathrm{a}.\mathrm{s}.,$$

(82)

with ${\xi }_n(X_1,\dots ,X_n)=\log \frac{1}{{ϵ}_n}·V(\mu /\sigma ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n/2}),{\widehat{\mu }}_n/\sigma ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n/2})).$

For the estimation error, we need to bound the rate of convergence of ${\xi }_n(X_1,\dots ,X_n)$ to zero almost surely. We first note that $\left\{1,\dots ,x_o({ϵ}_n)\right\}={\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}$ with $x_o({ϵ}_n)=\lfloor 1/\alpha \ln (k_0/{ϵ}_n)\rfloor$. Then from Hoeffding’s inequality we have that

$$\begin{array}{cc}\hfill {\mathbb{P}}_{\mu }^n\left(\left\{{\xi }_n(X_1,\dots ,X_n)>\delta \right\}\right)& \le 2^{\left|({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n/2})\right|}·e^{-2n\frac{{\delta }^2}{\log {(1/{ϵ}_n)}^2}}\hfill \\ & \le 2^{1/\alpha \ln (2k_0/{ϵ}_n)+1}·e^{-2n\frac{{\delta }^2}{\log {(1/{ϵ}_n)}^2}}.\hfill \end{array}$$

(83)

Considering ${ϵ}_n=O(n^{-\tau })$, an arbitrary sequence $({\delta }_n)$ being $o(1)$ and $l>0$, it follows from (83) that

$$\begin{array}{cc}\hfill \frac{1}{n^l}·\ln {\mathbb{P}}_{\mu }^n\left(\left\{{\xi }_n(X_1,\dots ,X_n)>{\delta }_n\right\}\right)& \le \frac{1}{n^l}\ln (2)\left[1/\alpha \ln (2k_0/{ϵ}_n)+1\right]-n^{1-l}\frac{{\delta }_n^2}{\log {(1/{ϵ}_n)}^2}.\hfill \end{array}$$

(84)

We note that the first term in the RHS of (84) is $O(\frac{1}{n^l}\log n)$ and goes to zero for all $l>0$, while the second term is $O(n^{1-l}\frac{{\delta }_n^2}{\log n^2})$. If we consider ${\delta }_n=O(n^{-q})$, this second term is $O(n^{1-2q-l}·\frac{1}{\log n^2})$. Therefore, for any $q\in (0,1/2)$ we can take an arbitrary $l\in (0,1-2q]$ such that ${\mathbb{P}}_{\mu }^n\left(\left\{{\xi }_n(X_1,\dots ,X_n)>{\delta }_n\right\}\right)$ is $O(e^{-n^l})$ from (84). This result implies, from the Borel-Cantelli Lemma, that ${\xi }_n(X_1,\dots ,X_n)$ is $o({\delta }_n)$, ${\mathbb{P}}_{\mu }$-a.s, which in summary shows that $\left|H({\mu }_{{ϵ}_n})-H({\widehat{\mu }}_{n,{ϵ}_n})\right|$ is $O(n^{-q})$ for all $q\in (0,1/2)$.

For the approximation error, it is simple to verify that:

$$\mu ({\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c)\le k_1·\sum _{x\ge x_o({ϵ}_n)+1}{e}^{-\alpha x}=k_1·{\tilde{\mathcal{S}}}_{x_o({ϵ}_n)+1}$$

(85)

and

$$\begin{array}{cc}\hfill \sum _{x\in {\tilde{\mathsf{\Gamma }}}_{{ϵ}_n}^c}\mu (\left\{x\right\})\log \frac{1}{\mu (\left\{x\right\})}& \le \sum _{x\ge x_o({ϵ}_n)+1}{k}_1{e}^{-\alpha x}\log \frac{1}{k_0{e}^{-\alpha x}}=k_1\log \frac{1}{k_0}·{\tilde{\mathcal{S}}}_{x_o({ϵ}_n)+1}\hfill \\ & +\alpha \log e·k_1·{\tilde{\mathcal{R}}}_{x_o({ϵ}_n)+1},\hfill \end{array}$$

(86)

where ${\tilde{\mathcal{S}}}_{x_o}\equiv {\sum }_{x\ge x_o}{e}^{-\alpha x}$ and ${\tilde{\mathcal{R}}}_{x_o}\equiv {\sum }_{x\ge x_o}x·e^{-\alpha x}$. At this point, it is not difficult to show that ${\tilde{\mathcal{S}}}_{x_o}\le M_1{e}^{-\alpha x_o}$ and ${\tilde{\mathcal{R}}}_{x_o}\le M_2{e}^{-\alpha x_o}·x_o$ for some constants $M_1>0$ and $M_2>0$. Integrating these partial steps, we have that

$$\begin{array}{c}\hfill a_{{ϵ}_n}\le k_1(1+H(\mu )+\log \frac{1}{k_0})·{\tilde{\mathcal{S}}}_{x_o({ϵ}_n)+1}+\alpha \log e·k_1·{\tilde{\mathcal{R}}}_{x_o({ϵ}_n)+1}\le O_1·{ϵ}_n+O_2·{ϵ}_n\log \frac{1}{{ϵ}_n}\end{array}$$

(87)

for some constant $O_1>0$ and $O_2>0$. The last step is from the evaluation of $x_o({ϵ}_n)=\lfloor 1/\alpha \ln (k_0/{ϵ}_n)\rfloor$. Therefore from (81) and (87), it follows that $\left|H(\mu )-H({\mu }_{{ϵ}_n})\right|$ is $O(n^{-\tau }\log n)$ ${\mathbb{P}}_{\mu }$-a.s. for all $\tau \in (0,1/2)$.

The argument concludes by integrating in (80) the almost sure convergence results obtained for the estimation and approximation errors. ☐

Proof of Theorem 7.

Let us define the event

$${\mathcal{B}}_n^{ϵ}=\left\{x^n\in {\mathbb{X}}^n:{\mathsf{\Gamma }}_{ϵ}(x^n)=A_{\mu }\right\},$$

(88)

that represents the detection of the support of $\mu$ from the data for a given $ϵ>0$ in (26). Note that the dependency on the data for ${\mathsf{\Gamma }}_{ϵ}$ is made explicit in this notation. In addition, let us consider the deviation event

$${\mathcal{A}}_n^{ϵ}(\mu )=\left\{x^n\in {\mathbb{X}}^n:V(\mu ,{\widehat{\mu }}_n)>ϵ\right\}.$$

(89)

By the hypothesis that $\left|A_{\mu }\right|<\infty$, then ${\mathbf{m}}_{\mu }={min}_{x\in A_{\mu }}{f}_{\mu }(x)>0$. Therefore if $x^n\in {({\mathcal{A}}_n^{{\mathbf{m}}_{\mu }/2}(\mu ))}^c$ then ${\widehat{\mu }}_n(\left\{x\right\})\ge {\mathbf{m}}_{\mu }/2$ for all $x\in A_{\mu }$, which implies that ${({\mathcal{B}}_n^{ϵ})}^c\subset {\mathcal{A}}_n^{{\mathbf{m}}_{\mu }/2}(\mu )$ as long as $0<ϵ\le {\mathbf{m}}_{\mu }/2$. Using the hypothesis that ${ϵ}_n\to 0$, there is $N>0$ such that for all $n\ge N$ ${({\mathcal{B}}_n^{{ϵ}_n})}^c\subset {\mathcal{A}}_n^{{\mathbf{m}}_{\mu }/2}(\mu )$ and, consequently,

$${\mathbb{P}}_{\mu }^n({({\mathcal{B}}_n^{{ϵ}_n})}^c)\le {\mathbb{P}}_{\mu }^n({\mathcal{A}}_n^{{\mathbf{m}}_{\mu }/2}(\mu ))\le 2^{k+1}·e^{-\frac{n{\mathbf{m}}_{\mu }^2}{4}},$$

(90)

the last from Hoeffding’s inequality considering $k=\left|A_{\mu }\right|<\infty$.

If we consider the events:

$$\begin{array}{cc}\hfill {\mathcal{C}}_n^{ϵ}(\mu )& =\left\{x^n\in {\mathbb{X}}^n:\left|H({\widehat{\mu }}_{n,{ϵ}_n})-H(\mu )\right|>ϵ\right\}\mathrm{and}\hfill \end{array}$$

(91)

$$\begin{array}{cc}\hfill {\mathcal{D}}_n^{ϵ}(\mu )& =\left\{x^n\in {\mathbb{X}}^n:\left|H({\widehat{\mu }}_n)-H(\mu )\right|>ϵ\right\}\hfill \end{array}$$

(92)

and we use the fact that by definition ${\widehat{\mu }}_{n,{ϵ}_n}={\widehat{\mu }}_n$ conditioning on ${\mathcal{B}}_n^{{ϵ}_n}$, it follows that ${\mathcal{C}}_n^{ϵ}(\mu )\cap {\mathcal{B}}_n^{{ϵ}_n}\subset {\mathcal{D}}_n^{ϵ}(\mu )$. Then, for all $ϵ>0$ and $n\ge N$

$$\begin{array}{cc}\hfill {\mathbb{P}}_{\mu }^n({\mathcal{C}}_n^{ϵ}(\mu ))& \le {\mathbb{P}}_{\mu }^n({\mathcal{C}}_n^{ϵ}(\mu )\cap {\mathcal{B}}_n^{{ϵ}_n})+{\mathbb{P}}_{\mu }^n({({\mathcal{B}}_n^{{ϵ}_n})}^c)\hfill \\ & \le {\mathbb{P}}_{\mu }^n({\mathcal{D}}_n^{ϵ}(\mu ))+{\mathbb{P}}_{\mu }^n({({\mathcal{B}}_n^{{ϵ}_n})}^c)\hfill \\ & \le 2^{k+1}\left[e^{-\frac{2n{ϵ}^2}{{({\mathbf{M}}_{\mu }+\frac{\log e}{{\mathbf{m}}_{\mu }})}^2}}+e^{-\frac{n{\mathbf{m}}_{\mu }^2}{4}}\right],\hfill \end{array}$$

(93)

the last inequality from Theorem 1 and (90). ☐