# Entropy and total variation distance

Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ and $Q$) be at most $\epsilon$. What is a standard, easily provable bound on the difference between the entropies of $X$ and $Y$?

(It is easy to see that such a bound must depend not only on $\epsilon$ but also on $N$.)

• Nobody has mentioned yet that the inequality $|H(P)−H(Q)| \le H(\varepsilon)+\varepsilon \log⁡(N−1)$ proven in the answers below is precisely the standard Fannes–Audenaert inequality, specialized to the case of diagonal density matrices? Sep 28, 2019 at 16:46

Claim. If $\|P-Q\|\leq\varepsilon\leq\frac{1}{2}$, then $|H(P)-H(Q)| \leq H(\varepsilon) + \varepsilon\log N$.

Proof. Let $\varepsilon':=\|P-Q\|$. Let $(X,Y)$ be an optimal coupling of $P$ and $Q$, so that \begin{align} \mathbb{P}(X\neq Y) = \|P-Q\| \;. \end{align} Using a standard construction, we can assume that $X$ and $Y$ have the particular form \begin{align} X &:= \begin{cases} Z & \text{if $B=0$,} \\ \tilde{X} & \text{if $B=1$,} \end{cases} & Y &:= \begin{cases} Z & \text{if $B=0$,} \\ \tilde{Y} & \text{if $B=1$,} \end{cases} \end{align} where $B$, $Z$ and $(\tilde{X},\tilde{Y})$ are independent and $B\sim\text{Bern}(\varepsilon')$.

Note that \begin{align} H(X|B) \leq H(X) \leq H(B) + H(X|B) \;. \end{align} For $H(X|B)$ we can write \begin{align} H(X|B) &= \varepsilon' H(X|B=1) + (1-\varepsilon') H(X|B=0) \\ &= \varepsilon' H(\tilde{X}) + (1-\varepsilon') H(Z) \;. \end{align} Thus, \begin{align} \varepsilon' H(\tilde{X}) + (1-\varepsilon') H(Z) &\leq H(X) \leq H(B) + \varepsilon' H(\tilde{X}) + (1-\varepsilon') H(Z) \;, \tag{$\clubsuit$} \end{align} and similarly, \begin{align} \varepsilon' H(\tilde{Y}) + (1-\varepsilon') H(Z) &\leq H(Y) \leq H(B) + \varepsilon' H(\tilde{Y}) + (1-\varepsilon') H(Z) \;. \tag{$\spadesuit$} \end{align}

Combining ($\clubsuit$) and ($\spadesuit$) we get \begin{align} |H(X)-H(Y)| &\leq H(B) + \varepsilon' |H(\tilde{X}) - H(\tilde{Y})| \\ &\leq H(\varepsilon') + \varepsilon' \log N \\ &\leq H(\varepsilon) + \varepsilon \log N \;, \end{align} as claimed. QED

Edit [2018--09--17] (following Iosif Pinelis's comment).
Refining the above reasoning a little bit, we can get the better bound \begin{align} |H(P)-H(Q)|\leq H(\varepsilon) + \varepsilon\log(N-1) \;. \end{align}

Indeed, let $\Sigma$ denote the $N$-element set that is the support of $P$ and $Q$. As before, let $\varepsilon':=\|P-Q\|$, and let us discard the trivial cases $\varepsilon'\in\{0,1\}$, so that $0<\varepsilon'<1$.

Recalling from the construction of an optimal coupling, define for $a\in\Sigma$, \begin{align} R_0(a) &:= P(a)\land Q(a) & P_0(a) &:= P(a)-R_0(a) \\ & & Q_0(a) &:= Q(a)-R_0(a) \;. \end{align} Observe that $R_0$, $P_0$ and $Q_0$ are non-negative functions and \begin{align} \sum_{a\in\Sigma}R_0(a)=1-\varepsilon' \qquad\text{and}\qquad \sum_{a\in\Sigma}P_0(a)=\sum_{a\in\Sigma}Q_0(a)=\varepsilon' \;. \end{align} Thus, $\tilde{R}:=R_0/(1-\varepsilon')$, $\tilde{P}:=P_0/\varepsilon'$ and $\tilde{Q}:=Q_0/\varepsilon'$ are probability distributions on $\Sigma$ satisfying \begin{align} P(a) &= (1-\varepsilon')\tilde{R}(a) + \varepsilon'\tilde{P} \\ Q(a) &= (1-\varepsilon')\tilde{R}(a) + \varepsilon'\tilde{Q} \;. \end{align} If we now choose $Z\sim\tilde{R}$, $\tilde{X}\sim\tilde{P}$, $\tilde{Y}\sim\tilde{Q}$ and $B\sim\text{Bern}(\varepsilon')$ independently, we have a coupling as promised above.

