2
$\begingroup$

Define the entropy of a random variable $X$ by : $$H(X):=\sum_{x\in X(\Omega)}p(x)\log\left(\frac{1}{p(x)} \right), $$ with $0\log 0:=0$ and $p(x)=P(X=x)$.

A fundamental inequality satisfied by $H$ is : $$H(X)\le |range(X)|, $$ with equality if and only if $X$ is a uniform random variable.

The entropic Ruzsa triangle inequality claims that for $X,Y,Z$ independent random variables, we have : $$H(X-Z)\le H(X-Y)+H(Y-Z)-H(Y)\quad (*)$$ My question is : can we deduce from $(*)$ that If $A,B,C$ are three finite subsets of a group $G$, then : $$|B||A-C|\le |A-B||B-C|, $$ where $P+Q:=\{p+q|(p,q)\in P\times Q \}$.

I still ignore if the result is true, but here is my attempt :

Let $Y$ a uniform random variable on $B$ and $X,Z$ random variables such that $X-Z$ is a uniform random variable on $A-C$ and $X,Y,Z$ are independant (does it exist ?). Then $H(Y)=\log|B|$, and : \begin{align*} \log|A-C|+\log|B|&=H(X-Z)+H(Y)\\&\le H(X-Y)+H(Y-Z)\\&\le log|A-B|+\log|B-C| \end{align*} Hence, the question would be : can we find $X,Y,Z$ such that $X,Y,Z$ are independent and $Y$ and $X-Z$ are uniform ?

$\endgroup$
1
  • $\begingroup$ Uh, after over a year, while going through my old answers, I realized I answered this question incorrectly, since I don't think the (X,Z) pair I gave you was independent. I am truly sorry. $\endgroup$
    – E-A
    Aug 12, 2020 at 21:09

1 Answer 1

1
$\begingroup$

Yes, though you might want to do the construction backwards; namely, you can construct X, Y, and Z as follows:

First things first, pick Y independently uniform on the set B.

Now, with every element x in A-C, associate an element a and c s.t. a-c=x (does not matter how you do this process; for every x, such an a and c exist by definition). Now, pick an element uniformly in this set A-C and set X=a and Z=c. By definition, X-Z will be uniform, since the events are determined by that set.

Your proof then goes through.

Edit: Note that in this construction, $X$ and $Z$ are not necessarily independent, so the proof does not actually go through; you might need to construct your (X,Z) pair by going through a bijection like this. (https://en.wikipedia.org/wiki/Ruzsa_triangle_inequality)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .