johnswentworth comments on johnswentworth’s Shortform

[johnswentworth]

Proof

Specifically, we’ll show that there exists an information throughput maximizing distribution which satisfies the undirected graph. We will not show that all optimal distributions satisfy the undirected graph, because that’s false in some trivial cases—e.g. if all the $Y$’s are completely independent of $X$, then all distributions are optimal. We will also not show that all optimal distributions factor over the undirected graph, which is importantly different because of the $P\left[X\right]>0$ caveat in the Hammersley-Clifford theorem.

First, we’ll prove the (already known) fact that an independent distribution $P\left[X\right]=P\left[X_1\right]P\left[X_2\right]$ is optimal for a pair of independent channels $(X_1\to Y_1,X_2\to Y_2)$; we’ll prove it in a way which will play well with the proof of our more general theorem. Using standard information identities plus the factorization structure $Y_1-X_1-X_2-Y_2$ (that’s a Markov chain, not subtraction), we get

$MI(X;Y)=MI(X;Y_1)+MI(X;Y_2|Y_1)$

$=MI(X;Y_1)+\left(MI\right(X;Y_2)-MI(Y_2;Y_1)+MI(Y_2;Y_1|X\left)\right)$

$=MI(X_1;Y_1)+MI(X_2;Y_2)-MI(Y_2;Y_1)$

Now, suppose you hand me some supposedly-optimal distribution $P\left[X\right]$. From $P$, I construct a new distribution $Q\left[X\right]:=P\left[X_1\right]P\left[X_2\right]$. Note that $MI(X_1;Y_1)$ and $MI(X_2;Y_2)$ are both the same under $Q$ as under $P$, while $MI(Y_2;Y_1)$ is zero under $Q$. So, because $MI(X;Y)=MI(X_1;Y_1)+MI(X_2;Y_2)-MI(Y_2;Y_1)$, the $MI(X;Y)$ must be at least as large under $Q$ as under $P$. In short: given any distribution, I can construct another distribution with as least as high information throughput, under which $X_1$ and $X_2$ are independent.

Now let’s tackle our more general theorem, reusing some of the machinery above.

I’ll split $Y$ into $Y_1$ and $Y_2$, and split $X$ into $X_{1-2}$ (parents of $Y_1$ but not $Y_2$), $X_{2-1}$ (parents of $Y_2$ but not $Y_1$), and $X_{1\cap 2}$ (parents of both). Then

$MI(X;Y)=MI(X_{1\cap 2};Y)+MI(X_{1-2},X_{2-1};Y|X_{1\cap 2})$

In analogy to the case above, we consider distribution $P\left[X\right]$, and construct a new distribution $Q\left[X\right]:=P\left[X_{1\cap 2}\right]P\left[X_{1-2}|X_{1\cap 2}\right]P\left[X_{2-1}|X_{1\cap 2}\right]$. Compared to $P$, $Q$ has the same value of $MI(X_{1\cap 2};Y)$, and by exactly the same argument as the independent case $MI(X_{1-2},X_{2-1};Y|X_{1\cap 2})$ cannot be any higher under $Q$; we just repeat the same argument with everything conditional on $X_{1\cap 2}$ throughout. So, given any distribution, I can construct another distribution with at least as high information throughput, under which $X_{1-2}$ and $X_{2-1}$ are independent given $X_{1\cap 2}$.

Since this works for any Markov blanket $X_{1\cap 2}$, there exists an information thoughput maximizing distribution which satisfies the desired undirected graph.