Back to the inequality, observe that since both $P$ and $Q$ are non-negative and normalized, there necessarily exist $a,b\in\Sigma$ such that $P_0(a)=0$ and $Q_0(b)=0$. This means that each of $\tilde{P}$ and $\tilde{Q}$ is in fact supported on a strict subset of $\Sigma$. Hence, \begin{align} |H(\tilde{X})-H(\tilde{Y})| &\leq \max\{H(\tilde{P}),H(\tilde{Q})\} \leq \log(N-1) \end{align} and the (updated) claim follows as before.

Note.
As the example H A Helfgott gave in the comments ($\require{enclose}\enclose{horizontalstrike}{N=0}$, $\require{enclose}\enclose{horizontalstrike}{X\sim\text{Bern}(\varepsilon)}$ and $\require{enclose}\enclose{horizontalstrike}{Y\sim\text{Bern}(0)}$) shows, this refined bound is sharp at least when $\require{enclose}\enclose{horizontalstrike}{N=2}$.
Iosif Pinelis gave the following example in his comment below which shows that the refined bound is sharp for every $N$ and $\varepsilon$:

Let $\Sigma:=\{1,2,\ldots,N\}$ and \begin{align} P(a) &:= \begin{cases} 1 & \text{if $a=1$,}\\ 0 & \text{otherwise,} \end{cases} & Q(a) &:= \begin{cases} 1-\varepsilon & \text{if $a=1$,}\\ \varepsilon/(N-1) & \text{otherwise.} \end{cases} \end{align} Then, $\|P-Q\|=\varepsilon$ and $|H(P)-H(Q)|=H(Q)=H(\varepsilon)+\varepsilon\log(N-1)$.

• Thanks! This is in general shaper than the above solution. I wonder whether a completely elementary proof (such as the one above) is useful? Sep 16, 2018 at 22:37
• (Well, for $N\leq 2$, $|H(X)-H(Y)|\leq \epsilon \log(N/\epsilon)$would be false , as the example of $X\sim \text{Bern}(\epsilon)$, $Y\sim \text{Bern}(0)$ shows. Still\dots) Sep 17, 2018 at 14:13
• @Algernon : I think the exact bound is $H(\varepsilon) + \varepsilon \ln(N-1)$. Can your reasoning be modified to get that? Sep 17, 2018 at 14:39
• @Algernon : The bound $H(\varepsilon) + \varepsilon\ln(N-1)$ is actually optimal for all $N$ and $\varepsilon$: Take $p_1=1$, $q_1=1-\varepsilon$, $q_2=\cdots=q_N=\varepsilon/(N-1)$. Sep 17, 2018 at 17:34
• Very nice answer, and I agree with Iosif that the example is tight for all $N$. I calculate $H(Y) = H(B) + H(Y|B)$, where $B$ is the indicator for $Y=1$. We have $H(B) = H(\epsilon)$ and $H(Y|B) = (1-\epsilon)(0) + \epsilon H(U)$ where $U$ is uniform on $\{2,\dots,N\}$. This gives $H(Y) = H(\epsilon) + \epsilon \log(N-1)$.
– usul
Sep 17, 2018 at 19:22

