= Solution
Take <information entropy> in bits and put $H(X_\varnothing)=0$. Write $C=A\cap B$, $U=A\setminus B$, and $V=B\setminus A$. The <chain rule for information entropy> gives
$$
\begin{aligned}
H(X_A)+H(X_B)-H(X_{A\cup B})-H(X_{A\cap B})
&=H(X_U\mid X_C)+H(X_V\mid X_C)-H(X_U,X_V\mid X_C)\\
&=H(X_U\mid X_C)-H(X_U\mid X_C,X_V)\\
&=I(X_U;X_V\mid X_C)\geq0.
\end{aligned}
$$
The last line uses nonnegativity of <conditional mutual information>, equivalently the conditional version of <conditioning reduces entropy>. All <random variables> are finite-valued, so every <conditional entropy> here is finite. Therefore \b[the entropy <set function> is a <submodular set function>]:
$$
\boxed{H(X_A)+H(X_B)\geq H(X_{A\cup B})+H(X_{A\cap B}).}
$$
This is <entropy submodularity>, with equality precisely when $X_U$ and $X_V$ satisfy <conditional independence> given $X_C$.
Back to article page
