Entropic Ruzsa distance ($d_R(X,Y)$)

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$.

For finitely supported random variables, the conditional entropic Ruzsa distance isThus the two conditioning values are sampled independently. If only one variable is conditioned, write $d_R(X\mid U;Y)$.

The simultaneous conditional distance samples one value of the conditioning variable for both arguments:It differs in general from $d_R(X\mid U;Y\mid U)$, which uses two independently sampled conditioning values.

If $U,V,X$ are independent random variables in ${\mathbb{F}}_2^n$, thenIndeed, conditioning reduces entropy and independence giveIn ${\mathbb{F}}_2^n$, $V=U+(U+V)$, so conditional entropy under a deterministic change of variables shows that the left-hand side is unchanged when $U$ and $V$ are exchanged. Averaging the displayed bound with its exchanged version gives the result.

The entropic Ruzsa distance satisfiesFor independent representatives this is equivalent to

For finitely supported random variables,Equivalently, independent $X,Y$ satisfy

For finitely supported random variables $A,B$ in an abelian group,To prove it, take two conditionally independent copies $(A_1,B_1)$ and $(A_2,B_2)$ of $(A,B)$ given $A+B$. Since $A_1+B_1=A_2+B_2$, entropy submodularity givesThe first two terms are at most $H(A)+H(B)$. The last joint entropy isConsequently $H(A_1-B_2)\le H(A+B)+2I(A;B)$. Subtractingfrom this bound proves the theorem.

A pair $(U,V)$ is $C$-relevant to $(X,Y)$ when

If $(U,V)$ is $C$-relevant to $(X,Y)$ and $U_1,U_2,V_1,V_2$ are mutually independent copies, then $(U_1+U_2,V_1+V_2)$ is $2C$-relevant to $(X,Y)$. The entropy submodularity for three independent sums impliesand similarly for $V$. The Entropic Ruzsa triangle inequality boundswhich proves the claim after addition.