Estimating Renyi Entropy of Discrete Distributions

I Introduction

A popular generalization of Shannon entropy is the Rényi entropy of order $\alpha\geq 0$, defined for $\alpha\neq 1$ by

Motivated by these and other applications, unbiased and heuristic estimators of Rényi entropy have been studied in the physics literature following , and asymptotically consistent and normal estimates were proposed in . However, no systematic study of the complexity of estimating Rényi entropy is available. For example, it was hitherto unknown if the number of samples needed to estimate the Rényi entropy of a given order $\alpha$ differs from that required for Shannon entropy, or whether it varies with the order $\alpha$, or how it depends on the alphabet size $k$.

I-B Definitions and results

We show that $S_{\alpha}(k)$ behaves differently in three ranges of $\alpha$. For $0\leq\alpha<1$,

namely the sample complexity grows super-linearly in $k$ and estimating the Rényi entropy of these orders is even more difficult than estimating the Shannon entropy. In fact, the upper bound follows from a corresponding result on estimation of power sums considered in (see Section III-C for further discussion). For completeness, we show in Theorem 10 that the empirical estimator requires $O(k^{1/\alpha})$ samples and in Theorem 14 prove the improvement by a factor of $\log k$. The lower bound is proved in Theorem 22.

namely as with Shannon entropy, the sample complexity grows roughly linearly in the alphabet size. The lower bound is proved in Theorem 21. In a conference version of this paper , a weaker $O(k)$ upper bound was established using the empirical-frequency estimator. For the sake of completeness, we include this result as Theorem 9. The tighter upper bound reported here uses the best polynomial approximation based estimator of and is proved in Theorem 13. In fact, in the Appendix we show that the empirical estimator can’t attain this $\log k$ improvement and requires $\Omega(k/\delta)$ and $\Omega((k/\delta)^{1/\alpha})$ samples for $\alpha>1$ and $\alpha<1$, respectively.

and in particular, the sample complexity is strictly sublinear in the alphabet size. The upper and lower bounds are shown in Theorems 12 and 16, respectively. Figure 1 illustrates our results for different ranges of $\alpha$.

Of the three ranges, the most frequently used, and coincidentally the one for which the results are most surprising, is the last with $\alpha=2,3,\ldots$. Some elaboration is in order.

It should also be noted that the estimators achieving the upper bounds are simple and run in time linear in the number of samples. Furthermore, the estimators are universal in that they do not require the knowledge of $k$. On the other hand, the lower bounds on $S_{\alpha}(k)$ hold even if the estimator knows $k$.

I-C The estimators

and is related to the Rényi entropy for $\alpha\neq 1$ via

We construct estimators for the power-sums of distributions with a multiplicative-accuracy of $(1\pm\delta)$ and hence obtain an additive-accuracy of $\Theta(\delta)$ for Rényi entropy estimation. We consider the following three different estimators for different ranges of $\alpha$ and with different performance guarantees.

Bias-corrected estimator

Polynomial approximation estimator

where $d$ and $\tau$ are both $O(\log n)$ and chosen appropriately.

Theorem 13 and Theorem 14 show that for $\alpha>1$ and $\alpha<1$, respectively, the sample complexity of $\widehat{P}_{\alpha}^{d,\tau}$ is $O(k/\log k)$ and $O(k^{\frac{1}{\alpha}}/\log k)$, resulting in a reduction in sample complexity of $O(\log k)$ over the empirical estimator.

Table I summarizes the performance of these estimators in terms of their sample complexity. The last column denote the lower bounds from Section V.

I-D Organization

The rest of the paper is organized as follows. Section II presents basic properties of power sums of distributions and moments of Poisson random variables, which may be of independent interest. The estimation algorithms are analyzed in Section III, in Section III-A we show results for the empirical or plug-in estimate, in Section III-B we provide optimal results for integral $\alpha$ and finally we provide an improved estimator for non-integral $\alpha>1$. Examples and simulation of the proposed estimators are given in Section IV. Section V contains our lower bounds for the sample complexity of estimating Rényi entropy. Furthermore, in the Appendix we analyze the performance of the empirical estimator for power-sum estimation with an additive-accuracy and also derive lower bounds for its sample complexity.

II Technical preliminaries

Further, for $\alpha>1$ and $0\leq\beta\leq\alpha$,

