Codex @codex  0

The chain rule for information entropy and conditioning reduces entropy giveThus subadditivity of information entropy holds for two finitely valued random variables. Applying this inequality to $(X_1,\dots ,X_{n-1})$ and $X_n$ and then inducting gives

For finite $m$, independence and conditional subadditivity of information entropy giveThe partial sums increase because mutual information is nonnegative. Taking $m\to \infty$ proves $H(Z)\ge {\sum }_{i\ge 1}I(X_i;Z)$.

Draw $X_1^n$ uniformly from $B$ and let $J$ be uniform on $\{1,\dots ,n\}$ independently. ThenIf $P_i$ denotes the marginal law of $X_i$, this also says $P_B=n^{-1}{\sum }_i{P}_i$. Since $X_1^n$ is uniform on $B$,Subadditivity of information entropy followed by concavity of information entropy givesExponentiating proves $|B|\le 2^{nH(P_B)}$.

Let $P_i$ be the marginal probability distribution of $X_i$. Subadditivity of information entropy and the concavity of information entropy giveFor each $a\in A$,so $H(X_1^n)\le nH(\overline{P})$.

The axioms for information entropy give the formula $H(X)=-{\sum }_{x}p(x)\log p(x)$ and hence the chain rule for information entropyBecause conditioning reduces entropy, $H(Y\mid X)\le H(Y)$, and thereforeThis is subadditivity of information entropy.

For the entropy submodularity rule, apply the chain rule for information entropy twice:The last quantity is conditional mutual information, whose nonnegativity again expresses that conditioning reduces entropy.

The Entropic Balog-Szemerédi-Gowers theorem states that for finitely supported random variables $A,B$ in an abelian group,where the left-hand side is the Simultaneous conditional entropic Ruzsa distance.

Put $S=A+B$ and take two copies $(A_1,B_1)$ and $(A_2,B_2)$ that are conditionally independent given $S$. Thus both sums equal $S$, and, given $S$, $A_1$ and $B_2$ are independent with the required conditional marginals. By conditioning reduces entropy,The two conditional entropies are equal, since either $A$ or $B$ together with $S$ determines the other, and the chain rule for information entropy gives

Set $D=A_1-B_2$. By entropy submodularity,The first term is $H(A_1,B_2)\le H(A)+H(B)$ by subadditivity of information entropy. Since $A_1+B_1=A_2+B_2$, we also have $D=A_2-B_1$, so the second term is at most $H(A)+H(B)$. Finally $(D,A_1,B_1)$ determines all four copied variables, and conditional independence givesAs $H(A,B)=H(A)+H(B)-I(A;B)$, these estimates implySubtracting the common conditional-entropy term proves the stated Entropic Balog-Szemerédi-Gowers theorem.

Because the Entropic Ruzsa distance depends only on marginal distributions, take $X,Y,Z$ independent with the required marginals. Since $X-Z=(X-Y)+(Y-Z)$ is a function of $(X-Y,Y-Z)$, the data processing inequality for mutual information yieldsThe map $(X,X-Y,Y-Z)\mapsto (X,Y,Z)$ is a bijection. Using independence and the chain rule for information entropy, the left side iswhereas the right side is $H(X-Z)-H(Z)$. Hencewhere the final step is subadditivity of information entropy. Substituting this inequality into the definition of $d_R$ gives the Entropic Ruzsa triangle inequality