# Bounding information of expression

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_{ where $$x_{ 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_{.

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_{ vs $$x^i$$.

• Does $I$ denote conditional entropy? – LeechLattice Sep 28 '19 at 4:44
• @Bullet51 It denotes the common information. $I(x;y)=H(x)-H(x|y)$ – Andy Sep 28 '19 at 8:30
• – D.W. Sep 28 '19 at 16:26
• @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. – Andy Sep 28 '19 at 16:39

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_{ 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_{ 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_{

Lemma 2:

$$\sum_2^n I(x_i ;x_{ implies

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

Proof of lemma 2 : Indeed $$\sum_2^n I(x_i ;x_{

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

$$I(x_i ;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)$$