The first inequality follows upon choosing $\beta=\alpha$. For $1<\alpha$ and $0\leq\beta\leq\alpha$, we get the second by (4). Note that by the monotonicity of Hölder means, we have

The final inequality follows upon rearranging the terms and using (4). ∎

II-B Bounds on moments of a Poisson random variable

We start with the expected value and the variance of falling powers of a Poisson random variable.

The next result establishes a bound on the moments of a Poisson random variable.

Let $X\sim{\rm Poi}(\lambda)$ and let $\beta$ be a positive real number. Then,

Let $Z=\max\{\lambda^{1/\beta},\lambda\}$.

The first inequality follows from the fact that either $X/Z>1$ or $\leq 1$. The equality follows from the fact that the integer moments of Poisson distribution are Touchard polynomials in $\lambda$. The second inequality uses the property that $\lambda/Z\leq 1$. Multiplying both sides by $Z^{\beta}$ results in the lemma. ∎

For $\alpha\leq 1$, $(1+y)^{\alpha}\geq 1+\alpha y-y^{2}$ for all $y\in[-1,\infty]$, hence,

Since $x^{\alpha}$ is a concave function and $X$ is nonnegative, the previous bound yields

where the last-but-one inequality is by Lemma 3. ∎

There is a constant $c^{\prime}_{\alpha}$ such that for any $d>0$,

To obtain an estimator which does not require a knowledge of the support size $k$, we seek a polynomial approximation $q_{\alpha}(x)$ of $x^{\alpha}$ with $q_{\alpha}(0)=0$. Such a polynomial $q_{\alpha}(x)$ can be obtained by a minor modification of the polynomial $q^{\prime}_{\alpha}(x)=\sum^{d}_{j=0}q_{j}x^{j}$ satisfying the error bound in Lemma 5. Specifically, we use the polynomial $q_{\alpha}(x)=q^{\prime}_{\alpha}(x)-q_{0}$ for which the approximation error is bounded as

To bound the variance of the proposed polynomial approximation estimator, we require a bound on the absolute values of the coefficients of $q_{\alpha}(x)$. The following inequality due to Markov serves this purpose.

Let $p(x)=\sum_{j=0}^{d}c_{j}x^{j}$ be a degree-$d$ polynomial so that $|p(x)|\leq 1$ for all $x\in$. Then for all $j=0,\ldots,m$

Since $|x^{\alpha}|\leq 1$ for $x\in$, the approximation bound (5) implies $|q_{\alpha}(x)|<1+\frac{c_{\alpha}}{d^{2\alpha}}$ for all $x\in$. It follows from Lemma 6 that

III Upper bounds on sample complexity

In this section, we analyze the performances of the estimators we proposed in Section I-C. Our proofs are based on bounding the bias and the variance of the estimators under Poisson sampling. We first describe our general recipe and then analyze the performance of each estimator separately.

The following reduction to Poisson sampling is well-known.

(Poisson approximation 1) For $n\geq 8\log(2/\epsilon)$ and $N\sim{\rm Poi}(n/2)$,

It remains to bound the probability on the right-side above, which can be done provided the bias and the variance of the estimator are bounded.

For $N\sim{\rm Poi}(n)$, let the power sum estimator $\widehat{\rm P}_{\alpha}=\widehat{\rm P}_{\alpha}(n,X^{N})$ have bias and variance satisfying

Then, there exists an estimator $\widehat{\rm P}^{\prime}_{\alpha}$ that uses $18n\log(1/\epsilon)$ samples and ensures

In the remainder of the section, we bound the bias and the variance for our estimators when the number of samples $n$ are of the appropriate order. Denote by $f_{\alpha}^{\text{e}}$, $f_{\alpha}^{\text{u}}$, and $f_{\alpha}^{d,\tau}$, respectively, the empirical estimator $\frac{1}{1-\alpha}\log\widehat{P}_{\alpha}^{\text{e}}$, the bias-corrected estimator $\frac{1}{1-\alpha}\log\widehat{P}_{\alpha}^{\text{u}}$, and the polynomial approximation estimator $\frac{1}{1-\alpha}\log\widehat{P}_{\alpha}^{d,\tau}$. We begin by analyzing the performances of $f_{\alpha}^{\text{e}}$ and $f_{\alpha}^{\text{u}}$ and build-up on these steps to analyze $f_{\alpha}^{d,\tau}$.

