Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 9 (Isoperimetry and Concentration of Measure)

Assume $X$ is nonempty, as is necessary for a probability measure to exist. Give its isometry group $I_X$ the uniform metricEvery distance-preserving self-map of a compact metric space is onto. Indeed, if $x_0\notin gX$, then $\delta =d(x_0,gX)>0$, and for $n>m$ the iterates satisfy $d(g^m{x}_0,g^n{x}_0)=d(x_0,g^{n-m}{x}_0)\ge \delta$. This infinite separated set contradicts compactness. Consequently $I_X$ is a group under composition, with the identity and inverses again isometries.

The metric $D$ is invariant under both left and right multiplication: left invariance uses preservation of distances, and right invariance uses surjectivity. Inversion is an isometry for $D$, and $D(gh,g^{\prime }{h}^{\prime })\le D(g,g^{\prime })+D(h,h^{\prime })$ proves continuity of multiplication. Moreover, $I_X$ is compact. A sequence of isometries has a subsequence converging at every point of a countable dense subset of $X$, by a diagonal argument. Their common Lipschitz constant $1$ and finite epsilon-nets of $X$ make this subsequence uniformly Cauchy. Its uniform limit preserves distances and is onto by the preceding argument. Thus $I_X$ is a compact metrizable topological group. A transitive group action means that for every $x,y\in X$ some $g\in I_X$ has $gx=y$.

We construct the invariant Borel probability measure directly. The Hall marriage theorem says that a finite bipartite graph with equal-sized vertex classes $A,B$ has a perfect matching precisely when every subset $S\subseteq A$ has at least $|S|$ neighbours in $B$. Its following consequence is useful. If $A,B$ are $\epsilon$-separated subsets of maximum cardinality in a compact metric space, join points whose distance is less than $\epsilon$. If some $S\subseteq A$ had fewer than $|S|$ neighbours, replacing those neighbours in $B$ by $S$ would produce a larger $\epsilon$-separated set. This contradicts maximal cardinality. Hence there is a bijection between $A$ and $B$ moving each point by less than $\epsilon$.

Choose ${\epsilon }_n\downarrow 0$ and maximum-cardinality ${\epsilon }_n$-separated sets $A_n\subset I_X$. Such sets exist: a finite covering by balls of radius less than ${\epsilon }_n/2$ bounds every separated set's cardinality. Fix $x_0\in X$ and define the empirical probability measuresFor $f\in C(X)$ let ${\omega }_f(r)={\sup }_{d(x,y)\le r}|f(x)-f(y)|$, which tends to zero with $r$ by uniform continuity. For every $h\in I_X$, left invariance of $D$ makes $h{A}_n$ another maximum-cardinality separated set. Match it to $A_n$ as above. ThenThe allowed compactness of probability measures on a compact metric space supplies a subsequence converging to $\mu$ in the weak-star topology. Passing to that limit for each fixed $h,f$ gives $\int fd\mu =\int f\circ hd\mu$. The same subsequence works for every $h,f$, since the displayed estimate held for all of them before taking the limit.

For uniqueness, put $F_n(x)=|A_n{|}^{-1}{\sum }_{a\in A_n}f(ax)$. For $x=h{x}_0$, right invariance of $D$ lets us match $A_{n}h$ with $A_n$. Transitivity therefore gives the uniform estimate $|F_n(x)-F_n(x_0)|\le {\omega }_f({\epsilon }_n)$ for every $x\in X$. If $\nu$ is any invariant Borel probability measure, thenTwo invariant probability measures consequently differ on the integral of $f$ by at most $2{\omega }_f({\epsilon }_n)$, hence agree on every continuous function. Continuous functions determine Borel probability measures on a compact metric space, so the invariant probability measure exists and is unique.

A real random variable is a sub-Gaussian random variable with exponent $b\ge 0$ when its moment-generating function satisfiesDifferentiating at $t=0$ from both sides gives $\mathbb{E}X=0$. Exponential integrability near zero justifies this differentiation. Conversely, if $|X|\le M$ and $\mathbb{E}X=0$, convexity givesThe last inequality follows by comparing power series using $(2j)!\ge 2^{j}j!$. The case $M=0$ is immediate. Thus a bounded random variable is sub-Gaussian exactly when it is centered; the bound $M$ is one possible exponent.

