# Some Coding Theorems for Nonadditive Generalized Mean-Value Entropies

Authors: Satish Kumar; Gurdas Ram; Vishal Gupta
Journal: International Journal of Mathematics and Mathematical Sciences
 (2012)

---

## Abstract

We give an optimality characterization of nonadditive
generalized mean-value entropies from suitable nonadditive and generalized
mean-value properties of the measure of average length. The results obtained
cover many results obtained by other authors as particular cases, as well as the
ordinary length due to Shannon 1948. The main instrument is thel(ni) function
of the word lengths in obtaining the average length of the code.


---

## Body

## 1. Introduction

Given a discrete random variableX taking a finite number of values (x1,x2,…,xn) with probabilities P=(p1,p2,…,pn), pi≥0, ∑i=1npi=1, the Shannon’s entropy of the probability distribution is given by(1.1)H(P)=-∑i=1npilog⁡(pi),
where the base of the logarithm is in general arbitrary.Shannon entropy is a very useful and powerful measure, having very rich meanings. Entropy has an important connection with noiseless coding. IfX=(x1,x2,…,xn) represents an information source with n messages and input probabilities p1,p2,…,pn, as given above, that is encoded into words of lengths N={n1,n2,…,nn} forming an instantaneous code, then(1.2)∑i=1nD-ni≤1,
where D is the size of the code alphabet.The average lengthL, for the instantaneous code is such that(1.3)L=pini≥-∑i=1npilog⁡D(pi)
with equality if and only if for each i(1.4)pi=D-ni.Result (1.4), (refer Shannon [5]), characterizes Shannon’s entropy as a measure of optimality of a linear function, namely, L, under the relation (1.2).Several generalizations of Shannon’s entropy have been studied by many authors in different ways. Here we will need the nonadditive generalized mean value measures such as(1.5)H(p1,p2,…,pn;1,α,β)=(D(β-1)/α-1)-1[D((β-1)/α)∑i=1npilog⁡Dpi-1],α,β>0,β≠1,(1.6)H(p1,p2,…,pn;α,β)=(D(1-β)/α-1)-1[(∑i=1npiα)(1/α)((β-1)/(α-1))-1],β>0,β≠1,α>0,α≠1;α≠β.
These quantities satisfy the “nonadditivity”(1.7)H(P*Q)=H(P)+H(Q)+(D(1-β)/α-1)H(P)H(Q).In this paper, we give an optimality characterization of entropies (1.5) and (1.6) from suitable nonadditive and generalized mean-value properties of the measure of average length. The results obtained cover many results obtained by other authors as particular cases, as well as the result (1.3). The main instrument is the l(·) function of the word lengths in obtaining the average length of the code.


## 2. Nonadditive Measure of Code Length

Let us consider two independent sourcesX={x1,x2,…,xn} and Y={y1,y2,…,ym} with associated probability distribution P=(p1,p2,…,pn) and Q=(q1,q2,…,qm). Then the probability distribution of the product XY={(xi,yi)} is P*Q=(p1q1,p1q2,…,p1qm,…,pnqm). Let the source Y be encoded with a code of length M={m1,m2,…,mm} and the pair (xi,yj) be represented by a sequence for xi and yj put side by side, so that the product source has code length sequence:(2.1)N+M={n1+m1,…,n1+mn,…,nn+mm}.
The additive measure of mean length is required to satisfy the requirement, refer Campbell [2],(2.2)L(P*Q,N+M,ϕ)=L(P,N,ϕ)+L(Q,M,ϕ),
where(2.3)L(P,N,ϕ)=ϕ-1(∑i=1npiϕ(ni)),ϕ being a continuous strictly monotonic increasing function.Campbell [3] proved a noiseless coding theorem for Renyi’s entropy of order α in terms of mean length (2.3) defined for ϕ(ni)=Dni.The mean length concerning Shannon’s entropy and orderα entropy of Renyi are both additive as they satisfy additivity of type (2.2).Here we deal with nonadditive measures of length denoted byL* which satisfy “nonadditivity relation”(2.4)L*(P+Q,N+M,ϕ)=L*(P,N,ϕ)+L*(Q,M,ϕ)+λL*(P,N,ϕ)L*(Q,M,ϕ),
and the mean value property(2.5)L*(P,N,ϕ)=ϕ-1(∑i=1npiϕ(l(ni))∑i=1npi),
where l(ni) is the function of length of a single element with code word length ni, which is nonadditive.