The empirical estimator was presented in (1). Using the Poisson sampling recipe given above, we derive upper bound for the sample complexity of the empirical estimator by bounding its bias and variance. The resulting bound for $\alpha>1$ is given in Theorem 9 and for $\alpha<1$ in Theorem 10.

For $\alpha>1$, $0<\delta<1/2$, and $0<\epsilon<1$, the estimator $f_{\alpha}^{\text{e}}$ satisfies

Similarly, to bound the variance, using independence of multiplicities:

where the equality holds for $k$ sufficiently large. The theorem follows by using Lemma 8. ∎

For $\alpha<1$, $\delta>0$, and $0<\epsilon<1$, the estimator $f_{\alpha}^{\text{e}}$ satisfies

For $\alpha<1$, once again we take a recourse to Lemma 4 to bound the bias as follows:

for every subset $A\subset[k]$. Upon choosing $A=\{x:\lambda_{x}\geq 1\}$, we get

where the last inequality uses (4). For bounding the variance, note that

Consider the first term on the right-side. For $\alpha\leq 1/2$, it is bounded above by since $z^{2\alpha}$ is concave in $z$, and for $\alpha>1/2$ the bound in (8) and Lemma 1 applies to give

where $(a)$ is from (9) and $(b)$ from the concavity of $z^{\alpha}$ in $z$. The proof is completed by combining the two bounds above and using Lemma 8. ∎

In fact, we show in the appendix that the dependence on $k$ implied by the previous two results are optimal.

Given a sufficiently small $\delta$, the sample complexity $S_{\alpha}^{f_{\alpha}^{\text{e}}}(k,\delta,\epsilon)$ of the empirical estimator $f_{\alpha}^{\text{e}}$ is bounded below as

While the performance of the empirical estimator is limited by these bounds, below we exhibit estimators that beat these bounds and thus outperform the empirical estimator.

III-B Performance of bias-corrected estimator for integral α𝛼\alpha

To reduce the sample complexity for integer orders $\alpha>1$ to below $k$, we follow the development of Shannon entropy estimators. Shannon entropy was first estimated via an empirical estimator, analyzed in, for instance, . However, with $o(k)$ samples, the bias of the empirical estimator remains high . This bias is reduced by the Miller-Madow correction , but even then, $O(k)$ samples are needed for a reliable Shannon-entropy estimation .

The next result provides a bound for the number of samples needed for the bias-corrected estimator.

For an integer $\alpha>1$, any $\delta>0$, and $0<\epsilon<1$, the estimator $f_{\alpha}^{\text{u}}$ satisfies

Since the bias is 0, we only need to bound the variance to use Lemma 8. To that end, we have

where the inequality uses Lemma 2. It follows from Lemma 1 that

which is less than $\delta^{2}/12$ if $\alpha^{2}k^{1-1/\alpha}/n$, for all $\delta$ sufficiently small. Applying Lemma 8 completes the proof. ∎

III-C The polynomial approximation estimator

We first give a brief description of the polynomial estimator of and then in Theorem 13 prove that for $\alpha>1$ the sample complexity of $\widehat{P}_{\alpha}^{d,\tau}$ is $O(k/\log k)$. For completeness, we also include a proof for the case $\alpha<1$, which is slightly different from the one in .

Therefore, for a given $\tau$ and $d$ the combined estimator $\widehat{P}_{\alpha}^{d,\tau}$ is

We derive upper bounds for the sample complexity of the polynomial approximation estimator.

For $\alpha>1$, $\delta>0$, $0<\epsilon<1$, there exist constants $c_{1}$ and $c_{2}$ such that the estimator $\widehat{P}_{\alpha}^{d,\tau}$ with $\tau=c_{1}\log n$ and $d=c_{2}\log n$ satisfies

Let $q(x)=\sum_{m=0}^{d}a_{m}x^{m}$ satisfy the polynomial approximation error bound guaranteed by Lemma 5, $i.e.$,

For $N_{x}^{\prime}>\tau$, the bias of empirical part of the power sum is bounded as

For variance, independence of multiplicities under Poisson sampling gives

The two bounds above along with Lemma 1 and (4) yield

For $d=\tau/8=\frac{1}{2}\log n$, the last terms in (15) are $o(1)$ which gives

