Mutual information ($I(X;Y)$)

For finite discrete random variables, mutual information is the reduction of information entropy provided by observing the other variable:The last expression makes the symmetry $I(X;Y)=I(Y;X)$ visible. It is nonnegative and is zero exactly when $X$ and $Y$ are independent random variables. One way to see both facts iswhere $D$ is the Kullback-Leibler divergence with base-two logarithms. The Gibbs inequality gives nonnegativity; equality means that the joint probability distribution factors. The statement extends to more general distributions via relative entropy, but differences of infinite information entropies must not be used as if they were finite numbers.

A binary symmetric channel gives a useful example. Let $X$ be a fair bit, let $N$ be an independent Bernoulli random variable with error probability $q$, and set $Y=X\oplus N$, where $\oplus$ is exclusive or. The output is also a fair bit, but knowing the input leaves just the error uncertainty:Here $h_2$ is binary entropy. At $q=0.1$, $h_2(q)\approx 0.469$, so the output carries about $0.531$ bits of mutual information about the input per use. This is an average uncertainty reduction, not a claim that each observed symbol can be divided into fractional physical bits.

At $q=1/2$, every output is equally likely for either input, so $I(X;Y)=0$. At $q=1$, the output is always the inverted input: knowing this rule lets the receiver recover the input exactly, so $I(X;Y)=1$ again. A high raw error rate need not mean low mutual information when the errors are predictable. For this particular channel the fair input is optimal, giving the binary symmetric channel capacity $1-h_2(q)$.

Mutual information detects dependence that ordinary correlation can miss. Let $X$ be uniform on $\{-1,0,1\}$ and $Y=X^2$. Symmetry gives $\mathbb{E}[X]=\mathbb{E}[XY]=0$, hence zero covariance and zero correlation, while $Y$ is completely determined by $X$. Thus $I(X;Y)=H(Y)=h_2(1/3)>0$. This distinction is useful whenever a relationship is nonlinear: knowing one variable can reveal another without a linear trend.

For a fixed finite discrete memoryless channel $W$, the function $p\mapsto I_p(X;Y)$ is concave on the input probability simplex. Indeed, the induced output law $q=pW$ is linear in $p$, the output Shannon entropy $H(q)$ is concave, and $H(Y\mid X)={\sum }_{x}p(x)H(W(\cdot \mid x))$ is linear. Their difference is therefore concave. Equivalently, at a mixture $p=\lambda p_1+(1-\lambda )p_2$, the concavity gap is $\lambda D(q_1\Vert q)+(1-\lambda )D(q_2\Vert q)\ge 0$ by Gibbs inequality. Thus every local maximum is a global maximum, and averaging over symmetries of the fixed channel cannot decrease mutual information.

For discrete random variables $X,Y,Z$,The difference between the left- and right-hand sides is the nonnegative conditional mutual information $I(X;Z\mid Y)$.

A union-intersection compression can only decrease the sum of information entropies ${\sum }_{A\in \mathcal{A}}H(X_A)$ for a finite-valued random vector $X$. Each elementary step follows from entropy submodularity; iteration proves the assertion with multiset multiplicities. Uniform coordinate multiplicity gives Shearer inequality by compressing to repeated full sets and empty sets.

Let $\mathcal{A}$ be a finite multiset of subsets and let $r_i$ count its occurrences of coordinate $i$. Its nested compression consists of $L_j=\{i:r_i\ge j\}$. Then ${\sum }_{j}H(X_{L_j})\le {\sum }_{A\in \mathcal{A}}H(X_A)$, by repeated entropy submodularity. This is the compression formulation in Balister and Bollobás, "Projections, Entropy and Sumsets".

For a nonempty ordered coordinate set $A$, write $A^{-}=[\min A-1]$ and $A^{+}=[\max A-1]\setminus A$. An exact $k$-cover satisfies ${\sum }_{A}H(X_A\mid X_{A^{+}})\le kH(X)\le {\sum }_{A}H(X_A\mid X_{A^{-}})$. A short proof uses the chain rule for information entropy contributions $h_i=H(X_i\mid X_{[i-1]})$: each conditional subset entropy bounds ${\sum }_{i\in A}{h}_i$ on the appropriate side, by conditioning reduces entropy. Weighting gives the lower inequality for a fractional packing and the upper inequality for a fractional cover. See Madiman and Tetali, "Information Inequalities for Joint Distributions".

