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]

For a measurable event $A$, applying Jensen inequality to $u\log u$ separately on $A$ and its complement shows that the Kullback-Leibler divergence between two probability measures is at least the divergence between the two event indicators. This reduces a general probability measure comparison to a binary one and is the key step in a proof of Pinsker's inequality.

The binary relative entropy is the Kullback-Leibler divergence between Bernoulli distributions:It is the exact exponent obtained by optimizing the Chernoff bound for a Bernoulli mean.

For probability distributions $P$ and $Q$ on a product space, the Kullback-Leibler divergence decomposes into the divergence of a marginal and the expected divergence of the corresponding conditional distributions. Iteration gives

On a compact parameter space, suppose the expected log-likelihood is continuous, uniquely maximized at the true parameter, and the normalized empirical log-likelihood converges uniformly in probability to its expectation. On the compact complement of every neighbourhood of the truth, the expected criterion has a strictly positive gap below its maximum. Uniform approximation by less than one-third of this gap excludes every empirical maximizer from that complement. Identifiability and nonnegativity of Kullback-Leibler divergence supply the unique expected maximizer. The proof works for any measurable choice of maximizer.

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.

Cross-entropy measures the average logarithmic loss incurred when outcomes follow one probability distribution $P$, but a model assigns probabilities using another probability distribution $Q$. For a finite alphabet, write their probability mass functions as $p_i$ and $q_i$. With base-two logarithms,The expectation is under the true or stipulated source law $P$, rather than the model $Q$. Terms with $p_i=0$ contribute nothing. If $p_i>0$ but $q_i=0$ for any outcome, the cross-entropy is $+\infty$: the model rules out an event that can occur. The result is measured in bits; natural logarithms give nats.

The useful identity is cross-entropy equals entropy plus relative entropy:The source's information entropy $H(P)$ is the baseline uncertainty. The Kullback-Leibler divergence is the extra average cost of a mismatched model, with the true law first and model second. Thus optimizing $Q$ for a fixed $P$ reduces the mismatch, rather than changing the source's own uncertainty. For finite alphabets, the minimum is $H(P)$, attained exactly at $Q=P$.

Take a three-symbol source with $P=(1/2,1/4,1/4)$. A matched binary prefix code assigns $A\mapsto 0$, $B\mapsto 10$, $C\mapsto 11$, with lengths $(1,2,2)$. A mismatched prefix code instead assigns $A\mapsto 10$, $B\mapsto 11$, $C\mapsto 0$, with lengths $(2,2,1)$, corresponding to $Q=(1/4,1/4,1/2)$. Both prefix codes decode exactly, but the most common symbol is shorter in the matched code. Under the same source $P$,The mismatched code costs an extra (1/4) bit per source symbol on average. No information is lost; the penalty is inefficient representation of this source. The mismatch penalty in lossless coding explains when this coding interpretation is exact.

Cross-entropy is also useful when evaluating a predictive distribution. A report that places tiny probability on the realized outcome receives a large logarithmic loss, even when it usually predicts the most common outcome correctly. The loss convention is the negative of the reward convention in the logarithmic scoring rule. Its expected loss is uniquely minimized by the correct probability distribution, making it a strictly proper scoring rule. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others treats this connection in §3.1, Example 3; its discussion uses rewards, so the signs are reversed for the losses here.^[ref]

I. J. Good's Rational Decisions by I. J. Good appeared in 1952. Its published summary describes a method for encouraging accurate probability estimates and a connection with information theory. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others traces the logarithmic scoring rule at least as far back as this 1952 paper.^[ref]

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 a complete binary prefix code with lengths ${\ell }_i$, the Kraft inequality is an equality: ${\sum }_i{2}^{-{\ell }_i}=1$. Put $q_i=2^{-{\ell }_i}$. The difference between expected codeword length and Shannon entropy isThe Kullback-Leibler divergence is nonnegative and vanishes exactly when $p=q$. Hence a complete code is entropy-tight exactly for its dyadic matching source. For example, lengths $(1,2,2)$ match probabilities $(1/2,1/4,1/4)$. Being an optimal prefix code among symbol-by-symbol codes is a weaker condition and does not imply this equality.

The deviance from ${\theta }_1$ to ${\theta }_2$ is twice the Kullback-Leibler divergence:

The fixed-design nonparametric regression model observes $Y_i=m(x_i)+\sigma {ϵ}_i$ at deterministic design points $x_i$. For independent and identically distributed random variables ${ϵ}_i$ with the standard normal distribution, comparing two mean functions has Kullback-Leibler divergence ${\sum }_i(m_1(x_i)-m_0(x_i){)}^2/(2{\sigma }^2)$.

