back

Last review : 09/12/2000

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 2.5 License.

Classification of Entropies

Here we attempt to classify some typical features of some entropy functions, i.e. measures of information content of objects. The basis of such a classification are wellknown : see for instance Wehrl [WEH], Li & Vitànyi [LIV] or Uspensky & Shen [USP, USH], Preskill [PRE]. Our table needs to be completed and checked. Thanks in advance to readers to contribute.

See also our papers (pdf) :

PINSON G. : Cognitive Information Theory, Proc. 14th Intern. Congress on Cybernetics, Ass. Int. de Cybernétique, Namur, Belgique, 1995.

PINSON G. : Beyond Boole Algebra with TMS320 DSP Multiprocessing, Proc. of The First European DSP Education and Research Conference, Texas Instrument, ESIEE, Paris, 25-26 septembre 1996.

PINSON G. : Beyond the "Information Wall" with discrete Information Processing , Analyse de systèmes, vol XXV, n°4, décembre 1999.

In order to systematize the study of entropies, we introduce some general notations and features.

Notations :

• =< less than or equal to
• >= greater than or equal to
• <x,y> = pairing function
• l(x) = length of the string x
• xⁿ = n-times concatenation of x

Let two objects x and y, and their information contents I(x) and I(y). Then :

• I(x|y) = conditional entropy
• I(x,y) = I(<x,y>) = joint entropy
• I(x:y) = mutual entropy

Several kinds of functions :

• Probability functions :
  • I(.) = H(x) : classical, Shannon entropy [SHA]
  • I(.) = H_d(x) : differential entropy (Shannon entropy for continuous distributions) [SHA, KOLa]
  • I(.) = S(x) : quantum, von Neumann entropy [NEU, PRE]

   

• Algorithmic functions. Non-decipherable sets are marked C, prefixed ones are marked K. Let a code string be marked with an upper case, let its source string be marked in index.
  • classical description (in bits) of classical objects
    • I(.) = C_C(x) : plain complexity or simple entropy (source C --> code C). C_C is denoted K_A in [KOLb], BB or KS in [USP], C in [LIV]
    • I(.) = C_K(x) : uniform complexity or decision entropy (source K --> code C). C_K is called "uniform complexity" in [LOVb], "decision complexity" in [ZVL]. C_K is denoted K_A(yⁿ;n) in [LOVb], KR in [ZVL], BT or KD in [USP], C(x;l(x)) in [LIV].
    • I(.) = K_C(x) : prefix complexity or prefix entropy (source C --> code K). K_C is denoted KP in [LEV], TB or KP in [USP], K in [LIV].
    • I(.) = K_K(x) : monotonic complexity or monotonic entropy (source K --> code K). K_K is denoted TT in [USP], KM in [LIV].
  • classical description (in bits) of quantum states
    • idem, all quantities red marked : C_C(x), C_K(x), K_C(x), K_K(x). See [VIT] for K_C(x).
  • quantum description (in qubits) of quantum states
    • idem, all quantities blue marked : C_C(x), C_K(x), K_C(x), K_K(x). See [BDL] for K_C(x).
  • quantum description (in qubits) of classical objects
    • Not examined. For any finite, classical string x, C(x) =< C(x) + O(1) [BDL]. The universal quantum computer can also simulate any classical Turing machine. (the converse is an open question)

     

Features :