Let $X=(X_1,\dots ,X_n)$ be a discrete random vector, and let $\mathcal{S}$ be a collection of subsets of $[n]$ in which every index occurs at least $r$ times. ThenApply the chain rule for information entropy to each projection $X_S$ and use conditioning reduces entropy to compare every term with the corresponding conditional entropy in the full chain rule.

If every pair of graphs in a family on $[n]$ has a graph intersection without an isolated vertex, the family has at most $2^{n(n-2)/2}$ members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most $2^{n-2}$. Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.

For finite discrete random variables, conditional mutual information measures the average reduction in uncertainty about $X$ from observing $Y$, when $Z$ is already known. With base-two logarithms, it is measured in bits:The second expression follows from the chain rule for conditional entropy and makes the symmetry in $X,Y$ visible. Equivalently, compute the mutual information separately in each conditional probability distribution and then average:Here $D$ is the Kullback-Leibler divergence, also computed with base-two logarithms; zero-probability terms contribute zero. The Gibbs inequality gives $I(X;Y\mid Z)\ge 0$, with equality exactly when $X$ and $Y$ have conditional independence given $Z$: the conditional joint probability mass function factors for every $z$ of positive probability.^[ref]

For a fully computed example, take independent random variables $X,Y$ that are fair bits, and let $Z=X\oplus Y$, where $\oplus$ is exclusive or. The complete joint probability distribution has only these four positive entries:

Every pair $(x,y)$ has probability $1/4=p_X(x)p_Y(y)$, so $I(X;Y)=4(1/4){\log }_{2}1=0$. But $p_Z(0)=p_Z(1)=1/2$. Given $Z=0$, the pairs $(0,0),(1,1)$ each have conditional probability $1/2$, while both conditional marginals are fair. ThusGiven $Z=1$, the pairs $(0,1),(1,0)$ give the same calculation. ThereforeThe conditional entropy calculation tells the same story: $H(X\mid Z)=1$ because either value of $Z$ leaves $X$ fair, whereas $H(X\mid Y,Z)=0$ because $X=Y\oplus Z$. Learning the exclusive or does not reveal either bit alone; it reveals whether they agree, so learning one then determines the other.

This example distinguishes conditional independence from ordinary independence. It also disproves the claim that conditioning always reduces mutual information, despite conditioning reduces entropy. There is no general ordering between $I(X;Y\mid Z)$ and $I(X;Y)$: the example above increases it from zero to one, while taking $Y=X$ and $Z=X$ for a fair bit decreases it from one to zero. The chain rule for mutual information explains why both are possible.^[ref]

Conditional mutual information is useful for asking whether an additional observation tells us anything after information already available has been accounted for. Its zero case expresses conditional independence exactly; in a Markov chain, this is the step that turns the chain rule for mutual information into the data processing inequality.

If outputs $V,W$ are conditionally independent given $U$, then $H(V,W\mid U)=H(V\mid U)+H(W\mid U)$. Expanding the entropy expressions proves the displayed mutual information identity. The chain rule also gives $I(U;V,W)\ge \max \{I(U;V),I(U;W)\}$, while the identity and nonnegativity give the upper bound by their sum. For two channels with common input and independent output noise conditional on that input, maximizing over the input law therefore bounds the joint-output capacity between the larger marginal capacity and the sum of the two marginal capacities. Their unconditional output dependence need not vanish: the subtracted $I(V;W)$ measures information shared through the common input.

Suppose a fair input bit $X$ is independent of a publicly known channel-position label $J$. At position $j$, let the channel be a binary symmetric channel with error probability $p_j$. Forgetting $J$ gives a binary symmetric channel with error $\overline{p}=\mathbb{E}{p}_J$. ThereforeThe chain rule for mutual information and $I(X;J)=0$ show that their difference is the nonnegative conditional mutual information $I(X;J\mid Y)$. Equivalently, the inequality follows from concavity of binary entropy. For $p_0=1/5,p_1=0$ with equal position weights, the known-position value is $0.639036$ bits and the pooled value is $0.531004$ bits. These quantities answer different statistical questions.

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:The order changes the individual contributions but leaves the total unchanged.^[ref] To prove the first identity, add and subtract the intermediate conditional entropy: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: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: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)\ge 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 identitywhich explains why there is no general rule that conditioning decreases mutual information.

