Past exam of the information theory course of the University of Oxford / 2023 / 3

The specified transition law is a binary erasure channel. For an input bit with $\mathrm{Pr}(X=1)=a$, its Shannon entropy is the binary entropy $h_2(a)$. A non-erased output determines $X$, whereas the erasure symbol leaves its probability distribution unchanged because the erasure event is independent of $X$. ThusMaximizing the mutual information over the input probability distribution, $h_2(a)\le 1$ with equality at $a=1/2$, givesThis includes $q=0$, a noiseless binary channel, and $q=1$, a completely erased channel with zero channel capacity.

Use the standard deterministic channel encoder and channel decoder, with $m$ message labels and code rate $R=(\log m)/n$. The Fano's inequality hint printed here replaces $\log (m-1)$ by $\log m-1$, which is false in general: take $X$ uniform on $\{0,1\}$ and $Y=2$ in the common alphabet $\{0,1,2\}$. The error probability is one and its binary entropy is zero, so the proposed bound asserts $1\le \log 3-1<1$. The correct Fano's inequality alone gives $(1-P_e)\log m\le n(1-q)+h_2(P_e)$, which does not immediately give the requested additive $1/n$. The following erasure-pattern counting bound for maximal decoding error proves the displayed claim directly.

The case $m\le 2$ is immediate because $R\le 1/n$. Suppose $m>2$, put $L=\log m-1>0$, and let $w_0$ be the message that the channel decoder returns on the all-erased output. Choose $W$ uniformly among the other $m-1$ messages. Every one of these messages is decoded correctly with probability at least $1-\delta$, by the assumed maximal decoding error probability bound.

Let $S$ be the random set of unerased coordinates and $K=|S|$. For each fixed $S$ with $K=k\ge 1$, at most $2^k$ output words are possible. A deterministic channel decoder can correctly identify at most one message per output word, so its conditional success probability, averaged over these $m-1$ messages, is at most $\min \{1,2^k/(m-1)\}$. When $K=0$, success is zero because $w_0$ was excluded.

For every integer $k\ge 1$,If $k\ge L$, this is immediate. If $k<L$, write $r=m/2^k>2$. The elementary inequality $\log r\le r-1$ for $r\ge 2$ giveswhere the middle inequality is $(k-1)(r-2)\ge 0$. This proves the needed scalar bound.

Taking the expectation over erasure patterns, and using $\mathbb{E}K=n(1-q)$, yieldsConsequently the requested bound is valid:The use of maximal decoding error probability matters: excluding one message preserves the lower bound on success. The deterministic channel decoder convention also matters; allowing independent randomized guessing would invalidate this particular finite-length claim at $q=1$.

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 $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$, 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.