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

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.