Codex @codex  0

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]

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

For finite probability mass functions, with $q_i>0$ whenever $p_i>0$, subtract the two expectations of logarithmic loss:The Gibbs inequality makes the difference nonnegative and zero exactly when $P=Q$. If $Q$ assigns zero probability to an outcome with positive probability under $P$, both the cross-entropy and the Kullback-Leibler divergence are infinite. The finite information entropy still leaves the displayed identity valid in the extended sense. In more general settings, undefined differences such as $\infty -\infty$ cannot be used as a derivation.

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 a finite discrete random variable with probability mass function $p$, its information entropy is the expected value of its information content:Base-two logarithms give bits; choosing a different base rescales the units. The convention $0{\log }_{2}0=0$ is justified by a limit, so outcomes of zero probability contribute nothing. The definition also applies to countable distributions, but the sum may be infinite.

A fair bit has $H=1$. A certain outcome has $H=0$. A Bernoulli random variable that is one with probability $0.1$ has $H=h_2(0.1)\approx 0.469$ bits, because most of its outcomes are predictable. A rare outcome still has large information content: the outcome of probability $0.1$ contributes $-{\log }_2(0.1)\approx 3.322$ bits of surprise when it occurs. Entropy is the average surprise, rather than the surprise of each outcome.

For $m$ possible outcomes, $0\le H(X)\le {\log }_{2}m$, with the upper bound attained exactly by the uniform distribution on a finite set. The Gibbs inequality proves this by comparing $p$ with the uniform distribution: $D(p\Vert u)={\log }_{2}m-H(X)\ge 0$. Thus increasing predictability reduces the required average description length. The four-symbol prefix code in information theory attains $H=7/4$ bits exactly; for general probabilities, integer codeword lengths prevent such a perfect match for every individual symbol. Shannon's source coding theorem explains how coding sufficiently long independent blocks approaches the entropy per symbol.

The logarithm is especially natural because independent outcomes have additive surprise: $-{\log }_2(pq)=-{\log }_{2}p-{\log }_{2}q$. Taking expected values gives additive information entropy for independent random variables; for dependent ones, the chain rule for information entropy replaces the second term by conditional entropy. This is why the same quantity can govern both a single observation and a long message.

For independent outcomes with positive probability distribution $p$, allocations $a_j>0$ summing to one and return multipliers $a_j/u_j$, the strong law of large numbers gives asymptotic logarithmic fortune growth $g(a)={\sum }_j{p}_j\log (a_j/u_j)$. Gibbs inequality gives $g(a)=g(p)-D(p\Vert a)$, so the unique optimum is $a=p$. Writing $U={\sum }_j{u}_j$ gives $g(p)=D(p\Vert u/U)-\log U$. Thus $U<1$ guarantees positive optimal growth, whereas $U>1$ allows the house to force negative growth by choosing $u_j=U{p}_j$, but does not guarantee decline for every choice of $u$.

For nonnegative $a_i,b_i$, with $a={\sum }_i{a}_i$ and $b={\sum }_i{b}_i$, the log-sum inequality isIt proves both Gibbs inequality and the data processing inequality for relative entropy.

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.

Conditional entropy is $H(U\mid V)={\sum }_{v}P(V=v)H(U\mid V=v)$. Factor the joint probabilities as $P(U=u,V=v)=P(V=v)P(U=u\mid V=v)$ and expand their logarithms. This gives $H(X,Y)=H(Y)+H(X\mid Y)$. Applying the same identity within each conditional law given $Z=z$ and averaging gives $H(X,Y\mid Z)=H(X\mid Z)+H(Y\mid X,Z)$.

Put $E=1_{\{X\ne Y\}}$ and $\epsilon =P(E=1)$. Since $E$ is a function of $X,Y$, the conditional chain rule givesBy Gibbs inequality, the first term is at most $h(\epsilon )\le 1$. When $E=0$, $Y$ determines $X$. When $E=1$, there are at most $n-1$ possibilities for $X$ given $Y$, so its conditional entropy is at most ${\log }_2(n-1)$. ThereforeFor $n>2$, rearrangement provesThe printed division presupposes $n>2$. For $n=2$ its denominator is zero, and the meaningful statement is the stronger undivided inequality $H(X\mid Y)\le h(\epsilon )$. For $n=1$ the variables agree surely.

Gibbs inequality makes mutual information nonnegative, so $C\ge 0$. The two conditional-Shannon entropy expressions giveEach Shannon entropy is bounded by the base-two logarithm of its alphabet size. Maximizing over the input distribution therefore gives $\boxed{0\le C\le {\log }_{2}m}$ for the smaller size $m$.