For $b>0$, the Markov inequality applied to $e^{tX}$ gives $\mathbb{P}(X>R)\le \exp (b^2{t}^2/2-tR)$. Choose $t=R/b^2$ and repeat with $-X$. The union bound yieldsIf $b=0$, the same exponential estimate with arbitrarily large $t$ shows $X=0$ almost surely, so all subsequent inequalities are trivial.

Integrating this tail probability estimate gives, for every real $k\ge 2$,We need $2\Gamma (k+1)\le k^k$. For integer $k$ this follows inductively from $2\cdot 2!=2^2$ and $(k+1)k^k\le (k+1{)}^{k+1}$. To cover real $k$ as well, set $H(k)=k\log k-\log \Gamma (k+1)-\log 2$. Differentiating the Gamma function integral gives $(\log \Gamma {)}^{\prime }(k+1)=\mathbb{E}\log Y$ for a Gamma distribution with shape $k+1$ and rate $1$. The Jensen inequality bounds this by $\log (k+1)$. Hence $H^{\prime }(k)\ge 1-\log (1+1/k)>0$ and $H(2)=0$. Taking the $2k$th root now provesHere $\Vert X{\Vert }_p=(\mathbb{E}|X{|}^p{)}^{1/p}$ is the Lp norm.

For the final assertion we prove the required Littlewood interpolation inequality, rather than assuming it. Apply Holder inequality with conjugate exponents $3/2$ and $3$:Raising to the power $3/2$ gives $\Vert X{\Vert }_2^3\le \Vert X{\Vert }_1\Vert X{\Vert }_4^2$. The preceding Lp norm estimate with $k=2$ says $\Vert X{\Vert }_4\le 2b$. Therefore

Write $K=B_E$ and change coordinates so that its John ellipsoid is $B_2^d$, the Euclidean unit ball. Then the standard symmetric-body inequalities areWe give the contact argument underlying the construction. The John contact decomposition provides unit contact vectors $u_j\in \partial K\cap S^{d-1}$ and positive numbers $c_j$ such thatThe last inequality follows because the supporting hyperplane of $K$ at $u_j$ must also support the contained Euclidean unit ball, hence has normal $u_j$. For completeness, the decomposition follows from maximal volume as follows. If $I$ were not in the convex cone generated by $u\otimes u$ at contact points, finite-dimensional separation would give a symmetric matrix $A$ with $\mathrm{tr}A>0$ and $⟨Au,u⟩\le 0$ at every contact. Subtract $\delta I$ for small $\delta >0$, retaining positive trace and obtaining strict negative values. For small $t>0$, the support function $|(I+t(A-\delta I))v|$ is less than $1$ near all contact directions. On the compact complement of those neighbourhoods, $h_K(v)-1$ has a positive minimum, so the perturbed ellipsoid remains inside $K$ there too. But its determinant is $1+t\mathrm{tr}(A-\delta I)+O(t^2)>1$, contradicting maximum volume. The cone is closed: its generating contact matrices form a compact set of trace $1$, so bounded traces bound their nonnegative coefficient sums. Finite-dimensional convexity then supplies finitely many contacts in the decomposition. Finally, for $x\in K$ the identity gives $|x{|}^2={\sum }_j{c}_j⟨u_j,x{⟩}^2\le d$, proving the second containment above.

Construct an orthonormal basis recursively. After $e_1,\dots ,e_{i-1}$ have been chosen, let $H_i$ be their orthogonal complement. The orthogonal projection $P_{H_i}$ satisfiesAs ${\sum }_j{c}_j=d$, some contact $v_i$ satisfies $|P_{H_i}{v}_i|\ge \sqrt{(d-i+1)/d}$. Choose $e_i=P_{H_i}{v}_i/|P_{H_i}{v}_i|$. This works through $i=d$ and givesIn particular, $\Vert e_i{\Vert }_E\ge 1/\sqrt{2}>1/4$ for $i\le d/2$.

Keep the contact vectors $v_i$ used for this basis. They lie in $\mathrm{span}(e_1,\dots ,e_i)$. Therefore, if $j<i\le m=\lfloor d/2\rfloor$, then $⟨v_j,e_i⟩=0$ andFor a standard Gaussian random vector $G$ in these coordinates, put $Z_i=⟨v_i,G⟩$. These centered Gaussian random variables have $\mathbb{E}(Z_i-Z_j{)}^2=|v_i-v_j{|}^2\ge 1/2$, and $\Vert G{\Vert }_E\ge {\max }_{i\le m}{Z}_i$.

