# A Joint Representation of Rényi’s and Tsalli’s Entropy with Application in Coding Theory

Authors: Litegebe Wondie; Satish Kumar
Journal: International Journal of Mathematics and Mathematical Sciences
 (2017)

---

## Abstract

We introduce a quantity which is called Rényi’s-Tsalli’s entropy of orderξ and discussed some of its major properties with Shannon and other entropies in the literature. Further, we give its application in coding theory and a coding theorem analogous to the ordinary coding theorem for a noiseless channel is proved. The theorem states that the proposed entropy is the lower bound of mean code word length.


---

## Body

## 1. Introduction

LetΔn={A=(a1,a2,…,an):ai≥0,i=1,2,…,n;∑i=1nai=1}, n≥2, be set of n-complete probability distributions. For any probability distribution A=(a1,a2,…,an)∈Δn, Shannon [1] defined an entropy given as (1)HA=-∑i=1nailog⁡ai,where the convention 0log⁡0=0 is adopted (see Shannon [1]). Throughout this paper, logarithms are taken to the base D(D>1). A number of parametric generalizations of Shannon entropy are proposed by many authors in literature which produces (1) for specific values of parameters. The presence of parameters makes an entropy more flexible from application point of view. One of the first generalizations of (1) was proposed by Rényi [2] as (2)HReA;ξ=11-ξlog⁡∑i=1naiξ;ξ>0≠1.Another well-known entropy was proposed by Havrda and Charvát [3](3)HhcA;ξ=21-ξ-1-1∑i=1naiξ-1;ξ>0≠1.Independently, Tsalli [4] proposed another parametric generalization of the Shannon entropy as (4)HTA;ξ=11-ξ∑i=1naiξ-1;ξ>0≠1.Equations (3) and (4) essentially have the same expression except the normalized factor. The Havrda and Charvát entropy is normalized to 1. That is, if A=1/2,1/2 then Hhc(A;ξ)=1 whereas Tsalli’s entropy is not normalized. Both the entropies yield the same result and we call these entropies as Tsalli-Havrda-Charvát entropy. Equations (2), (3), and (4) reduce to (1) when ξ→1.N. R. Pal and S. K. Pal [5, 6] have proposed an exponential entropy as(5)HppA=∑i=1naie1-ai-1.These authors claim that the exponential entropy has some advantage over Shannon’s entropy, especially within context of image processing. One such claim is that the exponential entropy has a fixed upper bound such as that for uniform distribution (1/n,1/n,…,1/n) and for the entropy in (5).(6)limn→∞⁡Hpp1n,1n,…,1n=e-1,as compared to infinite limit (as n→∞) for the entropies in (1) and (2) and also for that in (3) when ξ∈(0,1). Equation (5) was further generalized by Kvalseth [7] introducing a parameter as (7)HKA;ξ=1ξ∑i=1naie1-aiξ-1;ξ∈R.In this paper, we introduce and study a new information measure which is called Rényi’s-Tsalli’s entropy of order ξ and a new mean code word length and discuss the relation with each other. In Section 2, Rényi’s and Tsalli’s entropy is introduced and also some of its major properties are discussed. In Section 3, the application of proposed information measure in coding theory is given and it is proved that the proposed information measure is the lower bound of mean code word length.Now, in the next section, we propose a new parametric information measure.


## 2. A New Generalized Information Measure

However, in literature of information theory, there exists various generalizations of Shannon entropy; we introduce a new information measure as(8)HξA=1ξ-1-ξlog⁡∑i=1naiξ+∑i=1naiξ-1,ξ>0≠1;-∑i=1nailog⁡ai,ξ=1.Second case in (8) is a well-known Shannon entropy.The quantity (8) introduced in the present section is a joint representation of Rényi’s and Tsalli’s entropy of order ξ. Such a name will be justified, if it shares some major properties with Shannon entropy and other entropies in the literature. We study some such properties in the next theorem.


### 2.1. Properties of Proposed Entropy

