15
$\begingroup$

Let $\mu$ be a probability measure on a set of $n$ elements and let $p_i$ be the measure of the $i$-th element. Its Shannon entropy is defined by

$$ E(\mu)=-\sum_{i=1}^np_i\log(p_i) $$

with the usual convention that $0\cdot(-\infty)=0$.

The following are two fundamental properties:

Property 1: $E(\mu)$ takes its minimum on the Dirac measures.

Property 2: $E(\mu)$ takes its maximum on the uniform probability measure.

Now, for some application, I am really interested in a possible generalization when $\mu$ is a finitely additive probability measure on the natural numbers.

Question: Is it possible to define a notion of entropy of a finitely additive probability measure on the natural numbers in such a way that it verifies the following properties:

  • it takes its minimum on the Dirac measures
  • it takes its maximum on the finitely additive translation invariant probability measures

Any reference? Idea?

Thanks in advance,

Valerio

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Using the letter "E" may be confusing since it's used for expected value. It's somewhat conventional to use "H", and I suppose it could be amusing to pretend that the Greek word starts with eta, but unfortunately that's not true. (But maybe that's why "H" is used?) $\endgroup$
    – Michael Hardy
    Commented Jul 21, 2011 at 21:08

3 Answers 3

Reset to default
6
$\begingroup$

I don't know if someone has already defined such entropy and I am not an expert on these things, but (depending what is wanted) I would start with something like $$E(\mu)=\sup\left\{-\sum_{i=1}^n\mu(A_i)\log(\mu(A_i)) : \mathbb{N} = \bigcup_{i=1}^n A_i, A_i \text{ pairwise disjoint}\right\}.$$

Some properties this entropy would have are

  1. It equals the Shannon entropy for measures that are concentrated on finitely many numbers.
  2. It gives value $+\infty$ for finitely additive translation invariant probability measures.

A related definition for arbitrary measure spaces $(X,m)$ is the relative Shannon entropy (a.k.a. the Kullback–Leibler divergence) $$E(\mu) = \int_X \frac{d\mu}{dm} \log\left(\frac{d\mu}{dm}\right)dm,$$ where $\frac{d\mu}{dm}$ is the Radon-Nikodym derivative of $\mu$ w.r.t. $m$. One could fix a finitely additive measure $m$ and try to work with that.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ Tapio, why do you want the entropy of your finitely additive translation-invariant measure to be finite? In the limit as $n\to\infty$ the Shannon entropy of the uniform measure on $[n]$ converges to infinity. Wouldn't you therefore expect that such a `uniform' measure on $\mathbb N$ should have infinite entropy? $\endgroup$
    – Mark Peletier
    Commented Jul 22, 2011 at 12:30
  • 1
    $\begingroup$ Probably we like that the entropy of a translation invariant measure is infinite. But maybe we would like also some intermediate measure, namely finitely (non countably) additive probability measures having finite entropy. I am thinking of the following interpretation: the entropy of $\mu$ is a measure of the quantity of the lack of information carried by the measure $\mu$: certainty corresponds to Dirac measures and no information corresponds to translation invariant measures. Now take the following measure $\mu$: $\mu$ is defined on $2\mathbb N$ to be any translation invariant measure $\endgroup$
    – Valerio Capraro
    Commented Jul 22, 2011 at 13:58
  • 1
    $\begingroup$ This is why my suggestion is that it could be better to separate the atomic part from the non atomic. So maybe the entropy is not a number, but a pair of number, the first one describing the atomic part and the second one describing the non atomic. Maybe the second can take just the values $0$ or $\infty$. In this way we would have three cases: $(x,0)$: for a finitely supported measure; $(x,\infty)$, for a measure having atomic part and non-atomic part ($x=0$ corresponds to having just one atom); $(-\infty,\infty)$ (by convention) for measure having no atomic part. $\endgroup$
    – Valerio Capraro
    Commented Jul 22, 2011 at 18:21
  • 1
    $\begingroup$ Things get complicated fast. For example, I could take the average of a dirac measure and a translation invariant measure. You'll end up keeping track of the entropy of every restriction $\mu|S$ of your measure $\mu$ to subsets $S$ of $\mathbb{B}$. $\endgroup$
    – David Milovich
    Commented Jul 23, 2011 at 0:27
  • 1
    $\begingroup$ Er, $\mathbb{N}$, not $\mathbb{B}$. $\endgroup$
    – David Milovich
    Commented Jul 23, 2011 at 1:03
2
$\begingroup$

In the vein of what Tapio suggested, one place to look for some ideas is the Lott-Villani paper on optimal transport where they discuss various entropies (section 3.2 on p 923 on the version I linked)

In particular they discuss the Shannon entropy as discussed by Tapio. A side note - it is also called the Boltzmann H-functional. (See also definition 3.28 for another possible direction to try)

To answer your comment to Tapio's post:

