Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is well known that Entropy is additive, and that it is the only sensible choice for measuring uncertainty if we want additivity to hold, i.e.

$H(XY) = H(X)+H(Y)$

or more explicitly, if we have the constraint that

$\int_\chi\int_\chi p_1(x)p_2(x) f(p_1(x)p_2(x)) dx^2 = \int_\chi p_1(x) f(p_1(x)) dx + \int_\chi p_2(x) f(p_2(x))dx$

with $\int_\chi p_1 dx = \int_\chi p_2 dx = 1$. The only choice is $f(u) = k \log(u)$.

There is a similar problem concerning f-divergences, where we can introduce an additivity constraint:

$\int_\chi\int_\chi p_1(x)p_2(x) f\left(\frac{p_1(x)p_2(x)}{q_1(x)q_2(x)}\right) dx^2 = \int_\chi p_1(x) f\left(\frac{p_1(x)}{q_1(x)}\right) dx + \int_\chi p_2(x) f\left(\frac{p_2(x)}{q_2(x)}\right)dx$

I am pretty sure that the only valid functions $f$ are

$f(u) = (A/u+B)\log(u)$

but I do not know how to show that (or even if) this exhausts all the possibilities.

EDIT:

Corrected u to 1/u, to fit the definition of $u = p/q$ (usually it is $q/p$).

How I get to $(\frac{A}{u}+B)\log(u)$

First of all, if $f(u)$ and $g(u)$ are solutions, so is their linear combination: $a f(u) + b g(u)$. I can find two solutions that are not linearly related

1) $f(u) = k_1 \log u$

2) $f(u) = k_2 \frac{\log u}{u}$ (this effectively switches p and q)

these can be shown to work, making all the solutions of the form I proposed valid as they are linear combinations of (1) and (2). The problem I have is that I am not sure that there are not other functions that are not linearly related to either (1) or (2).

share|improve this question
    
$f$-diverence is usually defined as $D_f(p|q)=\int q(x) f\left(\frac{p(x)}{q(x)}\right)dx$ with $f$ strictly convex, $f(1)=0$ and $0\cdot f(0/0)=0$. –  Ashok Nov 12 '12 at 9:03
    
yes, but I'm not so fussed about the convexity, especially its strictness. Though if there is a proof that uses it, that is better than nothing. –  Lucas Nov 12 '12 at 15:51
    
@Ashok fixed upside down fraction for you :) well, made what I said consistent with it being upside down. –  Lucas Nov 12 '12 at 19:18
add comment

1 Answer

Edited: With due permission I am completely rewriting the proof.

Let $$D_f(P|Q)=\sum_i p_if(q_i/p_i)$$ where $f$ is a strictly convex function such that $f(1)=0$, satisfy additivity, i.e., $D_f(P_1\star P_2|Q_1\star Q_2)=D_f(P_1|Q_1)+D_f(P_2|Q_2)$ with $D_f((1,0)|(1/2,1/2))=1$, where $P\star Q$ is the product distribution, i.e., $(p_iq_j)_{i,j}$.

This proof is just a by product of Renyi's work.

Let $ P_1=P_2=(1,0),Q_1=(q_1,1-q_1), Q_2=(q_2,1-q_2)$.

Then $D_f(P_1\star P_2|Q_1\star Q_2)=f(q_1q_2)$, $D_f(P_1|Q_1)=f(q_1)$, and $D_f(P_2|Q_2)=f(q_2)$

So by additivity, $f(q_1q_2)=f(q_1)+f(q_2)$. And from $D_f((1,0)|(1/2,1/2))=1$, $f(1/2)=1$. Also from Jensen's inequality $D_f(P|Q)\ge f(1)=0$, hence $f$ is non negative.

The only $f$ satisfying the above three properties is $f(q)=-\log q$ and we are done.

share|improve this answer
    
I'm not quite sure what you have done here. I take it ${1}$ and ${1/2}$ are unnormalised probability distributions. I'll add what I have done so far to my question. –  Lucas Nov 12 '12 at 18:49
    
@Lucas: Yes I admit that the solution I have given is not very correct. I do not claim that I have given a correct solution. When someone gives a correct solution I will delete this. I am also working on this to make this very rigorous and correct. I am sure that we should proceed along this line. This was (still, it is) my opinion after I went through Renyi's paper. By this $D_f(\{1\}|\{1/2\})$, I mean $D_f((1,0)|(1/2,1/2))$. This is just a boundary condition to get the exact solution $f(p)=-\log p$ which Renyi also has in some other form. –  Ashok Nov 13 '12 at 5:08
    
I was just trying to understand it. –  Lucas Nov 13 '12 at 5:29
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.