Recall from (6) that $a<(1+c_{\alpha}/d^{2\alpha})(\sqrt{2}+1)^{d}$, and therefore, $a^{2}=O((\sqrt{2}+1)^{\log n})=n^{c_{0}}$ for some $c_{0}<1$. Using (18) we get

Therefore, the result follows from Lemma 8 for $k$ sufficiently large. ∎

We now prove an analogous result for $\alpha<1$.

For $\alpha<1$, $\delta>0$, $0<\epsilon<1$, there exist constants $c_{1}$ and $c_{2}$ such that the estimator $\widehat{P}_{\alpha}^{d,\tau}$ with $\tau=c_{1}\log n$ and $d=c_{2}\log n$ satisfies

We proceed as in the previous proof and set $\tau$ to be $4\log n$. The contribution to the bias of the estimator for a symbol $x$ with $N_{x}^{\prime}<\tau$ remains bounded as in (14). For a symbol $x$ with $N_{x}^{\prime}>\tau$, the bias contribution of the empirical estimator is bounded as

The first term can be bounded in the manner of (11) as

and, using (17), the following bound for the variance:

Here $a^{2}$ is the largest squared coefficient of the approximating polynomial and, by (6), is $O(2^{2c_{0}d})=O(n^{c_{0}\alpha})$ for some $c_{0}<1$. Thus, $a^{2}=o(n^{\alpha})$ and the proof follows by Lemma 8. ∎

IV Examples and experiments

The uniform distribution $U_{k}$ over $[k]=\left\{1,\ldots,k\right\}$ is given by

Its Rényi entropy for every order $1\neq\alpha\geq 0$, and hence for all $\alpha\geq 0$, is

The Zipf distribution $Z_{\beta,k}$ for $\beta>0$ and $k\in[k]$ is given by

Its Rényi entropy of order $\alpha\neq 1$ is

Table II summarizes the leading term $g(k)$ in the approximationWe say $f(n)\sim g(n)$ to denote $\lim_{n\rightarrow\infty}f(n)/g(n)=1$. $H_{\alpha}(Z_{\beta,k})\sim g(k)$.

We now illustrate the performance of the proposed estimators for various distributions for $\alpha=2$ in Figures 2 and $\alpha=1.5$ in Figures 3. For $\alpha=2$, we compare the performance of bias-corrected and empirical estimators. For $\alpha=1.5$, we compare the performance of the polynomial-approximation and the empirical estimator. For the polynomial-approximation estimator, the threshold $\tau$ is chosen as $\tau=\ln(n)$ and the approximating polynomial degree is chosen as $d=\lceil 1.5\tau\rceil$.

We test the performance of these estimators over six different distributions: the uniform distribution, a step distribution with half of the symbols having probability $1/(2k)$ and the other half have probability $3/(2k)$, Zipf distribution with parameter $3/4$ ($p_{i}\propto i^{-3/4}$), Zipf distribution with parameter $1/2$ ($p_{i}\propto i^{-1/2}$), a randomly generated distribution using the uniform prior on the probability simplex, and another one generated using the Dirichlet-$1/2$ prior.

In both the figures the true value is shown in black and the estimated values are color-coded, with the solid line representing their mean estimate and the shaded area corresponding to one standard deviation. As expected, bias-corrected estimators outperform empirical estimators for $\alpha=2$ and polynomial-approximation estimators perform better than empirical estimators for $\alpha=1.5$.

V Lower bounds on sample complexity

We first prove the lower bound for integers $\alpha>1$, which matches the upper bound in Theorem 12 up to a constant factor.

where the constant implied by $\Omega$ may depend on $\epsilon$.

Since for small values of $\delta$ we have $(1+\delta)^{1/2}<1+\delta$,

Next, we lower bound $S_{\alpha}(k)$ for noninteger $\alpha>1$ and show that it must be almost linear in $k$. While we still rely on Lemma 15 for our lower bound, we take recourse to Poisson sampling to simplify our calculations.

(Poisson approximation 2) Suppose there exist $\delta,\epsilon>0$ such that, with $N\sim{\rm Poi}(2n)$, for all estimators $\hat{f}$ we have

(Sufficiency of profiles). Consider an estimator $\hat{f}$ such that

for Poisson sampling with $N\sim{\rm Poi}(n)$, it holds that

Let $\mathbf{x}=(1,...,{d}))$. Consider the polynomial

