2. Inequalities and Their Consequences

The definitions of entropy, relative entropy, and mutual information become useful when they produce limits that hold for every probability model. This note develops the main inequalities. It continues Entropy and Mutual Information.

We use discrete random variables and base-2 logarithms throughout.

Notation convention

Uppercase letters such as $X$, $Y$, and $Z$ denote random variables; lowercase $x$, $y$, and $z$ denote realizations; and calligraphic letters such as $\mathcal{X}$ denote alphabets. Abstract PMFs are written $p(x)$ and $q(x)$, following the book. For a binary random variable with success probability $t$, its entropy is $H(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$.

---

1. Jensen’s Inequality and Its Consequences

1.1 Convexity and concavity

A function $f$ is convex on an interval if, for any $x_1,x_2$ in that interval and $0\le \lambda \le 1$,

$$f(\lambda x_1+(1-\lambda )x_2)\le \lambda f(x_1)+(1-\lambda )f(x_2).$$

Geometrically, the graph of a convex function lies below every chord connecting two points on the graph. A function is concave when $-f$ is convex, so its graph lies above its chords. If $f^{\prime \prime }(x)\ge 0$ throughout an interval, then $f$ is convex there; strict positivity gives strict convexity.

Figure 1: For an equally weighted two-point distribution, evaluating $f$ at the average input lies no higher than averaging the corresponding function values.

1.2 Jensen’s inequality

If $f$ is convex and $X$ is a random variable, then

$$\boxed{f(\mathbb{E}[X])\le \mathbb{E}[f(X)]}.$$

For a concave function, the inequality reverses. If $f$ is strictly convex, equality holds only when $X$ is constant with probability one.

Jensen’s inequality turns a pointwise shape property into a statement about expectations. This is why convexity appears repeatedly in information theory: entropy and relative entropy are themselves expectations of logarithmic quantities.

A two-point example

Let $X$ equal $1$ or $3$ with probability $1/2$, and choose the convex function $f(x)=x^2$. Then

$$f(\mathbb{E}[X])=f(2)=4,$$

whereas

$$\mathbb{E}[f(X)]=\frac{1}{2}(1^2)+\frac{1}{2}(3^2)=5.$$

Thus $f(\mathbb{E}[X])<\mathbb{E}[f(X)]$.

Proof

Let

$$\mu =\mathbb{E}[X]$$

be the mean of $X$. The key geometric fact is that a differentiable convex function lies above every tangent line. In particular, the tangent at $\mu$ gives the pointwise bound

$$f(x)\ge f(\mu )+f^{\prime }(\mu )(x-\mu )$$

for every possible value $x$ of $X$.

We can therefore replace $x$ by the random variable $X$. The inequality then holds for every value that $X$ can take:

$$f(X)\ge f(\mu )+f^{\prime }(\mu )(X-\mu ).$$

Expectation is monotone: if random variables $A\ge B$ with probability one, then

$$\mathbb{E}[A]\ge \mathbb{E}[B].$$

This follows because $A-B\ge 0$, so $\mathbb{E}[A-B]=\mathbb{E}[A]-\mathbb{E}[B]\ge 0$. Applying this rule to the pointwise tangent inequality gives

$$\begin{array}{rl}\mathbb{E}[f(X)]& \ge \mathbb{E}\left[f(\mu )+f^{\prime }(\mu )(X-\mu )\right]\\ & =f(\mu )+f^{\prime }(\mu )(\mathbb{E}[X]-\mu )\\ & =f(\mu ).\end{array}$$

The last term vanishes because $\mu =\mathbb{E}[X]$; deviations above and below the mean average to zero. Substituting the definition of $\mu$ now gives

$$\mathbb{E}[f(X)]\ge f(\mathbb{E}[X]),$$

which is Jensen’s inequality.

If $f$ is not differentiable at $\mu$, the same argument uses any supporting line at $\mu$ instead of a tangent. For a concave function, apply the result to $-f$, which reverses the inequality.

1.3 The information inequality

Relative entropy measures the cost of using the wrong model: it describes data from a distribution $p$ using a different model $q$. Because the true probabilities match the data-generating process, replacing them with $q$ cannot improve the average description.

Suppose a recommendation model was trained on last year’s behavior, but current users now behave differently. Relative entropy measures the mismatch between current behavior and the outdated model, and the information inequality guarantees that this mismatch cost is never negative.

Applying Jensen’s inequality to the concave function ${\log }_{2}t$ makes this guarantee precise:

$$\boxed{D(p\parallel q)\ge 0},$$

with equality if and only if $p(x)=q(x)$ for every $x$. The full support-aware proof appears in the preceding note.

Proof

If $q(x)=0$ for some $x$ with $p(x)>0$, then $D(p\parallel q)=+\infty$, so the inequality is immediate. Otherwise, we use

$$\ln t\le t-1,t>0.$$

This inequality comes from the fact that the concave function $\ln t$ lies below its tangent at $t=1$. Substitute $t=q(x)/p(x)$. Multiplying by the nonnegative number $p(x)$ preserves the inequality, and summing preserves it as well:

$$\begin{array}{rl}-D(p\parallel q)& =\sum _{x:p(x)>0}p(x){\log }_2\frac{q(x)}{p(x)}\\ & \le \frac{1}{\ln 2}\sum _{x:p(x)>0}p(x)\left(\frac{q(x)}{p(x)}-1\right)\\ & \le \frac{1}{\ln 2}\left(\sum _{x:p(x)>0}q(x)-1\right)\le 0.\end{array}$$

The last inequality uses ${\sum }_{x:p(x)>0}q(x)\le {\sum }_{x}q(x)=1$. We have shown that $-D(p\parallel q)\le 0$; multiplying by $-1$ reverses the inequality and gives $D(p\parallel q)\ge 0$.

Equality in $\ln t\le t-1$ requires $t=1$. Thus $q(x)=p(x)$ wherever $p(x)>0$, and equality of the total masses forces $q$ to have no mass elsewhere. Hence equality holds exactly when $p=q$.

Several fundamental results follow immediately.

1.3.1 Mutual information is nonnegative

Mutual information measures how much knowing one variable reduces uncertainty about another. Conditional mutual information measures the remaining reduction after some context is already known.

In medical prediction, for example, $X$ might be a diagnosis and $Y$ a lab result. The quantity $I(X;Y)$ measures how informative the result is, while $I(X;Y\mid Z)$ asks whether it still adds value after the patient’s history $Z$ is known.

Both quantities are nonnegative because they are relative entropies, or averages of relative entropies:

$$I(X;Y)=D(p(x,y)\parallel p(x)p(y))\ge 0.$$

Equality holds exactly when $p(x,y)=p(x)p(y)$, meaning $X$ and $Y$ are independent. Similarly,

$$I(X;Y\mid Z)\ge 0,$$

with equality exactly when $X$ and $Y$ are conditionally independent given $Z$.

Proof

Mutual information is the relative entropy between the true joint PMF and the product of its marginals:

$$I(X;Y)=D(p(x,y)\parallel p(x)p(y))\ge 0,$$

so nonnegativity follows directly from $D(p\parallel q)\ge 0$. Equality holds exactly when $p(x,y)=p(x)p(y)$, which is the definition of independence.

For conditional mutual information, fix a value $z$. The divergence

$$D(p(x,y\mid z)\parallel p(x\mid z)p(y\mid z))$$

is nonnegative. Conditional mutual information averages these divergences:

$$I(X;Y\mid Z)=\sum _{z}p(z)D(p(x,y\mid z)\parallel p(x\mid z)p(y\mid z)).$$

Every weight $p(z)$ is nonnegative, so the weighted average is nonnegative. It is zero exactly when $X$ and $Y$ are conditionally independent for every $z$ with $p(z)>0$.

1.3.2 The uniform distribution maximizes entropy

For a fixed finite alphabet, uncertainty is largest when every outcome has the same probability. Any bias makes some outcomes easier to anticipate.

A password generator illustrates this idea. It is hardest to predict when it chooses uniformly from all allowed strings; favoring common words or patterns lowers its entropy even though the possible strings are unchanged.

Thus, for any random variable on a finite alphabet $\mathcal{X}$,

$$\boxed{H(X)\le {\log }_2|\mathcal{X}|},$$

with equality if and only if $X$ is uniform.

Proof

Let $u(x)=1/|\mathcal{X}|$ be the uniform PMF. Compare $p$ with $u$ using relative entropy:

$$\begin{array}{rl}D(p\parallel u)& =\sum _{x}p(x){\log }_2\frac{p(x)}{1/|\mathcal{X}|}\\ & =\sum _{x}p(x){\log }_{2}p(x)+\sum _{x}p(x){\log }_2|\mathcal{X}|\\ & =-H(X)+{\log }_2|\mathcal{X}|.\end{array}$$

The last line uses ${\sum }_{x}p(x)=1$. Since relative entropy is nonnegative,

$$0\le {\log }_2|\mathcal{X}|-H(X),$$

which rearranges to $H(X)\le {\log }_2|\mathcal{X}|$. Equality holds exactly when $D(p\parallel u)=0$, or equivalently when $p=u$.

1.3.3 Conditioning reduces entropy on average

Conditioning means updating uncertainty after observing additional information. Since an observer can ignore information that is not useful, access to it cannot increase uncertainty on average.

For example, a navigation system may be uncertain about travel time $X$. Live traffic data $Y$ will not explain every delay, but it cannot worsen the system’s best average prediction. This leads to the inequality

$$\boxed{H(X\mid Y)\le H(X)}.$$

Equality holds if and only if $X$ and $Y$ are independent. This is an average statement: a particular observation $Y=y$ can increase uncertainty, even though averaging over all $y$ cannot.

Proof

Start from the mutual-information identity

$$I(X;Y)=H(X)-H(X\mid Y).$$

We have already proved that $I(X;Y)\ge 0$. Substituting this bound into the identity gives

$$H(X)-H(X\mid Y)\ge 0.$$

Adding $H(X\mid Y)$ to both sides yields $H(X\mid Y)\le H(X)$. Equality holds exactly when $I(X;Y)=0$, which is equivalent to independence.

The same idea extends to several variables. Adding their individual entropies treats them as unrelated, whereas dependence creates shared information and lowers their joint uncertainty.

Neighboring image pixels provide a practical example: encoding each pixel separately counts repeated structure, whereas a joint codec can exploit those dependencies. Combining the entropy chain rule with the fact that conditioning reduces entropy gives

$$\boxed{H(X_1,\dots ,X_n)\le \sum _{i=1}^{n}H(X_i)},$$

with equality exactly when $X_1,\dots ,X_n$ are mutually independent.

Proof

The entropy chain rule decomposes joint uncertainty into successive conditional uncertainties:

$$H(X_1,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1}).$$

