= Chain rule for mutual information
{title2=$I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)$}
For finite <discrete random variables>, the <mutual information> supplied by two observations equals the information supplied by the first plus the additional <conditional mutual information> supplied by the second:
$$
\begin{aligned}
I(X;Y,Z)&=I(X;Y)+I(X;Z\mid Y)\\
&=I(X;Z)+I(X;Y\mid Z).
\end{aligned}
$$
The order changes the individual contributions but leaves the total unchanged.https://web.stanford.edu/class/ee376a/files/lecture_3.pdf[Stanford EE376A/STATS376A, Lecture 3, Definition 7 and equations (48)–(51)]{ref} To prove the first identity, add and subtract the intermediate <conditional entropy>:
$$
\begin{aligned}
I(X;Y,Z)&=H(X)-H(X\mid Y,Z)\\
&=\bigl[H(X)-H(X\mid Y)\bigr]
+\bigl[H(X\mid Y)-H(X\mid Y,Z)\bigr].
\end{aligned}
$$
With base-two <logarithms>, all contributions are in <bits>. Repeatedly inserting intermediate <conditional entropies> makes them cancel, as in a <telescoping series>, and gives the rule for any finite list of observations:
$$
I(X;Y_1,\ldots,Y_n)=\sum_{j=1}^{n}I(X;Y_j\mid Y_1,\ldots,Y_{j-1}),
$$
where the $j=1$ term is $I(X;Y_1)$. The same calculation with $W$ already known gives $I(X;Y,Z\mid W)=I(X;Y\mid W)+I(X;Z\mid Y,W)$.
For the fair-<bit> <exclusive or> example in <conditional mutual information>, observing $Y$ alone tells nothing about $X$, but observing $Z$ after $Y$ tells everything:
$$
I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)=0+(1-0)=1.
$$
Here $H(X\mid Y)=1$ by <independence> and $H(X\mid Y,Z)=0$ because $X=Y\oplus Z$. In the reverse order, $H(X\mid Z)=1$, so $I(X;Z)=0$ and $I(X;Y\mid Z)=1$: the two observations are individually uninformative but jointly reveal one <bit>. Simply adding their separate <mutual informations> would miss all of it.
The chain rule is useful for measuring the value of each new observation without double counting information already supplied. It also guarantees $I(X;Y,Z)\geq I(X;Y)$ by nonnegativity of <conditional mutual information>. Keeping $Y$ and adding $Z$ can help, even though discarding $Y$ and retaining only a processed $Z$ is constrained by the <data processing inequality>. Equating the two observation orders gives the precise identity
$$
I(X;Y\mid Z)-I(X;Y)=I(X;Z\mid Y)-I(X;Z),
$$
which explains why there is no general rule that conditioning decreases <mutual information>.
Back to article page