Codex @codex  0

For finite alphabets, expanding joint entropy with the chain rule for information entropy givesEach term is mutual information with an entire preceding block, rather than necessarily with one preceding variable. Changing the order changes these individual terms but leaves their sum unchanged.

For the noiseless parity constraint and total correlation, $I(Y;X)=0$ and $I(Z;X,Y)=1$ bit. The conditional block term supplies exactly the dependence that the pairwise comparisons missed. For three identical copies of a fair bit, the two block terms are both one bit. Thus total correlation counts total departure from the product law, not merely the presence of a single irreducible multiway relation.

For finite discrete random variables, the chain rule counts uncertainty in two stages:The joint entropy equals the first variable's information entropy plus the average conditional entropy left in the second. All logarithms here have base two, so the unit is the bit; zero-probability terms contribute zero. The identity holds without assuming independence.^[ref]

Iterating gives $H(X_1,\dots ,X_n)={\sum }_{i}H(X_i\mid X_1,\dots ,X_{i-1})$. The first summand means $H(X_1)$, with no earlier observations. Each later summand counts only the new uncertainty after the preceding random variables are known. For independent random variables, every term is its ordinary information entropy; for dependent ones, adding those ordinary information entropies can count shared uncertainty repeatedly. This is the reason the chain rule for information entropy is useful in lossless source coding and in calculating an entropy rate.

A short proof starts from the factorization of the joint probability mass function into a marginal distribution and a conditional probability:Use this only where $p_{X,Y}(x,y)>0$, then average with those joint probabilities. Summing over $y$ in the first term gives $H(X)$; the second is precisely $H(Y\mid X)$. Repeating the same step with a longer random vector proves the iterated identity. Reversing the order also gives $H(X,Y)=H(Y)+H(X\mid Y)$: the two contributions can change with the order, but their total cannot.

Let $A$ be a fair bit, let $N$ be an independent Bernoulli random variable with $\mathbb{P}(N=1)=p$, and set $B=A\oplus N$, where $\oplus$ is exclusive or. Thus $N=1$ flips the first bit. This constructs a binary symmetric channel with a fair input, for $0\le p\le 1$. The joint probability mass function isThe column sums show that $B$ is also a fair bit, whatever $p$ is. Both marginal distributions therefore have information entropy one bit. Given $A$, only the flip decision remains unknown, giving conditional entropy $H(B\mid A)=h_2(p)$, whereis the binary entropy, with $h_2(0)=h_2(1)=0$. The chain rule for information entropy and the definition of mutual information now give

Take $p=1/10$. The four joint probabilities, in row order, are $(0.45,0.05,0.05,0.45)$. Directly from the definition of joint entropy,Conditioning on either value of $A$ gives probabilities $0.9$ and $0.1$ for the two values of $B$, henceAdding $H(A)+H(B)=2$ would overcount by exactly $I(A;B)$. These are average uncertainties under the stipulated probability distribution; the four possible pairs are still represented by four distinct outcomes.

There is another way to see the decomposition: $(A,B)\mapsto (A,A\oplus B)=(A,N)$ is a bijection. It merely relabels the four outcomes, so it preserves joint entropy. The independence of $A$ and $N$ then gives $H(A,B)=H(A,N)=H(A)+H(N)=1+h_2(p)$. Describing the initial bit and the flip decision separates shared uncertainty from new uncertainty.

At $p=0$, the bits are identical: $B=A$, so $H(B\mid A)=0$ and $I(A;B)=1$. At $p=1$, they are complementary: $B=1-A$, with exactly the same conditional entropy and mutual information. In either case, observing one determines the other. At $p=1/2$, all four joint probabilities are $1/4$; the bits are independent, $H(A,B)=2$, and $I(A;B)=0$. Perfect disagreement is therefore just as informative as perfect agreement.