and $q(z)=p(z)-\Delta$, where $\Delta$ is chosen small enough so that $q(z)$ has ${d}$ positive roots. Let $y_{1},...,y_{d}$ be the roots of the polynomial $q(z)$. By Newton-Girard identities, while the sum of ${d}$th power of roots of a polynomial does depend on the constant term, the sum of first ${d}-1$ powers of roots of a polynomial do not depend on it. Since $p(z)$ and $q(z)$ differ only by a constant, it holds that

Furthermore, using a first order Taylor approximation, we have

and so, the left side above is nonzero for all $\Delta$ sufficiently small provided

Denoting the right side above by $h(\alpha)$, note that $h(i)=0$ for $i=1,...,{d}-1$. Since $h(\alpha)$ is a linear combination of ${d}$ exponentials, it cannot have more than ${d}-1$ zeros (see, for instance, ). Therefore, $h(\alpha)\neq 0$ for all $\alpha\notin\{1,...,{d}-1\}$; in particular, $\|\mathbf{x}\|_{\alpha}\neq\|\mathbf{y}\|_{\alpha}$ for all $\Delta$ sufficiently small. ∎

We are now in a position to prove our converse results.

Given a nonintegral $\alpha>1$, for any fixed $0<\epsilon<1/2$, we have

Finally, we show that $S_{\alpha}(k)$ must be super-linear in $k$ for $\alpha<1$.

Given $\alpha<1$, for every $0<\epsilon<1/2$, we have

where the vectors $\mathbf{x}$ and $\mathbf{y}$ are given by Lemma 20 and $\beta$ satisfies $\alpha(1+\beta)<1$, and

Therefore, for sufficiently large $k$, (20) holds by Lemma 20 since $\alpha(1+\beta)<1$, and for $n<C_{2}k^{(1+\beta-1/d)}$ we get (21) by Theorem 19 as

The theorem follows since $d$ and $\beta<1/\alpha-1$ are arbitrary. ∎

Acknowledgements

The authors thank Chinmay Hegde and Piotr Indyk for helpful discussions and suggestions.

References

Appendix A: Estimating power sums

namely for an additive accuracy in this range, Rényi entropy requires more samples than power sums.

It follows that the power sum estimation results in and the Rényi-entropy estimation results in this paper complement each other in several ways. For example, for $\alpha<1$,

where the first inequality follows from Theorem 22 and the last follows from the upper-bound (22) derived in using a polynomial approximation estimator. Hence, for $\alpha<1$, estimating power sums to additive and multiplicative accuracy require a comparable number of samples.

On the other hand, for $\alpha>1$, Theorems 9 and 21 imply that for non integer $\alpha$, $\stackrel{{\scriptstyle\sim}}{{\smash{\stackrel{{\scriptstyle\sim}}{{\smash{\Omega}\rule{0.0pt}{4.73611pt}}}}\rule{0.0pt}{6.45831pt}}}\left(k\right)\leq S^{P\times}_{\alpha}(k)\leq O\left(k\right),$ while in the Appendix we show that for $1<\alpha$, $S^{P+}_{\alpha}(k)$ is a constant. Hence in this range, power sum estimation to a multiplicative accuracy requires considerably more samples than estimation to an additive accuracy.

The next result shows that the bias and the variance of the empirical estimator are $o(1)$.

For an appropriately chosen constant $c>0$, the bias and the variance of the empirical estimator are bounded above as

where the last inequality holds by Lemma 4 and Lemma 2since $x^{\alpha}$ is convex in $x$. Noting $\sum_{i}\lambda_{x}=n$, we get

Similarly, proceeding as in the proof of Theorem 9, the variance of the empirical estimator is bounded as

Further, since $x^{\alpha-1/2}$ is convex for $\alpha\geq 3/2$, the summation above is maximized when one of the $\lambda_{x}$’s is $n$ and the remaining equal which yields

Appendix B: Lower bound for sample complexity of empirical estimator

Given $\alpha<1$ and $\delta<c_{\alpha}$ for a constant $c_{\alpha}$ depending only on $\alpha$, the sample complexity $S_{\alpha}^{f_{\alpha}^{\text{e}}}(k,\delta,\epsilon)$ of the empirical estimator $f_{\alpha}^{\text{e}}$ is bounded below as