Features	Description	Relationships
1- Enumerability	The measure of information content of objects is recursively enumerable
2- Minimum (lower bound, incompressibility)	Entropy is equal to zero iff the message is known	I(0) = I(1) = 0
3- Maximum (upper bound)	There is an upper bound function of entropy	I(x) =< f(x)
4- Concavity	Entropy of a mean is greater than mean of elementary entropies	I(Skixi) >= SkiI(xi)
5- Monotony	Entropy of the whole is greater than entropy of the parts	I(x,y) >= I(x) I(x,y) >= I(y)
6- Additivity	Let two objects A and B : infomation on A only reduces uncertainty on B	I(x | y) =< I(x) I(y | x) =< I(y) I(x,y) = I(x) + I(y | x) I(x,y) = I(y) + I(x | y)
7- Subadditivity (triangle inequality)	Correlations between two parts of an object only reduce the whole entropy	I(x,y) =< I(x) + I(y | x) ( I(x,y) =< I(x) + I(y) )
8- Strong subadditivity	If two objects AB and BC (union ABC) have a common intersection B, then :	I(x,y,z) + I(y) =< I(x,y) + I(y,z)
9- Sign of I(x)	Entropy is positive or equal to zero	I(x) >= 0
10- Sign of I(x,y)	id.	I(x,y) >= 0
11- Sign of I(x | y)	Conditional entropy is positive or equal to zero	I(x | y) >= 0
12- Sign of I(x:y)	Mutual entropy is positive or equal to zero	I(x : y) >= 0
13- Symmetry	Information content of A about B is the same as information content of B about A	I(x : y) = I(y : x)
14- Coordinates system independence	There is no variability of entropy under transformations of coordinate systems	x --> x' : I(x') = I(x)
15- Randomness	There is always a probability measure	p(x) is defined for all x
16- Computability

Key :

Y Y Y	yes : true statement
N N N	no : false statement
	open question
*	see notes

 

General overview of entropies :

Features

H

Hd

S

CC

CK

KC

KK

CC

CK

KC

KK

CC

CK

KC

KK

1

Enumerability

Y

N

N*

Y

Y

Y*

Y

N

N

2

Minimum

Y

N

Y

Y

Y

Y

Y

Y

Y

3

Maximum

Y

N

Y

Y

Y

Y

Y

Y

Y

4

Concavity

Y

Y

Y

Y

Y

Y

Y

5

Monotony

Y

N

N

N

Y

Y

Y

6

Additivity

Y

Y

Y

N

Y

N*

7

Subadditivity

Y

Y

Y

N

N

Y

Y

N*

8

Strong subadd.

Y

Y

9

I(x) > 0

Y

N

Y

Y

Y

Y

Y

Y

Y

10

I(x,y) > 0

Y

N

Y

Y

Y

Y

Y

Y

Y

11

I(x|y) > 0

Y

N

N*

Y

Y

Y

Y

Y

Y

12

I(x:y) > 0

Y

Y

Y

Y

Y

Y

Y

Y

Y

13

Symmetry

Y

Y

Y

N

N

N*

14

Coord. indep.

Y

N

Y*

N*

N*

N*

N*

15

Randomness

Y

N*

Y

N

N

Y*

Y*

Y

Y

16

Computability

Y

Y

Y

N

N

N

N

N

N

Notes :

• H_d :
  • 15 : given a probability density law, the existence of H_d is subject to convergence of integrals  
• S :
  • 1 : the sample space is not countable (Hilbert space), but the measure space is.
  • 11 : see [CEAa,b]
  • 14 : basis change
• C_C
  • 14 : coordinates change = recursive permutation. But Y for C_C(x | l(x)) , see [LOVa]
• C_K
  • 14 : coordinates change = recursive permutation. Note the difference between C_C(x | l(x)) and C_C(x ; l(x)) = C_K(x) [LOVa,b].
• K_C
  • 1 : here, we add a special function : I(.) = k_C(x), or "explicit "prefix algorithmic complexity, which is : k_C(x) = K_C(x | <x,K_C(x)>), whose special properties are to be noticed [LIV, CHAa, b]. k_C is denoted Kc in [LIV]. But N for k_C(x) : k_C is not co-enumerable [LIV].
  • 6 : But Y for k_C(x), whose most features are similar to H (except enumerability).
  • 13 : But Y for k_C(x:y)
  • 14 : coordinates change = recursive permutation.
  • 15 : Kraft theorem.
• K_K
  • 14 : coordinates change = recursive permutation.
  • 15 : but N extending to continuous sample space, that is arbitrary difficult. On one hand, define a priori complexity K_K1 , based upon a semi-measure of probability on a continuous sample space : K_K1(x) = - log(P(x)). On an other hand, define monotonic complexity K_K0(x), based upon an algorithmic probability p(s) obtained from coding theorem : K_K0(x) = - log(p(x)). It is well known that K_K0 and K_K1 differ : K_K0(x) - K_K1(x) = Ack^-1(l(x)) + O(1) where Ack^-1 is the inverse of the Ackermann function [GAC, USP, LIV]
