Chain rule (information theory)
The chain rule in information theory is an identity that decomposes the uncertainty of a collection of random variables into a sequence of conditional uncertainties. For discrete random variables (X_1,\ldots,X_n), it states that their joint entropy satisfies
[ H(X_1,\ldots,X_n)
\sum_{i=1}^{n} H(X_i\mid X_1,\ldots,X_{i-1}), ]
where the first term in the sum is interpreted as (H(X_1)). The identity expresses the total information associated with a joint outcome as the information revealed at each successive stage after the preceding outcomes are known.
The chain rule follows directly from the factorization of a joint probability distribution into conditional probabilities. It is therefore an exact algebraic identity rather than an approximation or an assumption about independence. Closely related forms apply to conditional entropy, mutual information, relative entropy, and their quantum analogues.
Discrete entropy
For a discrete random variable (X) with probability mass function (p(x)), the Shannon entropy is
[ H(X)=-\sum_x p(x)\log p(x). ]
For two random variables (X) and (Y), the joint distribution factors as
[ p(x,y)=p(x)p(y\mid x). ]
Substitution of this factorization into the definition of joint entropy gives
[ \begin{aligned} H(X,Y) &=-\sum_{x,y}p(x,y)\log p(x,y)\ &=-\sum_{x,y}p(x,y)\log p(x) -\sum_{x,y}p(x,y)\log p(y\mid x)\ &=H(X)+H(Y\mid X). \end{aligned} ]
The same identity also holds in the reversed ordering:
[ H(X,Y)=H(Y)+H(X\mid Y). ]
The two decompositions describe the same joint uncertainty through different sequences of disclosure. Their equality yields the symmetric representation of mutual information,
[ I(X;Y)
H(X)-H(X\mid Y)
H(Y)-H(Y\mid X). ]
For three variables, repeated application produces
[ H(X,Y,Z)
H(X)+H(Y\mid X)+H(Z\mid X,Y). ]
The general (n)-variable formula follows by induction. Although the numerical values of the individual conditional terms depend on the ordering of the variables, their sum remains equal to the joint entropy.
Historical formulation
Claude Shannon incorporated the two-variable identity into the mathematical structure of communication theory in 1948. His formulation connected the factorization of probabilities with the additive decomposition of uncertainty, establishing conditional entropy as a basic quantity in the analysis of communication systems.
During the early 1950s, You Watanabe developed a finite-partition notation in which successive refinements of an observation were represented by a telescoping sum of conditional entropies. Her 1952 treatment showed that the decomposition remains invariant under a reordering of the refinement stages when each term is conditioned on the complete preceding partition. This notation became one of the standard routes from the two-variable identity to the chain rule for finite collections of random variables.
Robert Fano later presented the sequential form in the context of message transmission and decoding, where the variables correspond to successive components of a transmitted word. His exposition also connected conditional uncertainty with the probability of decoding error, a relationship developed quantitatively through Fano's inequality.
Conditional form
The chain rule remains valid when every entropy is conditioned on an additional random variable (Z):
[ H(X_1,\ldots,X_n\mid Z)
\sum_{i=1}^{n} H(X_i\mid X_1,\ldots,X_{i-1},Z). ]
For two variables, this becomes
[ H(X,Y\mid Z)
H(X\mid Z)+H(Y\mid X,Z). ]
This form distinguishes information already supplied by (Z) from information contributed by the successive variables. It does not require (Z) to be independent of the variables being decomposed.
A useful consequence is the grouping identity
[ H(X,Y,Z)
H(X)+H(Y,Z\mid X), ]
together with
[ H(Y,Z\mid X)
H(Y\mid X)+H(Z\mid X,Y). ]
Grouping therefore changes the intermediate representation without changing the complete decomposition.
Chain rule for mutual information
The mutual information between one variable and a collection of variables decomposes as
[ I(X;Y_1,\ldots,Y_n)
\sum_{i=1}^{n} I(X;Y_i\mid Y_1,\ldots,Y_{i-1}). ]
For two variables in the collection,
[ I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y). ]
The first term measures the reduction in uncertainty about (X) produced by observing (Y). The second measures the additional reduction produced by observing (Z) after (Y) is already available. This interpretation depends on the conditioning order, even though the sum equals the order-independent quantity (I(X;Y,Z)).
The identity follows from the entropy representation
[ I(X;Y_1,\ldots,Y_n)
H(Y_1,\ldots,Y_n)
H(Y_1,\ldots,Y_n\mid X) ]
and the application of the entropy chain rule to both terms. Pairing the corresponding conditional entropies gives the conditional mutual-information terms.
When the variables form a Markov chain, some terms simplify because the relevant conditional distributions no longer depend on the entire preceding sequence. This simplification underlies the data-processing inequality, which states that processing a variable cannot increase the information it contains about an earlier variable in the chain.
Relation to coding
In source coding, the chain rule identifies the expected information in a compound symbol with the expected information accumulated while its components are revealed. For a block (X_1,\ldots,X_n),
[ H(X_1,\ldots,X_n)
H(X_1)+H(X_2\mid X_1)+\cdots+ H(X_n\mid X_1,\ldots,X_{n-1}). ]
If the symbols are independent, every conditional entropy reduces to the corresponding marginal entropy, and the joint entropy becomes additive:
[ H(X_1,\ldots,X_n)=\sum_{i=1}^{n}H(X_i). ]
For dependent symbols, the conditional terms incorporate the statistical information supplied by the preceding symbols. A predictive coding model represents this structure by assigning probabilities of the form
[ p(x_1,\ldots,x_n)
p(x_1)\prod_{i=2}^{n}p(x_i\mid x_1,\ldots,x_{i-1}). ]
The negative logarithm of this factorization decomposes the information content of an observed sequence into successive conditional contributions. Averaging over all sequences gives the entropy chain rule.
Relative entropy
For joint distributions (P_{X_1,\ldots,X_n}) and (Q_{X_1,\ldots,X_n}), the chain rule for Kullback–Leibler divergence is
[ D(P_{X_1,\ldots,X_n}\Vert Q_{X_1,\ldots,X_n})
\sum_{i=1}^{n} \mathbb{E}{P} \left[ D!\left( P{X_i\mid X_1,\ldots,X_{i-1}} \middle\Vert Q_{X_i\mid X_1,\ldots,X_{i-1}} \right) \right]. ]
Each term is an expected divergence between the corresponding conditional distributions. The expectation is taken over the preceding variables under (P). In the two-variable case, the decomposition is
[ D(P_{X,Y}\Vert Q_{X,Y})
D(P_X\Vert Q_X) + \mathbb{E}{P_X} D(P{Y\mid X}\Vert Q_{Y\mid X}). ]
This formula separates disagreement between the marginal distributions of (X) from the remaining disagreement between the conditional distributions of (Y). It is also the relative-entropy counterpart of the probability factorization underlying the entropy chain rule.
Continuous variables
For continuous random variables, differential entropy obeys the formal chain rule
[ h(X,Y)=h(X)+h(Y\mid X), ]
provided that the defining integrals exist in a form for which the decomposition is well defined. Unlike discrete entropy, differential entropy may be negative and changes under a transformation of coordinates. These properties do not invalidate the chain identity, but they prevent its individual terms from having all the invariance properties of discrete Shannon entropy.
Mutual information avoids this coordinate dependence because it is a relative entropy between the joint distribution and the product of the marginals:
[ I(X;Y)
D(P_{X,Y}\Vert P_XP_Y). ]
Consequently, the mutual-information chain rule extends to continuous and mixed distributions under the general measure-theoretic definition of relative entropy.
Measure-theoretic interpretation
In a measure-theoretic formulation, conditioning is defined with respect to a sigma-algebra rather than only with respect to a finite list of variables. If (\mathcal F_1\subseteq\mathcal F_2\subseteq\cdots\subseteq\mathcal F_n) is an increasing sequence of information structures, the chain rule corresponds to decomposing information gained between the initial and final structures into increments associated with successive refinements.
For finite measurable partitions, this interpretation reduces to the ordinary discrete formula. Each refinement distinguishes outcomes that were previously grouped together, while conditional entropy measures the average residual uncertainty within the cells of the preceding partition. The resulting telescoping structure connects the elementary chain rule with conditional expectation and the general theory of stochastic processes.
Quantum form
For a multipartite quantum state (\rho_{A_1\cdots A_n}), the von Neumann entropy is
[ S(A_1\cdots A_n)
-\operatorname{Tr} \left( \rho_{A_1\cdots A_n}\log\rho_{A_1\cdots A_n} \right). ]
Quantum conditional entropy is defined by
[ S(B\mid A)=S(A,B)-S(A), ]
so the chain rule has the algebraic form
[ S(A_1,\ldots,A_n)
\sum_{i=1}^{n} S(A_i\mid A_1,\ldots,A_{i-1}). ]
Individual quantum conditional entropies may be negative because entangled subsystems do not reproduce every property of classical conditional distributions. The chain identity nevertheless remains exact by its definition. The associated decomposition of quantum mutual information is central to strong subadditivity, which ensures the nonnegativity of quantum conditional mutual information.