18
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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? $\endgroup$ Sep 28, 2019 at 16:46

3 Answers 3

12
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ Thanks! This is in general shaper than the above solution. I wonder whether a completely elementary proof (such as the one above) is useful? $\endgroup$ Sep 16, 2018 at 22:37
  • 1
    $\begingroup$ (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) $\endgroup$ Sep 17, 2018 at 14:13
  • 1
    $\begingroup$ @Algernon : I think the exact bound is $H(\varepsilon) + \varepsilon \ln(N-1)$. Can your reasoning be modified to get that? $\endgroup$ Sep 17, 2018 at 14:39
  • 1
    $\begingroup$ @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)$. $\endgroup$ Sep 17, 2018 at 17:34
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – usul
    Sep 17, 2018 at 19:22
6
$\begingroup$

$\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)$.

$\endgroup$
6
$\begingroup$

$\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}$.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Algernon
    Sep 18, 2018 at 16:52
  • $\begingroup$ Also, it should be $p^∗_i\leq q_i$ for $i>k$. $\endgroup$
    – Algernon
    Sep 18, 2018 at 16:52
  • 1
    $\begingroup$ @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$. $\endgroup$ Sep 18, 2018 at 17:52
  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 20, 2018 at 0:47

Your Answer

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

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