## Formalized Name Monotone Rearrangement Transports Measures on the Line ## Formalized Statement Let $\mu$ and $\nu$ be Borel probability measures on $\mathbb{R}$, and assume that $\mu$ is atomless. Define the distribution functions $F_\mu: \mathbb{R} \to [0,1]$ and $F_\nu: \mathbb{R} \to [0,1]$ by $F_\mu(x)=\mu((-\infty,x])$ and $F_\nu(y)=\nu((-\infty,y])$. For $t \in (0,1)$, define the left-continuous quantile function $Q_\nu: (0,1) \to \mathbb{R}$ by \begin{align*} Q_\nu(t)=\inf\{y \in \mathbb{R} : F_\nu(y) \geq t\}. \end{align*} Let \begin{align*} D:=\{x \in \mathbb{R}:0<F_\mu(x)<1\} \end{align*} and \begin{align*} E:=\mathbb{R}\setminus D=\{x \in \mathbb{R}:F_\mu(x)\in\{0,1\}\}. \end{align*} Let $T: \mathbb{R} \to \mathbb{R}$ be a Borel map such that \begin{align*} T(x) = Q_\nu(F_\mu(x)) \end{align*} for every $x \in D$. The values of $T$ on $E$ are arbitrary real values subject only to Borel measurability of $T$. Then $\mu(E)=0$, $T_{\#}\mu = \nu$, and $T|_D$ agrees with the nondecreasing map $Q_\nu\circ F_\mu:D\to\mathbb{R}$. ## Proof [proofplan] We first show that the endpoint set on which $F_\mu$ equals $0$ or $1$ is $\mu$-null, so only the formula $T = Q_\nu \circ F_\mu$ matters for the pushforward. Then we prove the probability integral transform directly: if $X$ has law $\mu$, then $F_\mu(X)$ is uniformly distributed on $(0,1)$. Next we prove the quantile transform directly by comparing the events $\{Q_\nu(U) \leq y\}$ and $\{U \leq F_\nu(y)\}$ for a uniform random variable $U$. Combining these two distributional identities gives $T_{\#}\mu = \nu$, and monotonicity follows from the monotonicity of $F_\mu$ and $Q_\nu$. [/proofplan] [step:Discard the endpoint set where the quantile formula is not used] Define the endpoint set \begin{align*} E := \{x \in \mathbb{R} : F_\mu(x) \in \{0,1\}\}. \end{align*} We claim that $\mu(E)=0$. Let \begin{align*} A_0 := \{x \in \mathbb{R} : F_\mu(x)=0\} \end{align*} and \begin{align*} A_1 := \{x \in \mathbb{R} : F_\mu(x)=1\}. \end{align*} If $A_0=\varnothing$, then $\mu(A_0)=0$. Otherwise define \begin{align*} a_0 := \sup A_0 \in [-\infty,\infty]. \end{align*} Since $F_\mu$ is nondecreasing, $A_0$ is an initial interval: if $x\in A_0$ and $z\leq x$, then $F_\mu(z)\leq F_\mu(x)=0$, hence $z\in A_0$. For each $m\in\mathbb{N}$ with $A_0\cap[-m,m]\neq\varnothing$, choose $x_m\in A_0$ such that $A_0\cap[-m,m]\subseteq (-\infty,x_m]$. Then \begin{align*} \mu(A_0\cap[-m,m])\leq \mu((-\infty,x_m])=F_\mu(x_m)=0. \end{align*} The countable exhaustion $A_0=\bigcup_{m=1}^{\infty}(A_0\cap[-m,m])$ gives $\mu(A_0)=0$. If $A_1=\varnothing$, then $\mu(A_1)=0$. Otherwise define \begin{align*} a_1 := \inf A_1 \in [-\infty,\infty]. \end{align*} Since $F_\mu$ is nondecreasing, $A_1$ is a final interval: if $x\in A_1$ and $z\geq x$, then $F_\mu(z)\geq F_\mu(x)=1$, hence $z\in A_1$. For each $m\in\mathbb{N}$ with $A_1\cap[-m,m]\neq\varnothing$, choose $x_m\in A_1$ such that $A_1\cap[-m,m]\subseteq [x_m,\infty)$. Because $F_\mu(x_m)=1$, we have $\mu((x_m,\infty))=0$; because $\mu$ is atomless, $\mu(\{x_m\})=0$. Therefore \begin{align*} \mu(A_1\cap[-m,m])\leq \mu([x_m,\infty))=\mu(\{x_m\})+\mu((x_m,\infty))=0. \end{align*} The countable exhaustion $A_1=\bigcup_{m=1}^{\infty}(A_1\cap[-m,m])$ gives $\mu(A_1)=0$. Hence \begin{align*} \mu(E) \leq \mu(A_0)+\mu(A_1)=0. \end{align*} [/step] [step:Show that $F_\mu(X)$ is uniformly distributed] Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let \begin{align*} X: (\Omega,\mathcal{F}) \to (\mathbb{R},\mathcal{B}(\mathbb{R})) \end{align*} be a random variable with law $\mu$, meaning $\mathbb{P}(X \in B)=\mu(B)$ for every $B \in \mathcal{B}(\mathbb{R})$. Define \begin{align*} U: \Omega \to [0,1], \qquad \omega \mapsto F_\mu(X(\omega)). \end{align*} We prove that $U$ is uniformly distributed on $[0,1]$. The atomless hypothesis implies continuity of $F_\mu$. For every $a \in \mathbb{R}$, \begin{align*} F_\mu(a)-\lim_{x \uparrow a}F_\mu(x)=\mu(\{a\})=0. \end{align*} For right-continuity, if $x_k\downarrow a$, then the intervals $(-\infty,x_k]$ decrease to $(-\infty,a]$, so continuity from above of the finite measure $\mu$ gives $F_\mu(x_k)\to F_\mu(a)$. Also, \begin{align*} \lim_{x \to -\infty} F_\mu(x)=0 \end{align*} and \begin{align*} \lim_{x \to \infty} F_\mu(x)=1 \end{align*} by continuity from below and above applied to the intervals $(-\infty,x]$. Fix $s \in [0,1]$ and define the Borel set \begin{align*} B_s := \{x \in \mathbb{R} : F_\mu(x) \leq s\}. \end{align*} If $s=0$, then $B_s=A_0$, so the first step gives $\mu(B_s)=0=s$. If $s=1$, then $B_s=\mathbb{R}$, so $\mu(B_s)=1=s$. Assume $0<s<1$. Define \begin{align*} a_s := \sup B_s \in \mathbb{R}. \end{align*} The preceding limits imply that $B_s$ is nonempty and bounded above, so $a_s$ is finite. Since $F_\mu$ is nondecreasing, $B_s$ is an initial interval. Continuity of $F_\mu$ gives $F_\mu(a_s)=s$: if $F_\mu(a_s)<s$, continuity gives points larger than $a_s$ still in $B_s$, contradicting the definition of $a_s$; if $F_\mu(a_s)>s$, continuity gives points below $a_s$ not in $B_s$, contradicting that $a_s$ is the supremum of the initial interval $B_s$. Because $B_s$ is either $(-\infty,a_s]$ or $(-\infty,a_s)$ and $\mu(\{a_s\})=0$, we obtain \begin{align*} \mu(B_s)=\mu((-∞,a_s])=F_\mu(a_s)=s. \end{align*} Therefore \begin{align*} \mathbb{P}(U \leq s)=\mathbb{P}(F_\mu(X) \leq s)=\mu(B_s)=s. \end{align*} Thus $U$ has distribution function $s \mapsto s$ on $[0,1]$. [guided] The goal is to compute the distribution function of \begin{align*} U: \Omega \to [0,1] \end{align*} by $U(\omega)=F_\mu(X(\omega))$. The delicate point is that $F_\mu$ may have flat intervals, so we cannot argue as if $F_\mu$ had an ordinary inverse. First we record the regularity of $F_\mu$. For every $a \in \mathbb{R}$, \begin{align*} F_\mu(a)-\lim_{x \uparrow a}F_\mu(x)=\mu(\{a\})=0, \end{align*} because $\mu$ has no atoms. For right-continuity, take any sequence $x_k\downarrow a$. The intervals $(-\infty,x_k]$ decrease to $(-\infty,a]$, so continuity from above of the finite measure $\mu$ gives $F_\mu(x_k)\to F_\mu(a)$. Hence $F_\mu$ is continuous. Also, \begin{align*} \lim_{x \to -\infty} F_\mu(x)=0 \end{align*} and \begin{align*} \lim_{x \to \infty} F_\mu(x)=1, \end{align*} since the intervals $(-\infty,x]$ decrease to $\varnothing$ as $x \to -\infty$ and increase to $\mathbb{R}$ as $x \to \infty$. Fix $s \in [0,1]$ and set \begin{align*} B_s := \{x \in \mathbb{R} : F_\mu(x) \leq s\}. \end{align*} If $s=0$, then $B_s=A_0$, so the endpoint-set step gives $\mu(B_s)=0=s$. If $s=1$, then $B_s=\mathbb{R}$ and $\mu(B_s)=1=s$. Now assume $0<s<1$. Define \begin{align*} a_s := \sup B_s. \end{align*} The limits of $F_\mu$ at $-\infty$ and $+\infty$ imply that $B_s$ is nonempty and bounded above, so $a_s \in \mathbb{R}$. Since $F_\mu$ is nondecreasing, $B_s$ is an initial interval: if $x \in B_s$ and $z \leq x$, then $F_\mu(z) \leq F_\mu(x) \leq s$, so $z \in B_s$. We now prove the key identity $F_\mu(a_s)=s$. If $F_\mu(a_s)<s$, continuity of $F_\mu$ at $a_s$ gives some $\varepsilon>0$ such that $F_\mu(x)\leq s$ for all $x \in (a_s,a_s+\varepsilon)$. This places points larger than $a_s$ in $B_s$, contradicting the definition of $a_s$ as the supremum of $B_s$. If $F_\mu(a_s)>s$, continuity gives some $\varepsilon>0$ such that $F_\mu(x)>s$ for all $x \in (a_s-\varepsilon,a_s+\varepsilon)$. Since $a_s$ is the supremum of the nonempty set $B_s$, there must be a point of $B_s$ in $(a_s-\varepsilon,a_s]$, a contradiction. Hence \begin{align*} F_\mu(a_s)=s. \end{align*} Because $B_s$ is an initial interval with endpoint $a_s$, it is either $(-\infty,a_s]$ or $(-\infty,a_s)$. The two possibilities have the same $\mu$-measure because $\mu(\{a_s\})=0$. Therefore \begin{align*} \mu(B_s)=\mu((-∞,a_s])=F_\mu(a_s)=s. \end{align*} Finally, since $X$ has law $\mu$, \begin{align*} \mathbb{P}(U \leq s)=\mathbb{P}(F_\mu(X) \leq s)=\mu(B_s)=s. \end{align*} This holds for every $s \in [0,1]$, so $U$ has the uniform distribution on $[0,1]$. [/guided] [/step] [step:Show that the quantile of a uniform random variable has law $\nu$] Let \begin{align*} Q_\nu: (0,1) \to \mathbb{R} \end{align*} be the quantile function defined by \begin{align*} Q_\nu(t)=\inf\{z \in \mathbb{R}:F_\nu(z)\geq t\}. \end{align*} Let $q_0\in\mathbb{R}$ be arbitrary, and define the Borel extension \begin{align*} \widetilde Q_\nu:[0,1]\to\mathbb{R} \end{align*} by $\widetilde Q_\nu(t)=Q_\nu(t)$ for $t\in(0,1)$ and $\widetilde Q_\nu(0)=\widetilde Q_\nu(1)=q_0$. Let $U$ be uniformly distributed on $[0,1]$. Since $\mathbb{P}(U \in \{0,1\})=0$, the arbitrary endpoint values of $\widetilde Q_\nu$ do not affect the law of $\widetilde Q_\nu(U)$. Fix $y \in \mathbb{R}$ and $t \in (0,1)$. We prove \begin{align*} Q_\nu(t) \leq y \quad \Longleftrightarrow \quad t \leq F_\nu(y). \end{align*} If $t \leq F_\nu(y)$, then $y$ belongs to the nonempty set $\{z \in \mathbb{R}:F_\nu(z)\geq t\}$, so its infimum satisfies $Q_\nu(t)\leq y$. Conversely, suppose $Q_\nu(t)\leq y$. For every $\varepsilon>0$, the definition of the infimum gives a point $z_\varepsilon \in \mathbb{R}$ such that \begin{align*} z_\varepsilon < Q_\nu(t)+\varepsilon \end{align*} and \begin{align*} F_\nu(z_\varepsilon)\geq t. \end{align*} Choose $\varepsilon>0$ so small that $Q_\nu(t)+\varepsilon<y+\delta$ for a prescribed $\delta>0$. Then $z_\varepsilon<y+\delta$, and monotonicity of $F_\nu$ gives \begin{align*} t\leq F_\nu(z_\varepsilon)\leq F_\nu(y+\delta). \end{align*} Letting $\delta \downarrow 0$ and using right-continuity of the distribution function $F_\nu$ yields $t\leq F_\nu(y)$. Therefore, on the event $\{0<U<1\}$, \begin{align*} \{\widetilde Q_\nu(U)\leq y\}=\{U\leq F_\nu(y)\}. \end{align*} The two events may differ only on $\{U\in\{0,1\}\}$, which has probability zero. Since $U$ is uniform on $[0,1]$ and $F_\nu(y)\in[0,1]$, \begin{align*} \mathbb{P}(\widetilde Q_\nu(U)\leq y)=\mathbb{P}(U \leq F_\nu(y))=F_\nu(y). \end{align*} Thus the distribution function of $\widetilde Q_\nu(U)$ is $F_\nu$, so $\widetilde Q_\nu(U)$ has law $\nu$. [/step] [step:Identify the law of $T(X)$ with the pushforward measure] Since $\mu(E)=0$ and $X$ has law $\mu$, \begin{align*} \mathbb{P}(X \in E)=\mu(E)=0. \end{align*} On $\Omega \setminus X^{-1}(E)$, the defining formula for $T$ gives \begin{align*} T(X(\omega)) = Q_\nu(F_\mu(X(\omega))) = \widetilde Q_\nu(U(\omega)). \end{align*} Therefore $T(X)=\widetilde Q_\nu(U)$ almost surely. Since $\widetilde Q_\nu(U)$ has law $\nu$, the random variable $T(X)$ has law $\nu$. For every Borel set $B \in \mathcal{B}(\mathbb{R})$, the definition of pushforward gives \begin{align*} (T_{\#}\mu)(B)=\mu(T^{-1}(B)). \end{align*} Because $X$ has law $\mu$, this equals \begin{align*} \mathbb{P}(X \in T^{-1}(B))=\mathbb{P}(T(X)\in B). \end{align*} Since $T(X)$ has law $\nu$, \begin{align*} \mathbb{P}(T(X)\in B)=\nu(B). \end{align*} Thus $(T_{\#}\mu)(B)=\nu(B)$ for every Borel set $B$, and therefore \begin{align*} T_{\#}\mu=\nu. \end{align*} [/step] [step:Record the monotone representative on the full measure transport set] The map $F_\mu:\mathbb{R}\to[0,1]$ is nondecreasing by monotonicity of measures. The map $Q_\nu:(0,1)\to\mathbb{R}$ is nondecreasing because if $0<s<t<1$, then \begin{align*} \{y \in \mathbb{R}:F_\nu(y)\geq t\}\subseteq \{y \in \mathbb{R}:F_\nu(y)\geq s\}, \end{align*} and taking infima gives \begin{align*} Q_\nu(s)\leq Q_\nu(t). \end{align*} Hence the composition \begin{align*} x \mapsto Q_\nu(F_\mu(x)) \end{align*} is nondecreasing on the set $\{x \in \mathbb{R}:0<F_\mu(x)<1\}$. This set has full $\mu$-measure by the first step, and $T$ agrees with this nondecreasing representative there by hypothesis. This proves the asserted monotonicity statement and completes the proof. [/step]