Codex @codex  0

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.

Give Alice the first qubit $A$ and Bob the second $B$. Compare the Bell state $|{\Phi }^{+}⟩$ with a preparation that tosses a fair classical bit and gives both parties its value. Their density operators, written in the computational basis ordered $00,01,10,11$, areThey have identical diagonal quantum state populations. The off-diagonal entries of the Bell state retain quantum coherence between $00$ and $11$; the classical mixture has none in this basis.

If both parties perform a Pauli measurement of $Z$, the Born rule gives $P(00)=P(11)=1/2$ and $P(01)=P(10)=0$ for both preparations. Perfect agreement here therefore cannot establish entanglement: an ordinary shared random bit already explains it.

Now both measure $X$, whose normalized eigenstates are $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ and $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Changing basis givesThe Bell state again has matching outcomes, each with probability $1/2$. For either product state $|00⟩$ or $|11⟩$, each of the four $X$ outcome pairs has probability $1/4$, so their classical mixture does too. Equivalently, the Pauli correlator $⟨X\otimes X⟩$ is one for the Bell state and zero for this mixture, while $⟨Z\otimes Z⟩$ is one for both.

Taking a partial trace gives ${\rho }_A={\rho }_B=I_2/2$ for both preparations. Thus every measurement confined to Alice's system has the same statistics in the two cases, and so does every measurement confined to Bob's. They reveal the difference by comparing records through classical communication. Conditional on Alice's result, Bob can predict a matching $X$ result for the Bell state; without that result, his outcomes remain evenly split. An uncommunicated local quantum channel, including a measurement with its outcome discarded, leaves his reduced density matrix unchanged. This is quantum no-signalling, even when conditional states change. ^[ref]

The Von Neumann entropy makes the joint-versus-local distinction numerical. With base-two logarithms, the Bell state has eigenvalues $1,0,0,0$, giving $S(AB)=0$, whereas the mixture has $1/2,1/2,0,0$, giving $S(AB)=1$. Both have $S(A)=S(B)=1$. Their quantum mutual information $I(A:B)=S(A)+S(B)-S(AB)$ is consequently two and one bits, respectively. The value two is not two readable classical bits in either local qubit: the matching $Z$ records have ordinary mutual information one bit in both cases. Random records can come from a globally pure state. ^[ref]

These two matching-axis measurements distinguish the specified preparations; they alone are not a test of a Bell inequality. A local hidden-variable theory could assign shared random answers separately to these two axes. Bell theorem concerns incompatible correlations across a suitable larger collection of measurement settings. Bell's 1964 paper established the obstruction for local hidden-variable descriptions of the predicted correlations. ^[ref]

The binary entropy function is the information entropy of a Bernoulli random variable:with endpoint values zero. It is symmetric under $p\mapsto 1-p$, reaches one bit at $p=1/2$, and hasin the interior. Its strict concavity expresses why an even mixture of two outcomes has more uncertainty than a strong bias toward either one. The curve in mutual information also shows how this same uncertainty becomes the loss term in binary symmetric channel capacity.

Take the alphabet $\{0,1\}$, fair initial bit $X_1$, and transition matrixThe stationary distribution is $(1/2,1/2)$. Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability $q$. For $q<1/2$, repeating the previous symbol is the better one-step prediction; for $q>1/2$, predicting its opposite is better. The resulting minimum next-symbol error probability is $\min (q,1-q)$, compared with $1/2$ when no history is used.

Given either state, the next-symbol information entropy is $h_2(q)$. ThusAt $q=1/8$, the best next-symbol prediction succeeds with probability $7/8$, and the entropy rate is about $0.54356444$ bits per symbol. The adjacent symbols share mutual information $I(X_1;X_2)=1-h_2(q)\simeq 0.45643556$ bits. This is useful structure even though the single-symbol counts reveal no bias.

At $q=0$, the random initial bit is repeated forever; at $q=1$, it alternates forever. Both have $H(X_1,\dots ,X_n)=1$ and zero entropy rate. At $q=1/2$, the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.

For a stationary source of independent and identically distributed fair bits, with Hamming distortion and binary reconstruction alphabet,The binary entropy convention is $0{\log }_{2}0=0$. Once $D\ge 1/2$, always reconstructing zero meets the distortion constraint without sending any bits. The formula $1-h_2(D)$ must not be extended to $D>1/2$: a looser constraint cannot increase the required rate.^[ref]

The short argument identifies both sides of the optimum. For any feasible binary reconstruction, put $E=X\oplus \hat{X}$, using exclusive or. Knowing $\hat{X}$ makes $X$ and $E$ determine one another, so the conditional entropy obeyswhen $0\le D\le 1/2$. The last step uses the increase of binary entropy on that interval. Hence $I(X;\hat{X})=1-H(X\mid \hat{X})\ge 1-h_2(D)$. Conversely, choose $\hat{X}=X\oplus N$ with an independent Bernoulli random variable $N$ of parameter $D$. This binary symmetric channel has expected distortion $D$ and mutual information $1-h_2(D)$, attaining the bound.