Conditioning reduces entropy, so each term satisfies

$$H(X_i\mid X_1,\dots ,X_{i-1})\le H(X_i).$$

Adding these term-by-term inequalities gives

$$H(X_1,\dots ,X_n)\le \sum _{i=1}^{n}H(X_i).$$

Equality requires equality at every step, meaning that each $X_i$ is independent of its predecessors. This is equivalent to mutual independence.

---

2. The Log-Sum Inequality

The log-sum inequality compares a fine-grained collection of ratios with the single ratio obtained after aggregation. Because combining categories discards detail, it cannot make two collections more distinguishable.

For example, two services may have different failure patterns across error categories, yet a dashboard reporting only total failures can hide that difference. To describe this loss mathematically, take nonnegative numbers $a_1,\dots ,a_n$ and $b_1,\dots ,b_n$, and define

$$A=\sum _{i=1}^n{a}_i,B=\sum _{i=1}^n{b}_i.$$

The log-sum inequality states

$$\boxed{\sum _{i=1}^n{a}_i{\log }_2\frac{a_i}{b_i}\ge A{\log }_2\frac{A}{B}}.$$

Equality holds when the ratios $a_i/b_i$ are constant wherever the terms have positive mass. As with relative entropy, a positive $a_i$ paired with $b_i=0$ makes the left side infinite.

