An optimal transport based characterization of convex order

Fix two probability measures $\mu,\nu\in\mathcal{P}(\mathbb{R}^{d})$ with

Recall that $\mu$ and $\nu$ are in convex order (denoted by $\mu\preceq_{c}\nu$) iff

As any convex function is bounded from below by an affine function, the above integrals take values in $(-\infty,\infty]$. The notion of convex order is very well studied, see e.g. Ross et al. (1996); Müller and Stoyan (2002); Shaked and Shanthikumar (2007); Arnold (2012) and the references therein for an overview. It plays a pivotal role in mathematical finance since Strassen (1965) established that $\mu\preceq_{c}\nu$ if and only if $\mathcal{M}(\mu,\nu)$ — the set of martingale laws on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ with marginals $\mu$ and $\nu$ — is non-empty. This result is also the reason why convex order has taken the center stage in the field of martingale optimal transport, see e.g. Galichon et al. (2014); Beiglböck et al. (2013, 2015); De March and Touzi (2019); Obłój and Siorpaes (2017); Guo and Obłój (2019); Alfonsi et al. (2019, 2020); Alfonsi and Jourdain (2020); Jourdain and Margheriti (2022); Massa and Siorpaes (2022) and the references therein. Furthermore, convex order plays a pivotal role in dependence modelling and risk aggregation, see e.g. Tchen (1980); Rüschendorf and Uckelmann (2002); Wang and Wang (2011); Embrechts et al. (2013); Bernard et al. (2017).
While there is an abundance of explicit characterizations of convex order available in one dimension (i.e. $d=1$) – see e.g. (Shaked and Shanthikumar, 2007, Chapter 3)) — the case $d>1$ seems to be less studied to the best of our knowledge. The main goal of this article is to fill this gap: we discuss a characterization of convex order, that holds in general dimensions, and is based on the theory of optimal transport (OT). Optimal transport goes back to the seminal works of Monge (1781) and Kantorovich (1958). It is concerned with the problem of transporting probability distributions in a cost-optimal way. We refer to Rachev and Rüschendorf (1998) and Villani (2003, 2008) for an overview. For this paper we only need a few basic concepts from OT. Most importantly we will need the cost functionals

Here $\Pi(\mu,\nu)$ denotes the set of probability measures on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ with marginals $\mu$ and $\nu$. Our main result is the following:

Theorem 1.1 states that convex order of $\mu$ and $\nu$ is equivalent to an order relation $C(\cdot,\cdot)$ on the space of probability measures. Contrary to standard characterizations of convex order using potential functions or cdfs, it holds in any dimension and can be seen as a natural generalization of the following result:

Corollary 1.2 itself has an interesting history. To the best of our knowledge, it was first stated in Carlier (2008) for compactly supported measures $\mu,\nu$. His proof relies on a well-known connection between convex functions and OT for the squared Euclidean distance called Brenier’s theorem (see Brenier (1991); Rüschendorf and Rachev (1990)) together with a certain probabilistic first-order condition, see (Carlier, 2008, Proposition 1). We emphasize here, that contrary to the setting of Brenier’s theorem, no assumptions on the probability measures $\mu$ and $\nu$ except for the compact support condition are made; in particular there is no need to assume that these are absolutely continuous wrt. the Lebesgue measure.

Interestingly, Carlier’s result does not seem to be very well-known in the literature on stochastic order. We conjecture that this is mainly due to his use of the french word “balayée” instead of convex order, so that the connection is not immediately apparent. For this reason, one aim of this note is to popularize Carlier’s result, making it accessible to a wider audience, while simultaneously showcasing potential applications. As it turns out, Corollary 1.2 is at least partially known to the mathematical finance community: indeed, the “only if” direction of Corollary 1.2 was rediscovered in (Alfonsi and Jourdain, 2020, Equation (2.2)) for (not necessarily compactly supported) probability measures $\mu,\nu$ with finite second moments.

Theorem 1.1 differs from Carlier’s work in three aspects: first, as the convex order is classically embedded in $\mathcal{P}_{1}(\mathbb{R}^{d})$ and does not require moments of higher order or compact support assumptions (see e.g. Nendel (2020)), Theorem 1.1 is simultaneously more concise and arguably more natural than Corollary 1.2. Second, our proof of Theorem 1.1 (and thus also Corollary 1.2) follows a different route than Carlier’s original proof, who argues purely on the space probability measures (i.e. the “primal side” in optimal transport). Instead, we combine Brenier’s theorem with the theory of the classical optimal transport duality. Lastly, we discuss three implications of Theorem 1.1: we first give a proof of a characterization of convex order in one dimension through quantile functions. Then we use Theorem 1.1 to derive new computational methods for testing convex order between $\mu$ and $\nu$. For the computation we exploit state of the art computational OT methods, which are efficient for potentially high-dimensional problems. These have recently seen a spike in research activity. We refer to Peyré and Cuturi (2019) for an overview. Finally we discuss applications of Theorem 1.1 to the theory of so-called model-independent arbitrages, see (Acciaio et al., 2013, Definition 1.2).

This article is structured as follows: in Section 2 we state examples and consequences of Theorem 1.1. In particular we connect it to some well-known results in the theory of convex order. The proof of the main results is given in Section 3. Sections 4 and 5 discuss numerical and mathematical finance applications of Theorem 1.1 respectively. Remaining proofs are collected in Section 6.

To sharpen intuition, let us first discuss the case $d=1$. By Theorem 1.1 we can obtain a new proof of a well-known representation of convex order on the real line, see e.g. (Shaked and Shanthikumar, 2007, Theorem 3.A.5). Here we denote the quantile function of a probability measure $\mu$ by

