Proof of Quantile Blocks of an Atomless Measure on the Line: Block Maps, Distances to Ordered Empirical Measures, and the Block Test Function

Each result cited is universally quantified over the data in its own statement, and is applied to the data named here.

Throughout, $\mathbb{R}=\mathbb{R}^{1}$ as in One-Dimensional Test Functions: Scalars, Derivatives, and the Difference Quotient of the Derivative, so that by One-Dimensional Test Functions: Scalars, Derivatives, and the Difference Quotient of the Derivative §scalars the space $L^{2}(\hat{\mu};\mathbb{R})$ consists of the classes of the Borel $\xi:\mathbb{R}\to\mathbb{R}$ with $\int\xi^{2}\,d\hat{\mu}<\infty$, with $\langle\xi,\eta\rangle_{\hat{\mu}}=\int\xi\eta\,d\hat{\mu}$ and $\lVert\xi\rVert_{\hat{\mu}}^{2}=\int\xi^{2}\,d\hat{\mu}$; it is a real Hilbert space by Wasserstein Spaces, Random Vectors, Vector Fields and Symmetric Matrices in Every Dimension: Standing Notation §fields, so the Cauchy-Schwarz and triangle inequalities hold for its inner product and norm. Integrals without a domain are over $\mathbb{R}$ (against $\hat{\mu}$ unless another measure is named), and $\int_{B}g$ means $\int g\mathbf{1}_{B}\,d\hat{\mu}$. With $d=1$ the configuration space is $\mathbb{R}^{N}$ and, the block index of Particle Blocks of the Configuration Space: Block Maps, Configurations, Product Maps and Diagonal Points §blocks being $b(k,1)=k$, the $k$-th particle of $x\in\mathbb{R}^{N}$ is $\mathfrak{p}_{k}(x)=x_{k}$. Changes of variables $\int g\,d(S_{\#}\rho)=\int g\circ S\,d\rho$ are those of Probability Measures on Euclidean Space and Random Vectors: Standing Notation §pushforward, used for nonnegative Borel $g$ and for $g$ integrable against $S_{\#}\rho$. For $j=0,1,\dots,N$ put $c_{j}=\frac{N-j}{N}$, so that $c_{0}=1$, $c_{j}<c_{j-1}$, $B_{i}=\{c_{i}<F\le c_{i-1}\}$ for $i<N$ and $B_{N}=\{F\le c_{N-1}\}$.

Step 1 (The distribution function). By claim 2 (monotonicity) of Basic Properties of a Measure, $F$ is nondecreasing with values in $[0,1]$. Fix $s\in\mathbb{R}$. As $m\ge1$ increases, the sets $(-\infty,s-\frac{1}{m}]$ increase with union $(-\infty,s)$, the sets $(s+\frac{1}{m},\infty)$ increase with union $(s,\infty)$, and the sets $(-\infty,m]$ and $(-m,\infty)$ increase with union $\mathbb{R}$. Hence, by claim 5 (continuity from below) and claim 3 (differences) of Basic Properties of a Measure, as $m\to\infty$,

By claim 1 (finite additivity) of Basic Properties of a Measure, $F(s)=\hat{\mu}((-\infty,s))+\hat{\mu}(\{s\})$, and $\hat{\mu}(\{s\})=0$ because $\hat{\mu}$ is atomless; so also $F(s-\frac{1}{m})\to F(s)$.

Step 2 (Level sets). We show: for real $t$ with $0<t\le1$ the set $L_{t}=\{s\in\mathbb{R}:F(s)\le t\}$ is Borel and $\hat{\mu}(L_{t})=t$. For $t=1$, $L_{1}=\mathbb{R}$ since $F\le1$. Let $0<t<1$. Since $F(-m)\to0<t$, some $F(-m)\le t$, so $L_{t}\neq\varnothing$. Since $F(m)\to1>t$, there is $n_{0}$ with $F(n_{0})>t$, and every $s\in L_{t}$ satisfies $s<n_{0}$, as $s\ge n_{0}$ would give $F(s)\ge F(n_{0})>t$. So $s_{t}=\sup L_{t}$ is a real number, by the Dedekind completeness of the real numbers. For each $m\ge1$ there is $s_{m}\in L_{t}$ with $s_{m}>s_{t}-\frac{1}{m}$, whence $F(s_{t}-\frac{1}{m})\le F(s_{m})\le t$; letting $m\to\infty$ and using Step 1 gives $F(s_{t})\le t$. Also $s_{t}+\frac{1}{m}\notin L_{t}$, so $F(s_{t}+\frac{1}{m})>t$, and Step 1 gives $F(s_{t})\ge t$. Thus $F(s_{t})=t$. If $s\le s_{t}$ then $F(s)\le F(s_{t})=t$, and if $s>s_{t}$ then $s\notin L_{t}$; hence $L_{t}=(-\infty,s_{t}]$, which is Borel, and $\hat{\mu}(L_{t})=F(s_{t})=t$.

Step 3 (Claim 1). For $1\le i\le N-1$ one has $0<\frac{1}{N}\le c_{i}\le\frac{N-1}{N}<1$ and $0<c_{i-1}\le1$, and $B_{i}=L_{c_{i-1}}\setminus L_{c_{i}}$ with $L_{c_{i}}\subseteq L_{c_{i-1}}$; also $B_{N}=L_{c_{N-1}}$ with $0<c_{N-1}=\frac{1}{N}\le1$. By Step 2 each $B_{i}$ is Borel, $\hat{\mu}(B_{N})=\frac{1}{N}$, and, by claim 3 of Basic Properties of a Measure, $\hat{\mu}(B_{i})=c_{i-1}-c_{i}=\frac{1}{N}$ for $i<N$. Let $i<j$, $s\in B_{i}$ and $t\in B_{j}$. Then $i<N$, so $F(s)>c_{i}$, while $F(t)\le c_{j-1}\le c_{i}$ because $j-1\ge i$. Hence $F(t)<F(s)$; in particular $s\neq t$, so $B_{i}\cap B_{j}=\varnothing$, and $t<s$, since $t\ge s$ would give $F(t)\ge F(s)$. Finally let $s\in\mathbb{R}$. If $F(s)\le c_{N-1}$ then $s\in B_{N}$. Otherwise $F(s)>c_{N-1}$; let $i$ be the least element of $\{1,\dots,N-1\}$ with $F(s)>c_{i}$. Then $F(s)\le c_{i-1}$, by $F\le1=c_{0}$ if $i=1$ and by minimality if $i>1$, so $s\in B_{i}$. Thus the $B_{i}$ are pairwise disjoint with union $\mathbb{R}$. Consequently every $s$ lies in exactly one $B_{i}$, and for every Borel $g:\mathbb{R}\to\mathbb{R}$ that is nonnegative or $\hat{\mu}$-integrable, $g=\sum_{i=1}^{N}g\mathbf{1}_{B_{i}}$ pointwise and so, by linearity of the integral,

Step 4 (Claim 2). Let $x\in\mathbb{R}^{N}$. For Borel $A\subseteq\mathbb{R}$, $T_{x}^{-1}(A)=\bigcup_{i:\,x_{i}\in A}B_{i}$, a finite union of Borel sets by Step 3; so $T_{x}$ is Borel. As $|T_{x}|\le\max_{i}|x_{i}|$, $T_{x}^{2}$ is bounded and integrable, so the class of $T_{x}$ lies in $L^{2}(\hat{\mu};\mathbb{R})$. By claim 1 of Basic Properties of a Measure, Step 3 and Basic Properties of Empirical Measures: Values, Integrals, Push-Forwards, Second Moment, and Lipschitz Dependence on the Configuration §values,

for every Borel $A$, so $(T_{x})_{\#}\hat{\mu}=\mu^{N}_{x}$, the empirical measure of The Empirical Measure of a Configuration of N Particles §empirical. For $x,y\in\mathbb{R}^{N}$, $(T_{x}-T_{y})^{2}=(x_{i}-y_{i})^{2}$ on $B_{i}$, so by (P) and Step 3, $\lVert T_{x}-T_{y}\rVert_{\hat{\mu}}^{2}=\sum_{i}(x_{i}-y_{i})^{2}\hat{\mu}(B_{i})=\frac{1}{N}\lVert x-y\rVert^{2}$. Now let $x$ be ordered and $s\le t$, with $s\in B_{i}$, $t\in B_{j}$. If $i<j$, Step 3 would give $t<s$; so $j\le i$, hence $x_{j}\ge x_{i}$, that is $T_{x}(t)\ge T_{x}(s)$. So $T_{x}$ is nondecreasing.

Step 5 (Claim 3: integrability and the upper bound). Let $x$, $\nu$, $T$ be as in claim 3, with $E$ a Borel set of full $\hat{\mu}$-measure on which $T$ is nondecreasing. By The Optimal Map as a Square-Integrable Vector Field: Integrability, Transport Cost and Uniqueness of the Class §square-integrable, applied in dimension $1$ with $S=T$ and the measures $\hat{\mu},\nu$, since $T_{\#}\hat{\mu}=\nu\in\mathcal{P}_{2}(\mathbb{R})$ we get $\int T^{2}\,d\hat{\mu}=M_{2}(\nu)<\infty$, so the class of $T$ lies in $L^{2}(\hat{\mu};\mathbb{R})$; in particular $T$ and $T_{x}T$ are $\hat{\mu}$-integrable (as $|T|\le\frac{1}{2}(1+T^{2})$ and $|T_{x}T|\le\frac{1}{2}(T_{x}^{2}+T^{2})$). Also $\mu^{N}_{x}\in\mathcal{P}_{2}(\mathbb{R})$ with $M_{2}(\mu^{N}_{x})=\frac{1}{N}\lVert x\rVert^{2}$ by Basic Properties of Empirical Measures: Values, Integrals, Push-Forwards, Second Moment, and Lipschitz Dependence on the Configuration §moment. By Couplings on Euclidean Space: Product Coupling, Swap, Finiteness of the Cost, Push-Forward Couplings, Modifying One Marginal, Quantisation, Gluing over a Finitely Supported Measure, and the Lipschitz Bound §pushforward and Step 4, $\gamma_{0}=(T_{x},T)_{\#}\hat{\mu}$ is a coupling of $\mu^{N}_{x}$ and $\nu$ with quadratic cost $\int(T_{x}-T)^{2}\,d\hat{\mu}=\lVert T_{x}-T\rVert_{\hat{\mu}}^{2}$. By The Quadratic Wasserstein Distance on Euclidean Space §distance, $W_{2}(\mu^{N}_{x},\nu)^{2}\le\lVert T_{x}-T\rVert_{\hat{\mu}}^{2}$.

Step 6 (Claim 3: reduction of the lower bound). Let $\gamma\in\Pi(\mu^{N}_{x},\nu)$ and write $a=\mathrm{pr}_{1}(z)$, $b=\mathrm{pr}_{2}(z)$ for $z\in\mathbb{R}^{2}$. By change of variables along $\mathrm{pr}_{1}$ and $\mathrm{pr}_{2}$ and the coupling property, $\int a^{2}\,d\gamma=M_{2}(\mu^{N}_{x})=\frac{1}{N}\lVert x\rVert^{2}$ and $\int b^{2}\,d\gamma=M_{2}(\nu)$, both finite; hence $b$ and $ab$ are $\gamma$-integrable ($|b|\le\frac{1}{2}(1+b^{2})$, $|ab|\le\frac{1}{2}(a^{2}+b^{2})$), and the quadratic cost is

Likewise, by Step 4 (with $y=0$) and Step 5, $\lVert T_{x}-T\rVert_{\hat{\mu}}^{2}=\int T_{x}^{2}+\int T^{2}-2\int T_{x}T=\frac{1}{N}\lVert x\rVert^{2}+M_{2}(\nu)-2\int T_{x}T$. So $I(\gamma)\ge\lVert T_{x}-T\rVert_{\hat{\mu}}^{2}$ follows once we show

Granting ($\ast$) for every $\gamma$, $\lVert T_{x}-T\rVert_{\hat{\mu}}^{2}$ is a lower bound of the costs, so it is at most their greatest lower bound $W_{2}(\mu^{N}_{x},\nu)^{2}$; with Step 5 and nonnegativity of both sides, $W_{2}(\mu^{N}_{x},\nu)=\lVert T_{x}-T\rVert_{\hat{\mu}}$.

Step 7 (Claim 3: layer-cake decomposition). Let $z_{1}>z_{2}>\dots>z_{m}$ ($m\ge1$) be the distinct values among $x_{1},\dots,x_{N}$, and $Z=\{z_{1},\dots,z_{m}\}$. For $p\in[m]$ let $k_{p}$ be the number of $i$ with $x_{i}\ge z_{p}$; as $x$ is ordered, $x_{i}\ge z_{p}$ and $j<i$ give $x_{j}\ge z_{p}$, so $\{i:x_{i}\ge z_{p}\}=\{1,\dots,k_{p}\}$, and for $p\le m-1$ we have $1\le k_{p}\le N-1$ (some $x_{i}$ equals $z_{p}$, and some equals $z_{m}<z_{p}$). For every $r\in Z$,

since for $r=z_{l}$ the indicator equals $1$ exactly when $p\ge l$ and the sum telescopes to $z_{l}-z_{m}$. Applied to $r=T_{x}(s)\in Z$, this gives $T_{x}=z_{m}+\sum_{p=1}^{m-1}(z_{p}-z_{p+1})\mathbf{1}_{U_{p}}$ with $U_{p}=\{T_{x}\ge z_{p}\}=B_{1}\cup\dots\cup B_{k_{p}}$, hence, $T$ being integrable,

On the other side, $Z$ is finite, so $\mathbb{R}\setminus Z$ is Borel, and by Basic Properties of Empirical Measures: Values, Integrals, Push-Forwards, Second Moment, and Lipschitz Dependence on the Configuration §values $\mu^{N}_{x}(\mathbb{R}\setminus Z)=0$; by the coupling property the set $G=\mathrm{pr}_{1}^{-1}(\mathbb{R}\setminus Z)$ has $\gamma(G)=0$. Off $G$ the identity above applies to $r=a$, so $\gamma$-almost everywhere $ab=z_{m}b+\sum_{p=1}^{m-1}(z_{p}-z_{p+1})\,b\,\mathbf{1}_{P_{p}}$ with $P_{p}=\mathrm{pr}_{1}^{-1}([z_{p},\infty))$, and, as $\int b\,d\gamma=\int t\,\nu(dt)=\int T\,d\hat{\mu}$ by change of variables along $\mathrm{pr}_{2}$ and along $T$,

Also $\gamma(P_{p})=\mu^{N}_{x}([z_{p},\infty))=\frac{k_{p}}{N}$ by Basic Properties of Empirical Measures: Values, Integrals, Push-Forwards, Second Moment, and Lipschitz Dependence on the Configuration §values. Since each $z_{p}-z_{p+1}>0$, ($\ast$) follows from

and when $m=1$ both sums are empty and ($\ast$) is an equality.

Step 8 (Claim 3: the bathtub comparison). Fix $p\le m-1$, put $k=k_{p}$ and $U=U_{p}$. By Step 3 and finite additivity, $\hat{\mu}(U)=\frac{k}{N}$; as $\hat{\mu}(\mathbb{R}\setminus E)=0$, $\hat{\mu}(U\cap E)=\frac{k}{N}>0$ and $\hat{\mu}(E\setminus U)=1-\frac{k}{N}>0$, so both sets are nonempty. If $u\in U\cap E$ and $t\in E\setminus U$, then $u\in B_{i}$ with $i\le k$ and $t\in B_{j}$ with $j>k$, so $t<u$ by Step 3, and $T(t)\le T(u)$ as $T$ is nondecreasing on $E$. Hence, by Dedekind completeness, $c=\sup\{T(t):t\in E\setminus U\}$ is a real number with $T\le c$ on $E\setminus U$ and $T\ge c$ on $U\cap E$. The function $(T-c)^{+}$ is Borel and integrable ($0\le(T-c)^{+}\le|T|+|c|$). Since $\hat{\mu}(\mathbb{R}\setminus E)=0$, $(T-c)^{+}=0$ on $E\setminus U$ and $(T-c)^{+}=T-c$ on $U\cap E$,

On the other hand, using $\gamma(P_{p})=\frac{k}{N}$, then $b-c\le(b-c)^{+}$ and $(b-c)^{+}\ge0$, then change of variables along $\mathrm{pr}_{2}$ and along $T$,

Combining the two displays gives ($\ast\ast$), hence ($\ast$), and the main assertion of claim 3 is proved.

Step 9 (Claim 3: the particular cases). Let $x,y$ be ordered. The identity map is Borel, nondecreasing on $\mathbb{R}$, and pushes $\hat{\mu}$ to $\hat{\mu}\in\mathcal{P}_{2}(\mathbb{R})$; with $T=\mathrm{id}$, Steps 5 to 8 and (P) give $W_{2}(\mu^{N}_{x},\hat{\mu})^{2}=\int(T_{x}-\mathrm{id})^{2}\,d\hat{\mu}=\sum_{i=1}^{N}\int_{B_{i}}(x_{i}-s)^{2}\,\hat{\mu}(ds)$. By Step 4, $T_{y}$ is Borel, nondecreasing on $\mathbb{R}$ and pushes $\hat{\mu}$ to $\mu^{N}_{y}$, which lies in $\mathcal{P}_{2}(\mathbb{R})$ by Basic Properties of Empirical Measures: Values, Integrals, Push-Forwards, Second Moment, and Lipschitz Dependence on the Configuration §moment; with $T=T_{y}$ and Step 4, $W_{2}(\mu^{N}_{x},\mu^{N}_{y})=\lVert T_{x}-T_{y}\rVert_{\hat{\mu}}=\frac{\lVert x-y\rVert}{\sqrt{N}}$. By the triangle inequality in $L^{2}(\hat{\mu};\mathbb{R})$ and the case $T=\mathrm{id}$ for $x$ and for $y$, $\lVert T_{x}-T_{y}\rVert_{\hat{\mu}}\le\lVert T_{x}-\mathrm{id}\rVert_{\hat{\mu}}+\lVert T_{y}-\mathrm{id}\rVert_{\hat{\mu}}=W_{2}(\mu^{N}_{x},\hat{\mu})+W_{2}(\mu^{N}_{y},\hat{\mu})$.

Step 10 (Claim 4). Fix a Borel representative of $q$. Since $\hat{\mu}\in\mathcal{P}_{2}(\mathbb{R})$, $\int s^{2}\,\hat{\mu}(ds)<\infty$, so $s\mapsto s$ and $q$ are integrable ($|s|\le\frac{1}{2}(1+s^{2})$, $|q|\le\frac{1}{2}(1+q^{2})$), $s\mapsto q(s)s$ is integrable ($|qs|\le\frac{1}{2}(q^{2}+s^{2})$), and so are $s\mapsto q(s)(x_{i}-s)$ and $s\mapsto(x_{i}-s)^{2}\le2x_{i}^{2}+2s^{2}$; thus $\chi$, $\bar{q}_{i}$ and $m_{i}$ are well defined, and two representatives of $q$ agree off a $\hat{\mu}$-null set, so the integrals do not depend on the choice. Expanding each integrand, using $\hat{\mu}(B_{i})=\frac{1}{N}$, $\int_{B_{i}}q=\frac{1}{N}\bar{q}_{i}$, $\int_{B_{i}}s\,\hat{\mu}(ds)=\frac{1}{N}m_{i}$ and (P),

a polynomial of degree at most $2$ in $x$ with real coefficients. It is continuous on $\mathbb{R}^{N}$, its partial derivatives are $\partial_{i}\chi(x)=\frac{1}{N}(\bar{q}_{i}+2Kx_{i}-2Km_{i})=\frac{1}{N}(\bar{q}_{i}+2K(x_{i}-m_{i}))$, affine hence continuous, and $\partial_{l}\partial_{i}\chi=\frac{2K}{N}$ if $l=i$ and $0$ otherwise, constants. So $\chi$ is of class $C^{2}$ on $\mathbb{R}^{N}$ in the sense of Differential Calculus and Convexity on Euclidean Open Sets: Standing Notation §derivatives, and its Hessian matrix is $D^{2}\chi(x)=\frac{2K}{N}I_{N}$. Now let $x$ be ordered. Since $T_{x}=x_{i}$ on $B_{i}$, (P) gives $\chi(x)=\int q\,(T_{x}-\mathrm{id})\,d\hat{\mu}+K\int(T_{x}-\mathrm{id})^{2}\,d\hat{\mu}=\langle q,T_{x}-\mathrm{id}\rangle_{\hat{\mu}}+K\lVert T_{x}-\mathrm{id}\rVert_{\hat{\mu}}^{2}$, and $\lVert T_{x}-\mathrm{id}\rVert_{\hat{\mu}}=W_{2}(\mu^{N}_{x},\hat{\mu})$ by Step 9 (the case $T=\mathrm{id}$). By the Cauchy-Schwarz inequality, $\langle q,T_{x}-\mathrm{id}\rangle_{\hat{\mu}}\ge-\lVert q\rVert_{\hat{\mu}}\lVert T_{x}-\mathrm{id}\rVert_{\hat{\mu}}=-\lVert q\rVert_{\hat{\mu}}W_{2}(\mu^{N}_{x},\hat{\mu})$, which gives the lower bound.

Step 11 (Claim 5). A Lipschitz $h$ is continuous, hence Borel by Probability Measures on Euclidean Space and Random Vectors: Standing Notation §borel-maps; being bounded, $h$ is integrable and $h^{2}$ is integrable, so $q-h\in L^{2}(\hat{\mu};\mathbb{R})$ and $\bar{q}_{i}$ is defined (Step 10). Let $x$ be ordered and $i\in[N]$. Since $\hat{\mu}(B_{i})=\frac{1}{N}$, $h(x_{i})=N\int_{B_{i}}h(x_{i})\,d\hat{\mu}$, so $\bar{q}_{i}-h(x_{i})=N\int_{B_{i}}(q-h(x_{i}))$. By the Cauchy-Schwarz inequality for the functions $\mathbf{1}_{B_{i}}$ and $(q-h(x_{i}))\mathbf{1}_{B_{i}}$,

Pointwise, $(q(s)-h(x_{i}))^{2}\le2(q(s)-h(s))^{2}+2(h(s)-h(x_{i}))^{2}\le2(q(s)-h(s))^{2}+2L_{h}^{2}(s-x_{i})^{2}$, using $(u+v)^{2}\le2u^{2}+2v^{2}$ and $|h(s)-h(x_{i})|\le L_{h}|s-x_{i}|$. Summing over $i$, dividing by $N$, and using (P) and the first formula of Step 9,