Proof from Jensen's inequality

Assume first that $B>0$ and every relevant $b_i>0$. Let

$$f(t)=t{\log }_{2}t.$$

This function is convex for $t>0$. Define weights and inputs by

$${\alpha }_i=\frac{b_i}{B},t_i=\frac{a_i}{b_i}.$$

The numbers ${\alpha }_i$ are valid weights because they are nonnegative and

$$\sum _i{\alpha }_i=\frac{{\sum }_i{b}_i}{B}=1.$$

Jensen’s inequality therefore gives

$$\sum _i{\alpha }_{i}f(t_i)\ge f\left(\sum _i{\alpha }_i{t}_i\right).$$

Now simplify each side. On the left,

$$B\sum _i{\alpha }_{i}f(t_i)=\sum _i{a}_i{\log }_2\frac{a_i}{b_i}.$$

Inside the function on the right,

$$\sum _i{\alpha }_i{t}_i=\sum _i\frac{b_i}{B}\frac{a_i}{b_i}=\frac{A}{B}.$$

Multiplying Jensen’s inequality by the positive number $B$ preserves its direction and produces

$$\sum _i{a}_i{\log }_2\frac{a_i}{b_i}\ge A{\log }_2\frac{A}{B}.$$

Zero-valued terms follow by continuity. If $a_i>0$ while $b_i=0$, the left side is infinite and the inequality is automatic.