$\newcommand{\de}{\delta} \newcommand{\ep}{\epsilon}$

Note that $p\ln p-p$ is decreasing in $p\in[0,1]$, so that $p\ln p-p\le q\ln q-q$ and hence $p\ln p-q\ln q\le p-q=|p-q|$ if $0\le q\le p\le1$.

Next, take any real $c\ge1$. Note that $g(p):=p\ln p+cp$ (with $g(0):=0$) is convex in $p\in[0,1]$. So, assuming $0\le p\le q\le1$ and $q\ge e^{-c}$, we have $g(p)\le g(0)\vee g(q)=0\vee g(q)=g(q)$ and hence $p\ln p-q\ln q\le c(q-p)=c|p-q|$. Thus, \begin{equation} p\ln p-q\ln q\le c|p-q| \end{equation} whenever $0\le p,q\le1$ and $q\ge e^{-c}$.

Also, $-q\ln q$ is increasing in $q\in[0,e^{-1}]$ and hence in $q\in[0,e^{-c}]$, so that $-q\ln q\le ce^{-c}$ for $q\in[0,e^{-c}]$. Also, $p\ln p\le0$ if $0\le p\le1$.

Therefore, the difference between the entropies of $Q=(q_i)_{i=1}^N$ and $P=(p_i)_{i=1}^N$ is \begin{equation} \sum_1^N p_i\ln p_i-\sum_1^N q_i\ln q_i=S_1+S_2+S_3, \end{equation} where \begin{align*} S_1 &:=\sum_{i\colon q_i\ge e^{-c}} (p_i\ln p_i-q_i\ln q_i)\le \sum_{i\colon q_i\ge e^{-c}}c|p_i-q_i| \le c\de \quad\text{if}\ \de\ge\|P-Q\|_1, \\ S_2 &:= \sum_{i\colon q_i< e^{-c}}p_i\ln p_i\le0, \\ S_3 &:= \sum_{i\colon q_i< e^{-c}}(-q_i\ln q_i)\le\sum_{i\colon q_i< e^{-c}}ce^{-c}\le Nce^{-c}. \end{align*} So, taking now $c=\ln\frac N\de$ and assuming $N\ge e\de$, we see that \begin{equation} \sum_1^N p_i\ln p_i-\sum_1^N q_i\ln q_i\le c\de+Nce^{-c} =2\de\ln\frac N\de. \end{equation} Taking here $\de=2\ep$ and noting that $N\ge1$, we conclude that \begin{equation} \sum_1^N p_i\ln p_i-\sum_1^N q_i\ln q_i\le 4\ep\ln\frac{N}{2\ep} \end{equation} if $\ep\le1/(2e)$.

$\newcommand{\De}{\Delta} \newcommand{\ep}{\epsilon} \newcommand{\R}{\mathbb{R}}$

Here is yet another answer providing the exact bound. This answer is perhaps a bit more elementary than the excellent answer given by user Algernon. Another advantage of this approach is that it produces the exact bound for any convex function $f$ in place of the function $p\mapsto p\ln p$.

To preserve the history of the question, I have also retained my previous answer, which used different (if somewhat similar) ideas and provided a suboptimal bound.

Take indeed any convex function $f\colon[0,1]\to\R$ and consider the difference \begin{equation} \De:=\sum_1^N f(p_i)-\sum_1^N f(q_i) \end{equation} between the "generalized" entropies of $Q=(q_i)_{i=1}^N$ and $P=(p_i)_{i=1}^N$. We want to find the exact upper bound on $\De$ subject to the given conditions on $(P,Q)$. In what follows, $(P,Q)$ is a point satisfying these conditions. Without loss of generality (wlog), for some $k\in\{1,\dots,N\}$ we have $p_i\ge q_i$ for $i\le k$, $p_i\le q_i$ for $i\ge k+1$, and $q_1\ge\cdots\ge q_k$, so that \begin{equation} \ep=\sum_1^k(p_i-q_i)=\sum_{k+1}^N(q_i-p_i)>0. \end{equation}