For $n$ independent observations with a normal distribution $N(\mu ,{\sigma }^2)$, $\sigma >0$ fixed, every estimator has ${\sup }_{\mu }{\mathbb{E}}_{\mu }|T-\mu |\ge \sigma /(4\sqrt{2n})$. Compare ${\mu }_0=0$ and ${\mu }_1=\sigma /\sqrt{2n}$: the joint Kullback-Leibler divergence is $1/4$, so the total variation–Hellinger–relative entropy inequality bounds total variation distance by $1/2$. Apply the Le Cam lower bound under absolute-error loss. Degenerate zero-noise laws do not satisfy a positive lower bound.

For nonnegative densities of possibly different total masses, this divergence includes the mass correction $-x+y$ as well as the logarithmic term. It is the Bregman distance of the maximum-entropy regularization functional at a positive reference $y$. Convexity of $s\log s-s$ proves nonnegativity. For equal masses the correction integrates to zero, recovering the Kullback-Leibler divergence; for probability density functions both masses are one. Use the usual extended-value conventions at zero reference density.

A graph cut consists of the edges joining a vertex subset to its complement. In a two-group stochastic block model, crossing and within-group edges have different Bernoulli distributions. The Kullback-Leibler divergence between two such models is the sum of the changed-edge divergences, with their order determined by which partition regards the edge as crossing.

Normalization of the reverse law gives an exact finite identity:The sum notation describes discrete paths; the corresponding path integral has the same change-of-variable argument. Jensen's inequality for the exponential function then gives $e^{-⟨{\Sigma }_F{⟩}_F}\le 1$, hence $⟨{\Sigma }_F{⟩}_F\ge 0$. Equivalently this mean is the Kullback-Leibler divergence between the forward path law and the reverse path law pulled back by $\Theta$. Equality requires those two laws to agree. ^[ref]

Rare negative entropy production contributes disproportionately to this expectation through $e^{-{\Sigma }_F}$. Missing such events in a finite sample can spoil an estimate of the identity. Matching probability support is also essential: reverse paths absent from the forward law cannot be recovered by cancelling forward weights. This Second law of thermodynamics statement concerns an ensemble average; an individual negative value is compatible with it.

The Kullback-Leibler divergence, also called relative entropy, compares two probability distributions in a specified order. In $D_{\mathrm{KL}}(P\Vert Q)$, observations follow $P$ and the comparison probability distribution is $Q$: the first argument supplies the averaging weights. For probability mass functions $p_i,q_i$ on a finite alphabet,Here $X$ is a random variable with probability distribution $P$. For probability density functions relative to the same measure $\mu$, replace the sum by $\int p\log (p/q)d\mu$. These formulas use natural logarithms unless stated otherwise. The expected value is under $P$, even though $Q$ appears in the denominator. ^[ref]

Take $P=(0.75,0.25)$ and $Q=(0.5,0.5)$ on two outcomes. Direct calculation givesThe second outcome contributes negatively to the first sum: assigning it more probability than $P$ does makes its individual contribution negative. Nevertheless, relative entropy nonnegativity guarantees a nonnegative total. Reversing the arguments changes both the likelihood ratio and the averaging probabilities; taking an absolute value inside the logarithm would define a different quantity.

The units depend on the logarithm: natural logarithms give nats, whereas base-two logarithms give bits. Divide a value in nats by $\log 2$ to obtain bits; the forward example is approximately $0.188722$ bits. Changing the base rescales every Kullback-Leibler divergence by the same positive factor. Since the two calculated directions differ, Kullback-Leibler divergence is asymmetric and cannot be a metric. It also need not satisfy the triangle inequality. ^[ref]

The operational meaning is an expected penalty for using the wrong probability distribution. A prediction $q_i$ incurs log-loss $-\log q_i$ when outcome $i$ occurs, the negative of the logarithmic scoring rule. Under $P$, its expected value is the cross-entropy $H(P,Q)=-{\sum }_i{p}_i\log q_i$. Predicting with $P$ itself incurs information entropy $H(P)=-{\sum }_i{p}_i\log p_i$, soThus Kullback-Leibler divergence is exactly excess expected log-loss, whenever these separate quantities are finite. ^[ref]

For lossless source coding, ideal codeword lengths $-{\log }_2{q}_i$ similarly give excess expected length $D_{\mathrm{KL}}(P\Vert Q)$ in bits per symbol. Actual prefix codes require integer codeword lengths; Shannon's source coding theorem explains how long blocks approach ideal per-symbol lengths. The interpretation concerns an average, not a fractional physical bit attached to every outcome. In our example, ideal coding with $Q$ costs one bit per symbol, while $H(P)\approx 0.811278$ bits; the difference is exactly the computed $0.188722$ bits. ^[ref]