2.1 Convexity of relative entropy

Joint convexity describes what happens when pairs of distributions are mixed. If the mixture label is hidden, information that could help distinguish the distributions is lost.

For example, a model may behave differently across user groups. If an evaluation pools the groups and hides their identities, distribution shifts can appear smaller than they do within each group. This effect is captured by joint convexity: for $0\le \lambda \le 1$,

$$\boxed{D(\lambda p_1+(1-\lambda )p_2\parallel \lambda q_1+(1-\lambda )q_2)\le \lambda D(p_1\parallel q_1)+(1-\lambda )D(p_2\parallel q_2)}.$$

Mixing two pairs of distributions cannot create more divergence than the corresponding mixture of their divergences.

Proof

Define the mixture PMFs

$$\bar{p}(x)=\lambda p_1(x)+(1-\lambda )p_2(x),\bar{q}(x)=\lambda q_1(x)+(1-\lambda )q_2(x).$$

For each fixed $x$, apply the log-sum inequality to

$$\begin{array}{rlrl}{a}_1& =\lambda p_1(x),& a_2& =(1-\lambda )p_2(x),\\ b_1& =\lambda q_1(x),& b_2& =(1-\lambda )q_2(x).\end{array}$$

Their sums are $\bar{p}(x)$ and $\bar{q}(x)$, so log-sum gives

$$\begin{array}{rl}& \lambda p_1(x){\log }_2\frac{p_1(x)}{q_1(x)}+(1-\lambda )p_2(x){\log }_2\frac{p_2(x)}{q_2(x)}\\ & \ge \bar{p}(x){\log }_2\frac{\bar{p}(x)}{\bar{q}(x)}.\end{array}$$

Summing this pointwise inequality over $x$ turns the left side into $\lambda D(p_1\parallel q_1)+(1-\lambda )D(p_2\parallel q_2)$ and the right side into $D(\bar{p}\parallel \bar{q})$, proving joint convexity.

2.2 Concavity of entropy

Entropy concavity describes the uncertainty introduced by mixing distributions. When the source label is hidden, the observer must also account for which source produced the sample.

For example, a warehouse may receive predictable product types from each supplier. Once supplier labels are removed and shipments are pooled, the product stream becomes harder to predict. Therefore, the mixture entropy satisfies

$$\boxed{H(\lambda p_1+(1-\lambda )p_2)\ge \lambda H(p_1)+(1-\lambda )H(p_2)}.$$

Thus, hiding which distribution generated a sample can only increase uncertainty. This also explains the bowed-down shape of the binary entropy curve.

Proof

Introduce a selector $S\sim \mathrm{Bernoulli}(\lambda )$. When $S=1$, draw $X$ from $p_1$; when $S=0$, draw it from $p_2$. If we do not observe $S$, the marginal PMF of $X$ is

$$p_X=\lambda p_1+(1-\lambda )p_2.$$

If $S$ is observed, conditional entropy averages the entropy of the selected source:

$$H(X\mid S)=\lambda H(p_1)+(1-\lambda )H(p_2).$$

