Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What are the axioms that a good notion of entropy must satisfy? Please note that I am not asking for the definitions of various types of entropy such as topological entropy or measure-theoretic entropy or etc. My question is, if $X$ is a 'space', in a broad sense (topological, measure, algebraic, etc.) and $\varphi:X\rightarrow X$ is a self-map, and if we want to define a good notion of entropy to measure the complexity of $\varphi$, what axioms should this notion satisfy?

EDIT: Perhaps a more reasonable question: For a system given by iterating a function, what should a good notion of entropy measure (with no or minimum reference to the type of space)?

share|improve this question
1  
pardon my ignorance, but haven't such questions long been considered in information theory? –  Suvrit Jun 30 '11 at 22:10
    
@Survit: I don't know. If you know of any reference, please post. –  Mahdi Majidi-Zolbanin Jun 30 '11 at 22:14
    
Check out the `characterization' section here, Mahdi: en.wikipedia.org/wiki/Entropy_(information_theory) –  Jon Bannon Jun 30 '11 at 22:19
    
@Jon: It seems that these axioms make sense in the context of a probability space, and they measure "uncertainty associated with a random variable" and would not make sense if $X$ is just a topological space. Yet, entropy can be defined in a topological dynamical system (see en.wikipedia.org/wiki/Topological_entropy). I was wondering if it is possible to characterize the notion of entropy with minimum reference to the type of the space involved? –  Mahdi Majidi-Zolbanin Jun 30 '11 at 22:34
    
how about "Kolmogorov complexity"? maybe the ideas behind it provide the necessary basis for the axiomatization that you are seeking? –  Suvrit Jul 1 '11 at 4:16
show 2 more comments

6 Answers

up vote 16 down vote accepted

This isn't a full axiomatisation, partly because it's a little vague, and partly because I only am really familiar with the notion of entropy in two contexts: topological space and measure space. Nevertheless, there's a commonality to the procedure in both those cases.

  1. Start with a space $X$ and a map $f\colon X\to X$.
  2. Coarse-grain your space to a certain scale, so that orbit segments that are very close together are not distinguishable.
  3. Count how many mutually distinguishable orbit segments of length $n$ it takes to be "significant"; call this number $a_n$.
  4. Find the growth rate $\lim_{n\to\infty} \frac 1n \log a_n$; this is the entropy at the particular coarse scale you chose.
  5. Let the coarse scale become finer and finer and take a limit to get the entropy.

Depending on how you make that procedure precise, you get various notions. For example, if $X$ is a topological space, "certain scale" means "code by an open cover", and "significant" means "covers X", then you get topological entropy. On the other hand, if $X$ is a measure space, "certain scale" means "code by a partition", and "significant" means "covers a set of uniformly positive measure", then you get measure-theoretic entropy.

I'd be interested in knowing if there are other notions of entropy for other sorts of spaces that have analogous definitions. Or for that matter, if there are other notions that don't have analogous definitions.

share|improve this answer
3  
I almost e-mailed you about this question, but then decided to trust that you'd find it on your own. :) –  Paul Siegel Jul 1 '11 at 13:11
2  
@Vaughn: There are also various notions of algebraic entropy that are defined for endomorphisms of algebraic structures such as groups or projective varieties. Some of these notions don't appear to have been defined according to the above axioms. For rational self-maps of projective varieties, for example, entropy is defined using its degree (see springerlink.com/content/nak975w6tk8lfjnl) and it seems that degree plays the role of the sequence $a_n$. –  Mahdi Majidi-Zolbanin Jul 1 '11 at 16:20
add comment

In addition to the wikipedia page, you can take a look at this fairly recent paper "A Characterization of Entropy in Terms of Information Loss" by John C. Baez, Tobias Fritz, Tom Leinster http://arxiv.org/abs/1106.1791

share|improve this answer
    
@Anthony: This is interesting, but still makes sense only in the context of a probability space. Please see my comment to Jon. –  Mahdi Majidi-Zolbanin Jun 30 '11 at 22:40
add comment

From a more physical perspective, there's the work of Lieb and Yngvason:

http://arxiv.org/abs/math-ph/0204007

share|improve this answer
add comment

The topological and measure-theoretic entropies of $(X,\varphi)$ formalize average entropy per iteration of partial observations ($\equiv$ the coarse-graining that Vaughn mentions above). (I am not familiar with other notions of entropy for dynamical systems.) In either case, one first needs an elementary notion of entropy for the class of allowed observations that is independent of $\varphi$.

Chris Hillman has some (sadly) unpublished notes in which he gives an elegant axiomatization of entropy that encompasses many more examples such as the Hausdorff dimension or what he calls the Galois entropy.

share|improve this answer
add comment

I want just to mention a framework in which we (Dikran Dikranjan, Anna Giordano Bruno and me) are going to redefine many notions of entropy.

The idea of prof. Dikranjan was to define the category of normed semigroups. Indeed, a normed semigroup is just a semigroup $S$ with a norm $$v:S\to \mathbb R_{\geq 0}$$ such that $v(xy)\leq v(x)+v(y)$. The morphisms in the category are just semigroup homomorphisms such that the norm of the image is $\leq$ than the norm of the original point.

In this category one can define a notion of entropy of an endomorphism $\phi:(S,v)\to (S,v)$. In fact one takes $$h(\phi)=\sup \left( \lim_{n\to\infty}\frac{v(x\phi(x)\dots\phi^{n-1}(x))}{n}: x\in S\right ) .$$ It is interesting to notice that already at this level, the above entropy function satisfies some good properties. Furthermore, it turns out that many of the usual notions of entropy (topological, algebraic, mesure-theoretic entropy, ...) for endomorphisms or automorphisms can be defined using a suitable functor from the category in which they are defined to the category of normed semigroups (the semigroup can be the set of subset with intersection (or sum in groups), the set of open covers with intersection, ... the norm can be $\log$ of the cardinality, measure, minimal cardinality of a subcover ...).

Let me conclude remarking that if you are looking for lists of axioms for entropy functions you should look to the following papers:

L. N. Stojanov, Uniqueness of topological entropy for endomorphisms on compact groups, Boll. Un. Mat. Ital. B 7 (1987) no. 3, 829–847. (axiomatic char. of topological entropy on compact groups)

D. Dikranjan and A. Giordano Bruno, Entropy on abelian groups, preprint; arXiv:1007.0533. (axiomatic char. of algebraic entropy on discrete groups)

L. Salce, P. Vamos, S. Virili, Length functions, multiplicities and algebraic entropy, Forum Math. (2011) (axiomatic char. of a notion of algebraic entropy on modules)

The above characterizations are discussed in the following survey,

D. Dikranjan, M. Sanchis, S. Virili, New and old facts about entropy in uniform spaces and topological groups, Topology appl. (2012) 1916-1942

share|improve this answer
add comment

This paper of Gromov seems to aim to answer exactly your question: to provide a category theoretic axiomatization of entropy that is as general as possible. He defines entropy as a functor from the category of things you actually observe, to the category of sets. His formalism probably applies to your case if you define your 'state detectors' P (on page 2) in an appropriate manner...

share|improve this answer
    
Dear o a: Thank you for sharing this paper. I had not seen this paper, I will look at it. –  Mahdi Majidi-Zolbanin Jul 19 '12 at 16:52
    
@Mahdi: be aware that the paper gets updated from time to time so you need to check ihes.fr/~gromov/topics/recent.html to find the most recent version (10 july as of now)...also, at the very end itmentions a result of Esnault-Viehweg ("Such ”rank inequalities” are reminiscent of inequalities for spaces of sections and (cohomologies in general) of positive vector bundles such e.g. as in the Khovanski-Teissier theorem and in the Esnault-Viehweg proof of the sharpened Dyson-Roth lemma, but a direct link is yet to be found") which appears close to your interests. –  o a Jul 20 '12 at 16:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.