First suppose $m(E)<\infty$. The interval-cover definition of Lebesgue outer measure, together with $m^{\ast }(E)=m(E)$, provides bounded open intervals $I_j$ covering $E$ such that ${\sum }_j|I_j|<m(E)+\epsilon$. If the definition uses intervals that are not open, enlarge each by an amount whose total is smaller than the available error. For the open set $U={\bigcup }_j{I}_j$, countable subadditivity and additivity of Lebesgue measure giveThis subtraction is valid because both measures are finite.

For arbitrary $E$, including $m(E)=\infty$, set $E_n=E\cap [n,n+1)$ for $n\in \mathbb{Z}$, and choose positive weights $w_n=2^{-|n|}/3$, whose sum is one. Each $E_n$ has finite Lebesgue measure, so the preceding argument gives an open set $U_n\supseteq E_n$ with $m(U_n\setminus E_n)<\epsilon w_n$. Then $U={\bigcup }_{n\in \mathbb{Z}}{U}_n$ is open, contains $E$, andThus the required form of regularity of Lebesgue measure does not require $E$ itself to have finite measure.

The density of the rational numbers gives a countable way to separate two unequal values:Indeed, $f(x)<g(x)$ holds exactly when some rational number lies strictly between them. Every set inside the union is a Lebesgue measurable set, by the definition of a measurable function and the closure properties of a sigma-algebra. Since $\mathbb{Q}$ is countable, the union is measurable.

Writing $\mathcal{L}$ for the collection of Lebesgue measurable sets, saying that $\mathcal{L}$ is a sigma-algebra means that $\mathbb{R}\in \mathcal{L}$, that $\mathbb{R}\setminus A\in \mathcal{L}$ whenever $A\in \mathcal{L}$, and that ${\bigcup }_{n=1}^{\infty }{A}_n\in \mathcal{L}$ whenever every $A_n\in \mathcal{L}$. These properties also imply closure under countable intersections and differences.

A real-valued function $f$ is a Lebesgue measurable function precisely when the inverse image of every Borel set is in $\mathcal{L}$. Equivalently, it suffices to test the half-lines:The equivalence follows because these half-lines generate the Borel sigma-algebra, and inverse images preserve complements and countable unions.

By part i, ${\chi }_{E_n}|g|\to 0$ almost everywhere, while $0\le {\chi }_{E_n}|g|\le |g|$ and $g$ is Lebesgue integrable. The dominated convergence theorem givesTo deduce absolute continuity of the Lebesgue integral, suppose the stated uniform conclusion failed for some ${\epsilon }_0>0$. For each $n$ one could choose a measurable set $A_n$ with $m(A_n)<2^{-n}$ but ${\int }_{A_n}|g|\ge {\epsilon }_0$. Applying the result just proved to this sequence contradicts the lower bound. Hencefor every measurable set $A$.

The points belonging to infinitely many $E_n$ form their limit superior of sets:For every $N$, countable subadditivity givesThus $\boxed{m(G)=0}$. Outside this null set, each point belongs to only finitely many $E_n$, so its indicator functions are eventually zero. Therefore $\boxed{{\chi }_{E_n}(x)\to 0\text{ almost everywhere}}$. This is the summable-measure argument behind the first Borel-Cantelli lemma; no independence assumption is needed.

Each interval retained at stage $n+1$ lies inside the stage-$n$ interval from which it was cut. Taking the union over all parent components proves $\boxed{C_{n+1}\subseteq C_n}$. Consequently the intersection defining $C$ is a nested intersection of nonempty compact sets.

The $2^n$ component intervals are pairwise disjoint and each has length $q_n/2^n$. Finite additivity of Lebesgue measure givesTheir endpoints do not cause overlaps, because the central gaps have strictly positive length.

At stage zero there is one closed interval. At every later stage each component is replaced by two closed end intervals separated by a positive open gap. Induction therefore gives exactly $2^n$ pairwise disjoint closed intervals at stage $n$. Their common length issince the decreasing sequence starts at $q_0=1$.