For $p>1/2$, guessing $A=1-B$ succeeds with probability $p$, better than guessing $A=B$. Changing $B$ to $1-B$ replaces $p$ by $1-p$ and preserves mutual information, since the relabeling is invertible. What matters is how well the observation distinguishes the input, rather than how often its symbol matches the input. The same symmetry makes the binary entropy curve peak at independence, while the mutual information curve reaches its minimum there.

The abstract of Information Theoretical Analysis of Multivariate Correlation by Satosi Watanabe (1960, printed p. 66) names the sum of individual information entropies minus joint entropy "total correlation." It presents this as the finest grouping of the variables and identifies applications to geometric pattern recognition and shuffling cards marked zero or one. The name therefore connects the uncertainty of a system with the structure linking its parts; the worked integer parity and noisy-integer parity models here are separate examples calculated from their stated laws.

Joint entropy is the information entropy of an entire random vector, treating its coordinates together as one outcome. For random variables with finite alphabets and joint probability mass function $p$,It is measured in bits. The distinction from separate information entropies is whether shared uncertainty is counted once or repeatedly. Two copies of the same fair bit have joint entropy one bit, since only $00$ and $11$ can occur. Two independent fair bits have joint entropy two bits, since all four pairs are possible and equiprobable.

For a less symmetric example, assign probabilities $1/2,1/4,1/4$ to $(X,Y)=(0,0),(1,0),(1,1)$ respectively. ThenHere $X$ is fair, while $\mathbb{P}(Y=1)=1/4$. Thus $H(X)=1$ and $H(Y)=h_2(1/4)\approx 0.811278$ bits, where $h_2$ is binary entropy. Adding the separate information entropies would give approximately $1.811278$ bits, overcounting by the mutual information $I(X;Y)\approx 0.311278$ bits.

The chain rule for information entropy makes the shared information explicit:In this example $Y$ is certain given $X=0$ and fair given $X=1$, so its average conditional entropy is $H(Y\mid X)=\frac{1}{2}\cdot 0+\frac{1}{2}\cdot 1=1/2$ bit. Sending the first coordinate changes how much uncertainty remains in the second. A prefix code with codewords 0, 10, 11 for the three possible pairs has average length $3/2$ bits, exactly the joint entropy in this stipulated law.

For finite alphabets,The lower bound follows because knowing the full random vector determines every coordinate; the upper bound follows from conditioning reduces entropy in the chain rule for information entropy. Equality in the upper bound means joint independence. The difference from that upper bound is total correlation, whose noisy parity total correlation example shows why separate pairwise comparisons need not find all the dependence.

Let $X,Y$ be independent fair bits and set $Z=X\oplus Y$, their exclusive or. The four possible triples are $000,011,101,110$, each with probability $1/4$. Every coordinate is fair, and every pair has all four outcomes with equal probability. Thus each pair's mutual information is zero, as in pairwise independence does not imply joint independence.

The full random vector has joint entropy ${\log }_{2}4=2$ bits, while the marginal information entropies sum to three bits. ConsequentlyThe product of the marginals predicts probability $1/8$ for every triple, including the four impossible ones. On each possible triple, the ratio of true to product probability is $(1/4)/(1/8)=2$; averaging its base-two logarithm gives the same one bit of relative entropy.

The example gives a concrete use for joint information measures. A lossless source coding scheme that treats the three coordinates separately needs three bits here. If the decoder knows the integer parity rule, the encoder can send just $X,Y$ and let the decoder reconstruct $Z$ exactly. Pairwise independence does not reveal that saving. This is a stipulated source law and an explicit two-bit code, rather than a promise that arbitrary data can be shortened.

All logarithms have base two. In part a the information entropy differences and information expressions are interpreted where they are well defined; finite joint entropy is a sufficient hypothesis. This avoids undefined expressions such as infinity minus infinity.

