## equivalence of 1-norm and relative entropy?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

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

-
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 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 at 7:37

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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!

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9464123249053955, "perplexity_flag": "head"}