Here is a proof of the Sudakov-Fernique inequality needed for this finite family. Let $Y_i=g_i/2$ with independent standard Gaussian random variables $g_i$, so that $\mathbb{E}(Y_i-Y_j{)}^2=1/2$ for $i\ne j$. Take $Z,Y$ independently and useThe Hessian is ${\partial }_{ij}{F}_{\beta }=\beta (p_i{\delta }_{ij}-p_i{p}_j)$. Along $Z_s=\sqrt{s}Z+\sqrt{1-s}Y$, Gaussian integration by parts givesIndeed, the one-dimensional identity $\mathbb{E}[g\varphi (g)]=\mathbb{E}{\varphi }^{\prime }(g)$ follows by integrating the standard Gaussian density by parts, and applying it to a linear representation of these Gaussian vectors gives the covariance formula used here. Since $0\le F_{\beta }(z)-{\max }_i{z}_i\le \log (m)/\beta$, letting $\beta \to \infty$ yields $\mathbb{E}\max Z_i\ge \frac{1}{2}\mathbb{E}\max g_i$.

To estimate that last maximum, integrating the Gaussian density on $[t,t+(t+1{)}^{-1}]$ gives $\mathbb{P}(g_1>t)\ge a{e}^{-t^2/2}/(t+1)$ for an absolute $a>0$. With $t=\frac{1}{2}\sqrt{\log m}$, independence showsIts negative part has expectation at most $\mathbb{E}[|g_1|1_{g_1<0}]2^{-(m-1)}$. Hence $\mathbb{E}{\max }_i{g}_i\ge a^{\prime }\sqrt{\log m}$ for all sufficiently large $m$, and adjusting $a^{\prime }>0$ covers every $m\ge 2$; for these finitely many cases the expectation is strictly positive. For $d\ge 4$, $\log \lfloor d/2\rfloor \ge \frac{1}{3}\log d$. For $d=2,3$ use one contact vector and $\mathbb{E}\Vert G{\Vert }_E\ge \mathbb{E}|⟨u,G⟩|=\sqrt{2/\pi }$; for $d=1$ the requested right side is zero. Thusfor an absolute $c>0$, independent of both dimension and the norm.

For a $d$-dimensional normed vector space, with unit ball $K$ and John ellipsoid $\mathcal{E}$, its volume ratio isIt is at least $1$ and invariant under invertible linear coordinate changes.

For ${\ell }_1^n$, the unit ball has volume $2^n/n!$: its intersection with each orthant is the standard simplex of volume $1/n!$. Its John ellipsoid is $n^{-1/2}{B}_2^n$. To verify maximum volume, let $A{B}_2^n$ be any centered inscribed ellipsoid. For each sign vector $\epsilon \in \{-1,1{\}}^n$, containment gives $|A^T\epsilon |\le 1$. Averaging over independent Rademacher random variables yields $\mathrm{tr}(A{A}^T)\le 1$. The arithmetic-geometric mean inequality for its squared singular values gives $|\det A|\le n^{-n/2}$. The scalar matrix $n^{-1/2}I$ attains this bound because $\Vert x{\Vert }_1\le \sqrt{n}|x|$. Centered ellipsoids suffice: if $a+A{B}_2^n$ is contained in the symmetric convex unit ball, averaging it with $-a+A{B}_2^n$ gives the centered copy with the same volume.

Using the stated Euclidean ball volume and $n=2k$,since $(2k)!/k!={\prod }_{j=k+1}^{2k}j\ge k^k$. Therefore $\mathrm{vr}({\ell }_1^{2k})\le \sqrt{8/\pi }$ uniformly in $k$.

The subsequent assertion for an arbitrary $2k$-dimensional space is false as printed. Here is a counterexample independent of any asymptotic section theorem. Take $E={\ell }_{\infty }^{2k}$. Its John ellipsoid is $B_2^{2k}$: an inscribed $A{B}_2^{2k}$ has every row of $A$ of Euclidean length at most $1$, so the Hadamard inequality gives $|\det A|\le 1$, attained by $A=I$. Let $F$ be any $k$-dimensional subspace and $f_1,\dots ,f_k$ an orthonormal basis of it. The random unit vectorhas $|x|=1$. Since ${\sum }_j{f}_j(i{)}^2\le 1$ for each coordinate $i$, the moment-generating function bound for independent Rademacher random variables givesChoose $r=\sqrt{2\log (8k)/k}$; the latter probability is at most $1/2$, so some unit vector in $F$ has $\Vert x{\Vert }_{\infty }\le r$. The proposed section inequality would therefore forceThus even one half-dimensional section cannot have the printed universal constant.

