Chain rule

Recap: chain rule for probabilities

Let $\mathbf{X}=(X_1,\dots ,X_n)$ be a discrete random vector (or a sequence of discrete random variables). The Chain Rule for probabilities provides a method to factorize the joint probability mass function $p(X_1,\dots ,X_n)$ into a product of conditional probabilities.

By recursively applying the definition of conditional probability, $p(A,B)=p(A|B)p(B)$, the following expansion is obtained:

$$\begin{array}{rl}p(X_1,\dots ,X_n)& =p(X_n\mid X_{n-1},\dots ,X_1)\cdot p(X_{n-1},\dots ,X_1)\\ & =p(X_n\mid X_{n-1},\dots ,X_1)\cdot p(X_{n-1}\mid X_{n-2},\dots ,X_1)\cdot p(X_{n-2},\dots ,X_1)\\ & =\dots \\ & =p(X_n\mid X_{n-1},\dots ,X_1)\cdot p(X_{n-1}\mid X_{n-2},\dots ,X_1)\cdots p(X_2\mid X_1)\cdot p(X_1)\end{array}$$

This recursive decomposition can be expressed concisely using product notation:

$$p(X_1,\dots ,X_n)=\prod _{i=1}^{n}p(X_i\mid X_{i-1},\dots ,X_1)$$

Notation Convention

In the product formula above there is an abuse of notation, since the term for $i=1$ is $p(x_1\mid x_0,\dots )$. By convention, the conditioning set for the first element is considered empty, reducing the term simply to the marginal probability $p(x_1)$.

---

Chain Rule for Entropy

The Chain Rule for Entropy allows for the decomposition of the joint entropy of a random vector into a sum of conditional entropies.

Let $\mathbf{X}=(X_1,\dots ,X_n)$ be a discrete random vector. The Chain Rule for Entropy states that:

$$H(X_1,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1)$$

Proof

The derivation follows from applying the chain rule for probabilities within the definition of joint entropy and from the application of logarithmic and expectation properties:

$$\begin{array}{rlrl}H(X_1,\dots ,X_n)& =\mathbb{E}\left[{\log }_2\frac{1}{p(X_1,\dots ,X_n)}\right]& & (\text{Definition of joint entropy})\\ & =\mathbb{E}\left[{\log }_2\frac{1}{{\prod }_{i=1}^{n}p(X_i\mid X_{i-1},\dots ,X_1)}\right]& & (\text{Substitution of the Probability Chain Rule})\\ & =\mathbb{E}\left[\sum _{i=1}^n{\log }_2\frac{1}{p(X_i\mid X_{i-1},\dots ,X_1)}\right]& & (\text{Logarithm of a product identity})\\ & =\sum _{i=1}^n\underset{H(X_i\mid X_{i-1},\dots ,X_1)}{\underbrace{\mathbb{E}\left[{\log }_2\frac{1}{p(X_i\mid X_{i-1},\dots ,X_1)}\right]}}& & (\text{Linearity of expectation})\\ & =\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1)& & (\text{Definition of conditional entropy})\end{array}$$

Notation Convention

In the summation formula above, there is a slight abuse of notation for the case $i=1$, which would strictly be expressed as $H(X_1\mid X_0,\dots ,X_1)$. By convention, the conditioning set for the first element is considered empty, reducing the term to the marginal entropy $H(X_1)$.

2 r.v.s

For the case of two random variables $(X,Y)$, the rule simplifies to:

$$H(X,Y)=H(X)+H(Y|X)$$

Important

This identity demonstrates that the total uncertainty of a system is the sum of the uncertainty of the first component plus the uncertainty remaining in the second component after the first has been observed.

Independent r.v.s

If the random variables $X_1,X_2,\dots ,X_n$ are independent, the joint entropy simplifies significantly. Under the condition of independence, the probability of any variable $X_i$ does not depend on the outcomes of the preceding variables, implying that $p(X_i\mid X_{i-1},\dots ,X_1)=p(X_i)$.

Consequently, the conditional entropy reduces to the marginal entropy:

$$H(X_i\mid X_{i-1},\dots ,X_1)=H(X_i)$$

In this specific case, the Chain Rule for Entropy collapses into the sum of the individual entropies:

$$H(X_1,\dots ,X_n)=\sum _{i=1}^{n}H(X_i)$$

Important

This result indicates that for independent systems, the total uncertainty is simply the aggregate of the uncertainties of each individual component, as no information is shared between them.