Kullback-Leibler divergence Created 2026-09-24 Updated 2026-10-14
The Kullback-Leibler divergence, also called relative entropy, compares two probability distributions in a specified order. In , observations follow and the comparison probability distribution is : the first argument supplies the averaging weights. For probability mass functions on a finite alphabet,Here is a random variable with probability distribution . For probability density functions relative to the same measure , replace the sum by . These formulas use natural logarithms unless stated otherwise. The expected value is under , even though appears in the denominator. [ref]
Take and on two outcomes. Direct calculation givesThe second outcome contributes negatively to the first sum: assigning it more probability than 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 to obtain bits; the forward example is approximately 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]
https://web.stanford.edu/~kedart/ee376a_winter1617/Lecture_3.pdf. Tse, relative entropy, 2017, Section 3.3
The operational meaning is an expected penalty for using the wrong probability distribution. A prediction incurs log-loss when outcome occurs, the negative of the logarithmic scoring rule. Under , its expected value is the cross-entropy . Predicting with itself incurs information entropy , soThus Kullback-Leibler divergence is exactly excess expected log-loss, whenever these separate quantities are finite. [ref]
https://web.stanford.edu/class/ee276/files/previous_notes/lecture_2.pdf. Weissman, information measures, 2024, property 3
For lossless source coding, ideal codeword lengths similarly give excess expected length 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 costs one bit per symbol, while bits; the difference is exactly the computed bits. [ref]
https://web.stanford.edu/~kedart/ee376a_winter1617/Lecture_3.pdf. Tse, information theory, 2017, Section 3.4
Zeros require explicit conventions. An outcome with contributes zero, including when ; the convention agrees with the relevant limit. If but , the Kullback-Leibler divergence is infinite: the predictor has declared impossible an outcome that can occur. On a finite alphabet, the probability support of must therefore be contained in the probability support of for a finite answer. For example, and give , but . For general probability measures, failure of absolute continuity of measures likewise gives infinity. Even does not guarantee a finite integral. [ref]
https://arxiv.org/pdf/1206.2459. van Erven and Harremoës, Rényi Divergence and Kullback-Leibler Divergence, 2014, Section II
To see how confidently wrong predictions are punished, hold the true Bernoulli distribution parameter at and vary the predicted parameter . Its binary relative entropy isIt vanishes at , equals approximately nats at , and equals nats at . Both endpoints give infinity because both outcomes remain possible under . 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 assigns positive probability to both.
For model selection, minimizing expected log-loss ranks candidate statistical models by , since 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 commonly minimizes against a target posterior distribution . Maximizing the evidence lower bound accomplishes this without evaluating the target's normalization constant. The averaging now follows : placing trial probability where the posterior distribution assigns almost none is strongly penalized. The chosen direction and trial family therefore matter. [ref]
https://www.cs.columbia.edu/~blei/papers/BleiKucukelbirMcAuliffe2017.pdf. Blei, Kucukelbir and McAuliffe, Variational Inference: A Review for Statisticians, 2017, Section 2.2
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]
https://ftp.cs.ucla.edu/pub/stat_ser/r350.pdf. Pearl, Causal inference in statistics: An overview, 2009, Section 2
The original reference is S. Kullback and R. A. Leibler's 1951 paper [ref]
https://doi.org/10.1214/aoms/1177729694. On Information and Sufficiency
, 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. Lossless source coding 2026-10-14
Lossless source coding encodes source messages so they can be recovered exactly. Shannon's source coding theorem relates its achievable average code length to information entropy.
Maximum entropy distribution on a finite set Created 2026-09-24 Updated 2026-09-28
Among probability distributions on a finite set of elements, the uniform distribution uniquely maximizes information entropy, attaining .
Maximum entropy distribution on the nonnegative integers Created 2026-09-24 Updated 2026-09-24
Among distributions on with fixed expected value , the geometric distribution with success probability uniquely maximizes information entropy. Its entropy is
For a finite list of real values , maximize information entropy with , , and . Lagrange multipliers giveThe constrained second variation is for any nonzero tangent perturbation, proving uniqueness of the entropy maximum whenever a feasible interior solution exists. The mean has derivative , so for nonconstant it decreases strictly with and ranges between the largest and smallest as ranges over the real line. Thus a finite exists uniquely exactly when .
At an extreme mean, strictly positive probabilities are impossible unless all coincide. If all , the mean constraint is redundant when , the maximum is uniform, and is not identifiable. This finite exponential family is an exponential tilting of the uniform distribution.
Maximum entropy on a finite alphabet Created 2026-10-05 Updated 2026-10-18
An information entropy on at most outcomes is at most , with equality for the uniform distribution on all outcomes. For the uniform reference , the Kullback-Leibler divergence is , proving the bound.
Method of types Created 2026-09-24 Updated 2026-10-14
The method of types combines two facts: there are few possible empirical distributions, and strings within each type class are equiprobable under an independent and identically distributed source. Information entropy determines how many strings share a frequency profile; relative entropy determines how unlikely that profile is under a specified source law. The connection is useful both for lossless source coding and for understanding rare observations.
The following formulas use natural logarithms, so information entropy and relative entropy are measured in nats. DefineHere is the source probability mass function and is an attainable empirical distribution. Use ; first assume every . Base-two logarithms give the equivalent formulas with and .
For independent and identically distributed observations from a probability mass function on a finite alphabet, expected relative entropy of the empirical distribution from is nonincreasing in sample size. The leave-one-out identity for empirical distributions and convexity of relative entropy in its first argument giveEvery deletion sample has the law of observations from . Taking expected values proves the assertion without requiring independence between deletion samples. Zero-probability symbols are absent almost surely. Since , the identity also shows that expected empirical information entropy increases towards the source information entropy. Convergence follows from the strong law of large numbers for empirical frequencies and boundedness and continuity of information entropy on a finite probability simplex.
Mutual information Created 2026-09-24 Updated 2026-10-14
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 visible. It is nonnegative and is zero exactly when and are independent random variables. One way to see both facts iswhere 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 be a fair bit, let be an independent Bernoulli random variable with error probability , and set , where is exclusive or. The output is also a fair bit, but knowing the input leaves just the error uncertainty:Here is binary entropy. At , , so the output carries about 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.
Binary entropy and retained information distinguish noisy transmission from predictable bit inversion
. Details. At , every output is equally likely for either input, so . At , the output is always the inverted input: knowing this rule lets the receiver recover the input exactly, so 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 .
Mutual information detects dependence that ordinary correlation can miss. Let be uniform on and . Symmetry gives , hence zero covariance and zero correlation, while is completely determined by . Thus . This distinction is useful whenever a relationship is nonlinear: knowing one variable can reveal another without a linear trend.
Nat (unit) 2026-10-14
The unit for information content or information entropy computed with natural logarithms. Converting to bits divides the numerical value by , so .
For a hereditary hypergraph property of -uniform hypergraphs, is the family on the labelled vertex set . For , its normalized speed lies between zero and two and is nonincreasing. Choose a uniformly random member on vertices and record its edge indicators. Each edge occurs in vertex-deletion restrictions. The Shearer inequality bounds its information entropy by the sum of the restriction entropies divided by . Each restriction has at most possible values. Division by gives . Empty families are handled directly by heredity.
Normalized subset entropy 2026-10-14
For a discrete random vector with coordinates, this is the average information entropy per coordinate over all subsets of size . Independent coordinates give the same average for every , even when their individual entropies differ. If all coordinates are copies of one random variable , the average is .
Parity constraint and total correlation 2026-10-14
Let be independent fair bits and set , their exclusive or. The four possible triples are , each with probability . Every coordinate is fair, and every pair has all four outcomes with equal probability. Thus each pair's mutual information is zero, as in pairwise independence does not imply joint independence.
The full random vector has joint entropy bits, while the marginal information entropies sum to three bits. ConsequentlyThe product of the marginals predicts probability for every triple, including the four impossible ones. On each possible triple, the ratio of true to product probability is ; averaging its base-two logarithm gives the same one bit of relative entropy.
The example gives a concrete use for joint information measures. A lossless source coding scheme that treats the three coordinates separately needs three bits here. If the decoder knows the integer parity rule, the encoder can send just and let the decoder reconstruct exactly. Pairwise independence does not reveal that saving. This is a stipulated source law and an explicit two-bit code, rather than a promise that arbitrary data can be shortened.
All logarithms have base two. In part a the information entropy differences and information expressions are interpreted where they are well defined; finite joint entropy is a sufficient hypothesis. This avoids undefined expressions such as infinity minus infinity.
For the maximum entropy distribution on the nonnegative integers, use the geometric distribution counting failures before the first success. Write and defineThe geometric series gives . Termwise differentiation of a power series applied to that geometric series for gives , hence .
For any competing probability mass function of mean , its cross-entropy against isThis is finite. The fact that finite cross entropy bounds countable information entropy must be justified without assuming in advance that is finite. Use with when . Including zero terms by their limiting convention yields, for every finite ,Let . The information entropy partial sums increase, the cross-entropy partial sums converge to the finite value above, and the final mass difference tends to zero. This proves finiteness and the upper bound. We may now writeRelative entropy nonnegativity has equality exactly when . Therefore the displayed geometric probability mass function is the unique maximizer, andThe mean constraint is essential: without it, uniform distributions on longer initial intervals have unbounded information entropy.
Past exam of the information theory course of the University of Oxford 2021 3 c iii Solution 2026-10-25
Choose noise values , giving exactly the outputs . The transition matrix, in that column order, isAn input probability mass function makes outputs equiprobable, so and . Hence bit per use, as required for comparison with the four-output case.
There is a strict improvement, which can also be computed exactly. Reflection of the input labels , accompanied by output reflection , leaves mutual information unchanged. Concavity of information entropy makes mutual information a concave function of the input probability mass function for a fixed transition matrix. Averaging an input law with its reflection therefore cannot decrease it. It suffices to considerThe outputs whose labels are even integers have total mass and conditional probability mass function , with information entropy . The outputs whose labels are odd integers have mass and conditional probability mass function , with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is , and its second derivative is negative. The unique maximum occurs at , givingThis additional optimization explains the collision pattern: outputs identify input , outputs identify the two extreme inputs, and only output is ambiguous.
Three original additive-noise channel diagrams: increasing noise separation changes output collisions and channel capacity
. Details. Past exam of the information theory course of the University of Oxford 2021 3 c i Solution 2026-10-25
Translate the output alphabet by and put . The reachable outputs becomeFor the two sets overlap in two points; for in one; for they are disjoint. In particular , and choosing noise values attains four.
With rows indexed by inputs and columns by outputs , independence and uniform two-point noise giveEvery conditional output distribution has information entropy one bit, so . The input probability mass function makes all four outputs equiprobable, attaining that bound. ThusUsing a zero-probability input in a channel-capacity maximization is legitimate; it is unrelated to the strictly positive source weights needed for the tree-shape claims in Question 2.
Solutions to all three questions.[ref] All logarithms are base two; information entropy is measured in bits and code rates in bits per channel use. Terms are zero. Question 3(b) contains an incorrect hint; its requested conclusion is proved directly below for deterministic channel codes. The repeat-until-success protocol in Question 3(c) requires to terminate.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 13 3 a Solution Created 2026-10-03 Updated 2026-10-14
Write for the number of labelled -uniform hypergraphs with the hereditary hypergraph property, so for . The assertion is nonincrease; strict decrease need not hold, since allowing all uniform hypergraphs gives .
If , heredity forces . If , the desired inequality is immediate. Otherwise choose uniformly from and record its edge indicators as a random vector . Its information entropy, with any fixed logarithm base, is . Deleting a vertex gives the restriction to the edges avoiding . By heredity and relabelling, this restriction has at most possible values, so .
Each edge coordinate occurs in exactly of these restrictions. For completeness, order all the edge coordinates. The chain rule for information entropy expands a restriction entropy as a sum of conditional coordinate entropies. The predecessors retained in a restriction form a subset of all predecessors, and conditioning reduces entropy; hence each restriction term is at least the corresponding full-vector term. Summing over the restrictions counts each full-vector term times. This proves the needed Shearer inequality:Since , division gives . Therefore the normalized speed of a hereditary hypergraph property satisfies
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 30 1 a Solution Created 2026-10-03 Updated 2026-10-14
Use base-two logarithms and the convention . Write and for . The conditional entropy is the average of the information entropies of these conditional laws:The careful form of Gibbs inequality is that, for two probability mass functions on a common countable set,where a term with gives . Equality holds exactly when . This is the nonnegativity of relative entropy.
First suppose . For every of positive probability, implies . Averaging the cross-entropies givesAll the summands here are nonnegative, so interchanging the sums is valid, and each conditional cross-entropy is finite. Applying Gibbs inequality to each shows that is at most its cross-entropy. Subtracting and averaging therefore givesEvery term on the right is nonnegative. The equality in the entropy conditioning inequality is thus equivalent to for all , which is exactly factorization of the joint probability mass function. Consequently
For arbitrary countable discrete random variables, the inequality remains valid in : the case is immediate. The finite-entropy condition is necessary for the usual equality characterization. For example, let for , with the normalizing constant, and let be an independent fair bit. The series defining the probability mass function converges, whereas its information entropy diverges like . Then and are dependent, but . In the infinite case, equality means precisely that the conditional entropy is also infinite; it does not imply independent random variables.



