Optional: Conditional Information and Data Processing

This follows Entropy and Information Measures. Read it after understanding joint entropy, conditional entropy, and mutual information; it is not a prerequisite for Chapter 2. All variables are finite and discrete, and all information is in bits.

Two apparently conflicting ideas meet here: adding a condition can strengthen dependence, while further processing cannot create information from nothing. The distinction concerns which information becomes available and which variables we compare.

Conditional mutual information: compare within contexts, then average

How much do $X$ and $Y$ share once $Z$ is known? Fix $Z=z$, compute mutual information within that conditional distribution, then average over contexts:

$$I(X;Y\mid Z)=\sum _{z}p(z)I(X;Y\mid Z=z).$$

Equivalently,

$$I(X;Y\mid Z)=H(Y\mid Z)-H(Y\mid X,Z).$$

The first term is uncertainty with the context already known; the second is what remains after also observing $X$. Conditional mutual information is nonnegative, but it has no fixed ordering relative to the unconditional $I(X;Y)$.

XOR: independent overall, perfectly dependent within groups

Take independent fair bits $X,Y$ and set $Z=X\oplus Y$. Without $Z$, all four pairs have probability $1/4$, so $I(X;Y)=0$.

Given $Z=0$, only $(0,0)$ and $(1,1)$ remain. Given $Z=1$, only $(0,1)$ and $(1,0)$ remain. Within either group, $Y$ alone still has 1-bit entropy, but $X$ determines $Y$. Each group's mutual information is 1 bit, as is their average.

This does not violate the average reduction of entropy under conditioning: $H(Y\mid Z)=H(Y)=1$, while $H(Y\mid X,Z)=0$. Extra information $Z$ changes what can be predicted jointly with $X$; it does not alter the original samples.

A shared source: context can remove additional dependence

Instead let $Z$ be fair and set $X=Y=Z$. Overall, $X$ and $Y$ are identical and $I(X;Y)=1$. Once $Z$ is given, both are determined, so $I(X;Y\mid Z)=0$.

These examples show conditional mutual information both above and below ordinary mutual information. Adding conditions does not always weaken dependence. Nor can their difference be treated as a necessarily nonnegative third overlap in a Venn diagram.

Data processing: the bound requires using only the observation

Suppose $X\to Y\to Z$ is a Markov chain:

$$p(x,y,z)=p(x,y)p(z\mid y).$$

Producing $Z$ uses only $Y$; once $Y$ is known, it receives no additional information from $X$. The data processing inequality states

$$I(X;Z)\le I(X;Y).$$

Information need not strictly decrease: an invertible transformation can preserve all of it. The result also does not mean a processed representation is less useful. Processing can make existing information easier for a restricted predictor to use; task accuracy and total mutual information are different quantities.

Choose an observed $Z$ and try to reconstruct $X$. Reversible processing leaves one candidate, with success 1; parity leaves two equiprobable candidates, with best success $1/2$; a constant leaves four, with success $1/4$. Relabeling the result as $W=3-Z$ leaves the candidate set unchanged: reading only the result cannot separate merged originals. These success rates belong to this uniform deterministic-grouping example; mutual information alone does not give such a general formula.

Here $Y=(X+1)\mathrm{mod}4$ reversibly relabels $X$ and preserves all 2 bits. Keeping only Y's parity merges the four original states into two groups, leaving 1 bit. Mapping every value to a constant leaves zero. The lost information is the distinction between states that can no longer be told apart.

The gap is exactly a conditional mutual information

Expand the same $I(X;Y,Z)$ in two orders:

$$\begin{array}{rl}I(X;Y,Z)& =I(X;Y)+I(X;Z\mid Y),\\ & =I(X;Z)+I(X;Y\mid Z).\end{array}$$

The Markov condition gives $I(X;Z\mid Y)=0$, hence

$$I(X;Y)-I(X;Z)=I(X;Y\mid Z)\ge 0.$$

The right-hand side asks: after observing processed output $Z$, how much more can the old observation $Y$ tell us about $X$? This is the information processing discarded, shown in gold. Equality holds exactly when that additional information is zero. Invertibility is sufficient for equality, but not necessary.

Why doesn't XOR violate data processing?

In the XOR example, $Z$ is computed from both $X$ and $Y$. It is not generated only from $Y$, so that Markov chain and its bound do not apply.

Likewise, if a processing step also accesses original data, relevant retrieved material, or another source of information about $X$, include those inputs in the observation before checking the Markov relation. Omitting additional inputs can make a valid computation appear to violate the inequality.

For representation learning, see the Information Bottleneck. Densities and differential entropy are introduced separately with Gaussian Channels.

References

• MIT 6.441, Chapter 2: Mutual Information.
• Cover & Thomas, Elements of Information Theory, Chapter 2.