## 3. Characterization of Nonadditive Measures of Code Length

We take the mean value nonadditive measures of length (2.5) to satisfy the relation (2.4), where the expression and notations used there have their meanings explained earlier.First of all we will determine the nonadditive length functionl of the code word length in satisfying the nonadditivity relation(3.1)l(n+m)=l(n)+l(m)+λl(n)l(m),λ≠0.
This by taking f(n)=1+λl(n) gives(3.2)f(n+m)=f(n)f(m).
The most general nonzero solution of (3.2) is(3.3)f(n)=D((1-β)/α)n,
where α>0, β≠1 are arbitrary constants (we have taken base D with a purpose here). So that(3.4)l(n)=D((1-β)/α)n-1λ,λ≠0,
at this stage we make a proper choice of the constant λ. By analogy, its value is dictated as(3.5)λ=(D(1-β)/α-1),β≠1asλ≠0.Another purpose served with this value ofλ is that when it tends to zero, that is, when β→1, the function of length l(n) should reduce to additive one which is l(n)=n. This value of λ can be obtained by imposing a boundary condition l(1)=1 also.So that finally we have(3.6)l(n)=D((1-β)/α)n-1D(1-β)/α-1,β≠1,α>0.
Next we proceed to determine L*(P,N,ϕ) by first evaluating the values of ϕ. To achieve this we put the value of l(n) from (3.6) in (2.5) and then use the relation (2.4) with λ=(D(1-β)/α-1), β≠1to get
(3.7)ϕ-1(∑i=1n∑j=1mpiqjϕ((D((1-β)/α)(ni+mj)-1)/(D(1-β)/α-1))∑i=1n∑j=1mpiqj)=ϕ-1(∑i=1npiϕ((D((1-β)/α)ni-1)/(D(1-β)/α-1))∑i=1npi)+ϕ-1(∑j=1mqjϕ((D((1-β)/α)mj-1)/(D(1-β)/α-1))∑j=1mqj)+(D(1-β)/α-1)ϕ-1(∑i=1npiϕ((D((1-β)/α)ni-1)/(D(1-β)/α-1))∑j=1npi)×ϕ-1(∑j=1mqjϕ((D((1-β)/α)mj-1)/(D(1-β)/α-1))∑j=1mqj).
Now let us take Q={q} and M={m} so that for P=(p1,p2,…,pn),pi≥0,∑i=1npi=1,(3.7) gives after some simplification
(3.8)ϕ-1(∑i=1npiϕ(D((1-β)/α)(ni+m)-1D(1-β)/α-1))=ϕ-1(∑i=1npiϕ(D((1-β)/α)ni-1D(1-β)/α-1))D((1-β)/α)m+D((1-β)/α)m-1D(1-β)/α-1,
or
(3.9)ψm-1(∑i=1npiψm(D((1-β)/α)ni-1D(1-β)/α-1))=ϕ-1(∑i=1npiϕ(D((1-β)/α)ni-1D(1-β)/α-1))D((1-β)/α)m+D((1-β)/α)m-1D(1-β)/α-1,
where(3.10)ψm(D((1-β)/α)ni-1D(1-β)/α-1)=ϕ(D((1-β)/α)(ni+m)-1D(1-β)/α-1).
Now, refer Hardy et al. [4], there must be a linear relation between ψm and ϕ, that is,(3.11)ψm(n)=A(m)ϕ(n)+B(m),
where A(m) and B(m) are independent of n.Using (3.10) and (3.11), we have(3.12)g(n+m)=A(m)g(n)+B(m),
where (3.13)g(n)=ϕ(D((1-β)/α)n-1D(1-β)/α-1),
or(3.14)G(n+m)=A(m)G(n)+G(m),
where(3.15)G(n)=g(n)-g(0)=g(n)-a,a=g(0).
From the symmetry of (3.14), we get(3.16)A(m)G(n)+G(m)=A(n)G(m)+G(n)⟹G(n)A(n)-1=G(m)A(m)-1=1K(say).
Thus,(3.17)A(n)-1=K(G(n))
for all real values of n.There are two cases, namely,K=0 and K≠0.IfK=0, A(n)=1, and (3.14) gives(3.18)G(n+m)=G(n)+G(m),
the most general continuous solution of which is given by(3.19)G(n)=cn,
where c is an arbitrary constant.This, by (3.15) and (3.13), gives(3.20)ϕ(D((1-β)/α)n-1D(1-β)/α-1)=a+cn
which gives(3.21)ϕ(n)=a+cα1-βlog⁡D[1+(D(1-β)/α-1)n],β≠1.
Again if K≠0, we have the relation obtained from (3.17) and (3.14):(3.22)A(n+m)=A(n)A(m),
the general continuous solution of which are(3.23)A(n)=0(whichweneglect)foralln,A(n)=Dtn,
where t is an arbitrary nonzero constant.This by using (3.17), (3.15) in (3.13), gives(3.24)ϕ(D((1-β)/α)n-1D(1-β)/α-1)=a+Dtn-1K
which gives(3.25)ϕ(n)=a+((D(1-β)/α-1)n+1)tα/(1-β)-1K,β≠1,t≠0,α>0.
The value of ϕ given by (3.21) and (3.25) determine the following two nonadditive measures of length defined by (2.5), that is,(3.26)L*(P,N;1,α,β)=(D(1-β)/α-1)-1[D((1-β)/α)∑i=1npini-1],(3.27)L*(P,N;t,α,β)=(D(1-β)/α-1)-1[D((1-β)/αt)log⁡D∑i=1npiDnit-1].
These code lengths denoted by L*(P,N;1,α,β) and L*(P,N;t,α,β) may be named as nonadditive type (α,β) lengths of order 1 and t, respectively.These results are contained in the following theorem.Theorem 3.1.
The mean length given by  (2.5) of a sequence of lengths  ni,i=1,2,…,n formed of the code alphabet of size  D of a probability distribution  P=(p1,p2,…,pn),pi≥0,∑i=1npi=1satisfying  ∑i=1nD-ni≤1 and nonadditivity relation can be only of one of the two forms given in  (3.26) and (3.27).


