We study convexity properties of the Rényi entropy as function of α>00$]]> on finite alphabets. We also describe robustness of the Rényi entropy on finite alphabets, and it turns out that the rate of respective convergence depends on initial alphabet. We establish convergence of the disturbed entropy when the initial distribution is uniform but the number of events increases to ∞ and prove that the limit of Rényi entropy of the binomial distribution is equal to Rényi entropy of the Poisson distribution.
Let (Ω,F,P) be a probability space supporting all distributions considered below. For any N≥1 introduce the family of discrete distributions p=(p1,p2,…,pN) with probabilities
pi≥0,1≤i≤N,N≥1,p1+⋯+pN=1.
In the present paper we investigate some properties of the Rényi entropy, which was proposed by Rényi in [14],
Hα(p)=11−αlog∑k=1Npkα,α>0,α≠1,0,\hspace{0.2778em}\alpha \ne 1,\]]]>
including its limit value as α→1, i.e., the Shannon entropy
H(p)=−∑k=1Npklog(pk).
Due to this continuity, it is possible to put H1(p)=H(p). We consider the Rényi entropy as a functional of various parameters. The first approach is to fix the distribution and consider Hα(p) as the function of α>00$]]>. Some of the properties of Hα(p) as the function of α>00$]]> are well known. In particular, it is known that Hα(p) is continuous and nonincreasing in α∈(0,∞), limα→0+Hα(p)=logm, where m is the number of nonzero probabilities, and limα→+∞Hα(p)=−logmaxkpk. However, for the reader’s convenience, we provide the short proofs of this and some other simple statements in the Appendix. One can see that these properties of the entropy itself and its first derivative are common for all finite distributions. Also, it is known that Rényi entropy is Schur concave as a function of a discrete distribution, that is
(pi−pj)∂Hα(p)∂pi−∂Hα(p)∂pj≤0,i≠j.
Some additional results such as lower bounds on the difference in the Rényi entropy for distributions defined on countable alphabets could be found in [12]. Those results usually use the Rényi divergence of order α of a distribution P from a distribution QDαP||Q=1α−1log∑i=1Npiαqiα−1,
which is very similar to the Kullback–Leibler divergence. Some most important properties of the Rényi divergences were reviewed and extended in [7]. Rényi divergences for most commonly used univariate continuous distributions could be found in [8]. The Rényi entropy and divergence is widely used in majorization theory [6, 15], statistics [4, 13], information theory [12, 7, 1] and many other fields. Boundedness of the Rényi entropy was shown in [5] for discrete log-concave distributions depending on its variance. There are other operational definitions of the Rényi entropy given in [11], which are used in practice. It is also used in analysis of financial time series. As it is stated in [16], the Rényi entropy can deal effectively with heavy-tailed distributions and reflect a short-range characteristics of financial time series. So, in some sense, entropy can be connected to the long- and short-range dependence of the selected stochastic processes and allows to compare the memory inherent to various processes. Other methods of comparing the memory of the processes are proposed, e.g., in [3] and [2]. What is more, the Rényi entropy is used in physics. For it to be physically meaningful as thermostatistical quantity it should not change drastically if the probability distribution is slightly changed. It is important that experimental uncertainty in determining the distribution function not cause entropy to diverge. In [9] it is shown that the Rényi entropy is uniformly continuous for probabilities on finite sets. In our paper we go on and find the rate of convergence. In the present paper we restrict ourselves to the standard Rényi entropy and go a step ahead in comparison of standard properties, namely, we investigate convexity of the Rényi entropy with the help of the second derivative. It turned out that from this point of view, the situation is much more interesting and uncertain in comparison with the behavior of the first derivative, and crucially depends on the distribution. One might say that all the standard guesses are wrong. Of course, the second derivative is continuous (evidently, it simply means that it is continuous at 1 because at all other points the continuity is obvious), but then the surprises begin. If the second derivative starts with a positive value at zero, it can either remain positive or have inflection points, depending on the distribution. If it starts from the negative value, it can have the first infection point both before 1 and after 1, depending on the distribution, too (point 1 is interesting as some crucial point for entropy, so, we compare the value of inflection points with it). The value of the second derivative at zero is bounded from below but unbounded from above. Due to the over-complexity of some expressions, which defied analytical consideration, we propose several illustrations performed by numerical methods. We investigate robustness of the Rényi entropy w.r.t. the distribution, and it turns out that the rate of respective convergence depends on initial distribution, too. Further, we establish convergence of the disturbed entropy when the initial distribution is uniform but the number of events increases to ∞, and prove that the limit of Rényi entropy of the binomial distribution is equal to entropy of the Poisson distribution. It was previously proved in [10] that the Shannon entropy of the binomial distribution is increasing to entropy of the Poisson distribution. Our proof of this particular fact is simpler because uses only Lebesgue’s dominated convergence theorem. The paper is organized as follows. Section 2 is devoted to the convexity properties of the Rényi entropy, Section 3 describes robustness of the Rényi entropy, and Section A contains some auxiliary results.
Convexity of the Rényi entropy
To start, we consider the general properties of the 2nd derivative of the Rényi entropy.
The form and the continuity of the 2nd derivative
Let us denote Si(α)=∑k=1Npkαlogipk, i=0,1,2,3. Denote also f(α)=log(∑k=1Npkα). Obviously, the function f∈C∞(R+), and its first three derivatives equal
f′(α)=S1(α)S0(α),f″(α)=S2(α)S0(α)−S12(α)S02(α),f‴(α)=S3(α)S02(α)−3S2(α)S1(α)S0(α)+2S13(α)S03(α).
In particular, if one considers the random variable ξ taking values logpk with probability pk, then
f′(1)=E(ξ)<0,f″(1)=E(ξ2)−(E(ξ))2>0,f‴(1)=E(ξ3)−3E(ξ2)E(ξ)+2(E(ξ))3,0,\\ {} \displaystyle {f^{\prime\prime\prime }}(1)=E({\xi ^{3}})-3E({\xi ^{2}})E(\xi )+2{(E(\xi ))^{3}},\end{array}\]]]>
and the sign of f‴(1) is not fixed (as we can see below, it can be both + and −).
Letpk≠0for all1≤k≤N. Then
(a) The 2nd derivativeHα″(p)equalsHα″(p)=−1(1−α)3∑k=1N(1−α)qk′(α)+2qk(α)logqk(α)pk,whereqk(α)=pkα∑k=1Npkα.
(b) The 2nd derivativeHα″(p)can be also presented asHα″(p)=−13f‴(θ)for some0<θ<α.
The 2nd derivativeHα″(p)is continuous onR+if we putH1″(p)=−13f‴(1)=−13(E(ξ3)−3E(ξ2)E(ξ)+2(E(ξ))3).
Equality (2) is a result of direct calculations. Concerning equality (3), we can present Hα(p) as
Hα(p)=f(α)−f(1)1−α,
therefore, −Hα(p) is a slope function for f. Taking successive derivatives, we get from the standard Taylor formula that
Hα′(p)=f′(α)(1−α)+f(α)(1−α)2=−12f″(η),
and
Hα″(p)=f″(α)(1−α)2+2f′(α)(1−α)+2f(α)=−13f‴(θ),
where η,θ∈(1,α). If α→1, then both η and θ tend to 1. Taking into account (1), we immediately get both equality (3) and statement (ii). □
Behavior of the 2nd derivative at the origin
Let us consider the starting point for the 2nd derivative, i.e., the behavior of Hα″(p) at zero as a function of a distribution vector p. Analyzing (2), we see that Hα″(p) as function of α is continuous in 0. Moreover,
qk(0)=1/N,qk′(0)=logpkN−∑k=1NlogpkN2,
so we can present Hα″(p) as
H0″(p)=−∑k=1N1Nlogpk−1N2∑i=1Nlogpi+2Nlog1Npk=∑k=1N1Nlogpk−1N2∑i=1Nlogpi+2NlogN+logpk=2logN+1N∑k=1N(logpk)2−1N2∑k=1Nlogpk2+2N∑k=1Nlogpk.
Now we are interested in the sign of Hα″(p). It is very simple to give an example of a distribution for which Hα″(p)>00$]]>. One of such examples is given in Figure 1. Negative Hα″(p) is also possible, however, at this moment we prefer to start with a more general result.
If some probability vector p is a point of local extremum ofHα″(p)then eitherp=p(uniform)=1N,…,1Nor it contains two different probabilities.
Let us formulate the necessary conditions for H0″(p) to have a local extremum at some point. Taking into account the limitation ∑k=1Npk=1, these conditions have the form
2logN+1N∑k=1N(logpk)2−1N2∑k=1Nlogpk2+2N∑k=1Nlogpk⟶extr∑k=1Npk=1.
We write the Lagrangian function
L=λ02logN+1N∑k=1N(logpk)2−1N2∑k=1Nlogpk2+2N∑k=1Nlogpk+λ∑k=1Npk−1.
If some p is an extremum point then there exist λ0 and λ such that λ02+λ2≠0 and ∂L∂pi(p)=0 for all 1≤i≤N, i.e.,
∂L∂pi=λ02Npilogpi−2N2pi∑k=1Nlogpk+2Npi+λ=0.
If λ0=0 then λ=0. However, λ02+λ2≠0, therefore we can put λ0=1. Then
−λpi=2Nlogpi−2N2∑k=1Nlogpk+2N.
Taking the sum of these equalities we get that λ=−2, whence
pi−1Nlogpi=1N−1N2∑k=1Nlogpk.
So, if the distribution vector p is an extremum point then p1−1Nlogp1=⋯=pN−1NlogpN. Let us take a look at the continuous function f(x)=x−1Nlogx, x∈(0,1). Its derivative equals
f′(x)=1−1Nx=0⇔x=1N,sign(f′(x))=signx−1N,limx→0+f(x)=+∞,limx→+1f(x)=1.
So, f(x) has its global minimum at point x=1N, and for any f(1N)<y≤1 there exist two points, x′≠x″, x′,x″∈(0,1) such that f(x′)=f(x″)=y. Thus, if H0″(p) achieves local extremum at vector p, then it contains no more than two different probabilities. Obviously, it can be p=p(uniform)=1N,…,1N. □
Note that H0″(p(uniform))=0. Therefore, in order to find the distribution for which H0″(p)<0, let us consider the distribution vector that contains only two different probabilities p0, q0 such that:
p0−q0=1Nlogp0−logq0,kp0+(N−k)q0=1,
where N,k∈N, N>kk$]]> and p0,q0∈(0,1).
Let p be the distribution vector satisfying (5). ThenH0″(p)<0.
First, we will show that H0″(p) is nonpositive. For that we rewrite H0″(p) in terms of p0 and q0:
H0″(p)=2logN+1Nk(logp0)2+(N−k)(logq0)2−1N2klogp0+(N−k)logq02+2Nklogp0+(N−k)logq0=2logN+k(N−k)N2(logp0)2−2logp0logq0+(logq0)2+2kNlogp0−logq0+2logq0=2logNq0+k(N−k)(p0−q0)2+2k(p0−q0).
We know that kp0+(N−k)q0=1, whence k=Nq0−1q0−p0, and N−k=1−Np0q0−p0. Then
H0″(p)=2logNq0+(1−Nq0)(Np0−1)+2(1−Nq0)=2logNq0+N(p0−q0)+1−N2p0q0=log(Nq0)2+logp0q0+1−N2p0q0=logN2p0q0−N2p0q0+1.
Note that logx−x+1<0 for x>00$]]>, x≠1. We want to show that under conditions (5) N2p0q0 cannot be equal to 1. Suppose that N2p0q0=1. Then it follows from (5) that
kN2+(N−k)q02=q0.
It means that q0 and p0 are algebraic numbers. Thus, their defference p0−q0 is also algebraic. On the other hand, by the Lindemann–Weierstrass theorem 1N(logp0−logq0) is transcendental number, which contradicts (5). So N2p0q0≠1 and H0″(p)<0. □
For anyn>22$]]>there existsN≥nand a probability vectorp=(p1,…,pN)such thatH0″(p)<0.
Consider a distribution vector p that satisfies conditions (5). From Lemma 3 we know that H0″(p)<0. Now we want to show that there exist an arbitrarily large N∈N and a distribution vector p of length N that satisfy those conditions. For that we denote
x=Np0,y=Nq0,r=kN=y−1y−x.
Then 0<x<1<y and r<1 and x−y=logx−logy. The function x−logx is decreasing on (0,1), is increasing on (1,+∞) and is equal to 1 at point 1. Let y=y(x) be the implicit function defined by x−y=logx−logy. By that we get the 1-to-1 correspondence from x∈(0,1) to y∈(1,+∞). We also have fuction the r(x)=y(x)−1y(x)−x. If we find x′∈(0,1) such that r′=r(x′) is rational then we could pick N,k∈N such that r′=kN and get q distribution vector p satisfying (5) with p0=xN, q0=yN. However, we will not look for such x′, bot will just show that they exist. To do that, observe that y(x) is a continuous function of x and so is the function r(x)=y(x)−1y(x)−x. What is more,
y(x)→+∞,x→0+sor(x)→1,x→0+.
Let us fix x0∈(0,1), r(x0)<1. Then for any r′∈(r(x0),1) there exists x′∈(0,x0) such that r(x′)=r′. By taking r′∈Q we get that there exists x′ such that kN<1 and is rational. Finally, we want to show that N can be arbitrarily large. For that simply observe that kN=r′ so as r′→1− we get that N→+∞. □
Let N be fixed. ThenH0″(p)as the function of vector p is bounded from below and is unbounded from above.
Recall that H0″(p)=0 on the uniform distribution and exclude this case from the further consideration. In order to simplify the notations, we denote xk=logpk, and let
SN:=N(H0″(p)−2logN)=∑k=1N(xk)2−1N∑k=1Nxk2+2∑k=1Nxk.
Note that there exists n≤N−1 such that
x1<log1N,…,xn<log1N,xn+1≥log1N,…,xN≥log1N.
Further, denote the rectangle A=[log1N;0]N−n⊂RN−n, and let
SN,1=∑k=1nxk,SN,2=∑k=n+1Nxk.
Let us establish that H0″(p) is bounded from below. In this connection, rewrite SN as
SN=∑k=1nxk2+∑k=n+1Nxk2−1N(SN,1)2+2SN,1SN,2+(SN,2)2+2SN,1+2SN,2.
By the Cauchy–Schwarz inequality we have
∑k=1nxk2≤n∑k=1nxk2,∑k=n+1Nxk2≤(N−n)∑k=n+1Nxk2.
Therefore
SN≥1−nN∑k=1nxk2+nN∑k=n+1Nxk2−2NSN,1SN,2+2SN,1+2SN,2=∑k=1n1−nNxk2+xk2−2NSN,2+nN∑k=n+1Nxk2+2SN,2=1N∑k=1nN−nxk2+2xkN−SN,2+nN∑k=n+1Nxk2+2SN,2.
There exists M>00$]]> such that for every n≤N−1 we have |SN,2|≤M because A is compact and SN,2 is continuous on A. Obviously, nN∑k=n+1Nxk2≥0. Finally, for every 1≤k≤n we have that N−nxk2+2xkN−S2 is bounded from below by the value −(N−S2,N)2N−n≥−N2−M2. Resuming, we get that SN is bounded from below, and consequently H0″(p) is bounded from below for fixed N.
Now we want to establish that H0″(p) is not bounded from above. In this connection, let ε>00$]]>, and let us consider the distribution of the form p1=ε, p2=⋯=pN=1−εN−1. Then we have
H0″(p)=2logN+1N∑k=1N(logpk)2−1N2∑k=1Nlogpk2+2N∑k=1Nlogpk=2logN+N−1Nlog1−εN−12+1N(logε)2−1N2(N−1)log1−εN−1+logε2+2(N−1)Nlog1−εN−1+2Nlogε=1N−1N2logε2+2N−2(N−1)N2log1−εN−1logε+2logN+N−1N−(N−1)2N2log1−εN−12+2(N−1)Nlog1−εN−1→+∞,ε→0+.
□
Superposition of entropy that is convex
Now we establish that the superposition of entropy with some decreasing function is convex. Namely, we shall consider the function
Gβ(p)=−H1+1β(p)=βlog∑k=1Npk1+1/β,β>0,0,\]]]>
and prove its convexity. Because now we consider the tools that do not include differentiation, we can assume that some probabilities are zero. In order to prove the convexity, we start with the following simple and known result whose proof is added for the reader’s convenience.
For any measure space(X,Σ,μ)and any measurablef∈Lp(X,Σ,μ)for some intervalp∈[a,b],fp=fLp(X,Σ,μ)is log-convex as a function of1/pon this interval.
For any p2,p1>00$]]> and θ∈(0,1), denote p=(θ/p1+(1−θ)/p2)−1 and observe that
θp/p1+(1−θ)p/p2=1.
Therefore, by the Hölder inequality
fpp=∫X|f(x)|θp·|f(x)|(1−θ)pμ(dx)≤∫X|f(x)|p1μ(dx)θp/p1∫X|f(x)|p2μ(dx)(1−θ)p/p2,
whence
logfp≤θlogfp1+(1−θ)logfp2,
as required. □
For any probability vectorp=(pk,1≤k≤N), the functionGβ(p),β>00$]]>, is convex.
It follows from Lemma 5 by setting X=1,…,N, μ(A)=∑k∈Apk, f(k)=pk, k∈X. □
It follows immediately from (6) that for the function
Gβ(p)=βlog∑k=1Npk1+1/β,β>0,0,\]]]>Hα(p)=G1α−1(p). For α>11$]]>, 1α−1 is convex. If there be such p that G·(p) be nondecreasing on an interval, then G1α−1(p) be convex on that interval and Hα(p) be convex, too. However,
Gβ′(p)=log∑k=1Npk1+1/β−1β∑k=1Npk1+1/βlogpk∑k=1Npk1+1/β=−∑k=1Npk1+1/β∑k=1Npk1+1/βlogpk1/β∑k=1Npk1+1/β≤0.
In some sense, this is a reason why we cannot say something definite concerning the 2nd derivative of entropy either on the whole semiaxes or even in the interval [1,+∞).
Graphs of <inline-formula id="j_vmsta185_ineq_169"><alternatives><mml:math>
<mml:msub>
<mml:mrow>
<mml:mi mathvariant="script">H</mml:mi>
</mml:mrow>
<mml:mrow>
<mml:mi mathvariant="italic">α</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo mathvariant="normal" fence="true" stretchy="false">(</mml:mo>
<mml:mi mathvariant="italic">p</mml:mi>
<mml:mo mathvariant="normal" fence="true" stretchy="false">)</mml:mo></mml:math><tex-math><![CDATA[${\mathcal{H}_{\alpha }}(p)$]]></tex-math></alternatives></inline-formula> and its second derivative for several probability distributions
Graphs of Hα(p) and Hα″(p), where p1=p2=0.4, p3=0.2. Here Hα(p) is convex as a function of α>00$]]>
Graphs of Hα(p) and Hα″(p), where p1=⋯=p198=1400, p199=p200=101400. Dot is the point where Hα″(p)=0 and this point is α=0.99422
Graphs of Hα(p) and Hα″(p), where p1=⋯=p10=0.01, p11=p12=0.15, p13=p14=0.3. Here the second derivative becomes positive long before point 1 (at point 0.11318)
Graphs of Hα(p) and Hα″(p), where p1=⋯=p10=0.08, p11=0.2. Here the second derivative becomes positive after point 1 (at point 2.9997)
Graphs of Hα(p) and Hα″(p), where p1=⋯=p100=0.0001, p101=⋯=p200=0.0079, p201=0.2. Here the second derivative has two zeros
Graph of Hα(p), where p1=p2=0.05,p3 is changing from 0 to 0.9 and p4=1−p1−p2−p3
Robustness of the Rényi entropy
Now we study the asymptotic behavior of the Rényi entropy depending on the behavior of the involved probabilities. The first problem is the stability of the entropy w.r.t. involved probabilities and the rate of its convergence to the limit value when probabilities tend to their limit value with the fixed rate.
Rate of convergence of the disturbed entropy when the initial distribution is arbitrary but fixed
Let us look at distributions that are “near” some fixed distribution p=(pk,1≤k≤N) and construct the approximate distribution p(ϵ)=(pk(ϵ),1≤k≤N) as follows. We can assume that some probabilities are zero, and we shall see that this assumption influences the rate of convergence of the Rényi entropy to the limit value. So, let 0≤N1<N be a number of zero probabilities, and for them we consider approximate values of the form pk(ϵ)=ckε, 0≤ck≤1, 1≤k≤N1. Further, let N2=N−N1≥1 be a number of nonzero probabilities, and for them we consider approximate values of the form pk(ϵ)=pk+ckε, |ck|≤1, N1+1≤k≤N, where c1+⋯+cN=0 and ε≤minN1+1≤k≤Npk. Assume also that there exists k≤N such that ck≠0, otherwise Hα(p)−Hα(p(ϵ))=0. So, we disturb the intial probabilities linearly in ε with different weights whose sum should necessarily be zero. These assumptions imply that 0≤pk(ϵ)≤1 and p1(ϵ)+⋯+pN(ϵ)=1. Now we want to find out how entropy of the disturbed distribution will differ from the initial entropy, depending on parameters ε, N and α. We start with α=1.
Let the number N and coefficientsc1,…,cNbe fixed, and letα=1. We have three different situations:
LetN1≥1and there existsk≤N1such thatck≠0. ThenH1(p)−H1(p(ϵ))∼εlogε∑k=1N1ck,ε→0.
Let for allk≤N1ck=0and∑k=N1+1Ncklogpk≠0. ThenH1(p)−H1(p(ϵ))∼ε∑k=N1+1Ncklogpk,ε→0.
Let for allk≤N1ck=0and∑k=N1+1Ncklogpk=0. ThenH1(p)−H1(p(ϵ))∼ε22∑k=N1+1Nck2pk,ε→0.
First of all, we will find the asymptotic behavior of two auxiliary functions as ε→0. First, let 0≤ck≤1. Then
ckεlog(ckε)=ckεlogε+ckεlogck=ckεlogε+o(εlogε),ε→0.
Second, let pk>00$]]>, |ck|≤1. Taking into account the Taylor expansion of logarithm
log(1+x)=x−x22+o(x2),x→0,
we can write:
(pk+ckε)log(pk+ckε)−pklogpk=ckεlogpk+(pk+ckε)log(1+ckpk−1ε)=ckεlogpk+(pk+ckε)ckpk−1ε−12(ckpk−1ε)2+o(ε2)=ε(cklogpk+ck)+ε2ck2pk−1−12ck2pk−1+o(ε2)=ε(cklogpk+ck)+ck2ε22pk+o(ε2),ε→0.
In particular, we immediately get from (3.1) that
(pk+ckε)log(pk+ckε)−pklogpk=o(εlogε),ε→0,
and
(pk+ckε)log(pk+ckε)−pklogpk=ε(cklogpk+ck)+o(ε),ε→0
Now simply observe the following.
(i)limε→0H1(p)−H1(p(ϵ))εlogε=limε→01εlogε∑k=1N1ckεlogckε+1εlogε∑k=N1+1N((pk+ckε)log(pk+ckε)−pklogpk)=limε→01εlogε∑k=1N1(ckεlogε+o(εlogε))+∑k=N1+1No(εlogε)=∑k=1N1ck.(ii) Since for any k≤N1 we have that ck=0 and the total sum c1+⋯+cN=0 then cN1+1+⋯+cN=0. Furthermore, in this case
limε→0H1(p)−H1(p(ϵ))ε=limε→01ε∑k=N1+1N((pk+ckε)log(pk+ckε)−pklogpk)=limε→01ε∑k=N1+1N(ε(cklogpk+ck)+o(ε))=∑k=N1+1N(cklogpk+ck)=∑k=N1+1Ncklogpk.(iii) In this case we have the following relations:
limε→0H1(p)−H1(p(ϵ))ε2=limε→01ε2∑k=N1+1N((pk+ckε)log(pk+ckε)−pklogpk)=limε→01ε2∑k=N1+1N(ε(cklogpk+ck)+ck2ε22pk+o(ε2))=limε→01ε2∑k=N1+1Nck2ε22pk+o(ε2)=12∑k=N1+1Nck2pk.
Theorem is proved. □
Now we proceed with α<1.
Let the number N and coefficientsc1,…,cNbe fixed, and letα<1. Then we have three different situations:
LetN1≥1and there existsk≤N1such thatck≠0. ThenHα(p)−Hα(p(ϵ))∼εαα−1∑k=1N1ckα∑k=N1+1Npkα−1,ε→0.
Let for allk≤N1ck=0and∑k=N1+1Nckpkα−1≠0. ThenHα(p)−Hα(p(ϵ))∼αεα−1∑k=N1+1Nckpkα−1∑k=N1+1Npkα−1,ε→0.
Let for allk≤N1ck=0and∑k=N1+1Nckpkα−1=0. ThenHα(p)−Hα(p(ϵ))∼αε22∑k=N1+1Nck2pkα−2∑k=N1+1Npkα−1,ε→0.
Similarly to proof of Theorem 2, we start with several asymptotic relations as ε→0. Namely, let pk>00$]]>, |ck|≤1. Taking into account the Taylor expansion of (1+x)α that has the form
(1+x)α=1+αx+o(x),x→0,
we can write:
αck(pk+ckε)α−1=αckpkα−1(1+ckpk−1ε)α−1=αckpkα−1(1+(α−1)ckpk−1ε+o(ε))=αckpkα−1+α(α−1)ck2pkα−2ε+o(ε),ε→0.
As a consequence, we get the following asymptotic relations:
αck(pk+ckε)α−1=o(εα−1),ε→0,
and
αck(pk+ckε)α−1=αckpkα−1+o(1),ε→0(i) Applying L’Hospital’s rule, we get:
limε→0Hα(p)−Hα(p(ϵ))εα=limε→01(α−1)εαlog∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α−1(α−1)εαlog∑k=1Npkα=1α−1limε→01αεα−1×∑k=1N1αckαεα−1+∑k=N1+1Nαck(pk+ckε)α−1∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=1α−1limε→0∑k=1N1ckα+ε1−α∑k=N1+1No(εα−1)∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=1α−1∑k=1N1ckα∑k=N1+1Npkα−1.(ii) In this case we can transform the value under a limit as follows:
limε→0Hα(p)−Hα(p(ϵ))ε=limε→01(α−1)εlog∑k=N1+1N(pk+ckε)α−log∑k=1Npkα=1α−1limε→0∑k=N1+1Nαck(pk+ckε)α−1∑k=N1+1N(pk+ckε)α=1α−1limε→0∑k=N1+1N(αckpkα−1+o(1))∑k=N1+1N(pk+ckε)α=αα−1∑k=N1+1Nckpkα−1∑k=N1+1Npkα−1.(iii) Finally, in the 3rd case,
limε→0Hα(p)−Hα(p(ϵ))ε2=limε→01(α−1)ε2log∑k=N1+1N(pk+ckε)α−log∑k=1Npkα=1α−1limε→012ε∑k=N1+1Nαck(pk+ckε)α−1∑k=N1+1N(pk+ckε)α=1α−1limε→012ε∑k=N1+1N(αckpkα−1+α(α−1)ck2pkα−2ε+o(ε))∑k=N1+1N(pk+ckε)α=1α−1limε→012ε∑k=N1+1N(α(α−1)ck2pkα−2ε+o(ε))∑k=N1+1N(pk+ckε)α=α2∑k=N1+1Nck2pkα−2∑k=N1+1Npkα−1.
Theorem is proved. □
Now we conclude with α>11$]]>. In this case, five different asymptotics are possible.
Let the number N and coefficientsc1,…,cNbe fixed, and letα>11$]]>. Then five different situations are possible:
Let∑k=N1+1Nckpkα−1≠0. Then for anyN1≥0andα>11$]]>, we have thatHα(p)−Hα(p(ϵ))∼αεα−1∑k=N1+1Nckpkα−1∑k=N1+1Npkα−1,ε→0.
Let∑k=N1+1Nckpkα−1=0,N1≥1, and there existsk≤N1such thatck≠0. Then forα<2it holds thatHα(p)−Hα(p(ϵ))∼εαα−1∑k=1N1ckα∑k=N1+1Npkα−1,ε→0.
Let∑k=N1+1Nckpkα−1=0,N1≥0and for allk≤N1we have thatck=0. Then forα<2it holds thatHα(p)−Hα(p(ϵ))∼αε22∑k=N1+1Nck2pkα−2∑k=N1+1Npkα−1,ε→0.
Let∑k=N1+1Nckpkα−1=0,α=2. Then for anyN1≥0andck,k≤N1, we have thatHα(p)−Hα(p(ϵ))∼ε2∑k=1Nck2∑k=N1+1Npk2−1,ε→0.
Let∑k=N1+1Nckpkα−1=0,α>22$]]>. Then for anyN1≥0andck,k≤N1, we have thatHα(p)−Hα(p(ϵ))∼αε22∑k=N1+1Nck2pkα−2∑k=N1+1Npkα−1,ε→0.
As in the proof of Theorem 3, we shall use expansions (8) and (9). The main tool will be L’Hospital’s rule.
(i) Let ∑k=N1+1Nckpkα−1≠0. Then for any N1≥0 and α>11$]]>, we have the following relations:
limε→0Hα(p)−Hα(p(ϵ))ε=limε→01(α−1)εlog∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α−1(α−1)εlog∑k=1Npkα=1α−1×limε→0∑k=1N1αckαεα−1+∑k=N1+1Nαck(pk+ckε)α−1∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=αα−1∑k=N1+1Nckpkα−1∑k=N1+1Npkα−1.(ii) Let ∑k=N1+1Nckpkα−1=0, N1≥1, and there exists k≤N1 such that ck≠0. Then for α<2 we have that
limε→0Hα(p)−Hα(p(ϵ))εα=limε→01(α−1)εαlog∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α−1(α−1)εαlog∑k=1Npkα=1α−1limε→01αεα−1×∑k=1N1αckαεα−1+∑k=N1+1Nαck(pk+ckε)α−1∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=1α−1limε→0∑k=1N1ckαεα−1+∑k=N1+1N((α−1)ck2pkα−2ε+o(ε))εα−1∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=1α−1∑k=1N1ckα∑k=N1+1Npkα−1.(iii) Let ∑k=N1+1Nckpkα−1=0, N1≥0 and for all k≤N1 we have that ck=0. Then for α<2 it holds that
limε→0Hα(p)−Hα(p(ϵ))ε2=limε→01(α−1)ε2log∑k=N1+1N(pk+ckε)α−log∑k=1Npkα=1α−1limε→012ε∑k=N1+1Nαck(pk+ckε)α−1∑k=N1+1N(pk+ckε)α=1α−1limε→0∑k=N1+1N(αckpkα−1+α(α−1)ck2pkα−2ε+o(ε))2ε∑k=N1+1N(pk+ckε)α=1α−1limε→0∑k=N1+1N(α(α−1)ck2pkα−2ε+o(ε))2ε∑k=N1+1N(pk+ckε)α=α2∑k=N1+1Nck2pkα−2∑k=N1+1Npkα−1.(iv) Obviously, in the case α=2 we have the simple value of the entropy:
H2(p)=−log∑k=1Npk2.
Therefore, if ∑k=N1+1Nckpkα−1=0, α=2, then for any N1≥0 and ck,k≤N1, we have that
limε→0H2(p)−H2(p(ϵ))ε2=limε→01ε2log∑k=1N1(ckε)2+∑k=N1+1N(pk+ckε)2−1ε2log∑k=1Npk2=limε→012ε×∑k=1N12ck2ε+∑k=N1+1N2ck(pk+ckε)∑k=1N1(ckε)2+∑k=N1+1N(pk+ckε)2=limε→0∑k=1N1ck2+∑k=N1+1Nck2∑k=1N1(ckε)2+∑k=N1+1N(pk+ckε)2=∑k=1Nck2∑k=N1+1Npk2−1.(v) Let ∑k=N1+1Nckpkα−1=0, α>22$]]>. Then for any N1≥0 and ck,k≤N1, we have that
limε→0Hα(p)−Hα(p(ϵ))ε2=limε→01(α−1)ε2log∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α−1(α−1)ε2log∑k=1Npkα=1α−1limε→012ε×∑k=1N1αckαεα−1+∑k=N1+1Nαck(pk+ckε)α−1∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=1α−1limε→0∑k=1N1αckαεα−1+∑k=N1+1N(α(α−1)ck2pkα−2ε+o(ε))2ε∑k=1N1(ckε)α+∑k=N1+1N(pk+ckε)α=α2∑k=N1+1Nck2pkα−2∑k=N1+1Npkα−1.
Theorem is proved. □
Convergence of the disturbed entropy when the initial distribution is uniform but the number of events increases to <italic>∞</italic>
The second problem is to establish conditions of stability of the entropy of uniform distribution when the number of events tends to ∞. Let N>11$]]>, pN(uni)=(1N,…,1N) be a vector of uniform distribution with N possible states, ε=ε(N)≤1N, and {ckN;N≥1,1≤k≤N} be a family of fixed numbers (not all zero) such that |ckN|≤1 and ∑k=1NckN=0. Note that for any N≥1 there are strictly positive numbers ckN for some k and consider the disturbed distribution vector pN′=(1N+c1Nε,…,1N+cNNε).
Letε(N)=o(1N),N→∞. ThenHα(pN)−Hα(pN′)→0,N→∞.
We know that Nε→0, as N→∞, and the family of numbers {ckn;n≥1,1≤k≤n} is bounded. Therefore the values
supn≥1,1≤k≤n(1+Ncknε)→1,infn≥1,1≤k≤n(1+Ncknε)→1,N→∞,
as the functions of N, and for every N≥1, supn≥1,1≤k≤n(1+Ncknε)≥1. Recall that the function xlogx is increasing for x≥1, and xlogx≤0 for 0<x<1. Moreover, Rényi entropy is maximal on the uniform distribution. As a consequence of all these observations and assumptions we get that
0≤H1(pN)−H1(pN′)=1N∑k=1N(1+NckNε)log(1+NckNε)≤1N∑k=1Nsupn≥1,1≤k≤n(1+Ncknε)logsupn≥1,1≤k≤n(1+Ncknε)=supn≥1,1≤k≤n(1+Ncknε)logsupn≥1,1≤k≤n(1+Ncknε)→0,N→∞.
Let α>11$]]>. Then
0≤Hα(pN)−Hα(pN′)=1α−1log1N∑k=1N(1+NckNε)α≤1α−1log1N∑k=1Nsupn≥1,1≤k≤n(1+Ncknε)α=αα−1logsupn≥1,1≤k≤n(1+Ncknε)→0,N→∞.
Similarly, for 0<α<1 we produce the transformations
0≤Hα(pN)−Hα(pN′)=1α−1log1N∑k=1N(1+NckNε)α≤1α−1log1N∑k=1Ninfn≥1,1≤k≤n(1+Ncknε)α=αα−1loginfn≥1,1≤k≤n(1+Ncknε)→0,N→∞,
and the proof follows. □
Binomial and Poisson distributions
In this section we look at convergence of Rényi entropy of the binomial distribution to Rényi entropy of the Poisson distribution.
Letλ>00$]]>be fixed. For anyα>00$]]>limn→∞HαBn,λn=Hα(Poi(λ)).
First, let α=1. We will find and regroup entropies of the binomial and Poisson distributions.
H1Bn,p=−∑k=0nnkpk(1−p)n−klognkpk(1−p)n−k=−∑k=0nnkpk(1−p)n−klognk−nplogp+(1−p)log(1−p)=−∑k=0nnkpk(1−p)n−k(logn!−logk!−log(n−k)!)+nplogn−nplognp−nlog(1−p)+nplog(1−p)=nplog(1−p)−nlog(1−p)−nplognp+nplogn−∑k=0nnkpk(1−p)n−k(logn!−logk!−log(n−k)!).H1(Poi(λ))=−∑k=0∞e−λλkk!loge−λλkk!=λ−λlogλ+∑k=0∞e−λλkk!logk!
We want to show componentwise convergence of entropies. For that let us take np=λ and observe that
nplog(1−p)=λlog(1−p)→λlog1=0,n→∞,p→0.−nlog(1−p)=log1−λn−n→λ,n→∞,p→0.−nplognp=−λlogλ,nplogn−∑k=0nnkpk(1−p)n−k(logn!−logk!−log(n−k)!)=∑k=0nnkpk(1−p)n−kklogn−∑k=0nnkpk(1−p)n−k(logn!−logk!−log(n−k)!)=∑k=0nnkpk(1−p)n−klognk−logn!+logk!+log(n−k)!=∑k=0nnkpk(1−p)n−klognk(n−k)!n!+logk!.
It is well known that log(x)x≤1, x>00$]]>. Using this fact, we get the following representation:
nkpk(1−p)n−klognk(n−k)!n!=n!(n−k)!k!λnk1−λnn−klognk(n−k)!n!=λkk!1−λnn−kn!nk(n−k)!lognk(n−k)!n!≤λkk!1−λnn−k≤λkk!.
For the second part of the sum simply observe that
nkpk(1−p)n−klogk!=n!(n−k)!k!λnk1−λnn−klogk!=λkk!logk!1−λnn−kn!(n−k)!nk≤λkk!logk!
As ∑k=0∞λkk!1+logk!<∞, by Lebesgue’s dominated convergence theorem:
limn→∞∑k=0nnkpk(1−p)n−klognk(n−k)!n!+logk!=∑k=0∞limn→∞nkpk(1−p)n−klognk(n−k)!n!+logk!=∑k=0∞limn→∞λkk!1−λnn−kn!(n−k)!nklognk(n−k)!n!+logk!=∑k=0∞e−λλkk!logk!
Finally, we get that
limn→∞H1Bn,λn=H1(Poi(λ)).
For α≠1 we have:
Hα(binomial)=11−αlog∑k=0nnkpk(1−p)n−kα,Hα(poisson)=11−αlog∑k=0+∞e−λλkk!α.
Thus, to show that
limn→∞HαBn,λn=Hα(Poi(λ)),
it is enough to show the convergence of sums, which follows from Lebesgue’s dominated convergence theorem and
nkpk(1−p)n−kα≤λkk!α,∑k=0+∞λkk!α<+∞.
□
Appendix
We let 0log0=0 by continuity and prove several auxiliary results. Stating these three lemmas, we assume that pi≥0, 1≤i≤N are fixed.
Hα(p)→H(p),α→1.
Using L’Hospital’s rule, we get the following relations:
limα→1Hα(p)=limα→111−αlog∑k=1Npkα=limα→11−1∑k=1Npkαlog(pk)∑k=1Npkα=−∑k=1Npklog(pk)=H(p).
□
Let H1(p):=H(p) (Shannon entropy), and so Hα(p) is defined for all α>00$]]> and is continuous in α.
Hα(p)is nonincreasing inα>00$]]>.
Indeed,
∂Hα(p)∂α=1(1−α)2log∑i=1Npiα+11−α∑k=1Npkαlogpk∑k=1Npkα=1(1−α)2∑k=1Npkα∑k=1Npkαlog∑i=1Npiα+logpk1−α=−1(1−α)2∑k=1Npkα∑i=1Npiαlogpkα∑i=1Npiα1pk.
Let qk=pkα∑i=1Npiα. Then
∂Hα(p)∂α=−1(1−α)2∑k=1Nqklogqkpk≤0.
The fact that Hα(p)≤H1(p)≤Hβ(p), where 0<β<1<α follows from Lemma 6. □
Hα(p)≤logNand it reaches maximum when distribution is uniform.
Let 1≤m≤N be the number of nonzero probabilities. Then we have
limα→0+Hα(p)=limα→0+11−αlog∑k=1Npkα=logm≤logN.
So Hα(p)≤logN due to Lemma 7. For the second part, put p1=⋯=pN=1N.
H1(p)=−∑k=1N1Nlog1N=logN.Hα(p)=11−αlog∑k=1N1Nα=11−αlogNNα=logN.
□
Let 1≤m≤N be the number of nonzero probabilities and without loss of generality let pk<p1=⋯=pN1 for every N1+1≤k≤N. Then we can also define
H0(p):=limα→0+Hα(p)=limα→0+11−αlog∑k=1Npkα=logm.H∞(p):=limα→+∞Hα(p)=limα→+∞11−αlog∑k=1Npkα==limα→+∞−∑k=1Npkαlogpk∑k=1Npkα=limα→+∞−N1logp1+∑k=N1+1Npkp1αlogpkN1+∑k=N1+1Npkp1α=−logp1.
ReferencesAcharya, J., Orlitsky, A., Suresh, A.T., Tyagi, H.: The Complexity of Estimating Rényi Entropy. Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (2015). Book Code:PRDA15. MR3451148. https://doi.org/10.1137/1.9781611973730.124Banna, O., Buryak, F., Yu, M.: Distance from fractional Brownian motion with associated Hurst index 0<H<1/2 to the subspaces of Gaussian martingales involving power integrands with an arbitrary positive exponent. Mod. Stoch. Theory Appl.7, pp. 191–202 (2020). MR4120614. https://doi.org/10.15559/20-vmsta156Banna, O., Mishura, Yu., Ralchenko, K., Shklyar, S.: Fractional Brownian Motion. Approximations and Projections. Wiley-ISTE, London (2019). 288 p.Bégin, L., Germain, P., Laviolette, F., Roy, J.-F.: PAC-Bayesian Bounds based on the Rényi Divergence. In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, vol. 51, pp. 435–444. PMLR (2016).Bobkov, S.G., Marsiglietti, A., Melbourne, J.: Concentration functions and entropy bounds for discrete log-concave distributions. arXiv:2007.11030v1 [math.PR]Erven, T., Harremoës, P.: Rényi Divergence and majorization. In: IEEE Transactions on Information Theory (ISIT), INSPEC 11434178 (2010).Erven, T., Harremoës, P.: Rényi Divergence and Kullback-Leibler Divergence. IEEE Trans. Inf. Theory60, 3797–3820 (2014). MR3225930. https://doi.org/10.1109/TIT.2014.2320500Gil, M., Alajaji, F., Linder, T.: Rényi divergence measures for commonly used univariate continuous distributions. Inf. Sci.249, 124–131 (2013). MR3105467. https://doi.org/10.1016/j.ins.2013.06.018Hanel, R., Thurner, S., Tsallis, C.: On the robustness of q-expectation values and Rényi entropy. Europhys. Lett. Assoc.852 (2009).Harremoës, P.: Binomial and Poisson Distributions as Maximum Entropy Distributions. IEEE Trans. Inf. Theory475, 2039–2041(2001). MR1842536. https://doi.org/10.1109/18.930936Harremoës, P.: Interpretations of Rényi entropies and divergences. Physica A (2006). MR2223335. https://doi.org/10.1016/j.physa.2006.01.012Ho, S.-W., Verdú, S.: Convexity/concavity of Rényi entropy and α-mutual information. In: IEEE International Symposium on Information Theory (ISIT), pp. 745–749 (2015). https://doi.org/10.1109/ISIT.2015.7282554Lenzi, E.K., Mendes, R.S., Silva, L.R.: Statistical mechanics based on Rényi entropy. Physica A280, 337–345 (2000). MR1758523. https://doi.org/10.1016/S0378-4371(00)00007-8Rényi, A.: On Measures of Entropy and Information. In: Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability, vol. 1, pp. 547–561. The Regents of University of the California, Berkeley, CA, USA (1961). MR0132570Sason, I.: Tight Bounds on the Rényi Entropy via Majorization with Applications to Guessing and Compression. Entropy20(12), 896 (2018).Yang, Y., Li, J., Yang, Y.: Multiscale multifractal multiproperty analysis of financial time series based on Rényi entropy. Int. J. Mod. Phys. C28(2) (2017). MR3284253. https://doi.org/10.1016/j.physa.2014.11.009