Theorem 1.
The parametric entropyHξ(A),{A=(a1,a2,…,an),0<ai≤1,∑i=1n‍ai=1} has the following properties.
(1) Symmetry. Hξ(a1,a2,…,an) is a symmetric function of (a1,a2,…,an).
(2) Nonnegative. Hξ(A)≥0 for all ξ>0(≠1).(3) Expansible
(9)
H
ξ
a
1
,
a
2
,
…
,
a
n
;
0
=
H
ξ
a
1
,
a
2
,
…
,
a
n
.(4) Decisive
(10)
H
ξ
0,1
=
H
ξ
1,0
=
0
.(5) Maximality
(11)
H
ξ
a
1
,
a
2
,
…
,
a
n
≤
H
ξ
1
n
,
1
n
,
…
,
1
n
=
1
ξ
-
1
-
ξ
log
⁡
n
1
-
ξ
+
n
1
-
ξ
-
1
.(6) Concavity. The entropy
H
ξ
(
A
)
is a concave function for
0
<
ξ
<
1
of the probability distribution
A
=
(
a
1
,
a
2
,
…
,
a
n
), ai≥0;∑i=1n‍ai=1.(7) Continuity. Hξ(a1,a2,…,an)is continuous in the regionai≥0for alli=1,2,…,nandξ>0(≠1).Proof.
The properties (1), (3), (4), and (5) follow immediately from the definition. For property (7), we know that(12)log⁡∑i=1naiξ+∑i=1naiξ-1is continuous in the region ai≥0 for all ξ>0. Thus, Hξ(A), is also continuous in the region ai≥0 and ξ>0(≠1) and i=1,2,…,n.
Property (2)
Case  1 (0<ξ<1)(13)∑i=1naiξ≥1.From (13), we get(14)log⁡∑i=1naiξ+∑i=1naiξ-1≥0,
since0<ξ<1⇒ξ-1-ξ>0.
Therefore, we get(15)1ξ-1-ξlog⁡∑i=1naiξ+∑i=1naiξ-1≥0;that is, Hξ(A)≥0.
Therefore, we conclude thatHξ(A)≥0 for all 0<ξ<1.
Case  2 (1<ξ<∞). The proof is on the same lines as in Case 1. (Note that inequality in (14) will get reversed for 1<ξ<∞.)
Property (6). Now, we prove that Hξ(A) is a concave function of A∈Δn.
Differentiating (8) twice with respect to ai, we get(16)∂2HξA∂ai2=ξξ-1-ξξ-1∑i=1naiξ∑i=1naiξ-2∑i=1naiξ+1-ξ∑i=1naiξ-12∑i=1naiξ2.
Now, for0<ξ<1,(17)ξ-1∑i=1naiξ∑i=1naiξ-2∑i=1naiξ+1-ξ∑i=1naiξ-12<0,ξξ-1-ξ>0.
This implies thatHξ(A) is a concave function of A∈Δn.


## 2.1. Properties of Proposed Entropy

Theorem 1.
The parametric entropyHξ(A),{A=(a1,a2,…,an),0<ai≤1,∑i=1n‍ai=1} has the following properties.
(1) Symmetry. Hξ(a1,a2,…,an) is a symmetric function of (a1,a2,…,an).
(2) Nonnegative. Hξ(A)≥0 for all ξ>0(≠1).(3) Expansible
(9)
H
ξ
a
1
,
a
2
,
…
,
a
n
;
0
=
H
ξ
a
1
,
a
2
,
…
,
a
n
.(4) Decisive
(10)
H
ξ
0,1
=
H
ξ
1,0
=
0
.(5) Maximality
(11)
H
ξ
a
1
,
a
2
,
…
,
a
n
≤
H
ξ
1
n
,
1
n
,
…
,
1
n
=
1
ξ
-
1
-
ξ
log
⁡
n
1
-
ξ
+
n
1
-
ξ
-
1
.(6) Concavity. The entropy
H
ξ
(
A
)
is a concave function for
0
<
ξ
<
1
of the probability distribution
A
=
(
a
1
,
a
2
,
…
,
a
n
), ai≥0;∑i=1n‍ai=1.(7) Continuity. Hξ(a1,a2,…,an)is continuous in the regionai≥0for alli=1,2,…,nandξ>0(≠1).Proof.
The properties (1), (3), (4), and (5) follow immediately from the definition. For property (7), we know that(12)log⁡∑i=1naiξ+∑i=1naiξ-1is continuous in the region ai≥0 for all ξ>0. Thus, Hξ(A), is also continuous in the region ai≥0 and ξ>0(≠1) and i=1,2,…,n.
Property (2)
Case  1 (0<ξ<1)(13)∑i=1naiξ≥1.From (13), we get(14)log⁡∑i=1naiξ+∑i=1naiξ-1≥0,
since0<ξ<1⇒ξ-1-ξ>0.
Therefore, we get(15)1ξ-1-ξlog⁡∑i=1naiξ+∑i=1naiξ-1≥0;that is, Hξ(A)≥0.
Therefore, we conclude thatHξ(A)≥0 for all 0<ξ<1.
Case  2 (1<ξ<∞). The proof is on the same lines as in Case 1. (Note that inequality in (14) will get reversed for 1<ξ<∞.)
Property (6). Now, we prove that Hξ(A) is a concave function of A∈Δn.
Differentiating (8) twice with respect to ai, we get(16)∂2HξA∂ai2=ξξ-1-ξξ-1∑i=1naiξ∑i=1naiξ-2∑i=1naiξ+1-ξ∑i=1naiξ-12∑i=1naiξ2.
Now, for0<ξ<1,(17)ξ-1∑i=1naiξ∑i=1naiξ-2∑i=1naiξ+1-ξ∑i=1naiξ-12<0,ξξ-1-ξ>0.
This implies thatHξ(A) is a concave function of A∈Δn.


