Past exam of the mathematics course of the University of Cambridge 2026 iii Paper 224 1 d Solution Created 2026-09-24 Updated 2026-09-25
Let be independent, with distributed as . Apply part (b) to :Adding an independent random variable cannot decrease information entropy, soIn terms of Entropic Ruzsa distance, this is . The Entropic Ruzsa triangle inequality and invariance under simultaneous negation now givewhich is the Entropic Ruzsa sum-difference inequality.
Past exam of the mathematics course of the University of Cambridge 2026 iii Paper 224 1 e Solution Created 2026-09-24 Updated 2026-10-03
For independent , expand the Entropic Ruzsa sum-difference inequality from part (d):Collecting the information entropy terms givesReplacing by interchanges sum and difference and preserves , yielding the requested orientation
Past exam of the mathematics course of the University of Cambridge 2026 ii Paper 2 12H b ii Solution Created 2026-09-24 Updated 2026-09-25
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 areThus . Finite normalization over infinitely many levels requires . Put , so . The geometric series givesThereforeFor the energy constraint, use and , obtained by differentiating the geometric series. This yieldsRecognizing the hyperbolic cotangent givesThe 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.
// Target: probability-and-statistics.bigb
Probability of a type class 2026-10-14
For a string of empirical distribution , independence givesMultiplying this by the size of a type class gives its exact probability. The entropy bounds for a type class then implyThese bounds apply to one attainable empirical distribution, not automatically to a tail event containing many classes.[ref]
The Method of Types by Imre Csiszár. §II, equation (II.1) and Lemma II.2, equation (II.5), printed pp. 2506–2507
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, soThe 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 iswhile 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.
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.
Shannon's rate-distortion theorem 2026-10-14
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
For a finite-alphabet memoryless classical information source with information entropy , every uniquely decodable code for blocks of source symbols has expected binary length at least . This follows from Kraft inequality for uniquely decodable codes and the entropy lower bound for prefix codes.
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 givesThus 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 isConditioning 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.
Three-input two-point additive-noise channel 2026-10-25
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, defineHere 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]
Information Theoretical Analysis of Multivariate Correlation by Satosi Watanabe. Abstract, printed p. 66: total correlation for the partition into individual variables
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 giveswhere 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.