For finite discrete random variables, suppose $X\to Y\to Z$ is a Markov chain: the final channel uses only $Y$, so $X$ and $Z$ have conditional independence given $Y$. In terms of the joint probability mass function,and hence $I(X;Z\mid Y)=0$. Then the two data processing inequalities areAll mutual informations here use base-two logarithms. Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.^[ref]

For a concrete cascade, take a fair bit $X$ and Bernoulli random variables $N_q,N_r$ with probabilities $q=0.1$, $r=0.2$ of being one. Assume $X,N_q,N_r$ are jointly independent random variables, and pass through two binary symmetric channels:The second noise is independent of both $X$ and $Y$, so this is a Markov chain. Both $Y$ and $Z$ are fair bits. The net exclusive or error is one exactly when one noise flips the bit and the other does not:Using the binary entropy $h_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$, the three mutual informations are fully determined:All numbers are in bits. The two losses are $I(X;Y\mid Z)\approx 0.3577507789$ and $I(Y;Z\mid X)\approx 0.1048182776$. Thus the cascade retains less information about the original source than either individual channel shares between its own input and output.

With $q=0.1$ fixed and $0\le r\le 1/2$, the effective error is $s=0.1+0.8r$. At $r=0$, $Z=Y$ and $I(X;Z)=I(X;Y)$; at $r=1/2$, $Z$ is independent of the previous variables and $I(X;Z)=I(Y;Z)=0$. The diagram plots these endpoints and the computed $r=0.2$ example.

The data processing inequality is useful for testing what a proposed decoder or data summary could possibly reveal: if its only input is $Y$, even randomized processing cannot provide more mutual information about $X$ than $Y$ already contains. The Markov chain hypothesis matters. In the exclusive or example from conditional mutual information, allowing a processor to use both $Y$ and $Z$ reveals $X$ exactly; that processor has additional input, so the conclusion for processing $Y$ alone does not apply.

The chain rule for mutual information proves both inequalities and identifies their exact gaps. First expand the information about $X$ in the two observation orders:Therefore $I(X;Y)-I(X;Z)=I(X;Y\mid Z)\ge 0$. Next use $Z$ as the variable being learned:Symmetry of mutual information gives $I(Y;Z)-I(X;Z)=I(Y;Z\mid X)\ge 0$. Both signs follow from the nonnegativity of conditional mutual information; the first gap also gives equality in data processing inequality.

Under the finite Markov chain hypothesis $X\to Y\to Z$, the gap identity in the data processing inequality givesBy the zero criterion for conditional mutual information, equality means that $X$ and $Y$ have conditional independence given $Z$. After seeing the processed output, the original observation provides no additional information about $X$. Similarly, equality in the other bound, $I(X;Z)=I(Y;Z)$, holds exactly when $I(Y;Z\mid X)=0$.

Equality does not require retaining every detail of $Y$. Let $X,W$ be independent fair bits, put $Y=(X,W)$, and let the processed output be $Z=X$, the first coordinate of $Y$. This is a Markov chain, andAlso $I(X;Y\mid Z)=H(X\mid X)-H(X\mid X,W)=0$. The output discards the entire unrelated bit $W$, reducing $H(Y)=2$ to $H(Z)=1$, while preserving all mutual information about $X$. This is what makes equality useful for choosing a compact observation that retains all information about the quantity of interest.

If $X\to Y\to Z$ is a Markov chain conditionally on $W$, thenIt follows by applying ordinary data processing inside every conditional distribution and averaging over $W$.

Send a uniform bit twice through independent binary symmetric channels of crossover probability $p$. The first received bit supplies $1-h_2(p)$ bits. Since the received bits disagree with probability $2p(1-p)$, the additional information in the second bit is