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



Bounding information of expression
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)$