The function is Lebesgue integrable. The inequalities $|\sin u|\le \min \{u,1\}$ for $u>0$ give bounds that handle the two ends of the $x$-axis differently. For $0<x<1$,For $x\ge 1$,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 $0<\eta <\pi /2$ and restrict to $x\ge 1$, $0<y<\eta$. There $\cos y\ge \cos \eta >0$. Tonelli's theorem for the nonnegative absolute value gives the lower boundThe last integral diverges. Indeed, on $[k\pi ,k\pi +\pi /6]$, $|\cos 2x|\ge 1/2$; each such interval contributes at least a positive constant times $1/(k+1)$. The harmonic series diverges. Hence the integral of $|g|$ is infinite, regardless of possible signed cancellations. One cannot infer Lebesgue integrability by formally applying Fubini's theorem to the oscillatory integrand.

Again $|e^{-ax}\sin (bx)|\le e^{-ax}$ proves Lebesgue integrability. Taking the imaginary part of the absolutely convergent complex integral in part i gives

The absolute value is bounded by $e^{-ax}$, whose integral is $1/a$. 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 $x^x=e^{x\log x}={\sum }_{k=0}^{\infty }(x\log x{)}^k/k!$. Since $|x\log x|\le 1/e$ on $(0,1)$, the Weierstrass M-test proves uniform absolute convergence, using the summable bounds $e^{-k}/k!$. 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 $k$, the change of variables $x=e^{-t}$ givesThe gamma function identity $\Gamma (k+1)=k!$ follows by repeated integration by parts. Since $\log x<0$ on $(0,1)$, the sign of the original integrand is $(-1{)}^k$, soFor $k=0$, the integral is one, consistent with the formula.

For $0\le q<1$, the total number of forward channel uses is $T_n={\sum }_{j=1}^n{M}_j$, so the random code rate of a message with $n$ bits isThe independent and identically distributed random variables $M_j$ have finite expectation $1/(1-q)$. 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 $q=1$, the algorithm never produces a completed transmission, so $R_n$ as a completed-code rate is undefined; the physical throughput is zero.

For $0\le q<1$, the number of attempts has the geometric distribution with success probability $1-q$:The tail-sum formula for expectation givesAt $q=0$, $M_1=1$ deterministically. At $q=1$, $M_1=+\infty$ and its expectation is $+\infty$, rather than a finite waiting time.

For $0\le q<1$, 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 $W_1,\dots ,W_n$. HenceIndeed, $\mathrm{Pr}(M_j>k)=q^k\to 0$, so each stage and the finite collection of $n$ 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 $q=1$, 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 $\epsilon >0$, the asymptotic equipartition property gives $\mathrm{Pr}(X^n\notin A^{n,\epsilon })\to 0$. The strong law of large numbers applied to $X_i$, which are bounded because their numerical alphabet is finite, gives $\mathrm{Pr}(X^n\notin B^{n,\epsilon })\to 0$. The union bound therefore yieldsSince $\delta >0$, eventually $\mathrm{Pr}(X^n\in S_n)\ge 2^{-\delta }$. Each word in $S_n$ has probability mass at most $2^{-n(H(p)-\epsilon )}$, soRearranging provesfor sufficiently large $n$. The key is that the factor $2^{-\delta }$ is a fixed number below one, however small $\delta$ is. This is an instance of typical sets with an additional high-probability constraint.

For every $x^n\in A^{n,\epsilon }$, the defining typical set constraint impliesLet $S_n=A^{n,\epsilon }\cap B^{n,\epsilon }$. Summing the lower probability mass bound over $S_n$ givesThereforeThe sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer $n$.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn input probability mass function $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence $C\ge 1$ 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 $0\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-y$, 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 $s$ and conditional probability mass function $(1/4,1/2,1/4)$, with information entropy $3/2$. The outputs whose labels are odd integers have mass $1-s$ and conditional probability mass function $(1/2,1/2)$, with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.