Information theory

Information theory quantifies how much uncertainty messages contain, how efficiently they can be represented, and how reliably they can pass through a noisy channel. Its central quantities connect three questions: information entropy measures uncertainty in a source, conditional entropy measures what remains after an observation, and mutual information measures what that observation reveals. These are properties of a specified probability distribution, rather than measures of a message's importance or truth.

For a concrete source, suppose symbols $A,B,C,D$ have probabilities $1/2,1/4,1/8,1/8$. A fixed-length binary representation needs two bits per symbol. Instead assign the prefix code $A\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $D\mapsto 111$. Reading from left to right gives an unambiguous decoding because no codeword begins another. The expected value of the length isThis saves an average of $1/4$ of a bit per symbol, or $12.5\%$ of the fixed-length representation, with no loss of symbols. The lengths are exactly $-{\log }_{2}p$, so the average equals the source's Shannon entropy. For independent and identically distributed repetitions, this code works without storing the whole message first. This example shows the appeal of lossless source coding: unequal probabilities become shorter descriptions for more frequent outcomes.

Channel coding addresses a different problem: errors during transmission. A shorter representation removes predictable structure; an error-correcting representation adds carefully chosen structure that helps recover corrupted symbols. Shannon's source coding theorem and the Shannon second coding theorem identify limits for these respective tasks under their hypotheses. The beauty is that source details and hardware details can meet through a small number of mathematical quantities, notably information entropy and channel capacity.

Claude E. Shannon's A Mathematical Theory of Communication appeared in the Bell System Technical Journal in July and October 1948. Its introduction separates the engineering problem of reproducing messages from their semantic meaning; subsequent sections develop probabilistic source models, noiseless coding, and transmission with noise. It also acknowledges earlier work by Harry Nyquist and Ralph Hartley.^[ref]

A ternary digit, taking one of three values. A codeword of length $l$ over a three-symbol alphabet uses $l$ trits. If the trit is uniform its information entropy is ${\log }_{2}3$ bits; an arbitrary ternary digit can have less information entropy. Expected codeword length in trits must therefore be distinguished from source information entropy measured in bits.

For probability distributions $p,q$ on the same finite alphabet, the Bhattacharyya coefficient measures their square-root overlap:The vectors $(\sqrt{p_i}{)}_i$ and $(\sqrt{q_i}{)}_i$ have unit Euclidean norm, so the Cauchy-Schwarz inequality gives $0\le B\le 1$. Equality $B=1$ holds exactly when the distributions agree; $B=0$ holds exactly when they assign positive probability to disjoint outcomes. For $p=(0.9,0.1)$ and $q=(0.6,0.4)$, $B=\sqrt{0.54}+0.2\approx 0.934847$. This overlap is not the probability that two independent draws agree, which here is $0.58$.

The fidelity of commuting mixed states reduces to this coefficient. More generally, the measurement characterization of quantum fidelity minimizes it over outcome distributions of a common quantum measurement, connecting classical overlap to the unsquared quantum fidelity.

The Bhattacharyya distance is the negative natural logarithm of the Bhattacharyya coefficient, with $-\ln 0=\infty$. It is zero for identical probability distributions and infinite for disjoint probability supports. Despite the name, it need not satisfy the triangle inequality required of a metric.

A communication channel describes how transmitted inputs become received outputs. In a probabilistic model, conditional probabilities specify which outputs each input can produce. A discrete memoryless channel uses the same finite transition law independently on successive symbols; channel capacity quantifies its optimal reliable transmission rate.

Information about earlier received outputs made available to the channel encoder while choosing subsequent inputs. For repeat-until-success coding over an erasure channel, an erasure report tells the sender to repeat the current bit, while a success report tells it to advance. A forward code rate calculation must specify whether this return communication is supplied freely or included in the resource count.

A bit is a binary classical symbol with two distinguishable values, zero and one. A uniform random bit has one bit of information entropy, while a biased binary symbol has less. Sending one bit means transmitting one symbol from this binary alphabet; the mutual information it carries about a particular input need not be one.

A bit vector is a fixed-length sequence of bits. An unsigned interpretation of a bit string assigns positional weights $1,2,4,\dots$; the vector itself need not represent an integer, since its coordinates can instead encode independent Boolean conditions.

The unit for information content or information entropy computed with natural logarithms. Converting to bits divides the numerical value by $\log 2$, so $1\mathrm{nat}=(1/\log 2)\mathrm{bits}$.

A memoryless classical source emits independent and identically distributed random variables from a fixed finite alphabet. Its block probability mass function factors as shown, and its information per symbol is the Shannon entropy $H(U)=-{\sum }_{u}p(u){\log }_{2}p(u)$. Zero-probability symbols never occur and contribute zero to the entropy. The typical sequence theorem describes the size and probability of the high-probability block set used for reliable compression.