If you use $m$ as the counting measure, then I believe that Tapio's definition agrees with the "limiting version" of what you wrote in some sense. If $m$ is the counting measure, then any probability measure $\mu$ is absolutely continuous wrt $m$. Then, its clear that $d\mu/dm (x) = \mu(x)$, so plugging this into the Shannon entropy formula from Tapio's post, we get $$ \tag{E} Ent(\mu|m) = \sum_{x\in \mathbb{N}} \mu(x) \log\mu(x) $$

I believe that the signt discrepancy is because Tapio's formula is usually called the Boltzman H-functional, whereas Shannon entropy is usually referred to as the negative of what Tapio wrote there but I am not exactly sure on these semantics.

Suppose that $\mu(n) = \frac {1}{2^n}$. Then $$ Ent(\mu|m) = \sum_{n=1}^\infty \frac{n \log 2}{2^n} \in (0,\infty) $$

Perhaps I have misunderstood your question/comment however? The entropy defined above does satisfy the first condition you give, i.e. that it takes its minimum on dirac measures (by jensen's inequality $Ent \geq 0$ and clearly $Ent(\delta_x|m) = 0$. I am a bit confused as to what a finitely additive translation probability measure on the natural numbers is? Does "finitely additive" mean a weaker condition than just "probability measure"? Can you give an example of one?

Improve this answer
$\endgroup$
2
  • $\begingroup$ "Finitely additive" means you weaken countable additivity to finite additivity. Here's the standard translation-invariant example: If S(x)=x+1, then the uniform probability measure U_n on [n]={1,...,n} is S-invariant up to an error of 1/n. Taking an ultralimit of the measures (u_n: n=1,2,3,...), we get an S-invariant, finitely additive probability measure on the naturals: for every set A, mu(A) is the ultralimit of $u_n(A\cap[n])$ with respect to some fixed non-principal ultrafilter. If you don't like ultralimits, you can use the Hahn-Banach Theorem (but that's equally non-constructive). $\endgroup$
    – David Milovich
    Commented Jul 22, 2011 at 5:38
  • $\begingroup$ Thanks for the comment, Otis, but, as David said above here finite additivity means just that you require that a measure is additive on disjoint union of finite sets. It seems to me that your construction holds just for countably additive measures (giving result zero most of the most interesting finitely additive cases). $\endgroup$
    – Valerio Capraro
    Commented Jul 22, 2011 at 19:00
2
$\begingroup$

I just wanted to say that topologically, your hand is forced: Tapio's supremum definition is the way to go.

Give the space $X$ of all maps from $\mathcal{P}(\mathbb{N})$ to $[0,1]$ the topology of pointwise convergence. The space $FAM$ of finitely additive probability measures on $\mathbb{N}$ is then a closed subspace of $X$. Let $FSM$ be the set of finitely supported measures in $FAM$. Let $FSA$ be the set of finite subalgebras of of $\mathcal{P}(\mathbb{N})$. Given $G\in FSA$ and $\mu\in FAM$, it is easy to (definably) choose $\mu_G\in FSM$ that agrees with $\mu$ on $G$: $\mu_G(\{\min(A)\})=\mu(A)$ for every atom $A\in G$. In $FAM$, each point $\mu$ has a neighborhood base consisting of sets of the form $U(\mu,G,\varepsilon)$, which I use to denote the set of $\nu\in FAM$ that agree with $\mu$ on $G$ up to error $\varepsilon$. Therefore, $FSM$ is dense in $FAM$.

The Shannon entropy Ent is continuous on $FSM$, and Ent extends uniquely to a continuous map from $FAM$ to $[0,\infty]$ given by Tapio's $Ent(\mu)=\sup\{Ent(\mu_G): G\in FSA\}$ (using my notation). To see this, the important step is to check that $Ent(\mu_G)\leq Ent(\mu_H)$ if $G\subseteq H$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So you are saying the Tapio's formula is the unique extension making sense?! $\endgroup$
    – Valerio Capraro
    Commented Jul 22, 2011 at 14:08
  • $\begingroup$ Well, if you're willing to let the codomain be something other than $[0,\infty]$, then others are out there. For example, you could use nonstandard analysis. All the standard subsets of $\mathbb{N}$ can fit inside some hyperfinite algebra $K$, so you can just set $Ent(\mu)=Ent(\mu_K)$ to get a hyperreal-valued entropy. If $Ent(\mu)$ is bounded by a standard real, then $Ent(\mu)$ is infinitely close to the "supremum entropy" of $\mu$. If $\mu$ is finitely supported, then $Ent(\mu)$ is the usual Shannon entropy. $\endgroup$
    – David Milovich
    Commented Jul 22, 2011 at 18:04
  • $\begingroup$ I am looking for something able to capture as much as possible the quantity of information brought by the measure (see the comments below Tapio's answer). $\endgroup$
    – Valerio Capraro
    Commented Jul 22, 2011 at 18:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .