Appendix E — Information theory
In this appendix, we briefly cover the necessary information theory concepts that are useful in understanding the derivation of the minimax lower bound in Section 5.6.
In the following, we assume that the underlying random variables are discrete and leave it to the reader to fill in the necessary details for the continuous extension.
E.1 Entropy
Definition E.1.
Consider a discrete r.v. \(X\) taking values in the set \(\X\) with p.m.f. \(p\). Then, the entropy \(H(X)\) is defined as
\[ H(X) = - \sum_{x\in \X} p(x) \log p(x), \]
where the \(\log\) is to base \(2\).
It is easy to see that \(H(X) \ge 0\) for any \(X\), since \(\log p(x) \le 0\) for \(p(x) \in [0,1]\). As an example, the entropy of a Bernoulli r.v. \(X\) with parameter \(p\) is \(H(X) = - p \log p - (1-p) \log (1-p)\). Plotting \(H(X)\) as a function of \(p\), it is easy to infer that \(H(X)\) is maximized at \(p=1/2\), \(H(X)=0\) at \(p=0\) and \(p=1\).
The notion of entropy has roots in information theory, as it gives the expected number of bits necessary to encode a random signal (\(=\) a random variable). We illustrate this interpretation through the following r.v.:
\[ \begin{align*} X = \begin{cases} a & \text{ w.p. } 1/2,\\ b & \text{ w.p. } 1/4,\\ c & \text{ w.p. } 1/8,\\ d & \text{ w.p. } 1/8. \end{cases} \end{align*} \]
If one were to design a sequence of binary questions to infer the value of the r.v. \(X\) and ask the minimum number of questions in expectation, then it would serve him/her to start with “Is \(X=a\)?” rather than start with “Is \(X=d\)?”. Now using the pmf of \(X\) given above, the expected number of questions asked is \(1\times \frac{1}{2} + 2\times \frac{1}{4} + 3 \times \frac{1}{8} + 3 \times \frac{1}{8}=\frac{7}{4}\). It is not a coincidence that \(H(X)\) turns out to be \(\frac{7}{4}\) for this r.v.
An equivalent interpretation is the following: Suppose that the value \(a\) is represented by the code “\(1\)”, \(b\) by “\(01\)”, \(c\) by “\(001\)” and \(d\) by “\(000\)”. Assuming that the values \(a,b,c,d\) occur with probabilities given above, the average code length turns out to be the same as \(H(X)\).
Definition E.2.
The joint entropy \(H(X,Y)\) of r.v. pair \((X,Y)\) with joint pmf \(p(x,y)\) is defined as
\[ H(X,Y) = - \sum_{x } \sum_{y} p(x,y) \log p(x,y). \]
Definition E.3.
The conditional entropy \(H(Y\mid X)\), assuming the r.v. pair \((X,Y)\) has joint pmf \(p(x,y)\), is defined as
\[ \begin{align*} H(Y\mid X) &= \sum_{x } p(x) H(Y\mid X=x) \\ &= -\sum_{x } p(x) \sum_{y} p(y\mid x) \log p(y\mid x) \\ &= -\sum_{x } \sum_{y} p(x,y) \log p(y\mid x). \end{align*} \]
Theorem E.1.
\(H(X,Y) = H(X) + H(Y\mid X)\).
Proof.
Follows by using the definition of \(H(X,Y)\) followed by a separation of terms using \(p(x,y)=p(x)p(y\mid x)\) to obtain \(H(X)\) and \(H(Y\mid X)\).
\(\square\)
We are now ready to define the concept of KL-divergence, also known as relative entropy, between two probability distributions.
E.2 KL-divergence
Definition E.4.
The KL-divergence \(\dkl{p}{q}\) between two pmfs \(p\) and \(q\) is defined as
\[ \dkl{p}{q} = \sum_x p(x) \log\left( \frac{p(x)}{q(x)} \right), \]
where, \(0 \log \frac{0}{q} = 0\) and \(p\log \frac{p}{0} = \infty\).
Definition E.5.
The total variation distance \(\tvnorm{P- Q}\) between two distributions \(P\) and \(Q\) on a common sigma field \(\X\) is defined as
\[ \tvnorm{P-Q}=\sup_{A\subset\X} \left|P(A)-Q(A)\right|. \]
We shall prove later that \(\tvnorm{P- Q}^2 \le \frac{1}{2}\dkl{P}{Q}\) – a fact well-known as Pinsker’s inequality.
Example E.1.
Let \(p\) and \(q\) be the probability mass functions (PMFs) of Bernoulli r.v.s with parameters \(\alpha\) and \(\beta\), respectively. Then,
\[ \dkl{p}{q} = \alpha \log \frac{\alpha}{\beta} + (1-\alpha) \log \frac{1-\alpha}{1-\beta}. \]
Plugging in values \(1/4\) and \(1/2\) for \(\alpha\) and \(\beta\), it is easy to see that \(\dkl{p}{q}\) is not equal to \(\dkl{q}{p}\).
KL-divergence is not a metric because it is not symmetric, as shown in the above example. Moreover, KL-divergence does not satisfy the triangle inequality. However, KL-divergence is non-negative and zero if and only if the probability distributions are the same – a claim made precise below.
Lemma E.2.
The KL-divergence \(\dkl{p}{q}\) between two PMFs \(p\) and \(q\) is non-negative and equals zero if and only if \(p(x)=q(x), \forall x\).
Proof.
Let \(A=\{x \mid p(x)>0\}\) be the support of \(p\). Then, using Jensen’s inequality for the concave \(\log\) function, we have
\[ \begin{align*} -\dkl{p}{q} & = -\sum_{x\in A} p(x) \log\left( \frac{p(x)}{q(x)}\right) \\ &= \sum_{x\in A} p(x) \log\left( \frac{q(x)}{p(x)}\right) \\ & \le \log\left(\sum_{x\in A} p(x) \frac{q(x)}{p(x)}\right) \\ & = \log \left(\sum_{x\in A} q(x)\right) \le \log \left(\sum_{x} q(x)\right) \\ &= \log 1 = 0, \end{align*} \]
which proves the first part of the claim. For the second part, observe that \(\log\) is stricly concave and hence, equality holds in Jensen’s if and only if \(\frac{p(x)}{q(x)}=1, \forall x\).
\(\square\)
Definition E.6.
The conditional KL-divergence between two PMFs \(p\) and \(q\) is defined as
\[ \dkl{p(y\mid x)}{q(y\mid x))} = \sum_x p(x) \sum_y p(y\mid x) \log \frac{p(y\mid x)}{q(y\mid x)}. \]
Lemma E.3.
(Chain rule)
\[ \dkl{p(x,y)}{q(x,y)} = \dkl{p(x)}{q(x)} + \dkl{p(y\mid x)}{q(y\mid x))}. \]
In addition, if \(x\) and \(y\) are independent, then
\[ \dkl{p(x,y)}{q(x,y)} = \dkl{p(x)}{q(x)} + \dkl{p(y)}{q(y)}. \]
Proof.
Notice that
\[ \begin{align*} &\dkl{p(x,y)}{q(x,y)} \\ & = \sum_x \sum_y p(x,y) \log \frac{p(x,y)}{q(x,y)} \\ &= \sum_x \sum_y p(x,y) \log \frac{p( x)}{q( x)} + \sum_x \sum_y p(x,y) \log \frac{p(y\mid x)}{q(y\mid x)} \\ &= \dkl{p(x)}{q(x)} + \dkl{p(y\mid x)}{q(y\mid x))}. \end{align*} \]
This proves the first claim in the lemma statement. The second claim can be easily inferred from the first.
\(\square\)
E.3 Pinsker’s inequality
Lemma E.4.
(Pinsker’s inequality) Given two PMFs \(p\) and \(q\), for any event \(A\), we have
\[ 2(p(A) - q(A))^2 \le \dkl{p}{q}. \]
Proof.
Fix an event \(A\). Then, we have
\[ \begin{align*} \sum_{x \in A} p(x) \log \frac{p( x)}{q( x)} \ge p(A) \log \frac{p( A)}{q( A)}. \tag{E.1} \end{align*} \]
The proof of the claim above is as follows: Letting \(p_A(x) = \frac{p(x)}{p(A)}\) and \(q_A(x) = \frac{q(x)}{q(A)}\), we have
\[ \begin{align*} \sum_{x\in A} p(x) \log \frac{p( x)}{q( x)} &= p(A) \sum_{x\in A} p_A(x) \log \frac{p(A) p_A( x)}{q(A)q_A( x)} \\ &= p(A) \log \frac{p(A)}{q(A)} \sum_{x\in A} p_A(x) + p(A) \sum_{x\in A} p_A(x) \log \frac{ p_A( x)}{q_A( x)} \\ & \ge p(A) \log \frac{p(A)}{q(A)}, \end{align*} \]
where the last inequality follows from the fact that
\(\sum_x p_A(x) \log \frac{ p_A( x)}{q_A( x)} = \dkl{p_A}{q_A} \ge 0\) and \(\sum_x p_A(x) =1\).
Letting \(\alpha=p(A)\) and \(\beta=q(A)\) and using (E.1), we have
\[ \begin{align*} \dkl{p}{q} &\ge \alpha \log \frac{\alpha}{\beta} + (1-\alpha) \log \frac{1-\alpha}{1-\beta} \\ & = \int_\alpha^\beta \left( \frac{-\alpha}{x} + \frac{1-\alpha}{1-x} \right) dx \\ & = \int_\alpha^\beta \left( \frac{x-\alpha}{x(1-x)} \right) dx \ge \int_\alpha^\beta \frac{x-\alpha}{1/4} dx \tag{ since $x(1-x) \le 1/4$} \\ &= 2(\alpha-\beta)^2. \end{align*} \]
Hence proved.
\(\square\)
The following result is now immediate from the bound in the lemma above.
Corollary E.5.
Given two PMFs \(p\) and \(q\), we have
\[ \tvnorm{p- q}^2 \le \frac{1}{2}\dkl{p}{q}. \]
Lemma E.6.
(Pinsker’s inequality: a variant)
Given two PMFs \(p\) and \(q\), for any event \(A\), we have
\[ P(A) + Q(A^c) \ge \frac1{2}\exp(-\dkl{p}{q}), \]
where \(P(A)\) (resp. \(Q(A^c)\)) is shorthand for \(\sum_{x\in A} p(x)\) (resp. \(\sum_{x\in A^c} q(x)\)).
Proof.
Notice that
\[ \begin{align*} \sum_x \min(p(x),q(x)) &= \sum_{x\in A} \min(p(x),q(x)) + \sum_{x\in A^c} \min(p(x),q(x)) \\ & \le \sum_{x\in A} p(x) + \sum_{x\in A^c} q(x) = P(A) + Q(A^c). \end{align*} \]
So, it is enough to prove a lower bound on \(\sum_{x\in A} \min(p(x),q(x))\). We claim that
\[ \sum_{x} \min(p(x),q(x)) \ge \frac{1}{2} \left( \sum_{x} \sqrt{p(x)q(x)}\right)^2. \]
The inequality above holds because
\[ \begin{align*} \left( \sum_{x} \sqrt{p(x)q(x)}\right)^2 &= \left( \sum_{x} \sqrt{\min(p(x),q(x)) \max(p(x),q(x))}\right)^2 \\ & \le \left( \sum_{x} \min(p(x),q(x)) \right) \left(\sum_{x} \max(p(x),q(x)) \right) \\ & \le 2 \sum_{x} \min(p(x),q(x)), \end{align*} \]
where the last inequality holds because
\[ \begin{align*} \sum_{x} \max(p(x),q(x)) &= \sum_{x} (p(x) + q(x) - \min(p(x),q(x))) \\ &\le 2 - \sum_{x} \min(p(x),q(x)) \le 2. \end{align*} \]
Now, we have
\[ \begin{align*} \left( \sum_{x} \sqrt{p(x)q(x)}\right)^2 &= \exp\left(2\log\left( \sum_{x} \sqrt{p(x)q(x)}\right)\right) \\ &= \exp\left(2\log\left( \sum_{x} p(x) \sqrt{\frac{q(x)}{p(x)}}\right)\right) \\ & \ge \exp\left(2\left( \sum_{x} p(x) \log\sqrt{\frac{q(x)}{p(x)}}\right)\right) \tag{Jensen's inequality} \\ & = \exp\left( \sum_{x} p(x) \log\frac{q(x)}{p(x)}\right) \\ & = \exp\left( - \dkl{p}{q}\right). \end{align*} \]
\(\square\)
E.4 Bibliographic remarks
The information theory background covered here is based on the classic text book by (Cover and Thomas 2012).
E.5 Exercises
Exercise 1.
For some \(0<\Delta<1/2\), let \(p\), \(q\) and \(r\) correspond to the PMFs of Bernoulli r.v.s with parameters \(\frac{1}{2}\), \(\frac{1+\Delta}{2}\) and \(\frac{1-\Delta}{2}\), respectively. Then,
\[ \begin{align*} \dkl{p}{q} \le \Delta^2, \dkl{q}{p} \le 2\Delta^2, \dkl{p}{r} \le \Delta^2 \textrm { and } \dkl{r}{q} \le 4\Delta^2. \end{align*} \]
Exercise 2.
For distributions \(P\) and \(Q\) of a continuous random variable, the KL-divergence is defined to be the integral:
\[ \dkl{P}{Q} = \int p(x) \log\left( \frac{p(x)}{q(x)} \right) dx, \]
where \(p\) and \(q\) denote the densities of \(P\) and \(Q\), respectively.
Answer the following:
Prove Pinsker’s inequality, i.e., given distributions \(P,Q\) of continuous r.v.s,
\[ \tvnorm{P- Q}^2 \le \frac{1}{2}\dkl{P}{Q}. \]
Suppose that \(P\) and \(Q\) correspond to univariate Gaussian distributions with means \(\mu_1, \mu_2\), and variances \(\sigma_1^2, \sigma_2^2\), respectively. Show that
\[ \dkl{P}{Q} = \frac{1}{2} \left( \log \frac{\sigma_2^2}{\sigma_1^2} + \frac{\sigma_1^2}{\sigma_2^2} - 1 \right) + \frac{(\mu_1-\mu_2)^2}{2\sigma_2^2}. \]
Suppose that \(P\) and \(Q\) correspond to bivariate Gaussian distributions with zero mean and covariance matrices \(\left[ \begin{array}{c c } 1 & \rho \\ \rho & 1 \end{array} \! \right]\) and \(\left[ \begin{array}{c c } 1 & \rho^2 \\ \rho^2 & 1 \end{array} \! \right]\), where \(\rho \in (0,1)\). Calculate \(\dkl{P}{Q}\), upper bound it using the simplest possible function of \(\rho\).
Exercise 3.
Suppose there are two coins. The first is a fair coin, while the second one is biased (i.e., it falls heads with probability \(\frac{3}{4}\)). Suppose \(n\) sample outcomes \(X_1,\ldots,X_n\) are generated using one of the two coins and an algorithm, say \(\A\), uses these samples to identify the source coin. Let \(\hat I_n\) denote the index that the algorithm \(\A\) returns as its estimate of the source coin. Let \(P_v\) (resp. \(P_{v'}\)) denote the law of the observed samples \((X_1,\ldots,X_n)\), when the underlying source is the fair (resp. biased) coin.
If \(n< 4\log 2\), then show that no algorithm can ensure
\[ \max(P_v(\hat I_n = 2),P_{v'}(\hat I_n = 1)) \le 0.22. \]
Hint: Use Pinsker’s inequality.