Zeros require explicit conventions. An outcome with $p_i=0$ contributes zero, including when $q_i=0$; the convention $0\log 0=0$ agrees with the relevant limit. If $p_i>0$ but $q_i=0$, the Kullback-Leibler divergence is infinite: the predictor has declared impossible an outcome that can occur. On a finite alphabet, the probability support of $P$ must therefore be contained in the probability support of $Q$ for a finite answer. For example, $P=(1,0)$ and $Q=(0.5,0.5)$ give $D(P\Vert Q)=\log 2$, but $D(Q\Vert P)=+\infty$. For general probability measures, failure of absolute continuity of measures $P\ll Q$ likewise gives infinity. Even $P\ll Q$ does not guarantee a finite integral. ^[ref]

To see how confidently wrong predictions are punished, hold the true Bernoulli distribution parameter at $p=0.75$ and vary the predicted parameter $q$. Its binary relative entropy isIt vanishes at $q=0.75$, equals approximately $2.894055$ nats at $q=0.01$, and equals $0.596495$ nats at $q=0.99$. Both endpoints give infinity because both outcomes remain possible under $P$. Predicting almost no successes is especially costly because successes actually occur three quarters of the time. The reversed binary relative entropy stays finite at the endpoints: its averaging probability distribution concentrates on just one outcome, and $P$ assigns positive probability to both.

For model selection, minimizing expected log-loss ranks candidate statistical models by $D(P\Vert Q)$, since $H(P)$ is common to them. The true probability distribution is usually unknown, so one estimates predictive performance using fresh observations or cross-validation. Fitting and assessing on the same data can reward overfitting; a small fitted Kullback-Leibler divergence alone does not establish useful prediction.

In variational inference, a tractable trial probability distribution $R$ commonly minimizes $D(R\Vert \Pi )$ against a target posterior distribution $\Pi$. Maximizing the evidence lower bound accomplishes this without evaluating the target's normalization constant. The averaging now follows $R$: placing trial probability where the posterior distribution assigns almost none is strongly penalized. The chosen direction and trial family therefore matter. ^[ref]

These comparisons do not by themselves establish causal inference. Two statistical models can reproduce the same observed probability distribution while predicting different responses to an intervention. Choosing the smaller Kullback-Leibler divergence therefore needs additional assumptions or experimental evidence before supporting a causal claim. ^[ref]

The original reference is S. Kullback and R. A. Leibler's 1951 paper ^[ref], published in The Annals of Mathematical Statistics 22(1), pages 79–86. Its title connects this comparison with sufficient statistics: the historical setting was statistical information, before today's widespread applications in prediction and variational inference.

The logarithmic scoring rule rewards the natural logarithm of the reported probability mass or probability density at the observed outcome. The title uses the reward convention. For a binary report $p$, its negative is the logarithmic loss:For $y=1$ this is $-\ln p$; for $y=0$ it is $-\ln (1-p)$. At an endpoint, use these outcome-specific forms: assigning zero probability to the outcome incurs infinite loss, while assigning it probability one gives zero. The natural logarithm therefore makes a confidently wrong binary forecast far more costly than the bounded Brier score does.

Under the stipulated Bernoulli distribution with $q=0.7$, the expected logarithmic loss isIts unique minimum is at $p=0.7$, where the expected loss is approximately $0.610864$. At $p=0.2$ it is approximately $1.193550$. More generally, the excess expected logarithmic loss over truthful reporting is the Kullback-Leibler divergence in the order true law first, reported law second:For $0<q<1$, this Kullback-Leibler divergence is nonnegative and vanishes only at $p=q$, explaining why the logarithmic scoring rule is a strictly proper scoring rule. The same Kullback-Leibler divergence identity applies to probability density functions relative to a common measure when the truthful expected logarithmic loss is finite and the comparison expected value is well defined.^[ref] For sequential forecasts, the existing prequential log score identity explains how logarithmic rewards add over observations.

A log-likelihood ratio compares two likelihoods on an additive scale. For independent observations its increments add. Under distributions $P_0,P_1$ with suitable integrability and common support, $E_0[\log (d{P}_1/d{P}_0)]=-D(P_0\Vert P_1)\le 0$ and $E_1[\log (d{P}_1/d{P}_0)]=D(P_1\Vert P_0)\ge 0$, where $D$ is Kullback-Leibler divergence. This sign change motivates likelihood-based sequential monitoring.

Markov chain variational inference optimizes an initial parametric probability distribution ${\nu }_{\eta }$ by minimizing $\mathrm{KL}(K^t{\nu }_{\eta }\Vert \pi )$ after a fixed number of Markov kernel updates. The best initial probability distribution can depend on $t$; Kullback-Leibler divergence contraction does not imply that optimization commutes with applying the Markov kernel.

An information entropy on at most $m$ outcomes is at most ${\log }_{2}m$, with equality for the uniform distribution on all $m$ outcomes. For the uniform reference $u$, the Kullback-Leibler divergence is $D(p\Vert u)={\log }_{2}m-H(p)\ge 0$, proving the bound.