Let $p_i^*:=q_i$ for $i=2,\dots,k$ and $p_1^*:=q_1+\ep[=\sum_1^k p_i-\sum_2^k q_i\le1]$. Then the vector $(p_1^*,\dots,p_k^*)$ majorizes (in the Schur sense) the vector $(p_1,\dots,p_k)$ and still satisfies the condition $p_i^*\ge q_i$ for $i\le k$. Also, since $f$ is convex, $\sum_1^k f(p_i)$ is Schur convex in $(p_1,\dots,p_k)$. So, wlog $(p_1,\dots,p_k)=(p_1^*,\dots,p_k^*)$.

In particular, $p_1>q_1$ and $q_m\ge p_m$ for all $m=2,\dots,N$. Moreover, wlog $p_m=0$ for any $m=2,\dots,N$. Indeed, take any $m=2,\dots,N$ with $p_m>0$ and replace $p_1,q_1,p_m,q_m$ respectively by $p_1+t,q_1+t,p_m-t,q_m-t$, where $t:=p_m\in(0,1-p_1]$; then all the conditions on $P,Q$ will still hold. After this replacement, $\De$ will change by the sum of the nonnegative expressions $[f(p_1+t)-f(q_1+t)]-[f(p_1)-f(q_1)]$ and $[f(q_m)-f(p_m)]-[f(q_m-t)-f(p_m-t)]$; this nonnegativity follows by the convexity of $f$. Making such replacements for each $m=2,\dots,N$ with $p_m>0$, we will change $\De$ by a nonnegative amount, and will also get $p_m=0$ for all $m=2,\dots,N$ indeed.

Thus, wlog \begin{gather} p_1=1=q_1+\ep,\quad p_i=0\ \forall i=2,\dots,N,\quad \sum_2^N q_i=\ep. \end{gather} Since $\sum_2^N f(q_i)$ is Schur convex in the $q_i$'s, wlog \begin{align} \De&=f(1)-f(q_1)+\sum_2^N f(0)-\sum_2^N f(q_i) \\ &\le f(1)-f(1-\ep)+(N-1)f(0)-(N-1)f(\tfrac\ep{N-1})=:\De_{f;\ep,N}. \end{align} The bound $\De_{f;\ep,N}$ on $\De$ is obviously exact, since it is attained when $p_1=1=q_1+\ep$ and $q_2=\cdots=q_N=\tfrac\ep{N-1}$.

In the particular case when $f(p)=p\ln p$ (with $f(0)=0$), the exact bound $\De_{f;\ep,N}$ becomes $H(\ep)+\ep\ln(N-1)$, where $H(\ep):=\ep\ln\frac1\ep+(1-\ep)\ln\frac1{1-\ep}$.

• Nice approach! I only didn't understand when you say $(p^*_{k+1},\ldots,p^*_N)$ majorizes the vector $(p_{k+1},\ldots,p_N)$. Both $p$ and $p^*$ are probability vectors and you have already shown that $(p^*_1,\ldots,p^*_k)$ majorizes $(p_1,\ldots,p_k)$. However, I agree that the entropy of $p^*$ must be no larger than the entropy of $p$, which seems to be what you are using. Sep 18, 2018 at 16:52
• Also, it should be $p^∗_i\leq q_i$ for $i>k$. Sep 18, 2018 at 16:52
• @Algernon : Thank you for your comments. I have now specified that the majorization is understood here in the Schur sense and given a corresponding reference. Also, I have now simplified the proof and no longer use $p_i^*$ for $i>k$. Sep 18, 2018 at 17:52
• It is now shown that the same approach produces the exact bound for any convex function $f$ in place of the function $p\mapsto p\ln p$. Sep 20, 2018 at 0:47