The valid orthogonal splitting with bounded volume ratio is that $L$ may depend on $V=\mathrm{vr}(E)$, and $L=32V^2$ suffices. This supplies a dimension-independent constant for the preceding ${\ell }_1^{2k}$ case, or whenever $V$ is bounded uniformly. We prove the complete qualified assertion, including its epsilon-net ingredient.

In John position, $\Vert x{\Vert }_E\le |x|$. Polar integration of the radial function $\rho (u)=1/\Vert u{\Vert }_E$ giveswhere $\sigma$ is normalized spherical measure.

A maximal $\epsilon$-separated subset of $S^{k-1}$ is an epsilon-net. Balls of radius $\epsilon /2$ about its points have disjoint interiors and lie in the ball of radius $1+\epsilon /2$. Comparing volumes bounds its cardinality by $(1+2/\epsilon {)}^k$. Finite existence follows from this packing bound, and maximality proves the net property without assuming a separate covering theorem.

Choose two orthogonal $k$-dimensional subspaces $F_0,F_0^{\perp }$ and one such net on each unit sphere. Rotate both by a common uniformly distributed orthogonal matrix $U$. This distribution can be obtained from Question 1 applied to the compact orthogonal group with its Frobenius metric; left and right multiplication are transitive isometries. Consequently $Uv$ is uniformly distributed on $S^{2k-1}$ for every fixed unit vector $v$. The union bound shows that the probability that some rotated net point has norm less than $2\epsilon$ is at mostSet $\epsilon =(32V^2{)}^{-1}$. Because $V\ge 1$, the bracket is at most $1/4+1/256$, and twice its $k$th power is less than $1$ for every $k\ge 1$. Some rotation therefore makes every point of both nets have norm at least $2\epsilon$.

The triangle inequality and $\Vert x{\Vert }_E\le |x|$ imply that $\Vert \cdot {\Vert }_E$ is $1$-Lipschitz for the Euclidean metric. Every unit vector of $U{F}_0$ or $U{F}_0^{\perp }$ is within $\epsilon$ of a good net point and thus has norm at least $\epsilon$. By homogeneity, on both orthogonal subspaces,For ${\ell }_1^{2k}$ the first computation gives the absolute choice $L=256/\pi$. The missing bounded-volume ratio restriction is essential; the literal unrestricted assertion cannot be proved.

Use the Lipschitz constant convention $\Vert f{\Vert }_L={\sup }_{x\ne y}|f(x)-f(y)|/d(x,y)$ in the final quantity; it is a seminorm, with constants having value zero. Also interpret the coupling space as $\mathcal{P}(X\times X)$. The printed $\mathcal{P}(X,Y)$ has an undefined $Y$. The third quantity has a duplicated printed label; it is placed in part iii here, with the fourth in part iv.

First prove weak optimal transport duality. For any feasible continuous pair $f,g$ and any coupling of probability distributions $\pi$ with marginals $P,Q$,Taking the supremum over pairs and infimum over couplings gives $m_d(P,Q)\le W(P,Q)$. These quantities are finite: $P\otimes Q$ is a coupling and the continuous cost $d$ is bounded on the compact metric space $X\times X$. The zero pair is feasible, so $0\le m_d\le W\le \mathrm{diam}X$.

The reverse inequality is established in part ii by finite approximation and a proof of the required finite linear programming duality. Parts iii and iv then show that all the dual formulations agree.

Fix $\epsilon >0$ and a finite epsilon-net $x_1,\dots ,x_N$ in $X$. Choose a Borel map $r:X\to \{x_1,\dots ,x_N\}$ with $d(x,r(x))\le \epsilon$, for example the nearest point with ties broken by index. Its cells $A_i$ give discrete probability measures with masses $p_i=P(A_i)$ and $q_i=Q(A_i)$. LetThe feasible set is nonempty and compact, so the minimum exists. Pushing any coupling forward by $(r,r)$ changes its cost by at most $2\epsilon$, hence $W_{\epsilon }\le W+2\epsilon$. Conversely, lift a discrete coupling by the measureTerms with zero row or column masses vanish. This lift has marginals $P,Q$, and its cost differs by at most $2\epsilon$. Therefore

