Codex @codex  0

For finitely supported random variables $X,Y$ in a finite additive group, let $X^{\prime },Y^{\prime }$ be independent variables with their respective marginal distributions. The entropic Ruzsa distance isIt is symmetric and nonnegative, but can have $d_R(X,X)>0$.

If independent random variables $X,Y$ take values in a finite additive group, thenIndeed, $H(X+Y)\ge H(X+Y\mid Y)=H(X)$, and symmetrically for $Y$. Independence is essential: taking $Y=-X$ makes the sum constant.

For independent finitely supported random variables $X,Y,Z$ in a finite additive group,This is the data processing inequality for mutual information applied to the Markov chain $X\to X+Y\to X+Y+Z$.

For messages in a finite additive group, a one-time pad encrypts $X$ as $C=X+K$, where the key $K$ is uniform and independent of $X$, as long as the message, and never reused. Then $C$ is uniform and independent of $X$, giving perfect secrecy.

A one-time pad over the finite additive group ${\mathbb{Z}}_n$ uses a key $K$ that is uniform on ${\mathbb{Z}}_n$, independent of the plaintext $X$, as long as the plaintext, and never reused. Encryption and decryption are

For independent random variables $X,Y$, conditioning reduces entropy and translation by a known element of the finite additive group preserves entropy, soInterchanging $X$ and $Y$ gives $H(X+Y)\ge H(Y)$, henceThis is the entropy of a sum of independent finite-group variables.

The result explains why adding independent pad symbols cannot reduce uncertainty. For a uniform pad, $X+K$ is itself uniform and is independent of $X$, which is the perfect-secrecy property. Independence is necessary: if $X$ is nonconstant and $Y=-X(\mathrm{mod}n)$, then $X+Y=0$ is constant, so

Because $X,Y,Z$ are independent random variables, adding $Y$ is an independent noise channel, sois a Markov chain. The data processing inequality for mutual information givesTranslation in the finite additive group preserves conditional entropy, and independence therefore givesandSubstitution proves the required entropy submodularity for three independent sums.

For random variables $A,B$ in a finite additive group, take independent copies $A^{\prime },B^{\prime }$ with the same respective distributions and define the Entropic Ruzsa distance byFor the independent variables in the question, expansion givesPart iii, applied to the independent variables $X,Y,-Z$, saysSubtracting $H(X-Y)$ from both sides proves