Conditioning reduces entropy, so $H(X)\ge H(X\mid S)$. Substituting the two expressions gives

$$H(\lambda p_1+(1-\lambda )p_2)\ge \lambda H(p_1)+(1-\lambda )H(p_2),$$

which proves concavity.

2.3 Concavity and convexity of mutual information

Mutual information responds differently depending on whether we change the input distribution or the channel. Mixing input strategies can improve how fully a fixed channel is used, whereas mixing channel behaviors hides which channel acted.

An engineer encounters both cases when designing a communication link: the signal frequencies can be optimized for a fixed channel, while unpredictable operating conditions effectively mix several channels. These cases lead to two opposite curvature properties.

First, for a fixed channel $p(y\mid x)$, let

$$p_{\lambda }(x)=\lambda p_1(x)+(1-\lambda )p_2(x),0\le \lambda \le 1.$$

Then mutual information is concave in the input PMF:

$$\boxed{I_{p_{\lambda }}(X;Y)\ge \lambda I_{p_1}(X;Y)+(1-\lambda )I_{p_2}(X;Y)}.$$

For a fixed input PMF $p(x)$, let the channel be the mixture

$$p_{\lambda }(y\mid x)=\lambda p_1(y\mid x)+(1-\lambda )p_2(y\mid x).$$

Mutual information is convex in the channel:

$$\boxed{I_{p_{\lambda }}(X;Y)\le \lambda I_{p_1}(X;Y)+(1-\lambda )I_{p_2}(X;Y)}.$$

The subscripts indicate which input distribution or channel is used to calculate the mutual information defined in the first note. Concavity in $p(x)$ is important when maximizing mutual information over input distributions, while convexity in $p(y\mid x)$ says that mixing channels cannot exceed the corresponding average mutual information.

Proof

Concavity in the input. For a fixed channel, use

$$I(X;Y)=H(Y)-H(Y\mid X).$$

The output PMF

$$p(y)=\sum _{x}p(x)p(y\mid x)$$

depends linearly on the input PMF. Since entropy is concave in a PMF, $H(Y)$ is therefore concave in $p(x)$. Meanwhile,

$$H(Y\mid X)=\sum _{x}p(x)H(Y\mid X=x)$$

is linear in $p(x)$ because the channel—and hence every $H(Y\mid X=x)$—is fixed. Subtracting a linear function from a concave function preserves concavity, so $I(X;Y)$ is concave in the input PMF.

Convexity in the channel. For a fixed input PMF, write

$$I(X;Y)=D(p(x,y)\parallel p(x)p(y)).$$

Mixing two channels mixes their joint PMFs because $p(x,y)=p(x)p(y\mid x)$. It also mixes their output PMFs because $p(y)={\sum }_{x}p(x)p(y\mid x)$. Thus both arguments of the divergence vary linearly with the channel. Applying joint convexity of relative entropy to these two arguments gives convexity of $I(X;Y)$ in $p(y\mid x)$.

---

3. The Data-Processing Inequality

The data-processing inequality says that processing a variable cannot create new information about its source. A later representation may reorganize useful information, but it cannot recover distinctions discarded by an earlier stage.

For example, let $X$ be a scene, $Y$ the detailed sensor image captured by a camera, and $Z$ a compressed thumbnail. The thumbnail can make some image features easier to use, but it cannot restore scene details discarded during image capturing. This flow is represented by the Markov chain

$$X\to Y\to Z$$

where $Z$ is conditionally independent of $X$ once $Y$ is known. Equivalently, their joint PMF factors as

$$\boxed{p(x,y,z)=p(x)p(y\mid x)p(z\mid y)}.$$

Figure 2: Once $Y$ is known, $Z$ receives no additional information directly from $X$.

The data-processing inequality says

$$\boxed{X\to Y\to Z⟹I(X;Z)\le I(X;Y)}.$$

No deterministic or randomized processing of $Y$ can increase the information it contains about $X$.

3.1 Proof using the chain rule

We evaluate $I(X;Y,Z)$ in two ways using the chain rule for mutual information. The first order reveals $Z$ and then $Y$:

$$I(X;Y,Z)=I(X;Z)+I(X;Y\mid Z).$$