We prove the lower bound for the uniform distributon over $k$ symbols in two steps. We first show that for any constant $c_{1}>1$ if $n<k/c_{1}$ then the additive approximation error is at least $\delta$ with probability one, for every $\delta<\log c_{1}$. Then, assuming that $n\geq k/c_{1}$, we show that the additve approximation error is at least $\delta$ with probability greater than $0.9$ if $n<k/\delta$.

Hence, for any $c_{1}>1$ and $n<k/c_{1}$ and any $0\leq\delta\leq\log c_{1}$, the additive approximation error is more than $\delta$ with probability one.

Moving to the second claim, suppose now $n>k/c_{1}$. We first show that with high probability, the multiplicities of a linear fraction of $k$ symbols should be at least a factor of standard deviaton higher than the mean. Specifically, let

where $Q$ denotes the $Q$-function, $i.e.$, the tail of the standard normal random variable, and the final inequality uses Slud’s inequality [38, Theorem 2.1].

Note that $A$ is a function of $n$ i.i.d. random variables $X_{1},X_{2},\ldots,X_{n}$, and changing any one $X_{i}$ changes $A$ by at most $2$. Hence, by McDiarmid’s inequality,

where the second inequality is by Bernoulli’s inequality and the third inequality holds for every $c_{4}\leq\alpha(\alpha-1)(c_{2}\sqrt{c_{1}})^{\alpha-2}/2$. Therefore, with probability $\geq 0.9$,

Given $\alpha<1$ and $\delta<c_{\alpha}$ for a constant $c_{\alpha}$ depending only on $\alpha$, the sample complexity $S_{\alpha}^{f_{\alpha}^{\text{e}}}(k,\delta,\epsilon)$ of the empirical estimator $f_{\alpha}^{\text{e}}$ is bounded as

We proceed as in the proof of the previous lemma. However, instead of using the uniform distribution, we use a distribution which has one “heavy element” and is uniform conditioned on the occurance of the remainder. The key observation is that there will be roughly $n^{\alpha}$ occurances of the “light elements”. Thus, when we account for the error in the estimation of the contribution of light elements to the power sum, we can replace $n$ with $n^{1/\alpha}$ in our analysis of the previous lemma, which yields the required bound for sample complexity.

Specifically, consider a distribution with one heavy element such that

We begin by analyzing the estimate of the second term in power sum, namely

Let $R=\sum_{i\in[k]}N_{i}$ be the total number of occurances of light elements. Since $R$ is a binomial $(n,\delta n^{\alpha-1})$ random variable, for every constant $c>0$

In the remainder of the proof, we shall assume that this large probability event holds.

where the last inequality uses $R\leq(1+c)n^{\alpha}\leq 2n^{\alpha}$. Thus, the empirical estimate is at most $3$ with probability close to $1$ when $k$ (and therefore $n$) large. It follows from (23) that

holds. Note that conditioned on each value of $R$, the random variables $(N_{i},i\in[k])$ have a multinomial distribution with uniform probabilities, $i.e.$, these random variables behave as if we drew $R$ i.i.d. samples from a uniform distribution on $[k]$ elements. Thus, we can follow the proof of the previous lemma mutatis mutandis. We now define $A$ as

To lower bound $p\left(N_{x}\leq\frac{n}{k}-c_{2}\sqrt{\frac{n}{k}\left(1-\frac{1}{k}\right)}\right)$ Slud’s inequality is no longer available (since it may not hold for ${\tt Bin}(n,p)$ with $p>1/2$ and that is the regime of interest for the lower tail probability bounds needed here). Instead we take recourse to a combination of Bohman’s inequality and Anderson-Samuel inequality, as suggested in [38, Eqns. (i) and (ii)]. It can be verified that the condition for [38, Eqns. (ii)] holds, and therefore,

Continuing as in the proof of the previous lemma, we get that the following holds with conditional probability greater than $0.9$ given each value of $R$ satisfying (24):

where $c_{3}$ is a sufficiently small constant such that $(1+x)^{\alpha}\leq 1+\alpha x-c_{3}x^{2}$ for all $x\geq 0$ and $c_{4}=c_{3}/(1+c)$. Thus,

Denoting $y=(k/n^{\alpha})$ and choosing $c_{1}$ and $c$ small enough such that $\widehat{P}_{\alpha}^{\text{e}}\leq 2$, for all sufficiently large $n$ we get from (23) that