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!


2 Answers 2


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!).

  • $\begingroup$ 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? $\endgroup$
    – zzzhhh
    Jan 27, 2013 at 7:21
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Ashok
    Jan 27, 2013 at 7:37
  • $\begingroup$ It's worth adding that convergence in $L^1$ is equivalent to pointwise convergence only for functions on finite sets. That's all the original question asked about, but the question is actually interesting more generally. $\endgroup$
    – John Baez
    Nov 26, 2015 at 0:35

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!


Your Answer

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

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