Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 210 / 4 / Solution

The total variation distance and Kullback-Leibler divergence arewith the divergence $+\infty$ when $P$ is not absolutely continuous with respect to $Q$.

For $P=\mathrm{Laplace}(0)$ and $Q=\mathrm{Laplace}(\mu )$,If $X\sim P$, direct integration on the intervals cut by $0$ and $\mu$ givesConsequently

One squared-loss form of Assouad's lemma is as follows. Suppose $(P_{\omega },{\theta }_{\omega }{)}_{\omega \in \{0,1{\}}^k}$ is an Assouad hypercube such thatand every pair of neighboring vertices satisfies $\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }})\le \eta$. ThenTo prove it, decode from $\hat{\theta }$ a nearest hypercube vertex. The separation condition converts estimation loss into a constant multiple of its Hamming error. Average this error under the uniform prior on $\omega$ and sum coordinatewise. For each coordinate, the two equally weighted mixtures with that bit equal to zero or one have total variation at most $\eta$ by convexity. The minimum average error of any binary test is $(1-\mathrm{TV})/2$, which gives the displayed bound after the nearest-vertex factor.

We now build such a hypercube inside the monotone cone. Let $k=\lfloor c_0{n}^{1/3}\rfloor$ and $m=\lfloor n/k\rfloor$. Divide the first $km$ coordinates into $k$ consecutive blocks. For $\omega \in \{0,1{\}}^k$, set on block $j$and extend the remaining coordinates at the last level. If $c_0,c_1$ are sufficiently small universal constants, every signal is nondecreasing and belongs to $[0,1{]}^n$.

Neighboring vertices differ by $\delta$ on one block, so their squared Euclidean separation is $m{\delta }^2$. Their product experiments differ only on that block and haveBy Pinsker's inequality, choosing $c_1$ small makes every neighboring total variation distance at most, say, $1/4$.

Apply Assouad's lemma with normalized squared loss $d^2(\theta ,{\theta }^{\prime })=n^{-1}\Vert \theta -{\theta }^{\prime }{\Vert }^2$. Here $a=m{\delta }^2/n=c_1^2/n$, and henceThis proves the lower half of the minimax rate for isotonic sequence estimation.