Reversing the order first reveals $Y$ and then $Z$:

$$I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y).$$

Because $X\to Y\to Z$ is a Markov chain, $X$ and $Z$ are conditionally independent once $Y$ is known. Therefore,

$$I(X;Z\mid Y)=0.$$

Equating the two chain-rule expansions now gives

$$I(X;Z)+I(X;Y\mid Z)=I(X;Y).$$

Conditional mutual information is nonnegative, so

$$I(X;Y)-I(X;Z)=I(X;Y\mid Z)\ge 0.$$

Rearranging proves $I(X;Z)\le I(X;Y)$. Equality holds precisely when $I(X;Y\mid Z)=0$, meaning that $Z$ preserves all information in $Y$ relevant to $X$.

The gap $I(X;Y\mid Z)$ is the information about $X$ discarded when $Y$ is replaced by $Z$. Equality means that the processing preserves everything in $Y$ relevant to $X$.

If $Z=g(Y)$ is a deterministic function, then $X\to Y\to g(Y)$ automatically, giving

$$I(X;g(Y))\le I(X;Y).$$

This formalizes a useful principle: transforming, compressing, or summarizing data may preserve information, but it cannot manufacture information about the source.

The same chain-rule identities also give a conditional form. If $X\to Y\to Z$, then

$$I(X;Y\mid Z)=I(X;Y)-I(X;Z)\le I(X;Y).$$

The Markov-chain assumption matters: conditioning on an arbitrary $Z$ can sometimes increase the measured dependence between $X$ and $Y$.

---

4. Sufficient Statistics

4.1 The main idea

A dataset often contains more detail than we need to learn an unknown quantity. A statistic is any summary computed from the data. It is sufficient when the summary retains everything in the original data that is relevant to the unknown quantity.

In plain language:

After seeing a sufficient statistic, looking at the full dataset teaches us nothing more about the quantity we want to estimate.

4.2 Coin-flip example

Suppose a coin has an unknown probability $\theta$ of landing heads. We flip it $n$ times and record the entire sequence. For example,

$$H,T,H,H,T.$$

To learn $\theta$, the order is irrelevant; only the number of heads matters. Define

$$S=\text{number of heads}.$$

If a particular sequence contains $s$ heads, its probability is

$$\mathrm{Pr}(\text{that sequence}\mid \theta )={\theta }^s(1-\theta {)}^{n-s}.$$

The likelihood depends on the sequence only through $s$. Thus, once we know the head count $S$, the original ordering contains no additional information about $\theta$. The count $S$ is therefore a sufficient statistic.

This is a genuine compression: instead of retaining all $n$ outcomes, we retain one number between $0$ and $n$.

4.3 Information-theoretic statement

A statistic is sufficient when it preserves all information in the full dataset about an unknown parameter. It may discard other details, but those details must provide no additional evidence about the parameter once the statistic is known.

For example, for repeated Gaussian measurements with known variance, the sample mean is sufficient for the unknown population mean. An analyst can retain that summary without keeping the order of every observation. To state this preservation precisely, we use:

• $\Theta$: the unknown parameter, treated as a random variable so mutual information is defined;
• $X^n=(X_1,\dots ,X_n)$: the complete dataset;
• $T(X^n)$: a summary computed from that dataset.

Because the summary is computed from the data, information flows as

$$\Theta \to X^n\to T(X^n).$$

The data-processing inequality gives

$$I(\Theta ;T(X^n))\le I(\Theta ;X^n).$$

The summary cannot contain parameter information that was absent from the full dataset. It is sufficient precisely when equality holds:

$$\boxed{I(\Theta ;T(X^n))=I(\Theta ;X^n)}.$$

The left side measures what the summary tells us about the parameter; the right side measures what the full dataset tells us. Equality means the summary preserves all parameter-relevant information.

One may therefore replace $X^n$ by $T(X^n)$ when inferring $\Theta$ without losing relevant information. Sufficiency does not require reconstructing the dataset; discarded details need only be irrelevant to $\Theta$.

Equivalent conditional-independence statement

Formally, $T(X^n)$ is sufficient for $\Theta$ when

$$\Theta \perp X^n\mid T(X^n).$$

