Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 30 1 b Solution Created 2026-10-03 Updated 2026-10-14
Introduce a selector with Bernoulli distribution of parameter , and construct by taking its conditional law given to be , and its conditional law given to be . No prescribed joint law of is needed. Summing over the selector gives the desired mixture probability mass function. The conditional entropy isSince conditioning cannot increase information entropy,This proves the concavity of information entropy. The argument also covers infinite information entropies with the convention that a zero mixing weight contributes zero. At or , the mixture is the corresponding original law and equality is immediate.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 30 1 c Solution Created 2026-10-03 Updated 2026-10-14
Fix . Take independent random variables and . Their convolution isby the binomial theorem. Thus has Poisson distribution with parameter . Conditioning on only translates , so . The entropy monotonicity under independent addition yields .
In fact the inequality is strict. The covariance is positive, so and are not independent random variables. Their information entropies are finite, and the equality criterion from part (a) excludes equality. Therefore the Poisson entropy monotonicity gives the stronger conclusion
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 31 2 Solution Created 2026-10-03 Updated 2026-10-14
Use base-two logarithms and put , with . Zero-probability letters can be omitted. The random variables are self-information values, are IID, and have finite mean because the alphabet is finite. Independence givesFor an arbitrary , define the typical setThe weak law of large numbers implies . Every string in this set satisfiesThis is the asymptotic equipartition property for the given finite IID source, here obtained directly from the weak law of large numbers.
For the upper bound, summing the lower bound on typical-string probabilities yields . For sufficiently large , its probability is at least , so it is an admissible set in the definition of . HenceFor the lower bound, let be any admissible set and write . ThenEach member of this intersection has probability at most . Therefore, for all sufficiently large ,This applies in particular to a minimum-size admissible set, giving a liminf at least . Letting proves both existence and the value of the minimal high-probability source-set exponent:For a deterministic source, and , consistent with the formula.
For coding, label the strings in an admissible set with distinct binary indices of length . A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically bits per source symbol describe any fixed fraction of the probability mass. More strongly, every rate permits block codes with error tending to zero: choose , encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most for large .
Conversely, a block encoder with at most outputs can reconstruct at most that many distinct input strings correctly. If , choose . Its success probability is at mostThis gives the strong converse for fixed-rate source coding. It is the operational significance of the information entropy limit for reliable source encoding at a rate. The allowance of a small reconstruction error matters: a fixed-length code that must encode every possible string without error generally needs the larger rate .
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 31 3 Solution Created 2026-10-03 Updated 2026-10-14
We give the bounds for an alphabet of size , including the binary case . Let be a length- code with codewords and minimum Hamming distance at least , where . Write for the maximum code size at a given distance andfor the number of words in a Hamming ball of radius . The th term chooses the changed coordinates and the alternative symbols in each.
For the Hamming bound, put . Balls of radius around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most . Counting those balls inside the ambient words provesNo linearity is needed. For a linear code of dimension over , replace by .
For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius- balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has , proving the existence boundOne may take the ceiling on the right because code size is integral.
For completeness, the sharper linear version is the Varshamov bound for linear codes. When is a prime power and , an linear code exists providedSet and choose columns of an parity-check matrix in order. When choosing column , exclude all combinations of at most earlier columns, including the zero combination. There are at most forbidden vectors, smaller than by the assumed inequality. A column can therefore be chosen. Inductively every set of at most chosen columns is independent: a relation involving the newest one would express it as a combination of at most earlier columns. The kernel has dimension at least and minimum Hamming distance at least , since a low-weight kernel vector would be such a column relation. If its dimension is larger than , take a -dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.
To derive the asymptotic bounds, define the q-ary entropywith the continuous endpoint conventions. Its derivative is , so it is increasing on and has maximum one at . Stirling's formula gives, uniformly for integer ,The sum defining is between its largest summand and times that summand. For radius fractions tending to , monotonicity of makes the largest exponent tend to . Consequently the Hamming ball volume exponent isFor , the exponent is one: use a radius fraction just below for a lower bound and for an upper bound.
Set and define the asymptotic rate-distance function byThe code rate is and the relative minimum distance is . A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to , so the finite Hamming bound and the volume exponent give the asymptotic Hamming boundThe covering radii have fraction tending to , giving the asymptotic Gilbert–Varshamov boundFor larger , this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.
The asymptotic lower bound is also achievable by linear codes over a finite field. For and sufficiently large , take redundancy , so . The linear existence condition produces dimension at least ; its rate has liminf at least . At , use the whole space, of rate one. In particular, for binary codes the bounds reduce towhere is the binary entropy function.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 4 ii Solution Created 2026-10-03 Updated 2026-10-14
For each , choose a proper coloring minimizing its color information entropy , so its coloring entropy weight is . A minimizing coloring exists: up to relabeling there are only finitely many partitions of its finite vertex set into color classes. Use independent dummy colors with the same marginal law as before. The marginal and conditional-entropy calculations in part (i) remain valid for any number of colors. Also any pair of vertices is joined in some covering graph and hence receives different forced colors there, so the full color vector still determines . Thus
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 4 i Solution Created 2026-10-03 Updated 2026-10-14
Choose uniformly among the vertices. For each covering graph use a proper binary coloring, and fill the color of an absent vertex with an independent random color having the same law as the color of a uniform vertex of that graph, as in the question's construction. Write for that color information entropy, so . The marginal distribution of is precisely this color law, and the variables are conditionally independent given : present colors are deterministic and absent colors use independent dummy draws. ThereforeAny two distinct vertices are joined in some and have different forced colors there. They cannot both be compatible with the same observed color vector, so . The mutual information identity now givesand hence .
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 12 4 i Solution Created 2026-10-03 Updated 2026-10-14
Let be the number of independent sets of the biregular graph . Choose one such set uniformly and write . All information entropies below use logarithms to base two, soWe will prove .
We state and justify the entropy facts used. For a finite-valued random variable , with . Its conditional entropy is the mean of this quantity over the conditioning variable. Factoring the joint probabilities proves the chain rule for information entropy, . Conditioning reduces entropy: . To see this, condition on and use concavity of to compare the mixture of the conditional distributions given with their mean entropy.
The precise Shearer inequality needed here is: if subsets of the indices of a finite random vector cover every index at least times, then . To prove it, order the indices. The chain rule for information entropy expandsThe inequality is conditioning reduces entropy. Summing over counts each nonnegative conditional term at least times and proves the assertion.
For every , its vertex neighbourhood has vertices. Every lies in exactly of these neighbourhoods. Hence Shearer inequality givesLet , the probability that no neighbour of is selected. Conditional on a particular selected subset of , a vertex with a selected neighbour is forbidden, and all other vertices of are available. Because there are no edges within , every subset of the available vertices is a valid completion. Uniform choice of makes these completions equally likely. The available coordinates are therefore independent fair binary choices, each of entropy one, and the forbidden coordinates are zero. Averaging their number givesBy the chain rule for information entropy,It remains to bound each bracket. Let , a binary vector of length , with distribution on , and put . Assign weight to the all-zero vector and weight to every nonzero vector. ThenThe first inequality is Jensen's inequality for the concave logarithm; the weights sum to . This explicitly handles zero probabilities and does not assume the neighbourhood indicators are independent.
There are right vertices, so combining the bounds and using givesExponentiating proves the required independent-set bound for biregular graphs. The proof uses both degree constraints: supplies the neighbourhood-cover multiplicity and the conditional-completion weight, while determines the number of neighbourhood patterns.
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 37 3 c Solution Created 2026-10-03 Updated 2026-10-14
For separate binary observations, the saturated model fits each outcome exactly and has maximized log-likelihood zero. With , the residual deviance is thereforeUse the identity in part (b) to replace by in its first term:Thus the deviance is twice the sum of the fitted binary information entropies. A deviance goodness-of-fit test against is unreliable for individual ungrouped binary observations: there is only one trial per saturated-model parameter, so the usual large-cell-count approximation fails. Deviance differences between fixed-dimensional nested logistic regression models can still support a likelihood-ratio test, subject to its usual regularity assumptions.
The three tree models are respectively , , and , with independent Bernoulli random variables conditional on the covariates. Testing the additional severity effect givesUnder , its reference distribution is asymptotically . The -value is approximately , giving overwhelming evidence that severity improves the fitted model. Holding severity fixed, doubling increases by one and multiplies the odds byThis is an odds ratio, not a multiplication of the event probability itself.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 13 2 iii Solution Created 2026-10-03 Updated 2026-10-06
The empty family satisfies the bound, so assume is nonempty and choose a graph according to the uniform distribution on a finite set . Let be its random vector of edge indicators, indexed by . Then its information entropy is .
For each vertex , put , so records the graph neighbourhood of . The possible graph neighbourhoods form an intersecting family of subsets of : the graph intersection of any two members of has no isolated vertex at . A subset and its complement cannot both occur. Pairing the subsets into complementary pairs gives at most possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore givesThis argument applies for . For the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.
Each edge belongs to exactly two of the sets . To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset . Each such step strictly increases , byThe potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for , the terminal chain consists of two copies of and empty sets. The compression of an entropy sum now givesExponentiating proves the entropy bound for graphs with isolated-vertex-free intersections:
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 13 2 ii Solution Created 2026-10-03 Updated 2026-10-06
An elementary union-intersection compression replaces two occurrences in a multiset by . By entropy submodularity, this changes the sum of information entropies byA compression of an entropy sum is obtained by iterating these elementary union-intersection compressions. Summing the inequalities over the sequence, with repetitions counted according to their multiset multiplicities, proves the required monotonicity:Neither the number of occurrences of an individual coordinate nor the total number of sets changes under union-intersection compression.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 13 2 i Solution Created 2026-10-03 Updated 2026-10-06
Take information entropy in bits and put . Write , , and . The chain rule for information entropy givesThe last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:This is entropy submodularity, with equality precisely when and satisfy conditional independence given .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 108 3 Solution Created 2026-10-03 Updated 2026-10-14
On a probability measure-preserving system, for a finite measurable partition , the entropy of a finite measurable partition isUse natural logarithms, so information entropy is measured in nats; another fixed logarithm base rescales all answers. The join of measurable partitions is their common refinement, and write , with an empty join the trivial partition. The entropy rate of a measurable partition and Kolmogorov-Sinai entropy are respectivelyThe block entropies form a subadditive sequence, so the first limit exists by the Fekete lemma. For finite partitions the conditional entropy of finite measurable partitions is .
Put and for . The chain rule for information entropy, applied from the last coordinate backwards, and measure preservation giveThe second equality uses invariance of the joint partition atom probabilities under the common pullback ; invertibility is unnecessary. Since conditioning reduces entropy, decreases to a nonnegative limit . The Cesaro convergence of a sequence of this convergent sequence has the same limit. ThereforeEquivalently , where . Here conditional entropy of a countable measurable partition conditioned on a sigma-algebra is computed using conditional partition atom probabilities; the martingale convergence theorem gives continuity under increasing conditioning sigma-algebras. This is the infinite-future formula for partition entropy rate.
The Kolmogorov-Sinai generator theorem states that if a finite or countable measurable partition has finite entropy of a countable measurable partition and its iterates generate the whole completed sigma-algebra modulo null sets, then . For an invertible system, generating means modulo null sets. For a noninvertible system a one-sided generator, using , suffices. The two-sided and one-sided versions must not be confused.
For a Bernoulli shift with discrete symbol probabilities , the coordinate-zero measurable partition has independent coordinate iterates. ThusFor a finite alphabet the coordinate partition is a generator of finite entropy of a finite measurable partition; on the two-sided sequence space use all integer coordinate iterates, and on the one-sided space use the nonnegative ones. The Kolmogorov-Sinai generator theorem proves the displayed answer in both cases. The same calculation applies to countably many symbols when their Shannon entropy is finite, using the countable finite-entropy version of the theorem. If the Shannon entropy is infinite, merge all but the first symbols into one cell. These finite coordinate partitions have entropy rate , so the system entropy is infinite. Zero-probability symbols contribute zero. In particular a fair -symbol shift has entropy .
For the final assertion, let and complete it modulo null sets. The approximation property forces modulo null sets. Indeed for each , choose approximating sets from finite blocks with error tending to zero. Their indicators approach in , and is a closed vector subspace, so is -measurable modulo a null set.
Invertibility now gives modulo null sets. In particular the present partition is measurable with respect to its entire future, so . The infinite-future formula gives . Since the given one-sided generator is also a two-sided generator, the Kolmogorov-Sinai generator theorem finishes the proof:This is finite one-sided generator of an invertible system forces zero entropy. Invertibility is essential: a fair binary one-sided Bernoulli shift has a finite one-sided generator and Kolmogorov-Sinai entropy .
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 1 11K Solution Created 2026-09-24 Updated 2026-10-03
Take every logarithm in base two. The information entropy of iswith . If the codeword has length , then its expected codeword length is
For any decipherable code, the Kraft inequality givesDefine the probability distribution . By Gibbs inequality,Since ,
Conversely, choose the integer lengthsThen , so their Kraft sum is at most one and the converse part of Kraft's inequality supplies a binary prefix code. Moreover,Thus the minimum expected length satisfies the Shannon noiseless coding theorem
For a decipherable code with arbitrary lengths , apply the lower bound to the uniform source . Its entropy is and its expected length is . Hencethe total length lower bound for a decipherable binary code.
Now consider the cumulative construction. Since and cannot have the same first binary digits: numbers sharing those digits lie in one half-open dyadic interval of length . Also, implies . Therefore no earlier codeword is a prefix of a later one, and no later, weakly longer codeword can be a prefix of an earlier one. The cumulative Shannon code is thus a prefix code, hence decipherable.
An optimal code minimizes expected codeword length over all decipherable codes for the specified source probabilities. The cumulative construction need not be optimal. For example, ifthen and the construction gives codewords and , with expected length . The prefix code has expected length , so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 224 1 a Solution 2026-09-28
Because and are independent random variables, conditioning on merely translates . The conditional entropy under a deterministic change of variables and the fact that conditioning reduces entropy therefore giveInterchanging and similarly gives , and henceThe proof applies to countable alphabets whenever the displayed information entropies are finite.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 224 2 f Solution 2026-09-28
On , part b gives . Hence the information entropy of the conditional law satisfiesParts d and e implyExponentiation proves .
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 2 3I a i Solution Created 2026-09-24 Updated 2026-09-25
A Bernoulli source is a sequence of independent and identically distributed random variables with a common probability mass function on the finite alphabet .
The source is reliably encodable at rate if, for each block length , there are an encoder with at most outputs and a decoder such that the block error probabilitytends to zero as .
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 4 3K a ii Solution Created 2026-09-24 Updated 2026-10-03
The unicity distance is the least ciphertext length for which the key is determined, or in the usual approximation the length at which the expected number of spurious keys falls to about zero. Assume equiprobable keys, a stationary plaintext source of information entropy rate , and ciphertext symbols that are approximately uniform on . The language redundancy per symbol isThe key equivocation is then approximated byHence the classical closed-form estimate is
Past exam of the mathematics course of the University of Cambridge 2025 iii Paper 164 1 i Solution Created 2026-09-24 Updated 2026-09-25
The axioms for information entropy give the formula and hence the chain rule for information entropyBecause conditioning reduces entropy, , and thereforeThis is subadditivity of information entropy.
For the entropy submodularity rule, apply the chain rule for information entropy twice:The last quantity is conditional mutual information, whose nonnegativity again expresses that conditioning reduces entropy.
Past exam of the mathematics course of the University of Cambridge 2025 iii Paper 164 3 ii Solution Created 2026-09-24 Updated 2026-09-25
Let be the set of valid quintuples and choose uniformly from . ThenApply Shearer's inequality to the ten pairs . Every index occurs in four pairs, so
Put . Since , it has cardinality . For each element of , its membership bits in are one of ; outside they are forced to be . Thus at most ordered pairs have any prescribed union. The chain rule for information entropy, conditional entropy, and the support bound for information entropy givebecause every belongs to . There are ten pairs, henceExponentiating proveswhich is the five-variable case of the entropy bound for pairwise-union tuples.
Past exam of the mathematics course of the University of Cambridge 2025 iii Paper 224 3 a Solution Created 2026-09-24 Updated 2026-09-25
For feasible mass functions at distortion levels , the mixture has nonzero-symbol mass at most . Concavity of information entropy givesTaking maximizing sequences proves