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

All logarithms have base two. In part a the information entropy differences and information expressions are interpreted where they are well defined; finite joint entropy is a sufficient hypothesis. This avoids undefined expressions such as infinity minus infinity.

The chain rule for conditional entropy givesIndeed, for every conditioning value $(x,z)$ of positive probability, each summand $-p(y\mid x,z){\log }_{2}p(y\mid x,z)$ is nonnegative. Its sum is zero exactly when the conditional probability mass function is concentrated at one value. Averaging over $(X,Z)$ therefore proves both the inequality and its equality criterion: equality holds exactly when $Y=f(X,Z)$ almost surely for some function $f$. Conditioning values of probability zero impose no restriction. This is a statement about discrete random variables; a differential entropy need not be nonnegative.

Expand the two observations in order using the chain rule for mutual information:The remaining conditional mutual information isRelative entropy nonnegativity proves the inequality. Equality requires every positive-weight relative entropy to vanish, which is equivalent to $p(y,z\mid x)=p(y\mid x)p(z\mid x)$ for every $x$ of positive probability. Thus equality holds exactly when $Y$ and $Z$ have conditional independence given $X$. No unconditional independence is required.

The chain rule for information entropy converts the two differences into conditional entropies. Their gap, in the order right minus left, isThis is additional conditioning reduces entropy. The relative entropy representation of conditional mutual information identifies exactly when that gap vanishes: equality holds if and only if $Y$ and $Z$ have conditional independence given $X$. Knowledge of $Y$ then changes no conditional probability of $Z$ after $X$ is known.

Here the asserted bound is actually an identity, so equality always holds whenever the displayed quantities are defined. Expand the same mutual information in two orders:Equating these expressions and using symmetry of mutual information and conditional mutual information givesThere is no further independence condition. Treating this part as a strict inequality would obscure its cancellation.

For probability mass functions on the finite alphabet, take logarithms to base two and define the relative entropy byA term with $q_i=0$ is zero, including $p_i=0$; a term with $q_i>0=p_i$ is $+\infty$. Fix $p_i>0$ and write $f_i(t)=t{\log }_2(t/p_i)$. For $t>0$,Thus $f_i$ is a convex function on $[0,\infty )$ by continuous extension to zero. For $0\le \lambda \le 1$, applying this scalar convexity to each coordinate and summing provesIf $p$ has zero coordinates, the finite-valued domain consists of probability mass functions supported on $\{i:p_i>0\}$; it is convex and the same proof applies there. Outside that domain the right side is infinite whenever an offending probability mass function has a positive mixture weight, so the extended-valued convexity assertion still holds. At mixture weights zero or one the inequality is an identity, without needing the expression $0\cdot \infty$.

Index correction: the printed definition only permits $i\le n$, although the required average includes $i=n+1$. Extend the same deletion formula to $1\le i\le n+1$. Without that extension the final summand is undefined; there is no new sample or different estimator to supply.

For a fixed outcome of the sample and a fixed symbol $x$, put $A_j=1_{\{X_j=x\}}$. The leave-one-out empirical distribution then satisfiesDividing by $n+1$ gives ${\hat{p}}_{n+1}=(n+1{)}^{-1}{\sum }_{i=1}^{n+1}{\hat{q}}_{n,i}$. Each of the $n+1$ indicator functions was counted exactly $n$ times before division by $n$. This leave-one-out identity for empirical distributions is deterministic; independence plays no part in this part.

Reference-distribution ambiguity: $\rho$ is not defined in the paper. If it is an arbitrary probability mass function, the printed inequality is false. For instance, choose $p=(1,0)$ and $\rho =(1/2,1/2)$. Every empirical distribution equals $p$, making the printed left side one bit and its right side zero. This is a counterexample for every $n\ge 1$.

Under the consistent interpretation $\rho =p$, the preceding leave-one-out identity for empirical distributions and convexity of relative entropy in its first argument give, for every sample,Deleting any one observation from $n+1$ independent and identically distributed random variables leaves $n$ independent observations with probability mass function $p$. Consequently each ${\hat{q}}_{n,i}$ has the same distribution as ${\hat{p}}_n$. They need not be independent of one another. Taking expected values and using linearity of expectation therefore provesZero coordinates of $p$ are never sampled, almost surely, so the calculation can be restricted to its probability support. In particular the expected values are finite on this finite alphabet.

The discrepancy cannot be removed by silently choosing any fixed reference. Whenever $\rho$ is positive on the probability support of $p$, direct subtraction and $\mathbb{E}{\hat{p}}_n=p$ give the expected relative entropy decompositionThus the valid arbitrary-reference version has $\rho$ on both sides; the printed mixed-reference version has an additional term whose sign prevents the proposed conclusion.

For the maximum entropy distribution on the nonnegative integers, use the geometric distribution counting failures before the first success. Write $r=a/(a+1)$ and defineThe geometric series gives ${\sum }_i{g}_i=1$. Termwise differentiation of a power series applied to that geometric series for $0<r<1$ gives ${\sum }_{i}i{r}^i=r/(1-r{)}^2$, hence ${\sum }_{i}i{g}_i=r/(1-r)=a$.

For any competing probability mass function $p$ of mean $a$, its cross-entropy against $g$ isThis is finite. The fact that finite cross entropy bounds countable information entropy must be justified without assuming in advance that $H(p)$ is finite. Use $\ln u\le u-1$ with $u=g_i/p_i$ when $p_i>0$. Including zero terms by their limiting convention yields, for every finite $N$,Let $N\to \infty$. The information entropy partial sums increase, the cross-entropy partial sums converge to the finite value above, and the final mass difference tends to zero. This proves finiteness and the upper bound. We may now writeRelative entropy nonnegativity has equality exactly when $p=g$. Therefore the displayed geometric probability mass function is the unique maximizer, andThe mean constraint is essential: without it, uniform distributions on longer initial intervals have unbounded information entropy.