Let be independent, with distributed as . Apply part (b) to :
Adding an independent random variable cannot decrease information entropy, so
In terms of Entropic Ruzsa distance, this is . The Entropic Ruzsa triangle inequality and invariance under simultaneous negation now give
which is the Entropic Ruzsa sum-difference inequality.
For independent , expand the Entropic Ruzsa sum-difference inequality from part (d):
Collecting the information entropy terms gives
Replacing by interchanges sum and difference and preserves , yielding the requested orientation
For , assign every outcome one of the -bit words. This complete fixed-length prefix code has expected length and meets the information entropy lower bound.
Write and use Lagrange multipliers for the particle-number and energy constraints. The stationary equations are
Thus . Finite normalization over infinitely many levels requires . Put , so . The geometric series gives
Therefore
For the energy constraint, use and , obtained by differentiating the geometric series. This yields
Recognizing the hyperbolic cotangent gives
The strict positivity of all occupations requires ; the paper's positivity assumptions alone do not guarantee this feasibility condition. For admissible energy the multiplier is uniquely . Equality is only the limiting state with all occupation in level zero, outside the stipulated strictly positive family; lower energy is impossible.
For rigor beyond formal multiplier equations, has fixed mean . The objective differs from times its information entropy only by the fixed constant . The maximum entropy distribution on the nonnegative integers is uniquely geometric at that mean, confirming the stationary family and its maximum character.
Poisson entropy monotonicity Created 2026-10-14 Updated 2026-11-05
The information entropy of a Poisson distribution is strictly increasing for . Given , take independent and . Their sum has Poisson distribution with mean , so entropy monotonicity under independent addition gives . All these information entropies are finite, and excludes equality.
For a string of empirical distribution , independence gives
Multiplying this by the size of a type class gives its exact probability. The entropy bounds for a type class then imply
These bounds apply to one attainable empirical distribution, not automatically to a tail event containing many classes.[ref] If but , every string in that class is impossible and .
As an exact example, take an independent and identically distributed binary source with . Each balanced four-symbol string has probability . There are six such strings, so
The relative entropy is . The exponential upper bound is , visibly larger than the exact probability. It captures the cost of an atypical frequency without supplying the exact finite-length prefactor.
For , the exact probability of twenty ones is
while the exponential upper bound is approximately . At the source frequency , relative entropy is zero and the upper bound is one; the exact probability of ten ones is only about . A likely neighborhood of frequencies need not give a large probability to a single exact profile.
Figure 1.
Relative entropy controls the rarity of an empirical frequency
. Exact probabilities from the binomial distribution for each possible number of ones in forty independent and identically distributed trials with , compared with the exponential relative entropy upper bound. The curves are calculated from a stipulated model, not observed data; the vertical scale is logarithmic. Details.
The striking cancellation is that there are about strings in a class, but each costs about . The information entropy terms cancel, leaving relative entropy as the rarity exponent. Summing over polynomially many classes preserves that leading exponential scale. This is the elementary counting mechanism behind finite-alphabet versions of Sanov theorem and many error exponents in hypothesis testing.
For a finite alphabet source with independent and identically distributed symbols, a finite reconstruction alphabet, and a bounded nonnegative separable distortion, the rate-distortion function is the asymptotic limit for fixed-length lossy codes. In particular, for a distortion target in the interior of the feasible range and every , sufficiently long block codes exist with rate at most and expected distortion at most . Every such -symbol code obeys , where is its actual expected distortion.[ref]
The outline is instructive. The data processing inequality bounds the mutual information in a reconstruction by the information entropy of the transmitted message, which is at most . Independence and the convexity of the rate-distortion function then give the per-symbol lower bound. For achievability, choose many reconstruction blocks using a suitable probability distribution, so that the source's typical blocks are likely to have an acceptable nearby reconstruction. This is a covering argument; it does not require recovering the original block exactly.
Shannon's source coding theorem Created 2026-10-14 Updated 2026-11-05
If at least two source symbols have positive probability, give each positive-probability block Shannon length . These lengths satisfy Kraft inequality, so a prefix code exists, and independence gives
Thus coding longer blocks approaches the information entropy in expected bits per source symbol. This is an average-length statement: rare blocks can have long codewords.
For a source with only one possible symbol, a one-bit codeword for each length- block gives rate when positive codeword lengths are required. The limiting theorem therefore remains true, although the strict one-block bound needs the nontrivial-alphabet assumption. Countably infinite alphabets require additional care about finite information entropy and the chosen code construction.
Choose one of two regimes once, with equal probability: a source of independent and identically distributed random variables with one-bit probability , or one with one-bit probability . Keep the chosen regime forever. The resulting source is a strictly stationary process, because shifting a block does not change either component law. It is not an ergodic stationary process: its limiting empirical frequency identifies the regime.
The source's information rate is
Conditioning on the single regime bit changes any block's information entropy by at most one bit, so dividing by the block length proves this rate. However, the limiting realized information content per symbol is approximately in the first regime and one in the second. The alternative component's likelihood ratio decays exponentially along a typical path from the chosen component, at a rate given by the positive relative entropy between the two Bernoulli distributions. The mixture therefore has two possible pathwise limits, not one limit equal to the averaged information rate.
Let the input alphabet be and let the output be , where independent noise is uniform on two distinct integers. Translating the output alphabet reduces the noise to , . The reachable output alphabet has size : it is the union of two three-element intervals shifted by .
For , every row of the transition matrix has conditional information entropy one bit, so . Input probabilities make the output uniform and attain one bit per use. For , the two translated input alphabets are disjoint and every output identifies its input. A uniform input then attains bits per use.
For , reflection symmetry and concavity of information entropy permit restricting to input probabilities . Conditional on output parity, outputs whose labels are even integers have probabilities and outputs whose labels are odd integers have probabilities . Consequently . Its strictly negative second derivative and stationary equation give and channel capacity . All three values follow from overlap of translated input alphabets, rather than from output alphabet size alone.
Total correlation Created 2026-09-28 Updated 2026-10-14
Total correlation measures how much dependence is lost when a joint probability distribution is replaced by the product of its marginal probability distributions. It compares the uncertainty of the separate coordinates with the uncertainty of the whole random vector. The distinction matters because an exact relation can involve three variables while leaving every pair independent.
For random variables with finite alphabets, define
Here is information entropy, the entropy of the full random vector is joint entropy, and is relative entropy. Base-two logarithms give bits; natural logarithms give nats. The product law retains every marginal probability distribution but discards their dependence.[ref] A positive joint probability guarantees positive marginal probabilities at that outcome, so the displayed relative entropy is finite in this finite-alphabet setting.
For two variables, total correlation is exactly mutual information. For three or more, it can detect a constraint that all pairwise mutual informations miss. Relative entropy nonnegativity gives , with equality exactly when the coordinates are jointly independent random variables.
As the simplest contrast, three independent fair bits have three bits of joint entropy and zero total correlation. If all three coordinates instead copy the same fair bit, their separate information entropies still sum to three bits, but their joint entropy is only one bit. Their total correlation is therefore two bits. The separate uncertainties count the same underlying choice three times.
Trit 2026-10-24
A ternary digit, taking one of three values. A codeword of length over a three-symbol alphabet uses trits. If the trit is uniform its information entropy is bits; an arbitrary ternary digit can have less information entropy. Expected codeword length in trits must therefore be distinguished from source information entropy measured in bits.
For a uniform distribution on a finite set of outcomes, direct expansion of relative entropy gives
where is information entropy in nats. Therefore minimizing relative entropy from this particular reference is equivalent to maximizing information entropy subject to the same constraint. This statement depends on the uniform reference; an arbitrary reference contributes its own weights.
In the three-outcome example, nats. The mean fixes one aggregate quantity, and information projection chooses how to distribute the remaining uncertainty. This extends maximum entropy on a finite alphabet, whose unconstrained maximizer is the uniform law itself.