An alphabet is a finite nonempty set of symbols from which strings or source outputs are formed.

The finite alphabet of symbols permitted on the stack of a pushdown automaton. It may contain nonterminal symbols, terminal symbols, and a fresh stack bottom marker, independently of the input alphabet.

A finite alphabet is an alphabet whose symbols form a finite set. The binary alphabet $\{0,1\}$ and a finite vocabulary of possible messages are examples.

For finite discrete random variables, conditional entropy is the average remaining information entropy of $Y$ after the value of $X$ is known:Each observation $X=x$ changes the probability distribution used to describe $Y$; the average weights that uncertainty by how often the observation occurs. An observation can increase uncertainty for one particular outcome, even though conditioning reduces entropy on average for finite variables.

For example, let $Y$ choose $A,B,C,D$ with probabilities $1/2,1/4,1/8,1/8$, and let $X$ report whether $Y=A$. If it reports yes, there is no remaining uncertainty. Otherwise the conditional probabilities are $1/2,1/4,1/4$, whose information entropy is $3/2$ bits. The two reports each occur with probability $1/2$, so $H(Y\mid X)=3/4$ of a bit. The original uncertainty was $7/4$ bits: this observation removes exactly one bit on average.

If $Y$ is a function of $X$, then $H(Y\mid X)=0$: the observation determines the answer. If $X$ and $Y$ are independent random variables, then $H(Y\mid X)=H(Y)$: the observation gives no improvement. These endpoints make conditional entropy useful for separating relevant observations from irrelevant ones. They also lead to the chain rule for information entropy, $H(X,Y)=H(X)+H(Y\mid X)$, which counts the first uncertainty and the remaining uncertainty without double counting.

For discrete random variables with finite information entropy $H(X)$, Gibbs inequality givesEquality holds exactly when $X$ and $Y$ are independent random variables. Finiteness matters: if $A$ has infinite information entropy and is independent of a fair bit $B$, then $X=(A,B)$ and $Y=B$ are dependent but $H(X)=H(X\mid Y)=+\infty$.

// Target: probability-and-statistics.bigb

For classical finite random variables, $H(X,Z\mid Y)=H(X\mid Y)+H(Z\mid X,Y)=H(Z\mid Y)+H(X\mid Z,Y)$. Each identity follows by inserting the corresponding joint entropy into $H(X,Z,Y)-H(Y)$. The two orders are particularly useful when one variable is a deterministic function of the others, as in Fano's inequality via an error indicator.

If $f(x,z)$ is a bijection of $x$ for every fixed $z$, thenIn particular, translating a random variable in a finite group by a value determined by the conditioning variable does not change its conditional entropy.

For finite discrete random variables $X,Y$, knowing $Y$ reduces the information entropy of $X$ on average:Equality holds exactly when $X$ and $Y$ are independent random variables. The average over observations is essential: $H(X\mid Y=y)$ can exceed $H(X)$ for a particular $y$. All logarithms here have base two, giving bits, and zero-probability terms contribute zero.^[ref]

For Bayesian inference, this compares a prior distribution with the posterior distributions produced by possible observations. An unexpected report can make previously unlikely alternatives plausible, while useful reports reduce uncertainty overall. For lossless source coding, an observation shared by encoder and decoder lets them choose descriptions for the appropriate conditional distribution; sending that observation also has a cost. The example below makes both the saving and that cost explicit.

In A Mathematical Theory of Communication by Claude Shannon (1948), the definition of conditional entropy is already an average over observations, followed by the inequality and its independence condition in section 6, property 6. The phrase “knowledge reduces uncertainty” must be read with that averaging convention.^[ref]

Consider a binary state $X$ and a report $Y$ with the following joint probability mass function:Before the report, $X=0$ is strongly favored: its information entropy is $H(X)=h_2(1/10)\approx 0.468996$ bits, where $h_2$ is binary entropy. A report $Y=1$ makes the two states equally likely, so $H(X\mid Y=1)=1$ bit, strictly larger than before. This report occurs with probability $1/5$. The more common report $Y=0$ determines $X=0$, giving $H(X\mid Y=0)=0$. Therefore the averaged conditional entropy isThe resulting mutual information is $I(X;Y)=h_2(1/10)-1/5\approx 0.268996$ bits. The rare report increases uncertainty about the state; that increase does not make the report useless. Together the reports remove uncertainty on average. These are stipulated probabilities in an exact model, not measured frequencies.