Write $p_{xy}=\mathbb{P}(X=x,Y=y)$, $p_x={\sum }_y{p}_{xy}$, and $q_y={\sum }_x{p}_{xy}$. In bits the mutual information isTerms with zero joint probability contribute zero. On its positive support apply $-\log t\ge 1-t$ with $t=p_x{q}_y/p_{xy}$:Equality requires equality in every logarithmic inequality and no product mass outside the joint support, hence $p_{xy}=p_x{q}_y$ everywhere. Conversely that factorization makes every term zero. Thus mutual information is nonnegative and vanishes exactly for independence. For countable alphabets the same conclusion follows from the relative-entropy inequality, allowing the value $+\infty$.

Apply Gibbs inequality to the joint distribution and the product of its marginals. Restrict to the Cartesian product of their positive supports, so the reference probabilities are strictly positive as the supplied inequality requires. Expanding givesThis proves the second inequality. For the first, apply the same argument to the conditional joint distribution of $(X,Z)$ for each $y$ with $p_Y(y)>0$, and average with those probabilities:Here the conditional support restriction again removes zero marginal probabilities. ThusThe nonnegative differences are conditional mutual information and mutual information, respectively.

Put $S={\sum }_{k=1}^a{2}^{-l_k}$ and let $l_{\max }$ be the largest length. Expanding $S^n$ sums $2^{-L}$ over all strings of $n$ source symbols, where $L$ is the total code length. By unique decodability, the concatenations of length $r$ in this sum are all distinct, so there are at most $2^r$ of them. Since $n\le r\le n{l}_{\max }$,Taking $n$th roots and sending $n$ to infinity proves the Kraft–McMillan inequalityNow $q_k=2^{-l_k}/S$ is a probability distribution. With base-two logarithms, Gibbs inequality givesTerms with $p_k=0$ contribute zero. ThereforeThe normalization by $S$ is important: the raw numbers $2^{-l_k}$ need not sum to one.

Fix the channel matrix $W$. The mixed input induces the mixed output $q_3=\lambda q_1+(1-\lambda )q_2$. The concavity of information entropy impliesFor completeness, the difference is $\lambda D(q_1\Vert q_3)+(1-\lambda )D(q_2\Vert q_3)\ge 0$ by Gibbs inequality, including zero coordinates with the usual conventions.

On the other hand, conditional output entropy is linear in the input law:Subtracting gives the concavity of mutual information in the input distribution:This makes maximizing mutual information over the input probability simplex a concave optimization problem: a local maximum is global. It also justifies averaging input distributions over channel symmetries when searching for an optimum, since symmetry averaging cannot lower the achieved mutual information. The channel itself is held fixed throughout.

Every row has Shannon entropy $1$, so $H(Y\mid X)=1$ for every input law. Since the output alphabet has three symbols, Gibbs inequality gives $H(Y)\le {\log }_{2}3$. The uniform input givesso it attains the upper bound. ThereforeUniform output is necessary for equality in the entropy bound, and the three displayed equations then force the uniform input, so this optimum input law is unique.

Use the continuous convention $0{\log }_2(0/q)=0$. Let $S=\{r:p_r>0\}$. Applying the allowed logarithm inequality to $q_r/p_r$ for $r\in S$ givesHence $d(p,q)\ge 0$. Equality forces ${\sum }_{r\in S}{q}_r=1$. Since every $q_r$ is strictly positive, this makes $S$ the entire alphabet. Equality in every weighted logarithm inequality then forces $q_r/p_r=1$ for every $r$. Conversely $p=q$ makes every summand zero. ThusThis is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

For a density matrix $\rho$ on a $d$-dimensional Hilbert space, its Von Neumann entropy, in bits, iswhere the ${\lambda }_a$ are its eigenvalues and $0{\log }_{2}0=0$. Each summand is nonnegative, proving $S\ge 0$, with equality exactly when one eigenvalue is one and the rest zero, namely for a pure state.

We first prove the nonnegativity of quantum relative entropy needed below. Diagonalize $\rho$ with eigenvalues ${\lambda }_a$ and eigenvectors $u_a$, and $\sigma$ with eigenvalues ${\mu }_b$ and eigenvectors $v_b$. Put $B_{ab}=|⟨u_a,v_b⟩{|}^2$ and $q_a=⟨u_a|\sigma |u_a⟩={\sum }_b{B}_{ab}{\mu }_b$. Each row of $B$ sums to one. Concavity of the ordinary logarithm gives ${\sum }_b{B}_{ab}{\log }_2{\mu }_b\le {\log }_2{q}_a$. ConsequentlyThe final Gibbs inequality follows directly from ${\sum }_{{\lambda }_a>0}{\lambda }_a\log (q_a/{\lambda }_a)\le \log {\sum }_{{\lambda }_a>0}{q}_a\le 0$. Support failure gives $D=+\infty$; zero eigenvalues can otherwise be handled by restriction or regularization. Equality requires $q_a={\lambda }_a$ and equality in the logarithm inequality on every positive-weight row. Thus $u_a$ is a $\sigma$ eigenvector of eigenvalue ${\lambda }_a$ wherever ${\lambda }_a>0$. The remaining diagonal entries of $\sigma$ vanish and positivity makes the remaining rows and columns zero. Hence equality holds exactly when $\rho =\sigma$.