Here is the finite linear programming duality proof. Write $d_{ij}=d(x_i,x_j)$ and consider the convex coneIt is closed and finitely generated. One elementary justification of closedness is to reduce each nonnegative representation to linearly independent generators, eliminating a coefficient along any linear dependence; after choosing a subsequence using the same subset of generators, their independent coordinates have bounded, convergent coefficients whenever the represented vectors converge. For $\eta >0$, the point $(p,q,W_{\epsilon }-\eta )$ lies outside $C$. Separation from this closed convex cone gives coefficients $(a,b,\tau )$ withIf $\tau =0$, summing the middle inequalities against any feasible $\pi$ contradicts the last one. Thus $\tau >0$, and $f_i=-a_i/\tau$, $g_j=-b_j/\tau$ obey $f_i+g_j\le d_{ij}$ with dual objective greater than $W_{\epsilon }-\eta$. The weak inequality already proved gives the reverse bound. Letting $\eta \downarrow 0$ proves finite strong duality.

Reduce this discrete dual to a single Lipschitz function. For a feasible pair put ${\varphi }_i={\min }_j(d_{ij}-g_j)$. The triangle inequality gives $|{\varphi }_i-{\varphi }_l|\le d_{il}$, while $f_i\le {\varphi }_i$ and $g_i\le -{\varphi }_i$. ConsequentlyConversely, any $1$-Lipschitz vector $\varphi$ gives a feasible pair $(\varphi ,-\varphi )$. Adding a constant leaves its objective unchanged, so impose ${\varphi }_1=0$. The resulting feasible set is compact, and its maximum is $W_{\epsilon }$.

For a maximizing vector, the McShane extension theorem has the following explicit proof in this situation. DefineThe triangle inequality proves that this extension is $1$-Lipschitz, and the discrete Lipschitz condition makes $\varphi (x_i)={\varphi }_i$. Thus $(\varphi ,-\varphi )$ is a continuous feasible pair. Because $|\varphi (x)-\varphi (r(x))|\le \epsilon$,Letting $\epsilon \downarrow 0$, together with part i, proves $m_d(P,Q)=W(P,Q)$. The infimum defining $W$ is also attained: the set of couplings is a closed subset of the compact space of probability measures on $X\times X$, and integrating the continuous cost is continuous for the weak-star topology.

Since Lipschitz functions are continuous, the feasible class here is smaller, giving $m_L\le m_d$. To prove the reverse inequality, take any continuous feasible pair $f,g$ and perform Lipschitz regularization of transport potentials:The minimum exists by compactness. For every $x,x^{\prime }$ the triangle inequality gives $h(x)\le d(x,x^{\prime })+h(x^{\prime })$; interchanging $x,x^{\prime }$ proves $|h(x)-h(x^{\prime })|\le d(x,x^{\prime })$. Thus $h$ has Lipschitz constant at most $1$.

The original constraint yields $f(x)\le h(x)$, and evaluating the minimum at $y=x$ gives $h(x)\le -g(x)$. Moreover, $h(x)-h(y)\le d(x,y)$, so $(h,-h)$ is a feasible Lipschitz pair withTaking the supremum over the original continuous pairs proves $m_L(P,Q)=m_d(P,Q)=W(P,Q)$. Notice that this is an exact regularization, with no density or approximation assumption about the initial pair.

Every function $h$ with Lipschitz constant at most $1$ yields a feasible pair $(h,-h)$, and replacing $h$ by $-h$ reverses the objective. HenceConversely, the Lipschitz regularization of transport potentials in part iii dominates every feasible pair by $(h,-h)$ with $\Vert h{\Vert }_L\le 1$, so $m_L\le \gamma$. Together with the preceding parts this proves the Kantorovich–Rubinstein theorem here in all four requested forms:The seminorm convention is essential. If instead $\Vert h{\Vert }_L$ meant $\Vert h{\Vert }_{\infty }+\mathrm{Lip}(h)$, the equality would fail: on a two-point space at distance $2$, with point masses at the two different points, $W=2$ whereas the latter unit-ball supremum is $1$. Indeed, an oscillation $a$ needs supremum norm at least $a/2$ and Lipschitz constant $a/2$, so the sum norm bounds $a$ by $1$, attained by values $-1/2,1/2$. This distinguishes the Lipschitz seminorm used above from a full bounded-Lipschitz norm.