0
$\begingroup$

Cross posted to theory exchange - https://cstheory.stackexchange.com/questions/45610/bounding-information-of-expression

Suppose $u_1,\ldots,u_n$ are uniformly iid in $\{0,1\}$.

Let $x_1,\ldots,x_n$ be random variables taking values in $\{0,1\}$.

I'm trying to bound the following sum which expresses each $x_i$ has to decide how to distribute his information;

$\sum_i I(u_i ;x_i) + \sum_i I(u_i ; x_{<i})$ where $x_{<i}$ denotes $x_1,\ldots,x_{i-1}$. I want to prove this is at most $(2-c)n$ for some $c>0$.

I naively thought at first it's even possibly to bound the following-

Denote by $x^i$ the vector of all $x_j$ apart from $x_i$.

$$\sum_i I(u_i;x_i) + \sum_i I(u_i;x^i)$$

Here is why naive proofs don't work for the strengthed version-

If we try to do something similiar to $\sum_i I(u_i;x_j) \leq I(u^j;x_j) \leq H(x_j)$, a naive attempt is to try and split each expression $I(u_i; x^i) = \sum_{j\neq i} I(u_i;x_j \mid x_{<j,\neq i})$.

Then rearrange this sum by fixing the index of $x; j$ and running over $u_i$, and then hope that since the $u_i$ are independent, for any event $W$ we'd have $\sum_i I(u_i; x_j \mid W)$ is small. Sadly this seems to not be true, if you take $x_j$ to be random idd of the $u_i$, and $W$ the indexes where $x_j = u_i$, then this sum is $n$! Of course here we have powerful limitations on $W$, but I can't find a way to express them correctly.

Here is even a counter-example for the strong version. Consider for $i\neq 1$, $x_i=u_i$, and $x_1 = u_2 + u_3+ \cdots +u_n$ where the sum is $\bmod 2$.

Thus we somehow need to use the $x_{<i}$ vs $x^i$.

$\endgroup$
4
  • $\begingroup$ Does $I$ denote conditional entropy? $\endgroup$ Sep 28, 2019 at 4:44
  • $\begingroup$ @Bullet51 It denotes the common information. $I(x;y)=H(x)-H(x|y)$ $\endgroup$
    – Andy
    Sep 28, 2019 at 8:30
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Sep 28, 2019 at 16:26
  • $\begingroup$ @D.W. I cheked out that thread before I cross posted, and saw people going for each direction, so I felt this is okay. Moreover, I really believe my question is very relevant on both sites, and the fact it got no attention here (in upvotes\answers\comments) caused me to do it. $\endgroup$
    – Andy
    Sep 28, 2019 at 16:39

1 Answer 1

0
$\begingroup$

While no one apparently is interested, I finally got it and will sketch it here if in the future someone will be interested in this.

So we know

$\sum_1^n I(u_i;x_i) + \sum_2^n I(u_i; x_{<i})$ is large, say at least $(2-\epsilon)n$ I will allow myself during the proof to subtract consts from the left and still say it's at least $(2-\epsilon)n$, which is okay because we can slightly change $\epsilon$.

I will use $X$ for $(x_1 ,..,x_n)$, and $x_{<i}$ for $(x_1 ,..,x_{i-1})$

Lemma 1:

Let $A,B,C$ be random variables from a common distribution space, $I(A;C) \geq I(A;B)+I(B;C) - H(B)$

The proof of this lemma is omitted.

We can use it as follows, $\sum_2^n I(x_i ;x_{<i}) \geq \sum_2^n I(u_i;x_i) + \sum_2^n I(u_i; x_{<i}) - (n-2) \geq (1-\epsilon)n$

Lemma 2:

$\sum_2^n I(x_i ;x_{<i}) \geq (1-\epsilon)n$ implies

$H(X) \leq \epsilon n$ .

Proof of lemma 2 : Indeed $\sum_2^n I(x_i ;x_{<i}) = \sum_2^n H(x_i) - \sum_2^n H(x_i |x_{<i})$

Now add and subtract $H(X_1)$ and use the chain rule to get

$I(x_i ;x_{<i}) \leq \sum_1^n H(x_i) - H(X) \leq n - H(X)$

Concluding the proof: We find $H(X) \leq \epsilon$, but we have $\sum_1^n I(x_i;u_i) \geq (1-\epsilon)n$. This is a contradiction for $\epsilon < 1/2$ because $\sum_1^n I(x_i;u_i) \leq I(X;u_i) \leq I(X;U) \leq H(X)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.