## 3. A Measure of Length

Let a finite set ofn input symbols X=(x1,x2,…,xn) be encoded using alphabet of D symbols; then it has been shown by Feinstein [8] that there is a uniquely decipherable code with lengths N1,N2,…,Nn if and only if Kraft’s inequality holds; that is,(18)∑i=1nD-Ni≤1,where D is the size of code alphabet. Furthermore, if(19)L=∑i=1nNiaiis the average code word length, then for a code satisfying (18), the inequality(20)L≥HAis also fulfilled and the equality L=H(A) holds if and only if(21)Ni=-logD⁡ai;∀i=1,2,…,n,∑i=1nD-Ni=1.If L<H(A), then by being suitably encoded into words of long sequences, the average length can be made arbitrarily close to H(A) (see Feinstein [8]). This is Shannon’s noiseless coding theorem. By considering Rényi’s entropy [2], a coding theorem analogous to the above noiseless coding theorem has been established by Campbell [9] and the authors obtained bounds for it in terms of HRe(A;ξ).Kieffer [10] defined class rules and showed HRe(A;ξ) is the best decision rule for deciding which of the two sources can be coded with expected cost of sequence of length N when N→∞, where the cost of encoding a sequence is assumed to be a function of length only. Further, in Jelinek [11], it is shown that coding with respect to Campbell’s mean length is useful in minimizing the problem of buffer overflow which occurs when the source symbol is produced at a fixed rate and the code words are stored temporarily in a finite buffer.There are many different codes whose lengths satisfy the constraints (18). To compare different codes and pick out an optimum code it is customary to examine the mean length, ∑i=1n‍Niai, and to minimize this quantity. This is a good procedure if the cost of using a sequence of length Ni is directly proportional to Ni. However, there may be occasions when the cost is more nearly an exponential function of Ni. This could be the case, for example, if the cost of encoding and decoding equipment was an important factor. Thus, in some circumstances, it might be more appropriate to choose a code which minimizes the quantity (22)C=ξlogD⁡∑i=1naiD-Niξ-1/ξ+∑i=1naiD-Niξ-1/ξξ-1;ξ>0≠1,where ξ is a parameter related to the cost. For reasons which will become evident later we prefer to minimize a monotonic function of C. Clearly, this will minimize C.In order to make the result of this paper more directly comparable with the usual coding theorem we introduce a quantity which resembles the mean length. Let a code length of orderξ be defined by(23)LξA=1ξ-1-ξξlogD⁡∑i=1naiD-Niξ-1/ξ+∑i=1naiD-Niξ-1/ξξ-1,ξ>0≠1.Remark 2.
Ifξ=1, then (23) becomes the well-known result studied by Shannon.Remark 3.
If allNi are the same, say, Ni=N, then (23) becomes(24)LξP=1ξ-1-ξN1-ξ+1-DN1-ξ;ξ>0≠1.
This is reasonable property for any measure of length to possess.In the following theorem, we give a lower bound forLξ(A) in terms of Hξ(A).Theorem 4.
IfN1,N2,…,Nn, denote the length of a uniquely decipherable code satisfying (18); then(25)LξA≥HξA.Proof.
By Ho¨lder’s inequality, (26)∑i=1nxip1/p∑i=1nyiq1/q≤∑i=1nxiyi,for all xi,yi>0,i=1,2,…,n, and 1/p+1/q=1;p<1(≠0);q<0; or q<1(≠0);p<0; equality holds if and only if, for some c, xip=cyiq. Note that the direction of Ho¨lder’s inequality is reverse of the usual one for p<1. (Beckenbach and Bellman [12], see p. 19). Making the substitutions, p=ξ-1/ξ; q=1-ξ; xi=aiξ/ξ-1D-Ni; yi=aiξ/1-ξ, in (26) and simplifying using (18). The following cases arise.
Case1 (whenξ>1)(27)∑i=1naiD-Niξ-1/ξ≤∑i=1naiξ1/ξ.From (27), we get(28)ξlogD⁡∑i=1naiD-Niξ-1/ξ+∑i=1naiD-Niξ-1/ξξ-1≤logD⁡∑i=1naiξ+∑i=1naiξ-1.Also, (29)ξ-1-ξ<0forξ>1.Thus, from (28) and (29), we may conclude that Hξ(A)≤Lξ(A).
Case2 (when0<ξ<1)(30)∑i=1naiD-Niξ-1/ξ≥∑i=1naiξ1/ξ.From (30), we get(31)ξlogD⁡∑i=1naiD-Niξ-1/ξ+∑i=1naiD-Niξ-1/ξξ-1≥logD⁡∑i=1naiξ+∑i=1naiξ-1.Also,(32)ξ-1-ξ>0for0<ξ<1.From (31) and (32), we get(33)HξA≤LξA.
Case3. It is clear that the equality in (25) is valid if Ni=-logDaiξ/∑i=1naiξ. The necessity of this condition for equality in (25) follows from the condition for equality in Ho¨lder’s inequality: in the case of reverse Ho¨lder’s equality given above, equality holds if and only if for some c, (34)xip=cyiq,i=1,2,…,n.Plugging this condition into our situation, with the xi,yi and p,q as specified, and using the fact that ∑i=1n‍ai=1, the necessity is true one. This proves the theorem.Remark 5.
Huffman [13] introduced a measure for designing a variable length source code which achieves performance close to Shannon’s entropy bound. For individual code word lengths Ni, the average length L¯=∑i=1n‍aiNi of Huffman code is always within one unit of Shannon’s measure of entropy; that is, H(A)≤L¯<H(A)+1, where H(A)=-∑i=1n‍ailog2(ai) is the Shannon’s measure of entropy. Huffman coding scheme can also be applied to code word length Lξ(A) for code word length Ni; the average length Lξ(A) of Huffman code satisfies (35)LξA≥HξA.In Table 1, we have developed the relation between the entropy Hξ(A) and average code word length Lξ(A).Table 1
ξ
>
0
(
≠
1
) (taking ξ=0.5). Relation between the entropy Hξ(A) and the average code word length Lξ(A). Ni denote the lengths of Huffman code words, η=Hξ(A)/Lξ(A) is the efficiency code, and ν=1-η is the redundancy of the code.
Relation betweenHξ(A) and Lξ(A)
Length of Huffman code words(Ni)
Huffman code words
a
i
ξ
H
ξ
(
A
)
L
ξ
(
A
)
Efficiency codeη=Hξ(A)Lξ(A)
Redundancy codeν=1-η
2
00
0.3
0.5
1.7228
1.8707
0.9209
0.0791
2
10
.25
2
11
0.2
3
011
0.1
4
0100
0.1
4
0101
.05From the Table1, we can observe that average code word length Lξ(A) exceeds the entropy Hξ(A).


