= Solution
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\leq\log3-1<1$. The correct <Fano's inequality> alone gives $(1-P_e)\log m\leq 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\leq2$ is immediate because $R\leq1/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\geq1$, 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\geq1$,
$$
\min\left\{1,\frac{2^k}{m-1}\right\}\leq\frac{k}{L}.
$$
If $k\geq L$, this is immediate. If $k<L$, write $r=m/2^k>2$. The elementary inequality $\log r\leq r-1$ for $r\geq2$ gives
$$
L=k-1+\log r\leq k+r-2\leq k(r-1)<\frac{k(m-1)}{2^k},
$$
where the middle inequality is $(k-1)(r-2)\geq0$. This proves the needed scalar bound.
Taking the <expectation> over erasure patterns, and using $\mathbb E K=n(1-q)$, yields
$$
1-\delta\leq\Pr(\widehat W=W)\leq\frac{\mathbb E K}{L}
=\frac{n(1-q)}{\log m-1}.
$$
Consequently the requested bound is valid:
$$
\boxed{R=\frac{\log m}{n}\leq\frac{1-q}{1-\delta}+\frac1n.}
$$
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$.
Back to article page
