Past exam of the communication Theory course of the University of Oxford / 2011 / 1

Use the continuous convention $0{\log }_2(0/q)=0$. Let $S=\{r:p_r>0\}$. Applying the allowed logarithm inequality to $q_r/p_r$ for $r\in S$ givesHence $d(p,q)\ge 0$. Equality forces ${\sum }_{r\in S}{q}_r=1$. Since every $q_r$ is strictly positive, this makes $S$ the entire alphabet. Equality in every weighted logarithm inequality then forces $q_r/p_r=1$ for every $r$. Conversely $p=q$ makes every summand zero. ThusThis is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

For the uniform distribution $u_r=1/n$, direct expansion givesPart (a) therefore proveswith equality exactly for $p_X(r)=1/n$ for every $r$. Thus the uniform distribution is the unique entropy maximizer.

Normalize the candidate distribution by settingThe supplied finite sum gives its meanThus it meets the constraint. Since ${\log }_2{q}_r={\log }_{2}c-r$, every other distribution $p$ with mean $m$ satisfiesNonnegativity and the equality case in part (a) proveThe maximum is unique; the entropy comparison uses the fixed mean rather than an unconstrained optimization.

The given logarithmic moment iswhere the $r=1$ term is zero. It is attained by the positive distributionwhose probabilities sum to one. Write $A=2/[n(n+1)]$, so ${\log }_2{q}_r={\log }_{2}A+{\log }_{2}r$. For any distribution $p$ with the required logarithmic moment,Consequently the unique maximizer and its entropy areThe increasing weights are consistent with the prescribed moment; they need not be a decreasing power law.

Write $w_i=(Aq{)}_i$. For each row put $S_i=\{j:a_{ij}>0\}$; the positive row entries ${\alpha }_i=(a_{ij}{)}_{j\in S_i}$ form a probability distribution because the row sum is one. When $w_i>0$, define the probability distributionPart (a), applied on this row support, gives $d(r_i,{\alpha }_i)\ge 0$. Its weighted sum expands asRows with $w_i=0$ contribute zero, since all $a_{ij}{q}_j$ in such a row vanish. Using the convention that zero-weight logarithmic terms are zero, the result isBoth stochasticity conditions have a role: row sums normalize the comparison distributions, while column sums preserve the total contribution from $q$.

This is entropy increase under doubly stochastic mixing.