Let $X$ be a Bernoulli random variable with $\mathrm{Pr}(X=1)=p$. Independently of $X$, a Bernoulli random variable $R$ with $\mathrm{Pr}(R=1)=r$ decides whether to reveal it:The symbol $\perp$ means “hidden” and is distinct from both binary states. This is a binary erasure channel with erasure probability $1-r$. The hidden report leaves the posterior distribution equal to the prior distribution, because hiding is independent of the state. Either visible report determines $X$. Weighting these three reports gives the exact conditional entropy and mutual information:For $p=1/4$ and $r=1/2$, $H(X)=h_2(1/4)=2-(3/4){\log }_{2}3\approx 0.811278$ bits, while $H(X\mid Y)=I(X;Y)\approx 0.405639$ bits. With $r=0$ the report tells us nothing; with $r=1$ it reveals the state completely. If $0<p<1$, every positive reveal probability makes the conditioning inequality strict. At $p=0$ or $p=1$, the state was already known and every value of $r$ gives equality.

For a Bayesian inference problem, this model distinguishes an uninformative missing report from a decisive observed state. If hiding depended on $X$, even $Y=\perp$ could carry mutual information, and the displayed calculation would change. In lossless source coding, suppose both encoder and decoder already know the reveal pattern for repeated independent and identically distributed pairs. Only the hidden states require descriptions. Applying Shannon's source coding theorem to those states gives an asymptotic average rate $(1-r)h_2(p)$ bits per original state. A single hidden state need not have a codeword of that fractional length.

The reveal pattern itself has information entropy $H(R)=h_2(r)$. If that pattern must also be sent, the chain rule for information entropy gives $H(R,X)=h_2(r)+h_2(p)$, since $R$ and $X$ are independent random variables. Equivalently, $H(Y)=h_2(r)+r{h}_2(p)$ and $H(X,Y)=H(Y)+H(X\mid Y)=h_2(r)+h_2(p)$. Thus a saving in the description of $X$ given $Y$ assumes that $Y$ is already available; it is not a free saving in the description of the whole pair.

For finite discrete random variables $X,Y,Z$, retaining $Y$ and also observing $Z$ givesEquality means conditional independence of $X$ and $Z$ given $Y$. Both sides average over reports; the additional observation is retained alongside $Y$.^[ref]

A short proof of the original inequality uses Kullback-Leibler divergence:Gibbs inequality makes each term nonnegative, vanishing exactly when $p_{X\mid Y=y}=p_X$: independence for every possible report. Applying this within each $Y=y$ and averaging proves the additional-conditioning inequality.^[ref]

With appropriate probability density functions and finite differential entropies, $h(X)-h(X\mid Y)=I(X;Y)\ge 0$, with equality iff independence. Differential entropy does not reverse the inequality; infinite or undefined quantities cannot justify subtraction.^[ref]

However, differential entropy can be negative and depends on the choice of coordinates. For $X$ with a uniform distribution on an interval of length $a>0$, $h(X)={\log }_{2}a$; in particular $a=1/2$ gives $-1$. Rescaling $X$ by a constant $c>0$ adds ${\log }_{2}c$ to both $h(X)$ and $h(X\mid Y)$, whenever they are finite, leaving the mutual information unchanged.^[ref]

If a continuously distributed $X$ is revealed exactly, its conditional distribution is a Dirac measure with no ordinary probability density function. The discrete identity $H(X\mid X)=0$ has no finite differential entropy counterpart. Mutual information, defined through relative entropy, is infinite here.^[ref]

Fano's inequality turns remaining uncertainty into a constraint on decision errors. If an observation leaves many plausible answers, a decoder cannot usually recover the answer reliably. Its elegant idea is to separate two uncertainties: whether the guess was wrong, and which alternative was correct when it was wrong.

Let $X,Y$ be discrete random variables, with $X$ taking values in a finite alphabet $\mathcal{X}$ of cardinality $M\ge 2$. Choose any deterministic decoder $\hat{X}=f(Y)$ whose output lies in $\mathcal{X}$, and define its average error probability $p_e=\mathbb{P}\{\hat{X}\ne X\}$. With base-two logarithms, Fano's inequality statesHere $H(X\mid Y)$ is conditional entropy and $h_2$ is binary entropy, with $0{\log }_{2}0=0$ at the endpoints. Both sides are measured in bits; using natural logarithms throughout gives the same inequality in nats. No uniform source, independence of $X,Y$, or optimality of the decoder is assumed. Requiring its output to belong to the same alphabet is what leaves at most $M-1$ alternatives after an error.^[ref]