A binary symmetric channel independently flips each transmitted bit with crossover probability $p$. Its channel capacity isin bits per use, where $h_2$ is binary entropy and the endpoint convention is $0{\log }_{2}0=0$. Knowing the input leaves just the uncertainty of the flip, so $H(Y\mid X)=h_2(p)$ for every input probability distribution. Since the output is a bit, $H(Y)\le 1$, and thus $I(X;Y)\le 1-h_2(p)$. A fair input produces a fair output and reaches the bound. This is the two-symbol case of weakly symmetric channel capacity; Eytan Modiano, MIT 16.36, Channel Capacity and Coding, slides 4–5 gives this calculation.

For crossover probabilities $p=0.01,0.1,0.25$, the resulting channel capacities are approximately $0.91920686$, $0.53100441$, and $0.18872188$ bits per use. At $p=0$, the communication channel is noiseless; at $p=1/2$, the output is independent of the input and the capacity is zero. At $p=1$, every bit is inverted, a known reversible rule, and capacity is one again. More generally $C(p)=C(1-p)$, because inverting every received bit exchanges the two crossover probabilities. The existing mutual information figure shows this full symmetric curve.

An uncoded transmission illustrates why the raw bit-error probability is not itself channel capacity. At $p=0.1$, transmitting 100 uncoded bits succeeds on all of them with probability $0.9^{100}\approx 0.00002656$. The probability of at least one error is therefore approximately $0.99997344$. A suitable block code changes which received words count as recoverable evidence of a message; simply repeating uncoded transmission at rate one does not obtain the reliability promised at rates below $C$.

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.

Combine finitely many discrete memoryless channels with disjoint input alphabets and disjoint output alphabets into a block-diagonal channel. The block label $B$ is determined by both input and output. If it has law $\alpha$, the mutual information is at most $H(\alpha )+{\sum }_i{\alpha }_i{C}_i$, attained by using each block's capacity-achieving conditional input law. Put $S={\sum }_i{2}^{C_i}$ and $r_i=2^{C_i}/S$. The expression equals ${\log }_{2}S-d(\alpha ,r)$, so Gibbs inequality proves the displayed capacity, attained for block probabilities ${\alpha }_i=r_i$. Even blocks of capacity zero contribute distinguishable block choices; three disjoint zero-capacity blocks give capacity ${\log }_{2}3$.

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 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.

Channel capacity is the best reliable information rate available through a specified communication channel. For a discrete memoryless channel with finite input and output alphabets, fixed transition probabilities $W(y\mid x)$, and no input-cost constraint, it isin bits per channel use, when the mutual information uses base-two logarithms. The maximization varies the input probability distribution, while keeping the communication channel fixed. A large input alphabet or a large output information entropy alone does not determine how much information gets through: the receiver needs information about the input, rather than merely unpredictable output.

The operational meaning comes from the Shannon second coding theorem. A block code represents one of $M$ possible messages by a word of length $n$, giving a rate ${\log }_{2}M/n$ bits per use. Take the message label from the uniform distribution on a finite set of those $M$ choices when measuring average decoding-error probability. For every fixed rate $R<C$, there are sequences of such block codes whose decoding-error probability tends to zero as $n$ grows; a rate above $C$ cannot have vanishing decoding-error probability. This is an asymptotic limit, rather than a promise that an arbitrary finite block code at a rate below $C$ works well. See MIT 18.310, Shannon's Noisy Coding Theorem, sections 1–2.

For a binary symmetric channel with crossover probability $p=0.1$, the binary symmetric channel capacity is approximately $0.53100441$ bits per use. Thus a binary code rate $R=1/2$ lies below the limit, while $R=3/4$ lies above it. At $R=1/2$, two transmitted symbols represent one message bit on average; the redundancy helps distinguish messages after noise. This does not split individual physical symbols into fractional pieces.

The result is useful because it separates two tasks. Computing channel capacity establishes the target imposed by the transition probabilities; constructing an effective block code attempts to approach that target with acceptable delay and decoding effort. The surprise is that reliability can improve indefinitely without forcing every positive rate to disappear. In his 1948 paper, Shannon defines noisy channel capacity in section 12 and develops its operational significance in section 13, Theorem 11. His original formulation uses information per unit time; the fixed-duration channel-use convention here expresses the same rate question per symbol. ^[ref].

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 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.

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]

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.

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.

If graphs $G_i$ cover the edges of an $n$-vertex graph with independence number at most $\alpha$, their coloring entropy weights satisfy the displayed bound. A random vertex's color is recorded in every covering graph containing it; independent dummy colors with matching marginal laws fill the other positions. Conditional on all recorded colors, compatible vertices form an independent set, leaving conditional entropy at most ${\log }_2\alpha$. The mutual information carried by the colors is at most $n^{-1}{\sum }_{i}w(G_i)$, proving the bound.

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.

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.

A finite-alphabet erasure channel transmits the input symbol unchanged with probability $1-f$ and replaces it by a distinct erasure flag with probability $f$, independently of the symbol. Given the flag, the posterior remains the input distribution; otherwise the input is known. Thus its mutual information is $(1-f)H(X)$.