The function is Lebesgue integrable. The inequalities for give bounds that handle the two ends of the -axis differently. For ,For ,Tonelli's theorem therefore provesThe factors of sine suppress the near-axis contributions that caused divergence in part i.
The function is not Lebesgue integrable. Fix and restrict to , . There . Tonelli's theorem for the nonnegative absolute value gives the lower boundThe last integral diverges. Indeed, on , ; each such interval contributes at least a positive constant times . The harmonic series diverges. Hence the integral of is infinite, regardless of possible signed cancellations. One cannot infer Lebesgue integrability by formally applying Fubini's theorem to the oscillatory integrand.
Again proves Lebesgue integrability. Taking the imaginary part of the absolutely convergent complex integral in part i gives
The absolute value is bounded by , whose integral is . Thus the function is Lebesgue integrable. The complex integral of an exponential function isTaking the real part, justified by absolute integrability, gives
The exponential series gives . Since on , the Weierstrass M-test proves uniform absolute convergence, using the summable bounds . Therefore one can integrate the series term by term over this finite interval. Using part i,This is the alternating identity in sophomore's dream. The same estimate also proves absolute convergence of the integrated series; no cancellation is needed to justify the interchange.
For each nonnegative integer , the change of variables givesThe gamma function identity follows by repeated integration by parts. Since on , the sign of the original integrand is , soFor , the integral is one, consistent with the formula.
Past exam of the information theory course of the University of Oxford 2023 3 c iii Solution 2026-10-25
For , the total number of forward channel uses is , so the random code rate of a message with bits isThe independent and identically distributed random variables have finite expectation . By the strong law of large numbers,Thus the protocol reaches the binary erasure channel channel capacity in its asymptotic forward throughput while guaranteeing zero error on every completed message. Its random transmission length and use of channel feedback distinguish it from the fixed-length channel codes in part (b). Independent erasure indicators suffice for this calculation; the message bits themselves need not be independent or uniformly distributed. At , the algorithm never produces a completed transmission, so as a completed-code rate is undefined; the physical throughput is zero.
Past exam of the information theory course of the University of Oxford 2023 3 c ii Solution 2026-10-25
For , the number of attempts has the geometric distribution with success probability :The tail-sum formula for expectation givesAt , deterministically. At , and its expectation is , rather than a finite waiting time.
Past exam of the information theory course of the University of Oxford 2023 3 c i Solution 2026-10-25
For , use repeat-until-success coding over an erasure channel: delete every erasure symbol from the received sequence and retain the non-erased bits in order. Each message bit contributes a string of erasures followed by exactly one correct non-erased copy. The channel encoder advances to the next bit only after this successful copy, so the retained bits are precisely . HenceIndeed, , so each stage and the finite collection of stages terminate almost surely. The protocol uses channel feedback: Alice must know whether an erasure occurred before deciding whether to repeat. This feedback is implicit in the stated algorithm and is not counted as a forward channel use.
At , no stage ever finishes, so there is no terminating zero-error decoder for arbitrary messages. This endpoint is excluded from the operational claim above.
Past exam of the information theory course of the University of Oxford 2023 2 c ii Solution 2026-10-25
For fixed , the asymptotic equipartition property gives . The strong law of large numbers applied to , which are bounded because their numerical alphabet is finite, gives . The union bound therefore yieldsSince , eventually . Each word in has probability mass at most , soRearranging provesfor sufficiently large . The key is that the factor is a fixed number below one, however small is. This is an instance of typical sets with an additional high-probability constraint.
Past exam of the information theory course of the University of Oxford 2023 2 c i Solution 2026-10-25
For every , the defining typical set constraint impliesLet . Summing the lower probability mass bound over givesThereforeThe sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer .
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 ii Solution 2026-10-25
Each of the three input values has two possible outputs, so their union has at most six elements. The preceding union formula also gives this bound. Choose noise values , whose two translated input alphabets are disjoint. With columns ordered the transition matrix isThus . Every output determines its input, explicitly , so . Consequently , with equality for a uniform input. ThereforeThe extra uncertainty of which noise value occurred does not reduce information about the input: the two possible outputs for each input remain distinguishable from those of every other input.
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.
Past exam of the information theory course of the University of Oxford 2021 2 b vi Solution 2026-10-25
Assume a full-support finite distribution. The preceding structural arguments show that every internal vertex has three tree children, except possibly one tree parent at depth with two tree children. Let and count these two kinds of internal vertex. Part iv gives ; no vertex has one tree child.
A finite rooted tree with tree leaves has edges, while counting outgoing edges gives . Equating the counts yieldsFor an odd integer , the right side forces to be an even integer. Since it is at most one, . Thus no deepest pair has only two sibling codewords, and the optimal code tree is a full ternary tree. This leaf-count identity also directly proves that a full ternary tree has an odd number of tree leaves.
Again the unrestricted zero-weight version is false: is an optimal prefix code for , with odd integer , but its two deepest tree leaves form a two-sibling pair. There is no contradiction with the proof because its tree root has only two tree children, which the full-support finite distribution assumption would forbid above the deepest level.
Past exam of the information theory course of the University of Oxford 2021 2 b v Solution 2026-10-25
Let again denote the largest codeword length, and assume a full-support finite distribution. The missing-branch exchange from part iii forces every internal vertex at depth at most to have three tree children. At depth , all tree children are tree leaves. Part ii rules out one tree child there; the hypothesis that there is no pair of two deepest sibling codewords rules out two tree children. Thus each such tree parent also has three tree children. Every internal vertex has exactly three tree children, which is a full ternary tree, called semi-complete in this paper. The same last-level argument covers .
Without the assumption of a full-support finite distribution the implication is false: for , the optimal prefix code has no deepest pair of two sibling codewords, but its code tree contains vertices with a single tree child. Empty unused tree children are not vertices of the code tree.
Past exam of the information theory course of the University of Oxford 2021 2 b iv Solution 2026-10-25
With a full-support finite distribution, suppose two distinct tree parents at depth each have exactly two tree children, both tree leaves. Move one tree leaf from the second pair into the vacant third tree child slot of the first tree parent. Its length remains , so this relocation does not change expected codeword length. The second tree parent now has a single tree child, which is a tree leaf. Replace that remaining tree child's codeword by the tree parent's word. This preserves the prefix code property and shortens a positive-probability codeword by one. Expected codeword length strictly decreases, a contradiction. Thus there is at most one deepest pair with exactly two sibling codewords.
If zero-probability symbols are retained without a reduction convention, the claim can fail. The probability mass function with prefix code has the optimal expected codeword length one, yet contains the two deepest pairs and . The contraction would only shorten a zero-probability word.
Past exam of the information theory course of the University of Oxford 2021 2 b iii Solution 2026-10-25
Suppose a tree parent at depth , with , has an unused outgoing digit. The missing tree child gives an empty code tree branch at depth . Move any deepest tree leaf into that position, retaining all other codewords and deleting the abandoned empty branch. The new word has no old word as a prefix, because it lies in an unused branch, and it is not a prefix of any retained word. Its length decreases from to . With a full-support finite distribution this reduces expected codeword length by , contradicting optimality. Hence all three tree children exist, and each has a descendant codeword. In fact every internal vertex above depth has all three tree children. Applying this to the tree parent of the specified prefix gives the claimed three extensions.
The positive-probability qualification attached only to the specified prefix does not by itself suffice. In the zero-weight example , choose the positive-probability word , so . There is no word starting with . The deepest tree leaf available for relocation has probability zero, so the strict-improvement argument fails. This is why the full-support finite distribution assumption is used for the structural conclusions.
Past exam of the information theory course of the University of Oxford 2021 2 b ii Solution 2026-10-25
First assume a full-support finite distribution, as stated above. Let be the largest codeword length and take a tree leaf at depth . Every existing tree child of its tree parent must also be a tree leaf: an internal tree child would have a descendant deeper than . If the chosen tree leaf were its tree parent's only tree child, moving its symbol to that tree parent would shorten its codeword by one, preserve the prefix code property, and reduce expected codeword length by its positive probability. That contradicts optimality. The tree parent therefore has at least two tree children, both tree leaves. A second codeword has the same first digits and a different last digit, proving the required deepest sibling codeword property for a ternary prefix code.
For the literal wording allowing zero probabilities, take and the prefix code . Its expected codeword length is one, which is minimal: with more than one message an empty codeword is impossible, so the positive-probability message must have length at least one. Yet the deepest tree leaf has no sibling codeword. Thus positivity or an additional convention removing redundant zero-weight branches is needed.
Past exam of the information theory course of the University of Oxford 2021 2 b i Solution 2026-10-25
Exchange the two complete codewords while leaving the code tree unchanged. The prefix code property is preserved because the set of codewords is unchanged. If but , the change in expected codeword length iscontradicting optimality. Hence implies . This probability monotonicity of optimal prefix-code lengths is valid even if some probabilities are zero; equal probabilities impose no order.[ref]
A Method for the Construction of Minimum-Redundancy Codes by David A. Huffman. p. 1099, Derived Coding Requirements: probability ordering and permissible exchange of equal-probability messages
There are unlisted articles, also show them or only show them.
