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 proves
The 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 bound
The 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 is
Taking 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 gives
The gamma function identity follows by repeated integration by parts. Since on , the sign of the original integrand is , so
For , the integral is one, consistent with the formula.
For , the total number of forward channel uses is , so the random code rate of a message with bits is
The 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.
For , the number of attempts has the geometric distribution with success probability :
The tail-sum formula for expectation gives
At , deterministically. At , and its expectation is , rather than a finite waiting time.
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 . Hence
Indeed, , 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.
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 yields
Since , eventually . Each word in has probability mass at most , so
Rearranging proves
for 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.
For every , the defining typical set constraint implies
Let . Summing the lower probability mass bound over gives
Therefore
The sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer .
Choose noise values , giving exactly the outputs . The transition matrix, in that column order, is
An 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 consider
The 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 yields
Its derivative is , and its second derivative is negative. The unique maximum occurs at , giving
This additional optimization explains the collision pattern: outputs identify input , outputs identify the two extreme inputs, and only output is ambiguous.
Figure 1.
Three original additive-noise channel diagrams: increasing noise separation changes output collisions and channel capacity
. Details.
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 is
Thus . Every output determines its input, explicitly , so . Consequently , with equality for a uniform input. Therefore
The 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.
Translate the output alphabet by and put . The reachable outputs become
For 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 give
Every conditional output distribution has information entropy one bit, so . The input probability mass function makes all four outputs equiprobable, attaining that bound. Thus
Using 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.
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 yields
For 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.
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.
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.
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.
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.
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 is
contradicting 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]

There are unlisted articles, also show them or only show them.