Once $T(X^n)$ is known, the parameter $\Theta$ and the remaining details of $X^n$ are conditionally independent. Equivalently, information flows in both directions through the statistic:

$$\Theta \to X^n\to T(X^n)\text{and}\Theta \to T(X^n)\to X^n.$$

This viewpoint connects information theory to maximum likelihood estimation. A minimal sufficient statistic goes one step further: it retains all parameter-relevant information using the coarsest possible sufficient summary.

---

5. Fano’s Inequality

Imagine that a doctor must identify a disease using only a medical scan. If several diseases produce nearly identical scans, then even the best image-based classifier will sometimes choose the wrong diagnosis. The difficulty is not necessarily a weakness of the classifier: the scan itself may not contain enough information to distinguish the diseases reliably.

Let $X$ be the true diagnosis, let $Y$ be the observed scan, and let the classifier’s estimate be

$$\hat{X}=g(Y).$$

Here $X$ takes values in a finite set $\mathcal{X}$ of possible diagnoses. The conditional entropy $H(X\mid Y)$ measures how much uncertainty about the diagnosis remains after the scan is observed, while $P_e$ is the probability that the estimate is wrong. Fano’s inequality connects these quantities: if $H(X\mid Y)$ is large, then $P_e$ cannot be very small. It therefore shows that no choice of classifier can overcome a fundamental lack of information in the observation.

The variables form the Markov chain $X\to Y\to \hat{X}$. Define the error indicator and probability of error by

$$E=1\{\hat{X}\ne X\},P_e=\mathrm{Pr}(\hat{X}\ne X).$$

Figure 3: Fano’s inequality connects the remaining uncertainty $H(X\mid Y)$ to the probability that an estimator fails.

Fano’s inequality states

$$\boxed{H(P_e)+P_e{\log }_2|\mathcal{X}|\ge H(X\mid \hat{X})\ge H(X\mid Y)}.$$

If $\hat{X}$ is restricted to the same alphabet $\mathcal{X}$, the first term can be strengthened to

$$\boxed{H(X\mid Y)\le H(P_e)+P_e{\log }_2(|\mathcal{X}|-1)}.$$

In particular, $P_e=0$ requires $H(X\mid Y)=0$.

5.1 Proof

The error indicator $E=1\{\hat{X}\ne X\}$ is completely determined once $X$ and $\hat{X}$ are known. Therefore,

$$H(E\mid X,\hat{X})=0.$$

Use the conditional entropy chain rule in two orders. First,

$$H(E,X\mid \hat{X})=H(X\mid \hat{X})+H(E\mid X,\hat{X})=H(X\mid \hat{X}).$$

Reversing the order gives

$$H(E,X\mid \hat{X})=H(E\mid \hat{X})+H(X\mid E,\hat{X}).$$

We bound these two terms separately. Conditioning reduces entropy, so

$$H(E\mid \hat{X})\le H(E)=H(P_e).$$

For the second term, split according to whether an error occurred:

$$\begin{array}{rl}H(X\mid E,\hat{X})& =(1-P_e)H(X\mid E=0,\hat{X})\\ & +P_{e}H(X\mid E=1,\hat{X}).\end{array}$$

If $E=0$, then $X=\hat{X}$ and the first entropy is zero. If $E=1$ and $\hat{X}\in \mathcal{X}$, then $X$ can be any of the remaining $|\mathcal{X}|-1$ values. The maximum-entropy bound therefore gives

$$H(X\mid E,\hat{X})\le P_e{\log }_2(|\mathcal{X}|-1).$$

Combining the two chain-rule expansions and the two bounds yields

$$H(X\mid \hat{X})\le H(P_e)+P_e{\log }_2(|\mathcal{X}|-1).$$

Finally, $\hat{X}=g(Y)$ is a processed version of $Y$. Data processing gives $I(X;\hat{X})\le I(X;Y)$. Subtracting both mutual informations from $H(X)$ reverses this into

$$H(X\mid \hat{X})\ge H(X\mid Y).$$

Combining the upper and lower bounds on $H(X\mid \hat{X})$ proves Fano’s inequality. If $\hat{X}$ is not restricted to $\mathcal{X}$, use the looser bound ${\log }_2|\mathcal{X}|$ in the error case.