The proofs of all results of this section are collected in Section 6. We continue with general $d\in\mathbb{N}$ and give a geometric interpretation of Corollary 1.2 by restating it as follows: $\mu\preceq_{c}\nu$ holds iff

for all $\rho\in\mathcal{P}(\mathbb{R}^{d})$ with bounded support, where $\delta_{z}$, $z\in\mathbb{R}^{d}$ is a Dirac measure. Indeed, varying $\rho$ over Dirac measures in (2) implies that the means of $\mu$ and $\nu$ have to be equal; equation (3) then follows from simple algebra. This implies in particular that the difference between squared Wasserstein cost from $\nu$ and $\mu$ to $\rho$ is maximised at the point masses. Lastly, Theorem 1.1 can also be reformulated as: $\mu\preceq_{c}\nu$ iff

i.e. for any $\rho\in\mathcal{P}(\mathbb{R}^{d})$ with bounded support, the maximal covariance between $\mu$ and $\rho$ is less than the one between $\nu$ and $\rho$. This provides a natural intuition for a classical pedestrian description of convex order, namely that “$\nu$ being more spread out than $\mu$”.

We next give a simple example for Corollary 1.2.

We now state two direct corollaries of Corollary 1.2. We consider the cost $c(x,y):=|x-y|^{2}/2$ and recall that a function $f$ is $c$-concave, if

for some function $g:\mathbb{R}^{d}\to\mathbb{R}$. We then have the following:

Corollary 1.2 also directly implies the following well-known result:

Let us start by setting up some notation. We denote the scalar product on $\mathbb{R}^{d}$ by $\langle\cdot,\cdot\rangle$. We write $|\cdot|$ for the Euclidean norm on $\mathbb{R}^{d}$. The ball in $\mathbb{R}^{d}$ around $x$ of radius $r>0$ will be denoted by $B_{r}(x)$. We write $\nabla f(x)$ for the derivative of a function $f:\mathbb{R}^{d}\to\mathbb{R}$ at a point $x\in\mathbb{R}^{d}$. We denote the $d$-dimensional Lebesgue measure by $\lambda$.

In order to keep this article self-contained, we summarise some properties of optimal transport at the beginning of this section, and refer to (Villani, 2003, Chapter 2.1) for a more detailed treatment.
By definition we have for any $\rho\in\mathcal{P}_{2}(\mathbb{R}^{d})$ that

In this section we thus (re-)define the cost function $c(x,y):=\langle x,y\rangle$ and recall that the convex conjugate $f^{*}:\mathbb{R}^{d}\to\mathbb{R}\cup\{\infty\}$ of a function $f:\mathbb{R}^{d}\to\mathbb{R}$ is given by

The subdifferential of a proper convex function $f:\mathbb{R}^{d}\to\mathbb{R}\cup\{\infty\}$ is defined as

It is non-empty if $x$ belongs to the interior of the domain of $f$. We have

Lastly we recall the duality

and the existence of an optimal pair $(f,f^{*})$ of (lower semicontinuous, proper) convex conjugate functions. Replacing $\mu$ by $\nu$ in the display above, we obtain a similar duality for $C(\nu,\rho)$.

In this section we illustrate Theorem 1.1 numerically. We focus on the following toy examples, where convex order or its absence is easy to establish:

A general numerical implementation for testing convex order of the two measures $\mu,\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$ in general dimensions and the examples discussed here can be found in the Github repository https://github.com/johanneswiesel/Convex-Order. In the implementation we use the POT package (https://pythonot.github.io) to compute optimal transport distances.

Let us set

and note that by Theorem 1.1 we have the relationship

Clearly the computation of $V(\mu,\nu)$ hinges on the numerical exploration of the convex set of probability measures $\mathcal{P}^{1}(\mathbb{R}^{d})$. We propose two methods for this: our first method only considers finitely supported measures $\rho$, which are dense in $\mathcal{P}^{1}(\mathbb{R}^{d})$ in the Wasserstein topology. It relies on the Dirichlet distribution on the space $R^{g-1}$, $g\in\mathbb{N}$, with density

for $x_{1},\dots,x_{g}\in[0,1]$ satisfying $\sum_{i=1}^{g}x_{i}=1$. Here $\alpha_{1},\dots,\alpha_{g}>0$, $\alpha:=(\alpha_{1},\dots,\alpha_{g})$ and $B(\alpha)$ denotes the Beta function. Fixing $g$ grid points $\{k_{1},\dots,k_{g}\}$ in $B_{1}(0)$, we can consider any realization of a Dirichlet random variable $(X_{1},\dots,X_{g})$ as a probability distribution assigning probability mass $X_{i}$ to the grid point $k_{i}$, $i\in\{1,\dots,g\}$. This leads to the following algorithm:

The main computational challenge in Algorithm 1 is the efficient evaluation of $C(\rho,\nu)$ and $C(\rho,\mu)$. For this we aim to write $C(\rho,\nu)$ and $C(\rho,\mu)$ as linear programs. We offer two different variants of Algorithm 1:

• •

  Indirect Dirichlet method with histograms: If we have access to finitely supported approximations a and b of $\mu$ and $\nu$ respectively and the measure $\rho$ is supported on $G$ as above, then we solve the linear programs $C(\textbf{a},\rho)$ and $C(\textbf{b},\rho)$ as is standard in optimal transport theory.

• •

  Indirect Dirichlet method with samples: here we draw a number of samples from $\mu$ and $\nu$ respectively and denote the respective empirical distributions of these samples by a and b. As before we assume that we have access to a probability measure $\rho$ supported on $G$. We then solve the linear programs $C(\textbf{a},\rho)$ and $C(\textbf{a},\rho)$.