Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 30 / 1

Use base-two logarithms and the convention $0{\log }_{2}0=0$. Write $p_y=\mathbb{P}(Y=y)$ and $q_y(x)=\mathbb{P}(X=x\mid Y=y)$ for $p_y>0$. The conditional entropy is the average of the information entropies of these conditional laws:The careful form of Gibbs inequality is that, for two probability mass functions $q,p$ on a common countable set,where a term with $q(x)>0=p(x)$ gives $+\infty$. Equality holds exactly when $q=p$. This is the nonnegativity of relative entropy.

First suppose $H(X)<\infty$. For every $y$ of positive probability, $q_y(x)>0$ implies $p_X(x)>0$. Averaging the cross-entropies givesAll the summands here are nonnegative, so interchanging the sums is valid, and each conditional cross-entropy is finite. Applying Gibbs inequality to each $q_y,p_X$ shows that $H(q_y)$ is at most its cross-entropy. Subtracting and averaging therefore givesEvery term on the right is nonnegative. The equality in the entropy conditioning inequality is thus equivalent to $q_y=p_X$ for all $p_y>0$, which is exactly factorization of the joint probability mass function. Consequently

For arbitrary countable discrete random variables, the inequality remains valid in $[0,\infty ]$: the case $H(X)=\infty$ is immediate. The finite-entropy condition is necessary for the usual equality characterization. For example, let $\mathbb{P}(A=n)=c/(n(\ln n{)}^2)$ for $n\ge 2$, with $c$ the normalizing constant, and let $B$ be an independent fair bit. The series defining the probability mass function converges, whereas its information entropy diverges like ${\sum }_{n}1/(n\ln n)$. Then $X=(A,B)$ and $Y=B$ are dependent, but $H(X)=H(X\mid Y)=\infty$. In the infinite case, equality means precisely that the conditional entropy is also infinite; it does not imply independent random variables.

Introduce a selector $B$ with Bernoulli distribution of parameter $\alpha$, and construct $W$ by taking its conditional law given $B=1$ to be $p_U$, and its conditional law given $B=0$ to be $p_V$. No prescribed joint law of $U,V$ is needed. Summing over the selector gives the desired mixture probability mass function. The conditional entropy isSince conditioning cannot increase information entropy,This proves the concavity of information entropy. The argument also covers infinite information entropies with the convention that a zero mixing weight contributes zero. At $\alpha =0$ or $1$, the mixture is the corresponding original law and equality is immediate.

For $N\sim \mathrm{Pois}(\lambda )$, the Poisson distribution givesThis information entropy is finite: ${\log }_2(n!)\le n^2$ for integer $n\ge 0$, while $\mathbb{E}{N}^2=\lambda +{\lambda }^2$.

Fix $0<{\lambda }_1<{\lambda }_2$. Take independent random variables $U\sim \mathrm{Pois}({\lambda }_1)$ and $V\sim \mathrm{Pois}({\lambda }_2-{\lambda }_1)$. Their convolution isby the binomial theorem. Thus $U+V$ has Poisson distribution with parameter ${\lambda }_2$. Conditioning on $V=v$ only translates $U$, so $H(U+V\mid V)=H(U)=F({\lambda }_1)$. The entropy monotonicity under independent addition yields $F({\lambda }_2)\ge F({\lambda }_1)$.

In fact the inequality is strict. The covariance $\mathrm{Cov}(U+V,V)=\mathrm{Var}(V)={\lambda }_2-{\lambda }_1$ is positive, so $U+V$ and $V$ are not independent random variables. Their information entropies are finite, and the equality criterion from part (a) excludes equality. Therefore the Poisson entropy monotonicity gives the stronger conclusion