### 3.1. Limiting and Particular Cases

It is immediate to see the following.(1)
(3.28)lim⁡t→0L*(P,N;t,α,β)=L*(P,N;1,α,β).(2)
(3.29)lim⁡β→1L*(P,N;1,α,β)=∑i=1npini=L,
the ordinary mean length due to Shannon [5].(3)
(3.30)lim⁡β→1L*(P,N;t,α,β)=1tlog⁡∑i=1npiDtni,
length of order t defined by Campbell [2].(4)
Forn1=n2=⋯=nn=n(say), both the expressions for length given by (3.26) and (3.27) reduce to
(3.31)(D((1-β)/α)-1)-1[D((1-β)/α)n-1],
which in the limiting case, when β approaches unity, reduces to n.(5)
Forα=β, the expression (3.26) becomes
(3.32)L*(P,N;1,α)=(D(1-α)/α-1)-1[D((1-α)/α)∑i=1npini-1].(6)
Forα=β, the expression (3.27) becomes
(3.33)L*(P,N;t,α)=(D(1-α)/α-1)-1[D((1-α)/αt)log⁡D∑i=1npiDnit-1].(7)
Forα→1 the expression (3.32) and (3.33) reduces to ∑i=1npini=L and (1/t)log∑i=1npiDtni, respectively.Thus, we have shown thatL*(P,N;1,α,β) and L*(P,N;t,α,β) are type α and β generalizations of(3.34)L=∑i=1npini,L(t)=1tlog⁡D∑i=1npiDtni,
respectively. We now prove the following theorem.Theorem 3.2.
Ifn1=n2=⋯=nn=n denote the lengths of an instantaneous/uniquely decipherable code formed of code alphabet of size D. (i)
(3.35)L*(P,N;1,α,β)≥H(P;1,α,β),
with equality if and only if  ni=-logDpi for all  i,(ii)
(3.36)L*(P,N;t,α,β)≥H(P;α,β),
with equality if and only if
(3.37)ni=-αlog⁡Dpi+log⁡D(∑i=1npiα),
where α=(1+t)-1.Proof.
As in Shannon’s case, refer Feinstien [6],(3.38)∑i=1npini≥-∑i=1npilog⁡Dpi.
Now (D(1-β)/α-1)≷0 according as β≶1.
Therefore, from the above after suitable manipulation, we get the inequality(3.39)D(1-β)/α∑i=1npini-1D(1-β)/α-1≥D(β-1)/α∑i=1npilog⁡Dpi-1D(1-β)/α-1,β≠1,
which is the result (3.35).
The case of equality can be discussed, as for Shannon’s, which holds only whenni=-logDpi, for each i.
We now proceed to part (ii). Ift=0, the result is the same proved in part (i). For other values, we use Holder’s inequality
(3.40)(∑i=1nxip)1/p⋅(∑i=1nyiq)≤xiyi,
where p-1+q-1=1 and p<1.
Making the substitutionsp=-t,q=(1-α),xi=pi(-1)/tD-ni and yi=pi1/t in (3.40), we get after suitable manipulations
(3.41)(∑i=1npiDtni)1/t≥(∑i=1npiα)1/(1-α)
with α=(1+t)-1
Raising the power to(1-β)/α of both sides of (3.41) and using that (D((1-β)/α)-1)≷0 according as β≶1, we get result (3.36) after simple manipulation.
Hence, the theorem is proved.


