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 1norm $\pq\_1=\sum p_iq_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 $\pq\_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
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 $\pq\_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
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_ip_i)\log q_i\leH(q)H(p)+\sumq_ip_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\pq\_1+M_1\pq\_1=M\pq\_1$ where $M=M_1+M_2$. Here I claimed that $H(q)H(p)\le M_2\pq\_1$ for some positive number $M_2$ due to the Mean Value Theorem extended to multidimensional 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!