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