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!
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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$– zzzhhhJan 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$– AshokJan 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$ Nov 26, 2015 at 0:35
$\begingroup$
$\endgroup$
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!