For an exact toy example, give $X$ the discrete uniform distribution on $\{A,B,C,D\}$. A channel reports $Y=X$ with probability $1-q$ and reports each of the other three symbols with probability $q/3$, where $0\le q\le 1$. Use the decoder $f(y)=y$. The output is uniform, and the conditional probabilities after any report $y$ areThus $p_e=q$ and direct calculation of the conditional entropy givesThis is equality in Fano's inequality for every $q\in [0,1]$. At $q=0.3$, each report leaves probabilities $(0.7,0.1,0.1,0.1)$, up to their order, and $H(X\mid Y)\approx 1.3568$ bits. The two contributions are $h_2(0.3)\approx 0.8813$ bits for the error flag and $0.3{\log }_{2}3\approx 0.4755$ bits for identifying the correct alternative after an error. These are theoretical probabilities, not measured data.

The identity decoder in this example minimizes error only for $0\le q\le 3/4$: its guessed symbol has the largest posterior probability exactly when $1-q\ge q/3$. At $q=3/4$, $X,Y$ are independent random variables and all four guesses tie. For $q>3/4$, guessing any one of the three other symbols has error probability $1-q/3<q$. Equality in Fano's inequality therefore does not certify an optimal decoder.

For usefulness, combine $h_2(p_e)\le 1$ with ${\log }_2(M-1)\le {\log }_{2}M$ to obtain the simpler consequenceFor a uniform $X$, $H(X\mid Y)={\log }_{2}M-I(X;Y)$, so this becomes $p_e\ge \max \{0,1-(I(X;Y)+1)/{\log }_{2}M\}$. This connects mutual information to unavoidable decision error in channel coding or classification in statistical learning; it can rule out reliable recovery regardless of the chosen decoder.^[ref]

The sharper right-hand side $F_M(p)=h_2(p)+p{\log }_2(M-1)$ increases from zero to ${\log }_{2}M$ on $0\le p\le 1-1/M$, then decreases: in the interior, $F_M^{\prime }(p)={\log }_2((M-1)(1-p)/p)$. When interpreting the inequality by inverting a curve, use its increasing branch to obtain a lower error threshold. A decoder that chooses a largest posterior probability, as in maximum a posteriori decoding, always has $p_e\le 1-1/M$, since the largest of $M$ conditional probabilities is at least $1/M$. Arbitrary decoders can have larger error. In particular, low conditional entropy does not force every decoder to work well: with a fair binary $X$ and $Y=X$, the rule $f(Y)=1-Y$ has $p_e=1$ even though $H(X\mid Y)=0$. Fano's inequality supplies a constraint, not an exact error prediction for each rule.

Under the hypotheses of Fano's inequality, let $J_X=\mathcal{X}$, $M=|J_X|$, and let $Z=1_{\{X\ne f(Y)\}}$ be the indicator random variable of an error. Its probability of being one is $p_e$. The $h$ in the displayed bound denotes binary entropy $h_2$ in bits. Since $Z$ is a deterministic function of $(X,Y)$, $H(Z\mid X,Y)=0$. Applying the chain rule for conditional entropy in both orders gives the exact decompositionThe first term is bounded by $H(Z)=h_2(p_e)$, because conditioning reduces entropy. For the second term, fix a report $Y=y$: if $Z=0$, then $X=f(y)$ is known; if $Z=1$, then $X$ lies among at most $M-1$ other symbols. Maximum entropy on a finite alphabet bounds the latter uncertainty by ${\log }_2(M-1)$. Averaging over the reports and the error flag givesThis proves Fano's inequality. Events of zero probability contribute zero to this average, so the proof also covers $p_e=0,1$ without assigning a conditional distribution to an impossible event.^[ref]

The decomposition also explains equality. The first bound is exact when the indicator random variable $Z$ and $Y$ are independent random variables: knowing the report does not change the error probability. The second is exact when, for every report with positive error probability, the wrong-symbol conditional distribution is uniform on all $M-1$ alternatives. Both conditions hold in the four-symbol toy channel of Fano's inequality. At $q=0$, the second condition is vacuous; at $q=1$, the flag is constant but three alternatives remain, giving $H(X\mid Y)={\log }_{2}3$. For $M=2$, there is just one alternative after an error, so the second term vanishes: all remaining uncertainty is whether the single alternative must replace the guess.

If a uniform index $J$ has $N$ possibilities and every proposed success neighbourhood contains at most $B<N$ possibilities, then any estimator has failure probability at least the displayed expression. Condition on its success indicator: conditional entropy is at most $\log 2+(1-p_e)\log B+p_e\log N$. Subtract this from $\log N$ to bound the mutual information and rearrange. A metric Hamming ball gives approximate recovery rather than exact index decoding.

If independent random variables $X,Y$ take values in a finite additive group, thenIndeed, $H(X+Y)\ge H(X+Y\mid Y)=H(X)$, and symmetrically for $Y$. Independence is essential: taking $Y=-X$ makes the sum constant.

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]