• C_C
  • 7 : for classical Kolmogorov complexity, C_C(xⁿ) =< C_C(x) + O(log n). Here, this relation does not hold (no-cloning theorem). So the inequality C_C (x,y) =< C_C (x) + C_C (y | x) + O(1) becomes C_C (x,y) =< C_C (x,x) + C_C (y | x) + O(1).

References :

[BDL] BERTHIAUME, A., Van DAM, W., LAPLANTE, S. : Quantum Kolmogorov Complexity, http://xxx.lanl.gov/abs/quant-ph/0005018

[CEAa] CERF, N. J., ADAMI, C. : Entropic Bell Inequalities, Phys. Rev. A, 55, p 3371-3374, 1997 http://xxx.lanl.gov/abs/quant-ph/9608047

[CEAb] CERF, N. J., ADAMI, C. : Information theory of quantum entanglement and measurement, Physica D, 120, p 62-81, 1998. (special issue for PhysComp '96) http://xxx.lanl.gov/abs/quant-ph/9605039

[CEAc] CERF, N. J., ADAMI, C. : Quantum extension of conditional probability, Phys. Rev. A., 60, p 893-897, 1999.

[CHAa] CHAITIN, G. : On the Length of Programs for Computing Finite Binary Sequences : Statistical Considerations, Journal of the ACM, 16, n°1, p 145-159, 1969.

[CHAb] CHAITIN, G. : Algorithmic Information Theory, Cambridge Univ Press, Cambridge 1987, 1990. http://www.cs.auckland.ac.nz/CDMTCS/chaitin/

[GAC] GÀCS, P. : On the relation between descriptional complexity and algorithmic probability, Theoretical Computer Science, n° 22, p 71-93, 1983.

[KOLa] KOLMOGOROV, A.N. : On the Shannon Theory of Information Transmission in the Case of Continuous Signals, IEEE Transactions on Information Theory, IT-2, p 102-108, 12/1956.

[KOLb] KOLMOGOROV, A.N. : Three Approaches to the Quantitative Definition of Information, Problems Information Transmission, 1, n°1, p 1-7, 1965.

[LEV] LEVIN, L.A. : Various measures of complexity for finite objects (axiomatic description), Soviet Math. Dokl., n°17, p 522-526, 1976 (Translated from the Russian version).

[LIV] LI M., VITÀNYI P.: An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, Berlin, 1993, 1997.

[LOVa] LOVELAND, D.W. : On minimal-program complexity measures, Conference Record of the ACM Symposium on theory of computing, p 61-65, mai 1969a.

[LOVb] LOVELAND, D.W. : A variant of the Kolmogorov concept of complexity, Information and Control, 15, p 510-526, 1969b.

[NEU] VON NEUMANN, J. : Mathematical Foundations of Quantum mechanics, Princeton University Press, Princeton, NJ, 1955.

[PRE] PRESKILL, J. : Advanced Mathematical Methods of Physics, Physics 229, UCLA, Los Angeles, 1997-98 et 1998-99.http://www.theory.caltech.edu/~preskill/ph229

[SHA] SHANNON, C.E. : A Mathematical Theory of Communication, AT&T Bell Laboratories Technical Journal, 27, p 379-423 and p 623-656, 1948.

[USP] USPENSKY V.A. : Complexity and Entropy : An Introduction to the Theory of Kolmogorov Complexity, in WATANABE O. (dir.), Kolmogorov Complexity and Computational Complexity, EATCS, Springer-Verlag, Berlin, 1992.

[USH] USPENSKY V.A., SHEN, A. : Relations Between Varieties of Kolmogorov Complexities, Mathematical Systems Theory, 29, n°3, p271-291, 1996.

[VIT] VITÀNYI P. : Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State, http://xxx.lanl.gov/abs/quant-ph/9907035

[WEH] WEHRL, A. : General properties of entropy, Review of Modern Physics, 50, n°2, p 221-260, 1978.

[ZVL] ZVONKIN, A.K., LEVIN, L.A. : The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Math. Surveys, 25, n°6, p 83-124, 1970.