5
$\begingroup$

Let $H$ be a function of finite sequences of probabilities (non-negative numbers summing up to 1) into real numbers, such that:

  • $H$ is continuous,
  • $H$ is symmetric w.r.t. the order of its arguments,
  • $H$ is additive, i.e. $H(P \otimes Q) = H(P) + H(Q)$,

where $P = \{p_i\}_i$, $Q = \{q_i\}_i$, $P \otimes Q = \{p_i q_j\}_{i,j}$. (A physicist would call the last property extensive.)

One class of examples is Rényi entropy $H_q$, along with linear combinations of $H_q$ (for different $q$s), what was already pointed out in the original paper:

Which other, if any, functions $H$ fulfill the above postulates?

$\endgroup$
4
  • $\begingroup$ if you insist on additivity, the Rényi entropy gives the most general form. $\endgroup$ Mar 1, 2014 at 15:35
  • $\begingroup$ @CarloBeenakker Is it proven somewhere? (Or obvious for some reason?) I looked at $e^H$ and it seamed to me that is need to have form $\prod_q \sum_i p_i^q$ (to make it symmetric and additive), but I don't know how to actually prove it. $\endgroup$ Mar 1, 2014 at 15:48
  • 1
    $\begingroup$ What do you mean by continuous? There are several possible topologies on the space of finitely supported probability measures. $\endgroup$ Mar 1, 2014 at 15:58
  • $\begingroup$ @NateEldredge "I can negotiate" (in Rényi's paper it was continuous as a function of $H(p,1-p)$). Here $L^1$ seems to be the most natural norm (unless you suggest sth different). $\endgroup$ Mar 1, 2014 at 16:05

2 Answers 2

4
$\begingroup$

Rényi conjectured that his generalized entropy is the most general form that satisfies addititivity. This was proven by Daróczy,

Z. Daróczy, Über die gemeinsame Charakterisierung der zu den nicht vollständigen Verteilungen gehörigen Entropien von Shannon und von Rényi. (1963)

J. Aczel and Z. Daróczy, Charakterisierung der Entropien positiver Ordnung und der Shannonschen Entropie. (1963)

Z. Daróczy, Über Mittelwerte und Entropien vollständiger Wahrscheinlichkeitsverteilungen. (1964)

$\endgroup$
3
  • 1
    $\begingroup$ Thanks! Unfortunately the papers are paywalled for me. I can see preview for one, and it seems it uses one more axiom (related to $H(P\cup Q)$ and a generalized mean with function $g$; alike in the Rényi's paper). $\endgroup$ Mar 1, 2014 at 16:21
  • $\begingroup$ @PiotrMigdal: hi again! I just came across the exact same problem. The papers that Carlo linked to indeed seem to make additional assumptions about the particular form of $H$. I can email the papers to you if you like. Have you found a satisfactory answer in the meantime? BTW one simple observation is that all linear combinations of Rényi entropies satisfy your conditions as well, so Carlo (resp Rényi) must have had something else in mind. $\endgroup$ Oct 27, 2014 at 23:09
  • $\begingroup$ @TobiasFritz Hi! I would be grateful for sending them to me. I wasn't working on it in the meantime. $\endgroup$ Oct 28, 2014 at 7:40
2
$\begingroup$

Here is a partial answer. As has been hinted at in the comments, one should expect that the space of functions under question strongly depends on the continuity assumption made. For example, the Rényi max-entropy $H_0$ and more generally all $H_\alpha$ with $\alpha\leq 0$ are not continuous as one of the probabilities tends to $0$. There are also subtler continuity properties that one could impose to exclude certain functions. For example, $H_\alpha$ is continuous with respect to the statistical distance if and only if $\alpha>1$. Or: the change in $H_\alpha(p)$ upon adding a fixed $\varepsilon$-tail to $p$ can be bounded in a $p$-independent manner if and only if $\alpha\leq 1$.

What the OP might have had in mind is the following simple continuity requirement: a function of probabilities $F$ is declared continuous if and only if it its restriction to every probability simplex $$ \Delta_n = \{(p_1,\ldots,p_n)\:|\: p_i\geq 0,\: \sum_i p_i=1\} $$ is continuous. Moreover, it is also natural to assume that $F$ is invariant under adding outcomes of zero probability, $$ F(p_1,\ldots,p_n)=F(p_1,\ldots,p_n,0). $$ With this additional assumption, $F$ becomes a function on the inductive limit of the simplices $\Delta_1\subset\Delta_2\subset\Delta_3\ldots$. Let me capture these requirements in a definition:

Definition: $F$ is an information measure if it is additive, continuous on every $\Delta_n$, and invariant under permutations and adding zero probabilities.

All the Rényi entropies $H_\alpha$ with $\alpha>0$ are information measures, and so is every linear combination. More generally, every integral \begin{equation} F(p) = \int_0^\infty H_\alpha(p) \mu(d\alpha) \end{equation} for a regular measure $\mu$ on $(0,\infty]$ is an information measure. But there are others as well: instead of integrating the Rényi entropies over $\alpha$, we can also differentiate and obtain new information measures.

To see what this gives, it makes things easier to get rid of the conventional $(1-\alpha)^{-1}$ factor in the definition of the Rényi entropies, and instead consider the family of information measures $$ Z_\alpha(p):= \log \sum_i p_i^\alpha = (1-\alpha) H_\alpha(p). $$ This is a bit easier to differentiate, and we obtain another family of information measures, $$ \frac{d Z_\alpha(p)}{d\alpha} = \frac{\sum_i p_i^\alpha \log p_i}{\sum_i p_i^\alpha}. $$ This recovers the Shannon entropy at $\alpha=1$. It can alternatively be written as $$ \frac{d Z_\alpha(p)}{d\alpha} = Z_\alpha(p) + \sum_i \frac{p_i^\alpha}{\sum_j p_j^\alpha} \log\left(\frac{p_i^\alpha}{\sum_j p_j^\alpha}\right), $$ where the second term is exactly the Shannon entropy of the 'quenched' distribution $p^\alpha$ defined in terms of taking all probabilities to the $\alpha$-th power and renormalizing. $$ \frac{d Z_\alpha(p)}{d\alpha} = Z_\alpha(p) - S(p^\alpha). $$ (More generally, plugging $p^\alpha$ into any information measure $p\mapsto F(p)$ results again in an information measure, but this doesn't give anything new for the non-Shannon Rényi entropies.)

By differentiating again and putting $\alpha=1$ for simplicity, one obtains another interesting information measure: $$ \frac{d^2 Z_\alpha(p)}{d\alpha^2}\bigg|_{\alpha=1}=\sum_i p_i \left(\log p_i\right)^2 - \left(\sum_i p_i \log p_i\right)^2. $$ This is related to the OP's question on higher moments of the surprisal: the second and higher derivatives of $Z_\alpha(p)$ result in second and higher powers of $-\log p_i$.

TL;DR. So then, what about the original question?

While not every information measure that I am aware of is an integral of Rényi entropies with respect to a regular measure, it is still conceivable that every information measure is the integral of Rényi entropies with respect to a certain kind of distribution $T$, $$ F(p) = \int_0^\infty H_\alpha(p) T(\alpha) d\alpha. $$ Taking $T$ to be a suitable linear combination of derivatives of the Dirac $\delta$ recovers the above examples. Someone who knows more about distributions may be able to say what kind of distribution $T$ needs to be for the integral to exist, and then we can formulate a precise classification conjecture in terms of distributions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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