Since $H(P_e)\le 1$, a weaker but convenient rearrangement is

$$\boxed{P_e\ge \frac{H(X\mid Y)-1}{{\log }_2|\mathcal{X}|}}.$$

This form is especially useful for impossibility results: prove that substantial conditional entropy remains, and a nontrivial lower bound on estimation error follows.

For uniform $X$, reliable recovery requires $I(X;Y)$ to be close to ${\log }_2|\mathcal{X}|$; otherwise the hypotheses cannot be distinguished reliably. This is a necessary condition for low error, not a guarantee that a particular estimator achieves it.

A related collision-probability bound

The collision-probability bound relates entropy to the chance that two independent draws produce the same outcome. Concentrated, low-entropy distributions create more collisions because a few outcomes receive most of the probability mass.

For example, if an identifier generator favors some identifiers, those values are selected repeatedly and collisions become common. A more uniform generator spreads requests across the available identifiers. To express this relationship, let $X$ and $X^{\prime }$ be independent draws from $p(x)$. Their probability of matching is

$$\mathrm{Pr}(X=X^{\prime })=\sum _{x\in \mathcal{X}}{p}^2(x).$$

Rewrite the sum as an expectation with respect to $X\sim p$:

$$\sum _x{p}^2(x)=\sum _{x}p(x)p(x)={\mathbb{E}}_p[p(X)]={\mathbb{E}}_p\left[2^{{\log }_{2}p(X)}\right].$$

The function $2^t$ is convex, so Jensen’s inequality gives

$${\mathbb{E}}_p\left[2^{{\log }_{2}p(X)}\right]\ge 2^{{\mathbb{E}}_p[{\log }_{2}p(X)]}.$$

By the definition of entropy, ${\mathbb{E}}_p[{\log }_{2}p(X)]=-H(X)$. Therefore,

$$\boxed{\mathrm{Pr}(X=X^{\prime })\ge 2^{-H(X)}},$$

with equality if and only if $p(X)$ is constant on the support of $p$, meaning that $X$ is uniform on its support.

More generally, if $X\sim p$ and $X^{\prime }\sim r$ are independent, then

$$\mathrm{Pr}(X=X^{\prime })=\sum _{x}p(x)r(x)={\mathbb{E}}_p\left[2^{{\log }_{2}r(X)}\right].$$

Applying Jensen again and using

$${\mathbb{E}}_p[{\log }_{2}r(X)]=-H(p)-D(p\parallel r)$$

gives

$$\mathrm{Pr}(X=X^{\prime })\ge 2^{-H(p)-D(p\parallel r)},$$

and exchanging $p$ and $r$ gives

$$\mathrm{Pr}(X=X^{\prime })\ge 2^{-H(r)-D(r\parallel p)}.$$

---

6. Summary

Result	Statement	Main message
Jensen	$f(\mathbb{E}X)\le \mathbb{E}f(X)$ for convex $f$	Convexity controls expectations
Information inequality	$D(p\parallel q)\ge 0$	Distribution mismatch is nonnegative
Maximum entropy	$H(X)\le {\log }_2|\mathcal{X}|$	Uniformity maximizes uncertainty
Conditioning	$H(X\mid Y)\le H(X)$	Information cannot hurt on average
Log-sum	${\sum }_i{a}_i\log (a_i/b_i)\ge A\log (A/B)$	Aggregation reduces distinguishability
Mutual information	Concave in $p(x)$; convex in $p(y\mid x)$	Its curvature depends on what is held fixed
Data processing	$X\to Y\to Z\Rightarrow I(X;Z)\le I(X;Y)$	Processing cannot create information
Sufficiency	$I(\Theta ;T(X^n))=I(\Theta ;X^n)$	A sufficient statistic loses no parameter information
Fano	$H(X\mid Y)\le H(P_e)+P_e{\log }_2(|\mathcal{X}|-1)$	Uncertainty forces estimation error

Together, these results connect the geometry of convex functions to limits on compression, inference, statistical summarization, and decoding.

---

Reference

Thomas M. Cover and Joy A. Thomas. Elements of Information Theory, 2nd ed., Sections 2.6-2.10. Wiley, 2006.