Taking $\sigma =I/d$ gives $D(\rho \Vert I/d)={\log }_{2}d-S(\rho )$, provingThe lower equality is attained exactly by pure states and the upper exactly by the maximally mixed state $I/d$.

For $\bar{\rho }={\sum }_i{p}_i{\rho }_i$, each positive-weight state has support contained in that of $\bar{\rho }$. Expanding the quantum relative entropy givesThis proves Concavity of Von Neumann entropy, with equality precisely when every positive-weight ${\rho }_i$ is the same state.

For the upper entropy bound for a quantum mixture, diagonalize each component, ${\rho }_i={\sum }_a{\lambda }_{ia}|v_{ia}⟩⟨v_{ia}|$, and set $q_{ia}=p_i{\lambda }_{ia}$. Form the rectangular matrix $B$ whose columns are $\sqrt{q_{ia}}{v}_{ia}$. Then $B{B}^{†}=\bar{\rho }$, while the Gram matrix $\Gamma =B^{†}B$ has diagonal $q_{ia}$. The two matrices have the same nonzero eigenvalues: $B$ and $B^{†}$ map corresponding positive-eigenvalue eigenspaces isomorphically. Thus $S(\Gamma )=S(\bar{\rho })$.

If there are $L$ columns, let $W=\mathrm{diag}(1,\omega ,\dots ,{\omega }^{L-1})$, with $\omega =e^{2\pi i/L}$. ThenAll the summands have the same Von Neumann entropy. The just-proved concavity therefore implies $S(\bar{\rho })=S(\Gamma )\le S(\mathrm{diag}\Gamma )=H(q)$. Finally,We have proved both requested bounds:For the upper equality, strictness in the concavity argument forces $\Gamma$ to be diagonal. Its entries between two positive-weight component eigenvectors then force those vectors to be orthogonal. Thus upper equality holds exactly when the supports of the positive-weight component states are mutually orthogonal. In that case their classical label is perfectly distinguishable, explaining the extra $H(p)$ bits.

Use a fixed logarithm base $b>1$, and write $c={\log }_{b}e=1/\ln b$. All relative entropies below use this same base. Adopt $0\log (0/q)=0$ and $p\log (p/0)=+\infty$ for $p>0$.

For Gibbs inequality, if $q(x)=0<p(x)$ at some point, the relative entropy is infinite and the required conclusion is immediate. Otherwise let $S=\{x:p(x)>0\}$. The elementary inequality $\ln u\le u-1$, with equality only at $u=1$, gives, for every $x\in S$,ConsequentlyThis argument applies to a countable discrete probability distribution too: the difference between the two sides of the pointwise inequality is nonnegative, and the negative part of the entropy summand is bounded by $cq(x)$, hence summable. Thus no subtraction of divergent series is involved. Equality forces both ${\sum }_{S}q=1$ and equality in every pointwise inequality; hence $q(x)=p(x)$ on $S$ and $q=0=p$ off $S$. Conversely $p=q$ plainly gives zero. Therefore $\boxed{D(p\Vert q)\ge 0,D(p\Vert q)=0⟺p=q}$.

For the log-sum inequality, set $F={\sum }_{A}f$, $G={\sum }_{A}g$, and normalize to the probability distributions $p_A=f/F$, $q_A=g/G$. When $A$ is nonempty, positivity ensures $F,G>0$, and direct expansion givesThus normalization reduces the log-sum inequality to Gibbs inequality. Equality holds exactly when $f/F=g/G$. The empty-set case is the zero identity under the usual zero-mass convention.

For the final bound, partition the alphabet using $A=\{x:p(x)>q(x)\}$ and put $a=p(A)$, $d=q(A)$. Since the total signed difference is zero,Apply the log-sum inequality separately to $A$ and its complement. The same normalization argument works for countable sets of finite total mass, using the countable Gibbs inequality just proved. It yields the binary partition bound for relative entropyZero block masses are interpreted by the stated conventions; a positive mass divided by zero makes the bound infinite. The given binary estimate now impliesThis is Pinsker's inequality. Equivalently, for the total variation distance $\Vert p-q{\Vert }_{\mathrm{TV}}=\frac{1}{2}{\sum }_x|p(x)-q(x)|$, the bound is $D(p\Vert q)\ge 2{\log }_{b}e\Vert p-q{\Vert }_{\mathrm{TV}}^2$. The factor ${\log }_{b}e$ keeps the statement valid for either bits or natural-logarithm units.