Bit-position information in a binary channel Created 2026-10-25 Updated 2026-10-31
Suppose a fair input bit is independent of a publicly known channel-position label . At position , let the channel be a binary symmetric channel with error probability . Forgetting gives a binary symmetric channel with error . ThereforeThe chain rule for mutual information and show that their difference is the nonnegative conditional mutual information . Equivalently, the inequality follows from concavity of binary entropy. For with equal position weights, the known-position value is bits and the pooled value is bits. These quantities answer different statistical questions.
Capacity after independent output erasure 2026-10-31
Pass the output of a discrete memoryless channel of channel capacity through an independent finite-alphabet erasure channel with erasure probability . Its capacity becomes .
To prove it, let be the original input, the original output, the erasure indicator, and the final output. Since the erasure marker is distinguishable, is determined by . It is independent of , so the chain rule for mutual information gives . Maximization over the same input distributions proves the formula. For the maximizing distributions are exactly the original channel's maximizers. For , every input distribution attains the zero capacity. Input-dependent erasure need not satisfy this scaling identity.
Conditional mutual information Created 2026-09-24 Updated 2026-10-14
For finite discrete random variables, conditional mutual information measures the average reduction in uncertainty about from observing , when 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 visible. Equivalently, compute the mutual information separately in each conditional probability distribution and then average:Here is the Kullback-Leibler divergence, also computed with base-two logarithms; zero-probability terms contribute zero. The Gibbs inequality gives , with equality exactly when and have conditional independence given : the conditional joint probability mass function factors for every of positive probability.[ref]
For a fully computed example, take independent random variables that are fair bits, and let , where is exclusive or. The complete joint probability distribution has only these four positive entries:
Table 1. .
Every pair has probability , so . But . Given , the pairs each have conditional probability , while both conditional marginals are fair. ThusGiven , the pairs give the same calculation. ThereforeThe conditional entropy calculation tells the same story: because either value of leaves fair, whereas because . 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 and : the example above increases it from zero to one, while taking and 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.
Data processing inequality 2026-10-14
For finite discrete random variables, suppose is a Markov chain: the final channel uses only , so and have conditional independence given . In terms of the joint probability mass function,and hence . 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]
https://web.stanford.edu/class/cs229t/scribe_notes/12_05_final.pdf. Stanford CS229T/STATS231, Theorem 2.1 and its chain-rule proof
For a concrete cascade, take a fair bit and Bernoulli random variables with probabilities , of being one. Assume are jointly independent random variables, and pass through two binary symmetric channels:The second noise is independent of both and , so this is a Markov chain. Both and 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 , the three mutual informations are fully determined:All numbers are in bits. The two losses are and . Thus the cascade retains less information about the original source than either individual channel shares between its own input and output.
With fixed and , the effective error is . At , and ; at , is independent of the previous variables and . The diagram plots these endpoints and the computed example.
The data processing inequality is useful for testing what a proposed decoder or data summary could possibly reveal: if its only input is , even randomized processing cannot provide more mutual information about than already contains. The Markov chain hypothesis matters. In the exclusive or example from conditional mutual information, allowing a processor to use both and reveals exactly; that processor has additional input, so the conclusion for processing alone does not apply.
The chain rule for mutual information proves both inequalities and identifies their exact gaps. First expand the information about in the two observation orders:Therefore . Next use as the variable being learned:Symmetry of mutual information gives . Both signs follow from the nonnegativity of conditional mutual information; the first gap also gives equality in data processing inequality.
Past exam of the communication Theory course of the University of Oxford 2009 3 c Solution 2026-10-31
Let record whether the second stage erased the symbol, and write its output as . The erasure marker is outside the original output alphabet, so is determined by . Independence makes independent of both and the first output . The chain rule for mutual information therefore givesThe erased branch gives zero information because its output is constant; the unerased branch has exactly the original joint input-output law. Maximizing over the same input distributions givesThis includes and . It is the capacity after independent output erasure; input-dependent erasure would not justify the independence step.
Past exam of the information theory course of the University of Oxford 2021 1 a ii Solution 2026-10-25
Expand the two observations in order using the chain rule for mutual information:The remaining conditional mutual information isRelative entropy nonnegativity proves the inequality. Equality requires every positive-weight relative entropy to vanish, which is equivalent to for every of positive probability. Thus equality holds exactly when and have conditional independence given . No unconditional independence is required.
Write . Because is determined by , the chain rule for mutual information givesThis is the data processing inequality. It holds for every input probability distribution. Maximizing each side over that same set of input probability distributions gives ; processing cannot increase channel capacity.
A simple sufficient condition for equality is that be injective on the reachable output alphabet. Then can be recovered from , giving and hence for every input law. The input that achieves the original channel capacity therefore achieves it after processing as well. Values of outside reachable outputs are irrelevant.
Injectivity is sufficient rather than necessary. More precisely, for finite alphabets equality in capacity data processing holds exactly when there is an original capacity-achieving input law for which and have conditional independence given . Sufficiency follows from the displayed gap identity. For necessity, maximize at an input law ; if its maximum equals , then , so both inequalities are equalities. Processing may discard output details unrelated to the input without losing channel capacity.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 1 11I b Solution Created 2026-09-24 Updated 2026-09-25
Let denote whether or was sent, and writewhere are independent Bernoulli variables of parameter . Because is uniform, is uniform, while . Thus the mutual information in the first received digit is
By the chain rule for mutual information, the extra information in the second digit is . Conditional on , the second channel error is independent of the first output, soMoreover,Given either value of , the second output therefore differs from it with probability , andConsequently the incremental information in a twofold binary repetition code isbits.
Past exam of the mathematics course of the University of Cambridge 2024 iii Paper 224 1 a Solution Created 2026-09-24 Updated 2026-09-25
If is a Markov chain, the two forms of the data processing inequality for mutual information areThe chain rule for mutual information and the Markov property giveUsing the other order,because conditional mutual information is nonnegative. This proves the first inequality. Applying the same result to the reversed Markov chain , which has the same conditional-independence statement, proves the second.
Past exam of the mathematics course of the University of Cambridge 2026 iii Paper 224 1 a Solution Created 2026-09-24 Updated 2026-09-25
Suppose is a Markov chain, so . The chain rule for mutual information givesand alsobecause conditional mutual information is nonnegative. Therefore . Similarly,while , so . These are the two data processing inequalities. In particular, applying any deterministic function or Markov kernel to either argument cannot increase mutual information.