## 3.1. Limiting and Particular Cases

It is immediate to see the following.(1)
(3.28)lim⁡t→0L*(P,N;t,α,β)=L*(P,N;1,α,β).(2)
(3.29)lim⁡β→1L*(P,N;1,α,β)=∑i=1npini=L,
the ordinary mean length due to Shannon [5].(3)
(3.30)lim⁡β→1L*(P,N;t,α,β)=1tlog⁡∑i=1npiDtni,
length of order t defined by Campbell [2].(4)
Forn1=n2=⋯=nn=n(say), both the expressions for length given by (3.26) and (3.27) reduce to
(3.31)(D((1-β)/α)-1)-1[D((1-β)/α)n-1],
which in the limiting case, when β approaches unity, reduces to n.(5)
Forα=β, the expression (3.26) becomes
(3.32)L*(P,N;1,α)=(D(1-α)/α-1)-1[D((1-α)/α)∑i=1npini-1].(6)
Forα=β, the expression (3.27) becomes
(3.33)L*(P,N;t,α)=(D(1-α)/α-1)-1[D((1-α)/αt)log⁡D∑i=1npiDnit-1].(7)
Forα→1 the expression (3.32) and (3.33) reduces to ∑i=1npini=L and (1/t)log∑i=1npiDtni, respectively.Thus, we have shown thatL*(P,N;1,α,β) and L*(P,N;t,α,β) are type α and β generalizations of(3.34)L=∑i=1npini,L(t)=1tlog⁡D∑i=1npiDtni,
respectively. We now prove the following theorem.Theorem 3.2.
Ifn1=n2=⋯=nn=n denote the lengths of an instantaneous/uniquely decipherable code formed of code alphabet of size D. (i)
(3.35)L*(P,N;1,α,β)≥H(P;1,α,β),
with equality if and only if  ni=-logDpi for all  i,(ii)
(3.36)L*(P,N;t,α,β)≥H(P;α,β),
with equality if and only if
(3.37)ni=-αlog⁡Dpi+log⁡D(∑i=1npiα),
where α=(1+t)-1.Proof.
As in Shannon’s case, refer Feinstien [6],(3.38)∑i=1npini≥-∑i=1npilog⁡Dpi.
Now (D(1-β)/α-1)≷0 according as β≶1.
Therefore, from the above after suitable manipulation, we get the inequality(3.39)D(1-β)/α∑i=1npini-1D(1-β)/α-1≥D(β-1)/α∑i=1npilog⁡Dpi-1D(1-β)/α-1,β≠1,
which is the result (3.35).
The case of equality can be discussed, as for Shannon’s, which holds only whenni=-logDpi, for each i.
We now proceed to part (ii). Ift=0, the result is the same proved in part (i). For other values, we use Holder’s inequality
(3.40)(∑i=1nxip)1/p⋅(∑i=1nyiq)≤xiyi,
where p-1+q-1=1 and p<1.
Making the substitutionsp=-t,q=(1-α),xi=pi(-1)/tD-ni and yi=pi1/t in (3.40), we get after suitable manipulations
(3.41)(∑i=1npiDtni)1/t≥(∑i=1npiα)1/(1-α)
with α=(1+t)-1
Raising the power to(1-β)/α of both sides of (3.41) and using that (D((1-β)/α)-1)≷0 according as β≶1, we get result (3.36) after simple manipulation.
Hence, the theorem is proved.



---

*Source: 315686-2012-02-19.xml*