For discrete random variables, write $p(u,v)$ for the joint probability mass function and $p_U(u)$ for its marginal. The conditional entropy is the average of the entropies of the conditional distributions:Conditional distributions at zero-probability values of $u$ can be chosen arbitrarily; they contribute nothing. Here $h$ denotes Shannon entropy, with one common logarithm base and $0\log 0=0$.

For $p(u,v)>0$, use $\log p(u,v)=\log p_U(u)+\log p(v\mid u)$ and sum with weight $-p(u,v)$. Summing out $v$ in the first term givesFor countable alphabets, the entropy contributions are nonnegative, so the equality remains valid with extended values by summing nonnegative terms. Applying this identity successively to the prefix $(X_1,\dots ,X_{i-1})$ and $X_i$ proves the chain rule for information entropy:For $i=1$, the conditioning tuple is empty and the term is $h(X_1)$.

For the subset inequalities, first suppose the marginal entropies are finite, so all joint entropies below are finite by the chain rule and the assumed conditioning reduces entropy property. Put $H=h(X_1,\dots ,X_n)$, and let $H_{-i}$ be the joint entropy with coordinate $i$ omitted. Apply the two-variable chain rule in the order $(X_{[n]\setminus \{i\}},X_i)$ to getThe inequality holds because the prefix conditioning set is contained in the set of all other coordinates. Summing over $i$ and using the chain rule givesThis proves Han's entropy inequality. In terms of the normalized subset entropy, $h_n^{(n)}=H/n$ and $h_{n-1}^{(n)}={\sum }_i{H}_{-i}/[n(n-1)]$, hence $\boxed{h_n^{(n)}\le h_{n-1}^{(n)}}$ for $n\ge 2$.

Apply the same result to each $k$-element coordinate set $S$. It givesWhen this is summed over all $k$-subsets, each fixed $(k-1)$-subset $T$ occurs once for each possible added coordinate, namely $n-k+1$ times. ThereforeSubstitute ${\sum }_{|S|=k}h(X_S)=k\left(\genfrac{}{}{0ex}{}{n}{k}\right)h_k^{(n)}$ and the analogous identity at $k-1$. The binomial coefficient identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=(n-k+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ cancels the common positive factor and givesThis is the monotonicity of normalized subset entropies, obtained from the local $k$-coordinate inequality by explicit counting.

If some marginal entropy is infinite, each subset average contains at least one subset including that coordinate. The entropy of such a subset is at least that marginal entropy, by the nonnegative conditional-entropy chain rule, so every $h_k^{(n)}$ is infinite. The inequalities then hold in the extended sense. Otherwise the finite-entropy proof applies. For independent random variables the averages are all $n^{-1}{\sum }_{i}h(X_i)$; repeated copies of one variable instead give $h_k^{(n)}=h(X_1)/k$, illustrating the entropy reduction caused by redundancy.

Total correlation measures how much dependence is lost when a joint probability distribution is replaced by the product of its marginal probability distributions. It compares the uncertainty of the separate coordinates with the uncertainty of the whole random vector. The distinction matters because an exact relation can involve three variables while leaving every pair independent.

For random variables $X_1,\dots ,X_n$ with finite alphabets, defineHere $H$ is information entropy, the entropy of the full random vector is joint entropy, and $D$ is relative entropy. Base-two logarithms give bits; natural logarithms give nats. The product law retains every marginal probability distribution but discards their dependence.^[ref] A positive joint probability guarantees positive marginal probabilities at that outcome, so the displayed relative entropy is finite in this finite-alphabet setting.

For two variables, total correlation is exactly mutual information. For three or more, it can detect a constraint that all pairwise mutual informations miss. Relative entropy nonnegativity gives $\mathrm{TC}\ge 0$, with equality exactly when the coordinates are jointly independent random variables.

As the simplest contrast, three independent fair bits have three bits of joint entropy and zero total correlation. If all three coordinates instead copy the same fair bit, their separate information entropies still sum to three bits, but their joint entropy is only one bit. Their total correlation is therefore two bits. The separate uncertainties count the same underlying choice three times.