## 4. Monotonic Behaviour of Mean Code Word Length

In this section, we study the monotonic behaviour of mean code word length (23) with respect to parameter ξ. Let P=(0.3,0.25,0.2,0.1,0.1,0.05) be the set of probabilities. For different values of ξ, the calculated values of Lξ(A) are displayed in Tables 2 and 3.Table 2
Computed valuesLξ(A) with respect to ξ(ξ<1).
ξ
.1
.2
.3
.4
.5
.6
.7
.8
.9
L
ξ
(
A
)
1.25
1.67
1.78
1.82
1.87
1.92
1.96
1.99
2.01Table 3
Computed valuesLξA with respect to ξ(ξ>1).
ξ
10
20
30
40
50
60
70
80
90
100
L
ξ
(
A
)
2.1618
2.2037
2.2199
2.2285
2.2337
2.2373
2.2399
2.2418
2.2433
2.2446Graphical representation of monotonic behaviour ofLξ(A) for (ξ<1) is shown in Figure 1.Figure 1
Monotonic behaviour of mean code word lengthLξ(A) (ξ<1).Graphical representation of monotonic behaviour ofLξ(A) for (ξ>1) is shown in Figure 2.Figure 2
Monotonic behaviour of mean code word lengthLξ(A) (ξ>1).Figures1 and 2 explain the monotonic behaviour of Lξ(A) for ξ<1 and ξ>1, respectively. From the figures, it is clear that Lξ(A) is monotonically increasing for ξ<1 as well as ξ>1.



---

*Source: 2683293-2017-10-15.xml*