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

For two pmf $p=\lbrace p_i\rbrace$ and $q=\lbrace q_i\rbrace$ on the same finite alphabet, we know that relateive entropy $D(p\|q)=\sum p_i\log\frac{p_i}{q_i}$ and 1-norm $\|p-q\|_1=\sum |p_i-q_i|$ are both measures of their distance. But it is unfortunate that relative entropy is not a norm. My question is: even so, do we still have equivalence between these two measure of distance? To be specific, assume $\|p-q\|_1\le C$ for some positive constant $C$, do we have $D(p\|q)\le MC$ for some positive $M$? If have, how to prove? Thanks a lot!

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

No, that is not true. Let $p^{(n)}\to q$ in $L^1$ such that $p^{(n)}$ lies in the (relative) interior of the probability simplex whereas $q$ is on the boundary (of the simplex), i.e., $q_i=0$ for some $i$. Then $D(P^{(n)}\|q)=\infty$ for every $n$.

But the other direction is true because of the Pinsker's inequality $\|p-q\|_1\le \sqrt{2D(p\|q)}$ (you may already know this fact!).

share|improve this answer
    
Yes, you are right. I should have considered the circumstances that $q_i=0$ for some symbol. But what if I put a restriction on $q$ that all $q_i$'s are positive? –  zzzhhh Jan 27 '13 at 7:21
2  
In that case ($q_i>0$ for all $i$), $D(p\|q)$ is continuous in $(p,q)$ and since convergence in $L^1$ is equivalent to pointwise convergence, we have equivalence of convergence in $L^1$ and $D(\cdot\|\cdot)$. –  Ashok Jan 27 '13 at 7:37
add comment

I have found a solution, but it seems not complete (will explain at the end)

$D(p\|q)=|D(p\|q)|=|\sum p_i\log p_i-\sum p_i\log q_i|=|\sum p_i\log p_i-\sum p_i\log q_i+\sum q_i\log q_i-\sum q_i\log q_i|$ $=|H(q)-H(p)+\sum(q_i-p_i)\log q_i|\le|H(q)-H(p)|+\sum|q_i-p_i||\log q_i|$. If we denote $M_1=\max\lbrace|\log q_i|=\log\frac{1}{q_i}\rbrace$, the last equation will be $\le M_2\|p-q\|_1+M_1\|p-q\|_1=M\|p-q\|_1$ where $M=M_1+M_2$. Here I claimed that $|H(q)-H(p)|\le M_2\|p-q\|_1$ for some positive number $M_2$ due to the Mean Value Theorem extended to multi-dimensional space and concavity of entropy wrt pmf. This seems true but I am not very sure. That's why I think the proof is incomplete. Could anyone please justify this inequality (it's better to point out such a proposition in some textbook)? Thank you!

share|improve this answer
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.