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

The inequality is true for ordinary addition, and also for addition in a group. For any fixed $y$, the translation $x\mapsto x+y$ is injective, so it merely relabels the probability masses in the conditional distribution. Since $X,Y$ are independent random variables,Averaging over $y$ and using conditioning reduces entropy proves entropy monotonicity under independent addition:There is no requirement that $X+Y$ remain in the original finite alphabet. The proof also gives $H(X+Y)\ge H(Y)$ by symmetry. Independence matters: for a nonconstant $X$ and $Y=-X$, the sum is constant while $H(X)>0$.

Let $N=|\mathcal{X}|\ge 2$ and let $E=1_{\{X\ne Y\}}$ be the error indicator random variable. Because $E$ is determined by $(X,Y)$, the chain rule for conditional entropy in its two orders givesBy conditioning reduces entropy, $H(E\mid Y)\le H(E)$. On $E=0$, knowing $Y$ determines $X$, so the corresponding conditional entropy is zero. On $E=1$, at most $N-1$ symbols remain possible for $X$. The maximum Shannon entropy of a probability distribution on at most $N-1$ symbols is $\log (N-1)$. ConsequentlyFor an arbitrary function $g:\mathcal{X}\to \mathcal{X}$, repeat the argument with $E_g=1_{\{X\ne g(Y)\}}$. This is still determined by $(X,Y)$; when it is zero, $X=g(Y)$, and when it is one, $X$ has at most $N-1$ possibilities for each $Y$. Thus Fano's inequality givesEvents of zero probability contribute zero to the conditional average, covering the error probabilities zero and one. If $N=1$, the left side and error probabilities are zero; the trivial conclusion is handled separately instead of writing $0\log 0$ as an ordinary finite product.

For the entropy summand $f(x)=-x\log x$, differentiation on $(0,1)$ givesSince $f(x)\to 0$ as $x\downarrow 0$, its continuous extension to $[0,1]$ is a concave function.

Fix $0<v<1$ and define the increment $D_v(t)=f(t+v)-f(t)$ on $[0,1-v]$. In its interior,Thus the increment is decreasing, and its endpoint values are $D_v(0)=f(v)$ and $D_v(1-v)=-f(1-v)$. ThereforeThe cases $v=0,1$ follow directly from the endpoint values.

To obtain the sharper half-interval bound, put $G(v)=f(v)-f(1-v)$. It has $G(0)=G(1/2)=0$, whileHence $G$ is a concave function on $[0,1/2]$ and lies above the chord joining its zero endpoints. Thus $f(v)\ge f(1-v)$ there, proving

Set $N=|\mathcal{X}|$, $d_i=|p_i-q_i|$ and $d={\sum }_i{d}_i=\Vert p-q{\Vert }_1$. If $d=0$, the two probability mass functions agree and the bound is zero. Otherwise every $d_i\le d\le 1/2$. The half-interval entropy summand bound, with $t=\min (p_i,q_i)$ and $v=d_i$, givesBy the triangle inequality, followed by Jensen's inequality for the concave function $f$,This proves the requested finite-alphabet entropy continuity bound: