In this post, we see Han’s inequality for relative entropy (KL divergence). Han’s inequality is used to derive entropy tensorization, and inequalities such as binary and Gaussain log-sobolev inequality are derived using entropy tensorization.
Han’s Inequality
Han’s Inequality states [ H(X_{1}, \ldots, X_{n}) \leq \frac{1}{n-1} \Sigma_{i=1}^{n} H(X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}), \label{eq:1}\tag{1} ] where $H(X)$ is the Shannon entoropy, $-\Sigma P \log P$, $P = p(x)$. Note that $X_{1}, \ldots, X_{n}$ do not need to be independent.
Proof
We use two basic property of the conditional entropy: [ H(X,Y) = H(X|Y) + H(Y) ] and [ H(X) \leq H(X|Y). ] From the first one, we obtain the chain rule of entropy: [ H(X_{1}, \ldots, X_{n}) = H(X_{1}) + H(X_{2}|X_{1}) + H(X_{3}| X_{1},X_{2}) + \cdots + H(X_{n}| H(X_{1}, \ldots, X_{n-1}). ]
Using the first one yields [ H(X_{1}, \ldots, X_{n}) = H(X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}) + H(X_{i} | X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}), ] and applying the second inequality to the second term in the RHS tells us that [ H(X_{i} | X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}) \leq H(X_{i} | X_{1}, \ldots, X_{i-1}). ] Summing $n$ inequalities for different $i$, we have [ n H(X_{1}, \ldots, X_{n}) \leq \Sigma_{i=1}^{n} H(X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}) + H(X_{1}) + H(X_{2}|X_{1}) + H(X_{3}| X_{1},X_{2}) + \cdots + H(X_{n}| H(X_{1}, \ldots, X_{n-1}). ] Applying the chain rule of entropy, [ n H(X_{1}, \ldots, X_{n}) \leq \Sigma_{i=1}^{n} H(X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}) + H(X_{1}, \ldots, X_{n}), ] and thus it becomes the statement, [ (n-1) H(X_{1}, \ldots, X_{n}) \leq \Sigma_{i=1}^{n} H(X_{1}, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{n}). ] The source of the inequality is the relationship $H(X) \leq H(X|Y)$, meaning that conditioning decreases entropy.
Han’s inequality for KL divergence
Symbols with superscript $i$ such as $x^{i}$ and $P^{i}$ denote $n-1$ dimensional vectors or distributions marginalized over the $i$-th element, meaning that the $i$-th element is excluded. Han’s inequality for KL divergence states [ D(Q \parallel P) \geq \frac{1}{n-1} \Sigma_{i=1}^{n} D(Q^{i} \parallel P^{i}) \label{eq:2}\tag{2} ] or equivalently, [ D(Q \parallel P) \leq \Sigma_{i=1}^{n} (D(Q \parallel P) - D(Q^{i} \parallel P^{i})). \label{eq:3}\tag{3} ]
Proof
Denoting $\Sigma_{x \in \mathcal{X}^{n}}$ by $\Sigma$ and $- \Sigma Q \log Q$ by $H_{Q}(X)$, we have [ D(Q \parallel P) = \color{green}{- \Sigma Q \log P} - H_{Q}(X) ] and [ D(Q^{i} \parallel P^{i}) = \color{blue}{- \Sigma_{x^{i} \in \mathcal{X}^{n-1}} Q^{i} \log P^{i}} - H_{Q^{i}}(X^{i}) ] where $H_{Q^{i}}(X^{i}) = - \Sigma_{x^{i} \in \mathcal{X}^{n-1}} Q^{i} \log Q^{i}$. Since Han’s inequality (Eq.$\,$($\ref{eq:1}$)) tells us [ - H_{Q}(X) \leq - \frac{1}{n-1} \Sigma_{i=1}^{n} H_{Q^{i}}(X^{i}), ] if [ \color{green}{- \Sigma Q \log P} \geq \frac{1}{n-1} \Sigma_{i=1}^{n} (\color{blue}{- \Sigma_{x^{i} \in \mathcal{X}^{n-1}} Q^{i} \log P^{i}}), ] we can say that Eq.$\,$($\ref{eq:2}$) holds. Indeed, it turns out that equality holds in the above, as we will see. Using the product property of $P$, i.e., $P = P^{i}P_{i}$ and $P=\prod_{i=1}^{n}P_{i}$, we have [ \color{green}{- \Sigma Q \log P} = - \Sigma Q(\log P^{i} + \log P_{i}) = - \frac{1}{n} \Sigma_{i=1}^{n} \Sigma Q(\log P^{i} + \log P_{i}). ] Since $ \Sigma_{i=1}^{n} \log P_{i} = \log \prod_{i=1}^{n}P_{i} = \log P, $ we have [ \color{green}{- \Sigma Q \log P} = - \frac{1}{n} \Sigma_{i=1}^{n} \Sigma Q(\log P^{i} - \frac{1}{n} \Sigma Q \log P). ] Rearranging, we have [ \color{green}{- \Sigma Q \log P} = - \frac{1}{n-1}\Sigma_{i=1}^{n} \Sigma Q \log P^{i}. ] Since $\Sigma Q = \Sigma_{x^{i} \in \mathcal{X}^{n-1}} \Sigma_{x_{i} \in \mathcal{X}^{1}} Q^{i} Q_{i}$, we have [ \color{green}{- \Sigma Q \log P} = \frac{1}{n-1} \Sigma_{i=1}^{n} (\color{blue}{- \Sigma_{x^{i} \in \mathcal{X}^{n-1}} Q^{i} \log P^{i}}). ]
We will derive eontropy tensorization using Eq.$\,$($\ref{eq:3}$) in the next post.