Kolmogorov-Smirnov distance and discrepancies versus Wasserstein distances

Gilles Pagès and Fabien Panloup ^†^†thanks: Sorbonne Université, Laboratoire de Probabilités, Statistique et Modélisation, UMR˜8001, case 158, 4, pl. Jussieu, F-75252 Paris Cedex 5, France. E-mail: gilles.pages@sorbonne-universite.fr^†^†thanks: Université d’Angers, CNRS, LAREMA, SFR MATHSTIC, F-49000 Angers, France. E-mail: fabien.panloup@univ-angers.fr

Abstract

We establish inequalities that compare the $p$ -Wasserstein distance to distances which are built as suprema of box measures. More precisely, when the measures are supported on $[0,1]^{d}$ , we obtain sharp upper-bounds of the $p$ -Wasserstein distance by (powers of) the (uniform) discrepancy. As an application, we retrieve the Proïnov Theorem. When the two distributions are supported by the whole ${\mathbb{R}}^{d}$ , their $p$ -Wasserstein distance is upper bounded by the product of a (power of) their Kolmogorov–Smirnov ( $K$ – $S$ ) distance with the sum of their $p$ -moments. Reverse inequalities are established when one of the two distributions has a density, depending on its ${\cal L}^{s}$ -integrability with respect to the Lebesgue measure for some $s>1$ .

Mathematics Subject Classification: Primary: 60E15, 60F25 Secondary 65C05, 11K38, 65D32.

Keywords: Wasserstein distance ; Kolmogorov-Smirnov distance ; star discrepancy ; uniform discrepancy.

1 Introduction

For a given norm $|\,.\,|$ on ${\mathbb{R}}^{d}$ , the $p$ -Wasserstein distance is defined when $p\geq 1$ by: for all $\mu$ , $\nu\in{\cal P}_{p}({\mathbb{R}}^{d})$ , the space of probability distributions on ${\mathcal{B}}or({\mathbb{R}}^{d})$ (Borel sets of ${\mathbb{R}}^{d}$ ) having (at least) $p$ -finite moments,

{\cal W}_{p}^{|\,.\,|}(\mu,\nu)=\inf\left\{\left[{\mathbb{E}}\,|X-Y|^{p}\right]^{\frac{1}{p}},{\mathbb{P}}_{X}=\mu,{\mathbb{P}}_{Y}=\nu\right\},

where ${\mathbb{P}}_{X}$ and ${\mathbb{P}}_{Y}$ denote the distributions of $X$ and $Y$ respectively. In the sequel, we will only write ${\cal W}_{p}$ (and assume throughout the paper that $p\geq 1$ ). It is well-known that ${\cal W}_{p}$ metrizes weak convergence with convergence of the $p$ -moments on ${\cal P}_{p}({\mathbb{R}}^{d})$ (see $e.g.$ [Vil09] for details). The $p$ -Wasserstein distance is now widely used in probabilistic and statistical applications. In statistics, this distance usually produces a robust alternative to Kullback-Leibler divergence taking into account the underlying metric structure. In probability theory, the Wasserstein distance is also widely used for quantifying the rate of convergence to equilibrium or analyzing the robustness of stochastic algorithms.

In this paper we establish inequalities that compare the $p$ -Wasserstein distance to the Kolmogorov-Smirnov ( $K$ – $S$ ) distance and its avatars on the state space $[0,1]^{d}$ , usually called discrepancies: for some probability distributions $\mu$ and $\nu$ on ${\mathcal{B}}or({\mathbb{R}}^{d})$ , we denote by $D^{\star}$ the distance defined by

D^{\star}(\mu,\nu)=\^{E}\sup_{x\in{\mathbb{R}}^{d}}\big|\mu\big(]\!]-\infty,x]\!]\big)-\nu\big((]\!]-\infty,x]\!]\big)\big|,

where $]\!]-\infty,x]\!]=\prod_{i=1}^{d}(-\infty,x^{i}]$ . When both distributions of interest are supported by unit hypercubes $[0,1]^{d}$ , the $K$ – $S$ distance is called the star discrepancy (which explains our notation). We will also consider the uniform discrepancy $D^{\infty}$ between $\mu$ and $\nu$ defined by

D^{\infty}(\mu,\nu)=\^{E}\sup_{x,\,y\in{\mathbb{R}}^{d}}\big|\mu\big([\![x,y]\!]\big)-\nu\big([\![x,y]\!]\big)\big|.

where $[\![x,y]\!]=\prod_{i=1}^{d}[x^{i},y^{i}]$ when $x^{i}\leq y^{i}$ for every $i\in\{1,\ldots,d\}$ and $[\![x,y]\!]=\emptyset$ otherwise. Discrepancy is an important setting, closely related with Quasi-Monte Carlo method (and optimal quantization theory, see Section 3.3 of [LP23]) where the empirical measure(s) associated to an $n$ -tuple or a sequence of $[0,1]^{d}$ -valued vectors is used to approximate the uniform distribution ${\cal U}([0,1]^{d})$ in order to replace sequences of pseudo-random numbers for the computation of integrals or expectations in Numerical Probability (see [Nie92, Pag26]). In these inequalities, special attention is paid to the constant to challenge specific results from QMC theory like Proïnov’s Theorem when one of the two distributions is the empirical measure associated to an $n$ -tuple. As well, $K$ – $S$ -distance, is certainly connected with the non parametric goodness of fit Kolmogorov-Smirnov test which is devoted to testing equality between two distributions, one being known or not (see e.g. [LR21, Sec 16.2]).

The objective is thus to provide precise estimates between ${\cal W}_{p}$ and $D^{\star}$ or $D^{\infty}$ . Before stating our results, let us remark that the topologies induced by these distances are slightly different. While ${\cal W}_{p}$ is a metric for the weak convergence in ${\cal P}_{p}({\mathbb{R}}^{d})$ with convergence of $p$ -moments, $D^{\star}$ and $D^{\infty}$ apply without conditions on the moments but their induced topology is finer than the weak convergence topology as illustrated by the following counterexample: if

\nu_{n}=\frac{1}{2}\big(\delta_{\frac{1}{2}}+\delta_{\frac{1}{2}(1+\frac{1}{n})}\big),\;n\geq 1,\quad\mbox{ and }\quad\nu=\delta_{\frac{1}{2}}

(1.1)

then $\nu_{n}$ weakly converges toward $\nu$ but $D^{\star}(\nu_{n},\nu){=D^{\infty}(\nu_{n},\nu)}=\frac{1}{2}$ for every $n\geq 1$ . Consequently, controlling discrepancies by Wasserstein distances will require an absolute continuity assumption on one of the two distributions under consideration. Conversely, we will need some additional moment assumptions when controlling the Wasserstein distance by $D^{\star}$ or $D^{\infty}$ .

Contributions and plan of the paper. We first focus on the control of the Wasserstein distance by discrepancies (or $K$ – $S$ -distance). For this part, we will rely on the inspiring papers by [DSS13] and [FG15] which establish universal upper-bounds for the Wasserstein distances based on a telescopic splitting of the distributions. Section 2 is devoted to upper-bounding the Wasserstein distance ${\cal W}_{p}$ by the uniform discrepancy for $[0,1]^{d}$ -supported distributions with a special attention paid to the values of the semi-universal constants depending on $p$ and the dimension $d$ . In view of the optimization of the inequalities, we provide a variant of the estimates of [DSS13] and [FG15] (see Inequality (2.6) of Proposition 2.2) based on a slight modification of the coupling scheme proposed in [DSS13]. These estimates allow us to state our first estimate in Theorem 2.3 for $[0,1]^{d}$ -supported distributions. At first reading, it can be summed up as follows: for a given norm $|\,.\,|$ on ${\mathbb{R}}^{d}$ and a given $p\geq 1$ , a constant $K_{p,d}$ (which is made explicit in the result) exists such that

{\cal W}_{p}(\mu,\nu)\leq K_{p,d}\big(D^{\infty}(\mu,\nu)\big)^{\frac{1}{p}\wedge\frac{1}{d}}.

Owing to an optimization strategy, the constant $K_{p,d}$ is then refined in Theorem 2.6 in the special case $p=1$ . Extending to $D^{\star}$ with the help of the standard inequality $D^{\infty}\leq 2^{d}D^{\star}$ (see (2.2) for background), this result allows to retrieve a celebrated inequality from Quasi-Monte-Carlo theory with some slightly larger but more universal constants (see Section 2.4 and Remark 2.2 for details) a.k.a. Proïnov’s theorem (see [Pro88]).

In Section 3.1 , we extend the bounds to the whole space ${\mathbb{R}}^{d}$ and obtain the following typical bound when $\mu$ and $\nu$ have finite moments or order $q>p$ (see Theorem 3.2 for a precise setting)

{\cal W}_{p}(\mu,\nu)\leq K_{p,d,q}D^{\infty}(\mu,\nu)^{\frac{1}{d}\wedge(\frac{1}{p}-\frac{1}{q})}.

With the inequality $D^{\infty}\leq 2^{d}D^{\star}$ (which also holds on ${\mathbb{R}}^{d}$ ), the above bound also holds with respect to the $K$ – $S$ -distance $D^{\star}$ .

Finally, we consider the reverse problem in Section 3.2, $i.e.$ : bounding $D^{\infty}$ or $D^{\star}$ by the Wasserstein distance. In Theorem 3.4, we show that if $\mu$ or $\nu$ has a density $g$ w.r.t. the Lebesgue measure $\lambda_{d}$ on ${\mathbb{R}}^{d}$ , the following type of result holds:

D^{\star}(\mu,\nu)\leq K_{r,d}{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)^{\frac{d}{r+d}},

where $r>1$ depends on the moments of $g$ and $r=1$ if $g$ is bounded. This bounded case has been already proved in [GL23] but with non-explicit constants. This reverse inequality is only written for ${\cal W}_{1}$ -distance since it is based on the dual Kantorovich-Rubinstein representation but certainly extends to ${\cal W}_{p}$ since ${\cal W}_{1}\leq{\cal W}_{p}$ .

2 Discrepancies for $[0,1]^{d}$ -supported distributions

As mentioned in the introduction, we first consider $[0,1]^{d}$ -supported distributions and will investigate the more general case of non-compactly supported probability measures in Section 3.

2.1 Definitions, notation and a technical lemma

We define the partial order on ${\mathbb{R}}^{d}$ as follows: for $d\!\in{\mathbb{N}}$ , $x=(x^{1},\ldots,x^{d})$ , $y=(y^{1},\ldots,y^{d})\!\in{\mathbb{R}}^{d}$ ,

x\preceq y\quad\mbox{ if }\quad x^{i}\leq y^{i}\mbox{ for every $i\!\in\{1,\ldots,d\}$.}

We can define the closed and semi-open boxes as follows: when $x\preceq y$ ,

	$\displaystyle[\![x,y]\!]=\{u\in[0,1]^{d}:x^{i}\leq u^{i}\leq y^{i},\,i=1,\ldots,d\}=\prod_{i=1}^{d}[x^{i},y^{i}]$
	$\displaystyle]\!]x,y]\!]=\{u\in[0,1]^{d}:x^{i}<u^{i}\leq y^{i},\,i=1,\ldots,d\}=\prod_{i=1}^{d}(x^{i},y^{i}].$

and otherwise (i.e. if $x\npreceq y$ ), $[\![x,y]\!]=\varnothing$ . Note that $[\![x,y]\!]$ is also empty whenever $x^{i}=y^{i}$ for some index $i$ .

When $\mu$ and $\nu$ are two probability measures on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ , the uniform and star discrepancy between $\mu$ and $\nu$ (introduced in the first section) take the form:

D^{\infty}(\mu,\nu)=\^{E}\sup_{x,\,y\in[0,1]^{d}}\big|\mu\big([\![x,y]\!]\big)-\nu\big([\![x,y]\!]\big)\big|.

and

D^{\star}(\mu,\nu)=\^{E}\sup_{x\in[0,1]^{d}}\big|\mu\big([\![0,x]\!]\big)-\nu\big([\![0,x]\!]\big)\big|.

It is classical background (see e.g [Nie92]) that both $D^{\infty}$ and $D^{\star}$ are $[0,1]$ -valued strongly equivalent distances on the set of probability measures on $[0,1]^{d}$ since

D^{\star}\leq D^{\infty}\leq 2^{d}D^{\star}{\color[rgb]{0.75,0,0.25},}

(2.2)

(see e.g. [Nie92]) but whose induced topology is not that of weak convergence of distributions on $[0,1]^{d}$ , as emphasized in (1.1). However if the generalized c.d.f of $\mu$ defined by $F_{\nu}(x)=\nu([\![0,x]\!])$ is continuous then

\nu_{n}\stackrel{{\scriptstyle w}}{{\longrightarrow}}\nu\quad\mbox{ if and only if }\quad{D^{\star}}(\nu_{n},\nu)\to 0\quad\mbox{ as }\quad n\to+\infty.

(2.3)

The continuity of $F_{\nu}$ is equivalent to the fact that, if $(e^{i})_{i=1:d}$ denotes the canonical basis of ${\mathbb{R}}^{d}$

\forall\,x\!\in[0,1]^{d},\;\forall\,i\!\in\{1,\ldots,d\},\quad\nu\big(x+(e^{i})^{\perp}\big)=0

where $(e^{i})^{\perp}:=\{y\!\in{\mathbb{R}}^{d}:y^{i}=0\}$ . Note that for convenience we may extend any measure on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ into a measure on $({\mathbb{R}}^{d},{\cal B}or({\mathbb{R}}^{d}),\lambda_{d})$ by setting $\nu(A)=\nu(A\cap[0,1]^{d})$ .

The particular case where $\nu$ has a continuous c.d.f., especially when $\nu={\cal U}([0,1]^{d})$ , and $\mu$ is the empirical measure of a random or deterministic $n$ -tuple whose components are $[0,1]^{d}$ -valued, has been extensively investigated since the 1950s motivated by the so-called Quasi-Monte Carlo method (QMC, see [KN74, Nie92]).

This suggests and justifies to compare in a general framework discrepancies and Wasserstein distances ${\cal W}_{p}$ , $1\leq p<+\infty$ in a strong sense. To be more precise we will upper-bound these Wasserstein distances without any a priori restrictions on the distributions beyond the existence of finite $p$ -moments whereas, for the reverse bounds, we will assume that (at least) one of the two distributions is absolutely continuous (w.r.t. the Lebesgue measure) to avoid the above counterexample (1.1).

First we need the following technical lemma whose proof is postponed to Appendix A.

Lemma 2.1.

$(a)$ Let $\mu$ and $\nu$ two probability measures on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ . Then

D^{\infty}(\mu,\nu)\geq\sup_{x,\,y\in[0,1]^{d}}\big|\mu\big(]\!]x,y]\!]\big)-\nu\big(]\!]x,y]\!]\big)\big|.

$(b)$ If furthermore, $\mu\big((0,1]^{d}\big)=\nu\big((0,1]^{d}\big)=1$ , then

D^{\infty}(\mu,\nu)=\sup_{x,\,y\in[0,1]^{d}}\big|\mu\big(]\!]x,y]\!]\big)-\nu\big(]\!]x,y]\!]\big)\big|.

$(c)$ Without the additional assumption of $(b)$ , we have:

D^{\infty}(\mu,\nu)=\sup_{x,\,y\in[0,1]^{d},x\preceq y}\big|\mu\big(]\![x,y]\!]\big)-\nu\big(]\![x,y]\!]\big)\big|,

where $]\![x,y]\!]$ is defined by

]\![x,y]\!]=\begin{cases}]\!]x,y]\!]\textnormal{ if $x^{i}>0,\,\forall\,i\in\{1,\ldots,d\}$}\\ \left\{u\in[0,1]^{d},x^{i}<u^{i}\leq y^{i}\textnormal{ if $x^{i}>0$},0\leq u^{i}\leq y^{i}\textnormal{ if $x^{i}=0$}\right\}\textnormal{ otherwise.}\end{cases}

2.2 Bounding Wasserstein distances by the uniform discrepancy

To achieve our first goal, we will rely on the following bounds for the Wasserstein distances: (2.4) is mainly adapted from Lemma 5 in [FG15] whereas (2.6) also uses ideas from former results contained in [DSS13].

Proposition 2.2 (Existing upper-bound and a variant).

$(a)$ Let $\mu$ and $\nu$ two probability measures on $\big([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d}\big)$ be such that $\mu\big((0,1]^{d}\big)=\nu\big((0,1]^{d}\big)=1$ . Then,

{\cal W}^{p}_{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}\frac{2^{p}+1}{2}\sum_{\ell=1}^{+\infty}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}|\mu(F)-\nu(F)|

(2.4)

where $\displaystyle\mathfrak{d}_{d}=\sup_{x,y\in(0,1]^{d}}|y-x|$ depends on $p$ , $d$ and the norm $|\cdot|$ on $(0,1]^{d}$ and

{\cal P}_{\ell}=\Big\{a+(-2^{-(\ell+1)},2^{-(\ell+1)}]^{d},\;a=\frac{2\mathbf{k}+\mbox{\bf 1}}{2^{\ell+1}},\,\mathbf{k}\!\in\{0,\ldots,2^{\ell}-1\}^{d}\Big\}

(2.5)

with $\mbox{\bf 1}=(1,\^{E}\ldots,1)$ . Note that ${\rm card}({\cal P}_{\ell})=2^{d\ell}$ . We also have for any $\ell_{0}\in\mathbb{N}^{*}$ ,

{\cal W}^{p}_{p}(\mu,\nu)\leq{\mathfrak{d}_{d}^{p}}\bigg(\frac{2^{p}+1}{2}\sum_{\ell=1}^{\ell_{0}}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}|\mu(F)-\nu(F)|+2^{-p\ell_{0}}\bigg).

(2.6)

$(b)$ When $\mu$ and $\nu$ are probability measures on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ , then (2.4) still holds with the family of $(\tilde{{\cal P}_{\ell}})_{\ell\geq 0}$ , where $\tilde{{\cal P}_{\ell}}$ is a partition of $[0,1]^{d}$ which only differs from ${{\cal P}_{\ell}}$ for the semi-open boxes with a multi-index $\mathbf{k}=(k_{1},\ldots,k_{d})\!\in\{0,\ldots,2^{\ell}-1\}^{d}$ for which there exists $i\!\in\{1,d\}$ such that $k_{i}=0$ . When such is the case, the semi-open box $]\!]\frac{\mathbf{k}}{2^{\ell}},\frac{\mathbf{k}+\mathbf{1}}{2^{\ell}}]\!]=\frac{2\mathbf{k}+\ \mathbf{1}}{2^{\ell+1}}+(-2^{-(\ell+1)},2^{-(\ell+1)}]^{d}$ is replaced¹¹ 1 More simply, when a semi-open box of ${\cal P}_{\ell}$ has one or several faces which are included in the faces of $[0,1]^{d}$ , we add them to define the elements of $\tilde{{\cal P}_{\ell}}$ . by

\Big]\!\Big[\frac{\mathbf{k}}{2^{\ell}},\frac{\mathbf{k}+\mathbf{1}}{2^{\ell}}\Big]\!\Big]:=\left\{u\in[0,1]^{d},\frac{k_{i}}{2^{\ell}}<u^{i}\leq\frac{k_{i}+1}{2^{\ell}}\textnormal{ if $k_{i}\geq 1$},0\leq u^{i}\leq\frac{1}{2^{\ell}}\textnormal{ if $k_{i}=0$}\right\}.

Proof.

$(a)$ Step 0. Inequality (2.4) is a straightforward adaptation of [FG15, Lemma 5] written for the canonical Euclidean norm in the set $(-1,1]^{d}$ . For Inequality (2.6), one needs to slightly modify [DSS13, Lemma 2] by introducing a sequence $(\hat{\cal P}_{\ell})_{\ell\geq 0}$ of partitions built as follows:

•

For $\ell\in\llbracket 0,\ell_{0}\rrbracket$ , $\hat{\cal P}_{\ell}={\cal P}_{\ell}$ ,

•

For $\ell\geq\ell_{0}+1$ and a given integer $K\geq 2$ , $\hat{\cal P}_{\ell}$ is deduced from $\hat{\cal P}_{\ell-1}$ by dividing each element of $\hat{\cal P}_{\ell-1}$ into $K^{d}$ new elements. More precisely,

\hskip-28.45274pt\hat{{\cal P}_{\ell}}=\Big\{a+(-2^{-\ell_{0}-1}K^{-(\ell-\ell_{0})},2^{-\ell_{0}-1}K^{-(\ell-\ell_{0})}]^{d},\;a=\frac{2{\bf k}+\mbox{\bf 1}}{2^{\ell_{0}+1}K^{\ell-\ell_{0}}},\,{\bf k}\!\in\{0,\ldots,2^{{\ell_{0}}}K^{\ell-\ell_{0}}-1\}^{d}\Big\}.

(2.7)

We have ${\rm Card}(\hat{\cal P}_{\ell})=2^{d\ell_{0}}K^{d(\ell-\ell_{0})}$ . Since for any $\ell\geq 1$ , $\hat{\cal P}_{\ell}$ is built by partitioning each set of $\hat{\cal P}_{\ell-1}$ , the proof of [DSS13, Lemma 2] still works. More precisely, noting that the diameter of an element of ${\hat{\cal P}_{\ell}}$ is $2^{-\ell}\mathfrak{d}_{d}$ when $\ell\leq\ell_{0}$ and $2^{-\ell_{0}}K^{-(\ell-\ell_{0})}$ when $\ell\geq\ell_{0}+1$ .

Step 1. First assume that $\mu$ and $\nu$ satisfy the condition

\forall\,C\!\in{\hat{\mathcal{P}}=\bigcup_{\ell\geq 1}\hat{{\cal P}_{\ell}}},\quad\nu(C)>0\Longrightarrow\mu(C)>0.

with the convention $\frac{0}{0}=0$ . Then, a careful reading of the proof of [DSS13, Lemma 2] leads to (where $L$ denotes a stopping time defined in the proof of this lemma):

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq\frac{\mathfrak{d}_{d}^{p}}{2}\mathbb{E}[2^{-pL}{\bf 1}_{\{L\leq\ell_{0}\}}+2^{-p\ell_{0}}K^{-p(L-\ell_{0})}{\bf 1}_{\{L>\ell_{0}\}}]$
		$\displaystyle\leq\frac{\mathfrak{d}_{d}^{p}}{2}\sum_{\ell=0}^{\ell_{0}}2^{-p\ell}\sum_{F\in\hat{\cal P}_{\ell}}\nu(F)\sum_{C\textnormal{ child of }F}\left\|\frac{\nu(C)}{\nu(F)}-\frac{\mu(C)}{\mu(F)}\right\|$
		$\displaystyle+\frac{\mathfrak{d}_{d}^{p}}{2}\sum_{\ell=\ell_{0}+1}^{+\infty}2^{-p\ell_{0}}K^{-p(\ell-\ell_{0})}\sum_{F\in\hat{\cal P}_{\ell}}\nu(F)\sum_{C\textnormal{ child of }F}\left\|\frac{\nu(C)}{\nu(F)}-\frac{\mu(C)}{\mu(F)}\right\|.$

At this stage, we use the argument from [FG15, Lemma 5]: noting that

\nu(F)\left|\frac{\nu(C)}{\nu(F)}-\frac{\mu(C)}{\mu(F)}\right|\leq|\nu(C)-\mu(C)|+\frac{\mu(C)}{\mu(F)}|\mu(F)-\nu(F)|,

and setting

\delta_{\ell}=\sum_{F\in\hat{\cal P}_{\ell}}|\mu(F)-\nu(F)|,

we get

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq\frac{\mathfrak{d}_{d}^{p}}{2}\left(\sum_{\ell=1}^{\ell_{0}}\delta_{\ell}(2^{-p\ell}+2^{-p(\ell-1)})+\delta_{\ell_{0}+1}(2^{-p\ell_{0}}+2^{-p\ell_{0}}K^{-p})\right)$
		$\displaystyle+\frac{\mathfrak{d}_{d}^{p}}{2}\left(\sum_{\ell=\ell_{0}+2}^{+\infty}\delta_{\ell}(2^{-p\ell_{0}}K^{-p(\ell-\ell_{0}-1)}+2^{-p\ell_{0}}K^{-p(\ell-\ell_{0})})\right)$
		$\displaystyle\leq\frac{\mathfrak{d}_{d}^{p}}{2}(2^{p}+1)\sum_{\ell=1}^{\ell_{0}}2^{-p\ell}\delta_{\ell}+\mathfrak{d}_{d}^{p}2^{-p\ell_{0}}+O(K^{-p}),$

where, in the last line, we used that $\delta_{\ell}\leq 2$ for any $\ell\geq 1$ . The result follows by letting $K$ go to $+\infty$ .

Step 2. To get rid of the above weak absolute continuity assumption on $\mu$ and $\nu$ , we introduce for $\varepsilon\!\in(0,1)$ , $\mu_{\varepsilon}=\varepsilon\nu+(1-\varepsilon)\mu$ . Then

{\cal W}^{p}_{p}(\mu_{\varepsilon},\nu)\leq{\mathfrak{d}_{d}^{p}}\bigg(\frac{2^{p}+1}{2}\sum_{\ell=1}^{\ell_{0}}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}|\mu_{\varepsilon}(F)-\nu(F)|+2^{-p\ell_{0}}\bigg).

It is clear that $\mu_{\varepsilon}$ converges in total variation to $\mu$ so that the finite sum in the right hand side of the above inequality converges to that of (2.6). On the other hand, as $Z_{\varepsilon}Y+(1-Z_{\varepsilon})X$ where $X\sim\mu$ , $Y\sim\nu$ and $Z\sim{\cal B}(\{0,1\},\varepsilon)$ , independent of $X$ , $Y$ has distribution $\varepsilon\nu+(-\varepsilon)\mu$ , one checks that

{\cal W}^{p}_{p}(\mu_{\varepsilon},\mu)\leq{\mathbb{E}}\,|Z_{\varepsilon}Y+(1-Z_{\varepsilon})X-X|^{p}={\mathbb{E}}\^{E}|Z_{\varepsilon}|^{p}{\mathbb{E}}\,|X-Y|^{p}=\^{E}\varepsilon{\mathbb{E}}\,|X-Y|^{p}\xrightarrow{\varepsilon\rightarrow 0}0.

Hence $|{\cal W}_{p}(\mu_{\varepsilon},\nu)-{\cal W}^{p}(\mu,\nu)|\leq{\cal W}^{p}(\mu_{\varepsilon},\mu)\to 0$ as $\varepsilon\to 0$ which establishes (2.6).

$(b)$ One first checks that the coupling argument of [DSS13, Lemma 2] is still true with $[0,1]^{d}$ and the family of partitions $(\tilde{P}_{\ell})_{\ell}$ . Hence, [FG15, Lemma 5] whose proof is based on this lemma and on arguments which do not depend on the space and the partition, also extends to $[0,1]^{d}$ . ∎

From Proposition 2.2, we can deduce the following upper-bounds of the $p$ -Wasserstein distance by the uniform discrepancy.

Theorem 2.3 (Bounding Wasserstein distance by the uniform discrepancy).

Let $\mu$ and $\nu$ two probability measures on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ . Then,

•

If $p>d$ then

\displaystyle{\cal W}_{p}^{p}(\mu,\nu)

\displaystyle\leq\frac{\mathfrak{d}_{d}^{p}(2^{p}+1)}{2(2^{p-d}-1)}D^{\infty}(\mu,\nu).

If furthermore, $1+2^{-p}-2^{p-d}>0$ , i.e. $p<d+\frac{\log(1+\sqrt{1+2^{-(d-2)}})}{\log 2}-1$ , then

\displaystyle{\cal W}_{p}^{p}(\mu,\nu)

\displaystyle\leq\frac{\mathfrak{d}_{d}^{p}}{2^{p-d}-1}\left[\frac{2^{p}+1}{2}D^{\infty}(\mu,\nu)-2^{p(1-\frac{1}{d})}\left(1+2^{-p}-2^{p-d}\right)D^{\infty}(\mu,\nu)^{\frac{p}{d}}\right].

•

If $p=d$ then

{\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{d}\bigg(\bigg(\frac{(d+1)2^{d-1}}{d}+\frac{1}{2d}\bigg)D^{\infty}(\mu,\nu)+\frac{2^{d}+1}{2d\log 2}D^{\infty}(\mu,\nu)\log\Big(\frac{1}{D^{\infty}(\mu,\nu)}\Big)\bigg).

•

If $p<d$ then

{\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}{2^{-\frac{p}{d}}}\bigg(\frac{2^{p}+1}{1-{2^{p-d}}}+2^{p}\bigg)D^{\infty}(\mu,\nu)^{\frac{p}{d}}.

Proof.

We first prove the result when $\mu$ and $\nu$ are supported by $(0,1]^{d}$ .

Step 1: $\mu\big((0,1]^{d}\big)=\nu\big((0,1]^{d}\big)=1$ . In this case, the elements of ${\cal P}_{\ell}$ (defined by (2.5)) are all semi-open boxes. Hence, we deduce using Lemma 2.1 that, for every $\ell\geq 1$ ,

	$\displaystyle\sum_{F\in{\cal P}_{\ell}}\|\mu(F)-\nu(F)\|$	$\displaystyle\leq\min\Big(\sum_{F\in{\cal P}_{\ell}}\mu(F)+\nu(F),2^{d\ell}D^{\infty}(\mu,\nu)\Big)$
		$\displaystyle=\min\Big(2,2^{d\ell}D^{\infty}(\mu,\nu)\Big).$		(2.8)

Hence by (2.4) and (2.6), for any $\ell_{0}\in\mathbb{N}\cup\{+\infty\}$ ,

\displaystyle{\cal W}_{p}^{p}(\mu,\nu)

\displaystyle\leq\mathfrak{d}_{d}^{p}\left(\frac{2^{p}+1}{2}\sum_{\ell=1}^{\ell_{0}}2^{-p\ell}\min\big(2,2^{d\ell}D^{\infty}(\mu,\nu)\big)+2^{-p\ell_{0}}\right).

(2.9)

Note that for the case $\ell_{0}=0$ , the above inequality is true with the convention $\sum_{\emptyset}=0$ (since the inequality ${\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}$ is always true).

Case 1 $(p>d)$ . We first apply (2.9) with $\ell_{0}=+\infty$ and obtain:

\displaystyle{\cal W}_{p}^{p}(\mu,\nu)

\displaystyle\leq\mathfrak{d}_{d}^{p}\frac{2^{p}+1}{2}\sum_{\ell=1}^{\ell_{0}}2^{(d-p)\ell}D^{\infty}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}\frac{2^{p}+1}{2}\frac{2^{d-p}}{1-2^{d-p}}D^{\infty}(\mu,\nu).

(2.10)

Second, we apply (2.9) with $\ell_{0}=\ell^{\star}-1$ where

\ell^{\star}:=\inf\{\ell\geq 1,2^{d\ell}D^{\infty}(\mu,\nu)\geq 2\}.

One can check that

\ell^{\star}=\bigg\lceil\frac{\log(2/D^{\infty}(\mu,\nu))}{d\log 2}\bigg\rceil\geq\lceil\tfrac{1}{d}\rceil\geq 1,

since $\log D^{\infty}(\mu,\nu)\leq 0$ . As a consequence, applying (2.9) with $\ell_{0}=\ell^{\star}-1$ , we get

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq\mathfrak{d}_{d}^{p}\left[\frac{2^{p}+1}{2}\sum_{\ell=1}^{\ell^{\star}-1}2^{(d-p)\ell}D^{\infty}(\mu,\nu)+2^{-p(\ell^{\star}-1)}\right]$
		$\displaystyle\leq\mathfrak{d}_{d}^{p}\left[b_{p,d}(1-2^{-(p-d)(\ell^{\star}-1)})D^{\infty}(\mu,\nu)+2^{-p(\ell^{\star}-1)}\right],$		(2.11)

with

b_{p,d}=\frac{2^{p}+1}{2({2^{p-d}-1})}.

For a given $r>0$ , one can check that

\begin{split}&2^{-r(\ell^{\star}-1)}\leq 2^{-\frac{r}{d}\frac{\log(2/D^{\infty}(\mu,\nu))}{\log 2}+r}=2^{r(1-\frac{1}{d})}D^{\infty}(\mu,\nu)^{\frac{r}{d}},\\ &2^{-r(\ell^{\star}-1)}\geq 2^{-\frac{r}{d}}D^{\infty}(\mu,\nu)^{\frac{r}{d}}.\end{split}

(2.12)

Plugging these inequalities into (2.11), this leads to:

{\cal W}_{p}^{p}(\mu,\nu)\leq b_{p,d}D^{\infty}(\mu,\nu)+\left(-b_{p,d}2^{1-\frac{p}{d}}+2^{p(1-\frac{1}{d})}\right)D^{\infty}(\mu,\nu)^{\frac{p}{d}}.

One can check that

b_{p,d}2^{1-\frac{p}{d}}-2^{p(1-\frac{1}{d})}=\frac{2^{p(1-\frac{1}{d})}}{2^{p-d}-1}\left(1+2^{-p}-2^{p-d}\right).

This provides the second announced estimate.

Case 2 $(p=d)$ . Here, (2.9) again applied with $\ell_{0}=\ell^{\star}-1$ yields

{\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}\left(\frac{2^{p}+1}{2}(\ell^{\star}-1)D^{\infty}(\mu,\nu)+2^{-p(\ell^{\star}-1)}\right).

Using that $\ell^{\star}-1<\frac{\log(2/D^{\infty}(\mu,\nu))}{d\log 2}$ and (2.12) (applied with $r=p$ ), we obtain

{\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}\frac{2^{p}+1}{2}\frac{\log(2/D^{\infty}(\mu,\nu))}{d\log 2}D^{\infty}(\mu,\nu)+2^{p(1-\frac{1}{d})}D^{\infty}(\mu,\nu).

The estimate follows.

Case 3 ( $p<d$ ). By (2.9) applied with $\ell_{0}=\ell^{\star}-1$ , we obtain similarly to (2.11)

{\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}\left(\frac{(2^{p}+1)2^{(d-p)(\ell^{\star}-1)}}{2(1-{2^{p-d}})}D^{\infty}(\mu,\nu)+2^{-p(\ell^{\star}-1)}\right).

By the second inequality of (2.12) and the one below (applied with $r=d-p$ ),

2^{r(\ell^{\star}-1)}\leq 2^{\frac{r}{d}\frac{\log(2/D^{\infty}(\mu,\nu))}{\log 2}}=2^{\frac{r}{d}}D^{\infty}(\mu,\nu)^{-\frac{r}{d}},\quad r\geq 0,

we deduce that

{\cal W}_{p}^{p}(\mu,\nu)\leq\mathfrak{d}_{d}^{p}\left(\frac{(2^{p}+1)2^{-\frac{p}{d}}}{1-{2^{p-d}}}D^{\infty}(\mu,\nu)^{\frac{p}{d}}+2^{p(1-\frac{1}{d})}D^{\infty}(\mu,\nu)^{\frac{p}{d}}\right).

Step 2 (General case). Here, we have to use Proposition 2.2 $(b)$ and thus to consider the elements of $\tilde{{\cal P}}_{\ell}$ . These elements take the form $]\![x,y]\!]$ defined in Lemma 2.1 $(c)$ . Hence, from this result and from (2.4) and (2.6), we deduce that (2.9) still holds true with $\tilde{{\cal P}}_{\ell}$ . The sequel of the above proof being entirely based on this inequality, we deduce that the conclusions also hold true in the general case. ∎

When $p=d=1$ , the above bounds are sub-optimal due to the following proposition (where the norm is the absolute value).

Proposition 2.4 (One dimensional setting for ${\cal W}_{1}$ ).

If $p=d=1$ , then

{\cal W}_{1}(\mu,\nu)\leq D^{\star}(\mu,\nu)\leq D^{\infty}(\mu,\nu).

Proof.

This relies on the Koksma-Hlawka inequality, which reads as follows in one dimension in the version established in [BL94] or [Pag26]. For every function $f:[0,1]\to{\mathbb{R}}$ with finite variation in the measure sense, meaning that there is a signed measure $m_{f}$ on $\big([0,1],{\cal B}or([0,1])\big)$ such that $m_{f}(\{0\})=0$ and $f(x)=f(1)+m_{f}([0,1-x])$ , one has

\big|\mu(f)-\nu(f)\big|\leq D^{\star}(\mu,\nu)|m_{f}|([0,1])

where $|m_{f}|$ stands for the total variation measure of $m_{f}$ . In one dimension, a Lipschitz continuous function $f$ has finite variation in the above sense since it is $du$ - $a.e.$ differentiable with a bounded derivative $f^{\prime}$ satisfying

f(x)=f(0)+\int_{0}^{x}f^{\prime}(u)du=f(1)-\int_{0}^{1-x}f^{\prime}(1-v)dv

so that $m_{f}(du)=-f^{\prime}(1-u)du$ and $|m_{f}|=|f^{\prime}(1-u)|du$ . Then $m_{f}(\{0\})=0$ and $|m_{f}|([0,1])\leq\|f^{\prime}\|_{L^{\infty}(du)}=[f]_{\rm Lip}$ . Consequently for every Lipschitz function

\big|\mu(f)-\nu(f)\big|\leq[f]_{\rm Lip}D^{\star}(\mu,\nu).

The Monge-Kantorovich representation of the ${\cal W}_{1}$ -distance

{\cal W}_{1}(\mu,\nu)=\sup_{[f]_{\rm Lip}\leq 1}\int f(d\mu-d\nu)

yields the announced result. ∎

This result suggests that the $\log$ -term in the upper-bound obtained in Theorem 2.3 for the case $p=d$ is possibly superfluous. At least such is the case when $d=1$ . Proïnov’s Theorem in the following section also leads in favor of the same direction. An extension of this result to general $K$ – $S$ distance based on another method is proposed in Section 3.1 .

In order to partially synthesize Proposition 2.2, we derive the following corollary.

Corollary 2.5.

If ( $d\geq 2$ and $p\neq d$ ) or ( $d=1$ ), there exists a real constant $K_{p,d}$ depending on $p$ , $d$ such that, for every $\mu$ , $\nu\!\in{\cal P}([0,1]^{d})$

{\cal W}_{p}(\mu,\nu)\leq K_{p,d}\sup_{x,y\,\in[0,1]^{d}}|x-y|\big(D^{\infty}(\mu,\nu)\big)^{\frac{1}{p}\wedge\frac{1}{d}}.

Toward a Law of Iterated Logarithm (Monte Carlo simulation). Let $(U_{n})_{n\geq 1}$ be an i.i.d. sequence of uniformly distributed vectors on $[0,1]^{d}$ . Then Chung’s Law of Iterated Logarithm (see [Chu49, Kie61]) for the star discrepancy reads

\varlimsup_{n}\sqrt{\frac{2n}{\log\log n}}D^{\star}(U_{1},\ldots,U_{n})=1\quad{\mathbb{P}}\mbox{-}a.s.

Combining this result with that of Corollary 2.5 yields that, if ( $d\geq 2$ and $p\neq d$ ) or ( $d=1$ ), then there exists a real constant $K_{p,d}$ only depending on $p$ , $d$ such that, under the assumptions of this corollary

\varlimsup_{n}\bigg({\frac{2n}{\log\log n}}\bigg)^{\frac{1}{2}(\frac{1}{p}\wedge\frac{1}{d})}{\cal W}_{p}\Big(\frac{1}{n}\sum_{k=1}^{n}\delta_{U_{k}},{\cal U}([0,1]^{d})\Big)\leq K_{p,d}\quad{\mathbb{P}}\mbox{-}a.s.

where $K_{p,d}$ is a finite real constant from Corollary 2.5.

2.3 A refinement when $p=1$ and $d>1$

In view of the connection with Proïnov’s Theorem recalled in Section 2.4, we propose a refined result for the ${\cal W}_{1}$ -distance when the dimension $d$ is greater than $2$ . By an optimization strategy on the choice of $\ell_{0}$ defined in Proposition 2.2, we get the sharper upper-bound with an explicit smaller constant.

Theorem 2.6.

Let $\mu$ and $\nu$ two probability measures on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ . Then, for any integer $d\geq 2$ ,

{\cal W}_{1}(\mu,\nu)\leq\mathfrak{d}_{d}{2^{-\frac{1}{d}}}\left(\frac{3(d-1)}{2(1-2^{1-d})}\right)^{\frac{1}{d}}\frac{2d}{d-1}D^{\infty}(\mu,\nu)^{\frac{1}{d}}.

In particular,

{\cal W}_{1}(\mu,\nu)\leq\mathfrak{d}_{d}\kappa_{d}D^{\star}(\mu,\nu)^{\frac{1}{d}}\quad\mbox{ with }\quad\kappa_{d}=2^{1-\frac{1}{d}}\left(\frac{3(d-1)}{2(1-2^{1-d})}\right)^{\frac{1}{d}}\frac{2d}{d-1}.

Remark 2.1.

$\rhd$ One can check that $\kappa_{d}\xrightarrow{d\rightarrow+\infty}4$ .

$\rhd$ The optimization of $\ell_{0}$ proposed in the proof below is not completely natural in view of the proof of Theorem 2.3 where the integer $\ell^{\star}$ is precisely defined to optimize the bounds. However, the definition of $\ell^{\star}$ involves an upper integer part which may have bad effects on the constants.

$\rhd$ Such a strategy may also be applied in the other cases which may slightly improve the results at the price of technicalities that we considered useless for the paper.

Proof.

We only treat the case where $\mu((0,1]^{d})=\nu(([0,1]^{d})=1$ . The extension to the general case can be done exactly as in the proof of Theorem 2.3. We start from (2.9) when $p=1$ , namely

\displaystyle{\cal W}_{1}(\mu,\nu)

\displaystyle\leq\mathfrak{d}_{d}\left(\frac{3}{2}\,\sum_{\ell=1}^{\ell_{0}}2^{(d-1)\ell}D^{\infty}(\mu,\nu)+2^{-\ell_{0}}\right).

We introduce a parameter $a\geq 1$ and define $\ell_{0}^{(a)}$ by

\ell_{0}^{(a)}=\bigg\lceil\frac{\log(2/(aD^{\infty}(\mu,\nu)))}{d\log 2}\bigg\rceil-1.

Note that $\ell_{0}^{(a)}=\ell^{\star}-1$ when $a=1$ . In order to ensure that $\ell_{0}\geq 0$ , we first assume that

\frac{2}{aD^{\infty}(\mu,\nu)}>1.

(2.13)

In this case, following the strategy of the proof of Theorem 2.3 when $p<d$ with $\ell_{0}=\ell_{0}^{(a)}$ (instead of $\ell_{0}=\ell^{\star}-1$ ), we get

{\cal W}_{1}(\mu,\nu)\leq\mathfrak{d}_{d}2^{-\frac{1}{d}}\left(\frac{3}{1-{2^{1-d}}}a^{\frac{1}{d}-1}+2a^{\frac{1}{d}}\right)D^{\infty}(\mu,\nu)^{\frac{1}{d}}.

This suggests to minimize the function $h$ defined by:

h(a)=\frac{3}{1-2^{1-d}}a^{\frac{1}{d}-1}+2a^{\frac{1}{d}}.

One checks that this functions attains its minimum at the point

a^{\star}=\frac{3(d-1)}{2(1-2^{1-d})}\quad\textnormal{and that}\quad h(a^{\star})=\left(\frac{3(d-1)}{2(1-2^{1-d})}\right)^{\frac{1}{d}}\left(\frac{2}{d-1}+2\right).

The result follows if $a^{\star}$ satisfies the condition (2.13). Otherwise,

D^{\infty}(\mu,\nu)\geq\frac{2}{a^{\star}}=\frac{4(1-2^{1-d})}{3(d-1)},

and using that ${\cal W}_{1}(\mu,\nu)\leq\mathfrak{d}_{d}$ , we get

{\cal W}_{1}(\mu,\nu)\leq\mathfrak{d}_{d}\leq\mathfrak{d}_{d}\left(\frac{3(d-1)}{4(1-2^{1-d})}\right)^{\frac{1}{d}}D^{\infty}(\mu,\nu)^{\frac{1}{d}}\leq\mathfrak{d}_{d}2^{-\frac{1}{d}}h(a^{\star})D^{\infty}(\mu,\nu)^{\frac{1}{d}}.

The previous bound is thus still available in this case. ∎

2.4 Connections with QMC & MC methods

The discrepancy is mostly used in the theory of uniformly distributed sequences and their applications to Quasi-Monte Carlo simulation (QMC). A distribution $\nu$ being fixed on $[0,1]^{d}$ – mostly the uniform distribution ${\cal U}([0,1]^{d})$ – it is commonly used to measure the way the empirical measure induced by a $\big([0,1]^{d}\big)^{n}$ -valued $n$ -tuple $(\xi_{k})_{k=1,\ldots,n}$ approximates the original measure $\nu$ . To be more precise one considers

D^{\star,\nu}\big((\xi_{k})_{k=1,\ldots,n}\big):=D^{\star}\Big(\frac{1}{n}\sum_{k=1}^{n}\delta_{\xi_{k}},\nu\Big)

or its counterpart $D^{\infty,\nu}\big((\xi_{k})_{k=1,\ldots,n}\big)$ defined accordingly w.r.t. $D^{\infty}$ . For an introduction to QMC methods in Numerical Probability, we refer among others to [Nie92] or [Pag26]. One important theoretical result in this field is Proïnov’s theorem (see [Pro88]) which can be formulated as follows.

Proposition 2.7 (Proïnov Theorem (1984)).

Let $d$ , $n\!\in{\mathbb{N}}$ and let $\big([0,1]^{d}\big)^{n}$ -valued $n$ -tuple $(\xi_{k})_{k=1,\ldots,n}$ . Then there exists a real constant $C_{d}\!\in[1,4]$ such that

{{\cal W}_{1}^{\ell^{\infty}}\Big(\frac{1}{n}\sum_{k=1}^{n}\delta_{\xi_{k}},{\cal U}([0,1]^{d})\Big)\leq C_{d}D^{\star,{\cal U}([0,1]^{d})}\big((\xi_{k})_{k=1,\ldots,n}\big)^{\frac{1}{d}},}

where ${\cal W}_{1}^{\ell^{\infty}}$ denotes the Wasserstein distance w.r.t. the $\ell^{\infty}$ -norm on $[0,1]^{d}$ . Moreover when $d=1$ , then $C_{1}=1$ and both error moduli attain their minimum, $n$ being fixed, at $\Big(\frac{2k-1}{2n}\Big)_{k=1,\ldots,n}$ with a common resulting value $\frac{1}{2n}$ .

Remark 2.2.

$\bullet$ The definition of the star discrepancy in [Pro88] is slightly different from that of $D^{\star}(\mu,\nu)$ , namely $\sup_{x,\,y\in[0,1]^{d}}\big|\mu\big([\![0,y[\![\big)-\nu\big([\![0,x[\![\big)\big|$ , but this modulus turns out to be lower or equal to $D^{\star}(\mu,\nu)$ using arguments similar to those used to prove Lemma 2.1.

$\bullet$ Since $D^{\infty}\leq 2^{d}D^{\star}$ , we can compare the improved general constant $\kappa_{d}$ from Theorem 2.6 the (bounds known on) constant $C_{d}$ appearing in Proïnov’s Theorem (which holds in a more restricted framework), having in mind that ${\mathfrak{d}_{d}=1}$ for the $\ell^{\infty}$ -norm. Let us recall that this constant $\kappa_{d}$ is given by

\displaystyle\kappa_{d}=2^{1-\frac{1}{d}}\left(\frac{3(d-1)}{2(1-2^{1-d})}\right)^{\frac{1}{d}}\frac{2d}{d-1}\longrightarrow 4\quad\mbox{ as }\quad d\to+\infty.

Numerical computations for medium values of $d$ are as follows: if $d=2$ , $\kappa_{2}\simeq 9.7980$ , if $d=3$ , $\kappa_{3}\simeq 7.5595$ , if $d=4$ , $\kappa_{4}\simeq 6.7537$ , if $d=5$ , $\kappa_{5}\simeq 6.3096$ , if $d=6$ , $\kappa_{6}\simeq 6.0147$ , if $d=7$ , $\kappa_{7}\simeq 5.7983$ , if $d=8$ , $\kappa_{8}\simeq 5.6299$ , if $d=9$ , $\kappa_{9}\simeq 5.4937$ , if $d=10$ , $\kappa_{10}\simeq 5.3806$ , if $d=11$ , $\kappa_{11}\simeq 5.2850$ , if $d=12$ , $\kappa_{12}\simeq 5.2028$ , if $d=20$ , $\kappa_{20}\simeq 4.8087$ . if $d=50$ , $\kappa_{50}\simeq 4.3867$ , if $d=100$ , $\kappa_{100}\simeq 4.2182$ .

$\bullet$ Our constants are thus slightly larger than those of the original theorem (which lie into $[1,4]$ ) but it is worth noting that our bounds are universal: they do not hold only for the uniform distribution ${\cal U}([0,1]^{d})$ but also for any distribution $\nu$ on $[0,1]^{d}$ (and any empirical measure).

Toward a Law of Iterated Logarithm. Let $(U_{n})_{n\geq 1}$ be an i.i.d. sequence of uniformly distributed vectors on $[0,1]^{d}$ . Then Chung’s Law of Iterated Logarithm (see [Chu49]) for the star discrepancy reads

\varlimsup_{n}\sqrt{\frac{2n}{\log\log n}}D^{\star}(U_{1},\ldots,U_{n})=1\quad{\mathbb{P}}\mbox{-}a.s.

Combining this results with that of Corollary 2.5 yields that, if $d\geq 2$ and $p\neq d$ or ( $d=1$ ), then there exists a real constant $K_{p,d}$ only depending on $p$ , $d$ such that, under the assumptions of this corollary

\varlimsup_{n}\bigg({\frac{2n}{\log\log n}}\bigg)^{\frac{1}{2}(\frac{1}{p}\wedge\frac{1}{d})}{\cal W}_{p}\Big(\frac{1}{n}\sum_{k=1}^{n}\delta_{U_{k}},{\cal U}([0,1]^{d})\Big)\leq K_{p,d}\quad{\mathbb{P}}\mbox{-}a.s.

where $K_{p,d}$ is a finite real constant from Corollary 2.5.

2.5 Bounding the star discrepancy by the $L^{1}$ -Wasserstein distance

We refer to Section 3.2 devoted to Kolmogorov-Smirnov distance between distributions with possibly unbounded supports. Note that these bounds require that at least one of the two distributions under consideration is absolutely continuous. The obtained bound cannot be improved in the case of $[0,1]^{d}$ -supported distributions, at least in a reasonably general framework.

3 Kolmogorov-Smirnov distance vs $p$ -Wasserstein distance on ${\cal P}_{p}({\mathbb{R}}^{d})$

3.1 Bounding the $p$ -Wasserstein distance by the $K$ – $S$ distance

We consider now probability distributions on the whole space ${\mathbb{R}}^{d}$ and we straightforwardly update the definitions of the star and uniform discrepancies. The first one is then also known as the Kolmogorov-Smirnov distance ( $K$ – $S$ distance). This section allows to treat the $[0,1]^{d}$ -supported distributions but with worse constants where the $K$ – $S$ distance is commonly known as (star) discrepancy.

Definition 3.1.

Let $\mu$ and $\nu$ two probability measures on $([0,1]^{d},{\cal B}or([0,1]^{d}),\lambda_{d})$ . We define the Kolmogorov -Smirnov distance, denoted $K$ – $S$ , by

D^{\star}(\mu,\nu)=\^{E}\sup_{x\in{\mathbb{R}}^{d}}\big|\mu\big(]\!]-\infty,x]\!]\big)-\nu\big((]\!]-\infty,x]\!]\big)\big|,

where, by an abuse of notation, we also denote $-\mathbf{\infty}=(-\infty,\ldots,-\infty)$ . This distance can be simply seen as star discrepancy defined in a more general setting. We also define the uniform discrepancy between $\mu$ and $\nu$ by

D^{\infty}(\mu,\nu)=\^{E}\sup_{x,\,y\in{\mathbb{R}}^{d}}\big|\mu\big([\![x,y]\!]\big)-\nu\big([\![x,y]\!]\big)\big|.

One easily checks like in Lemma 2.1 that, with these definitions,

D^{\infty}(\mu,\nu)=\^{E}\sup_{x,y\in{\mathbb{R}}^{d}}\big|\mu\big(]\!]x,y]\!]\big)-\nu\big(]\!]x,y]\!]\big)\big|

(3.14)

since $\mu([\![x,y]\!])=\lim_{n}\mu(]\!]x-\mbox{\bf 1}/n,y]\!])$ and that the bounds (2.2)

D^{\star}\leq D^{\infty}\leq 2^{d}D^{\star}

(3.15)

between these quantities still hold.

The following Proposition, which is the combination of Lemmas 5 and 6 from [FG15], is the key result on which we rely in this section. We set:

{\cal B}_{n}=(-2^{-n},2^{-n}]^{d}\backslash(-2^{-(n-1)},2^{-(n-1)}]^{d}.

Proposition 3.1.

Let $p\!\in(0,+\infty)$ and let $d\geq 1$ . There exists a positive constant $K_{p,d}$ such that for every pair $(\mu,\nu)\in{\cal P}_{p}({\mathbb{R}}^{d})^{2}$ ,

{\cal W}_{p}^{p}(\mu,\nu)\leq K_{p,d}\sum_{n\geq 0}2^{pn}\sum_{\ell\geq 0}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}\big|\mu(2^{n}F\cap{\cal B}_{n})\^{E}-\nu(2^{n}F\cap{\cal B}_{n})\^{E}\big|,

(3.16)

where $2^{n}F=\{2^{n}x,\;x\!\in F\}$ , ${\cal P}_{0}=\{(-1,1]^{d}\}$ and, for every $\ell\geq 1$ ,

{\cal P}_{\ell}=\Big\{a+(-2^{-\ell},2^{-\ell}]^{d},\;a=\frac{2{\bf k}+\mbox{\bf 1}}{2^{\ell}},\,{\bf k}\in\{-2^{\ell-1},\ldots-1,0,1,\ldots,2^{\ell-1}-1\}^{d}\Big\}.

Note that ${\rm card}({\cal P}_{\ell})=2^{d\ell}$ and (with obvious notation) ${\rm card}(2^{n}{\cal P}_{\ell}\cap{\cal B}_{n})=2^{d(\ell-1)^{+}}$ .

Theorem 3.2.

Let $q>p$ and $\mu$ , $\nu$ two probability measures with finite $q$ -moments. There exist real constants $\kappa_{p,q,d}>0$ such that

{\cal W}_{p}^{p}(\mu,\nu)\leq\kappa_{p,q,d}\big(M_{\frac{\mu+\nu}{2}}(q)\vee 1)\left\{\begin{array}[]{ll}D^{\infty}(\mu,\nu)^{\frac{p}{d}}&\mbox{ if }p<\frac{dq}{q+d}\\ D^{\infty}(\mu,\nu)^{1-\frac{p}{q}}&\mbox{ if }\frac{dq}{q+d}<p\mbox{ and }p\neq d\end{array}\right.

(3.17)

where $M_{\frac{\mu+\nu}{2}}(q)=\frac{1}{2}\int_{{\mathbb{R}}^{d}}|\xi|^{q}(\mu+\nu)(d\xi)$ .

Remarks. $\bullet$ The above result can be partially summed up into: if $p\neq d$ and $p\neq\frac{dq}{d+q}$ then

{\cal W}_{p}^{p}(\mu,\nu)\leq\kappa_{p,q,d}\big(M_{\frac{\mu+\nu}{2}}(q)\vee 1)D^{\infty}(\mu,\nu)^{\frac{p}{d}\wedge(1-\frac{p}{q})}.

This is in line with what was obtained for $[0,1]^{d}$ -supported distributions (for which $q=+\infty$ ).

$\bullet$ If $p=d$ our approach fails to provide a direct bound. However , for every $\varepsilon\!\in(0,q-d)$ , one has

{\cal W}_{p}(\mu,\nu)\leq{\cal W}_{d+\varepsilon}(\mu,\nu)\leq\kappa_{1+\varepsilon,q,d}^{\frac{1}{d+\varepsilon}}\big(M_{\frac{\mu+\nu}{2}}(q)\vee 1)^{\frac{1}{d+\varepsilon}}D^{\infty}(\mu,\nu)^{\frac{1}{d+\varepsilon}-\frac{1}{q}}.

(3.18)

$\bullet$ However, in one dimension, a specific approach is possible based on the representation formula (see e.g. [Vil03])

{\cal W}_{1}(\mu,\nu)=\int_{-\infty}^{\infty}|F_{\mu}(x)-F_{\nu}(x)|dx,

where $F_{\mu}$ and $F_{\nu}$ denote the cumulative distribution functions of $\mu$ and $\nu$ respectively. Then, for every $a>0$ ,

	$\displaystyle{\cal W}_{1}(\mu,\nu)$	$\displaystyle\leq\int_{-\infty}^{-a}F_{\mu}(x)+F_{\nu}(x)dx+2aD^{\star}(\mu,\nu)+\int_{a}^{+\infty}(1-F_{\mu}(x))+(1-F_{\nu}(x))dx$
		$\displaystyle\leq\int_{a}^{+\infty}{\mathbb{P}}(\|X\|>x)+{\mathbb{P}}(\|Y\|>x)dx+2aD^{\star}(\mu,\nu)$		(3.19)

where $X$ and $Y$ are $\mu$ and $\nu$ -distributed respectively. If $X$ and $Y$ both have finite moments of order $q$ , one has

\int_{a}^{+\infty}{\mathbb{P}}(|X|>x)dx\leq{\mathbb{E}}[|X|^{q}]\int_{a}^{+\infty}x^{-q}dx\leq{\mathbb{E}}[|X|^{q}]a^{1-q},

which yields after an obvious optimization

{\cal W}_{1}(\mu,\nu)\leq 2M_{\frac{\mu+\nu}{2}}(q)D^{\star}(\mu,\nu)^{1-\frac{1}{q}}.

$\bullet$ If $\mu$ and $\nu$ have exponential moments in the sense that $\int_{{\mathbb{R}}}e^{\lambda|\xi|}(\mu+\nu)(d\xi)<+\infty$ for some $\lambda>0$ , then it follows from (3.19) that,

{\cal W}_{1}(\mu,\nu)\leq\int_{{\mathbb{R}}}e^{\lambda|\xi|}(\mu+\nu)(d\xi)\frac{e^{-\lambda a}}{\lambda}+2aD^{\star}(\mu,\nu)

Setting $a=\frac{1}{\lambda}\log(1/D^{\infty}(\mu,\nu))$ yields

{\cal W}_{1}(\mu,\nu)\leq\frac{1}{\lambda}\bigg(\int_{{\mathbb{R}}}e^{\lambda|\xi|}(\mu+\nu)(d\xi)D^{\star}(\mu,\nu)+2D^{\star}(\mu,\nu)\log(1/D^{\infty}(\mu,\nu))\bigg).

$\bullet$ If $\mu_{n}$ , $n\geq 1$ are (uniform) empirical measures of the form $\mu=\mu_{n}=\frac{1}{n}\sum_{k=1}^{n}\delta_{\xi^{n}_{k}}$ here $\xi^{n}_{1},\ldots,\xi^{n}_{n}\!\in{\mathbb{R}}^{d}$ . Then

M_{\mu_{n}}(q),\;n\geq 1,\mbox{ is bounded iff }\sup_{n\geq 1}\frac{1}{n}\sum_{k=1}^{n}|\xi^{n}_{k}|^{q}<+\infty.

Proof. Step 1. Let $\ell\geq 1$ . It is clear that $\frac{2k+\mbox{\bf 1}}{2^{\ell}}+(-2^{-\ell},2^{-\ell}]^{d}=]\!]k2^{-\ell},(k+\mbox{\bf 1})2^{-\ell}]\!]$ is a semi-open box so that, for every $F\!\in{\cal P}_{\ell}$ , either $2^{n}F\cap{\cal B}_{n}=\varnothing$ for $2^{d(\ell-1)}$ semi-open boxes or, for the $(2^{d}-1)2^{d(\ell-1)}=2^{d\ell}(1-2^{-d})$ others

\big|\mu(2^{n}F\cap{\cal B}_{n})\^{E}-\nu(2^{n}F\cap{\cal B}_{n})\^{E}\big|\leq D^{\infty}(\mu,\nu)

owing to (3.14).

If $\ell=0$ , $\big|\mu({\cal B}_{n})\^{E}-\nu({\cal B}_{n})\^{E}\big|\leq\min(\mu({\cal B}_{n})\^{E}+\nu({\cal B}_{n}),D^{\infty}(\mu,\nu)\big)$ .

Consequently, if we set

m=\frac{1}{2}(\mu+\nu)\quad\mbox{ and }\quad M_{m}(q)=\int_{{\mathbb{R}}^{d}}|\xi|_{\infty}^{q}m(\delta\xi)=\frac{1}{2}\Big(\int_{{\mathbb{R}}^{d}}|\xi|_{\infty}^{q}\mu(\delta\xi)+\int_{{\mathbb{R}}^{d}}|\xi|_{\infty}^{q}\nu(\delta\xi)\Big),

one has

$\displaystyle\sum_{F\in{\cal P}_{\ell}\cap{\cal B}_{n}}\big\|\mu(2^{n}F\cap{\cal B}_{n})\^{E}-\nu(2^{n}F\cap{\cal B}_{n})\^{E}\big\|$	$\displaystyle\leq\min\big(\mu({\cal B}_{n})+\nu({\cal B}_{n}),2^{d(\ell-1)^{+}}D^{\infty}(\mu,\nu)\big)$
	$\displaystyle\leq\min\big(2m({\cal B}_{n}),2^{d\ell}D^{\infty}(\mu,\nu)\big)$
	$\displaystyle\leq\min\big(2M_{m}(q)2^{-q(n-1)},2^{d\ell}D^{\infty}(\mu,\nu)\big),$	(3.20)

where we used the triangle inequality to establish the left bound in the min of the first line.

Step 2 (Technical lemma).

Lemma 3.3.

Let $p>0$ . Let $t>0$ be fixed and let $L:(0,+\infty)\to{\mathbb{R}}_{+}$ be defined by

L(u):=\sum_{\ell\geq 0}2^{-p\ell}\min\big(u,2^{d\ell}D^{\infty}(\mu,\nu)\big).

The function $L$ satisfies the following upper-bounds depending on $p$ and the dimension $d$ where $C_{p,d}>0$ denotes a positive constant only depending on $p$ , $\beta$ , $d$ that may vary from line to line.

•

If $p>d$ , then

$L(u)\leq C_{p,d}\min\Big(u,D^{\infty}(\mu,\nu)\Big).$
•

If $p=d$ then,

$L(u)\leq C_{p,d}(1+\left(\log(u/D^{\infty}(\mu,\nu))\right)_{{+}})D^{\infty}(\mu,\nu).$

•

If $p<d$ , then

L(u)\leq C_{p,d}\Big(u^{1-\frac{p}{d}}D^{\infty}(\mu,\nu)^{\frac{p}{d}}\mbox{\bf 1}_{\{u>D^{\infty}(\mu,\nu)\}}+u\mbox{\bf 1}_{\{u\leq D^{\infty}(\mu,\nu)\}}\Big).

Proof.

$\triangleright$ If $p>d$ , one has

L(u)\leq\min\bigg(u\sum_{\ell\geq 0}2^{-p\ell},D^{\infty}(\mu,\nu)\sum_{\ell\geq 0}2^{-(p-d)}\bigg)=\min\Big(\frac{u}{1-2^{-p}},\frac{D^{\infty}(\mu,\nu)}{1-2^{-(p-d)}}\Big).

$\triangleright$ If $p=d$ there are two sub-cases. If $u<2^{-d}D^{\infty}(\mu,\nu)$ , then $L(u)=\frac{u}{1-2^{-p}}$ . Otherwise $\ell^{*}=\left\lceil\frac{\log(u/D^{\infty}(\mu,\nu))}{d\log 2}\right\rceil\!\in\Big[\frac{\log(u/D^{\infty}(\mu,\nu))}{d\log 2},1+\frac{\log(u/D^{\infty}(\mu,\nu)}{d\log 2}\Big)$ so that $\ell^{*}\geq 0$ and

L(u)\leq\ell^{*}D^{\infty}(\mu,\nu)+\frac{2^{-p\ell^{*}}}{1-2^{-p}}\leq\Big(1+\frac{1}{1-2^{-p}}+\frac{\log(u/D^{\infty}(\mu,\nu))}{d\log 2})\Big)D^{\infty}(\mu,\nu).

$\triangleright$ If $p<d$ either $u<2^{-d}D^{\infty}(\mu,\nu)$ and $L(u)=\frac{u}{1-2^{-p}}$ . Otherwise $\ell^{*}$ defined as above is nonnegative and

	$\displaystyle L(u)$	$\displaystyle=\sum_{\ell=0}^{\ell^{}-1}2^{-p\ell}2^{d\ell}D^{\infty}(\mu,\nu)+\sum_{\ell\geq\ell^{}}2^{-p\ell}u$
		$\displaystyle=D^{\infty}(\mu,\nu)\frac{2^{(d-p)\ell^{}}-1}{2^{d-p}-1}+u\frac{2^{-p\ell^{}}}{1-2^{-p}}$
		$\displaystyle\leq D^{\infty}(\mu,\nu)\frac{2^{(d-p)(1+\log(u/D^{\infty}(\mu,\nu))}}{2^{d-p}-1}+u\,2^{-p}\frac{2^{-p\frac{\log(u/D^{\infty}(\mu,\nu))}{d\log 2}}}{1-2^{-p}}$
		$\displaystyle\leq\Big(\frac{1}{1-2^{-(d-p)}}+\frac{1}{2^{p}-1}\Big)\big(D^{\infty}(\mu,\nu)\big)^{\frac{p}{d}}u^{1-\frac{p}{d}}.$

∎

Step 3. It follows from (3.16), Step 1 and the definition of the function $L$ that

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq K_{p,d}\sum_{n\geq 0}2^{pn}\sum_{\ell\geq 0}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}\big\|\mu(2^{n}F\cap{\cal B}_{n})\^{E}-\nu(2^{n}F\cap{\cal B}_{n})\^{E}\big\|$
		$\displaystyle\leq K_{p,d}\sum_{n\geq 0}2^{pn}\sum_{\ell\geq 0}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}\min\big(2^{1+q}M_{m}(q)2^{-qn},2^{d\ell}D^{\infty}(\mu,\nu)\big)$
		$\displaystyle\leq K^{\prime}_{p,d}(M_{m}(q)\vee 1)\sum_{n\geq 0}2^{pn}\sum_{\ell\geq 0}2^{-p\ell}\sum_{F\in{\cal P}_{\ell}}\min\big(2^{-qn},2^{d\ell}D^{\infty}(\mu,\nu)\big)$
		$\displaystyle=K^{\prime}_{p,d}(M_{m}(q)\vee 1)\sum_{n\geq 0}2^{pn}L\big(2^{-qn},D^{\infty}(\mu,\nu)\big).$

Now we inspect the usual three cases. The letters $C$ and $c$ denote positive constants depending only on its indices that may vary from line to line.

$\triangleright$ If $p>d$ , it follows from Proposition 3.1 and Lemma 3.3 that

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq C^{\prime}_{p,q,d}\sum_{n\geq 0}2^{np}\min\big(2^{-qn},D^{\infty}(\mu,\nu)\big)$
		$\displaystyle=C^{\prime}_{p,q,d}\Big(n^{\star}D^{\infty}(\mu,\nu)+\sum_{n\geq n^{\star}}2^{n(p-q)}\Big)$

where $n^{\star}=\left\lceil-\frac{\log(D^{\infty}(\mu,\nu))}{q\log 2}\right\rceil\geq 1$ . Hence

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq C_{p,q,d}\bigg(\frac{2^{-n^{\star}(q-p)}}{1-2^{-(q-p)}}+\frac{1}{q\log 2}\log(1/D^{\infty}(\mu,\nu))D^{\infty}(\mu,\nu)\bigg)$
		$\displaystyle\leq C_{p,q,d}\bigg(\frac{(D^{\infty}(\mu,\nu))^{1-\frac{p}{q}}}{1-2^{-(q-p)}}+\frac{1}{q\log 2}\log(1/D^{\infty}(\mu,\nu))D^{\infty}(\mu,\nu)\bigg)$
		$\displaystyle\leq C_{p,q,d}D^{\infty}(\mu,\nu)^{1-\frac{p}{q}}.$

$\triangleright$ If $p<\frac{qd}{q+d}$ then it follows Proposition 3.1 and Lemma 3.3 that

	$\displaystyle{\cal W}_{p}^{p}(\mu,\nu)$	$\displaystyle\leq C_{p,q,d}\sum_{n\geq 0}2^{(p-q(1-\frac{p}{d}))n}D^{\infty}(\mu,\nu)^{\frac{p}{d}}\mbox{\bf 1}_{\{c_{p,q,d}2^{-qn}>D^{\infty}(\mu,\nu)\}}+2^{-(q-p)n}\mbox{\bf 1}_{\{c_{p,q,d}2^{-qn}\leq D^{\infty}(\mu,\nu)\}}$
		$\displaystyle=C_{p,q,d}\bigg(\sum_{n=0}^{n^{\star}-1}2^{(p-q(1-\frac{p}{d}))n}D^{\infty}(\mu,\nu)^{\frac{p}{d}}+\frac{2^{-(q-p)n^{\star}}}{1-2^{-(q-p)}}\bigg)$
		$\displaystyle=C_{p,q,d}\bigg(\frac{2^{(p-q(1-\frac{p}{d}))n^{\star}}-1}{2^{(p-q(1-\frac{p}{d})}-1}D^{\infty}(\mu,\nu)^{\frac{p}{d}}+2^{-(1-\frac{p}{d})d}(D^{\infty}(\mu,\nu))^{1-\frac{p}{q}}\bigg)$

with $n^{\star}=\left\lceil\frac{\log(c_{pq,d}/D^{\infty}(\mu,\nu))}{q\log 2}\right\rceil$ . Hence, if $p<\frac{qd}{q+d}$ then $p-q(1-\frac{p}{d})<0$ so that

{\cal W}_{p}^{p}(\mu,\nu)\leq C_{p,q,d}\big(D^{\infty}(\mu,\nu)^{\frac{p}{d}}+D^{\infty}(\mu,\nu)^{1-\frac{p}{q}}\big)\leq C^{(3)}_{p,q,d}D^{\infty}(\mu,\nu))^{\frac{p}{d}}

since $\frac{p}{d}\leq 1-\frac{p}{d}$ and $D^{\infty}(\mu,\nu)\leq 1$ .

If $p>\frac{qd}{q+d}$ then $p-q(1-\frac{p}{d})>0$ and one easily checks using that $n^{\star}<1+\frac{\log(c_{pq,d}/D^{\infty}(\mu,\nu))}{q\log 2}$ that

{\cal W}_{p}^{p}(\mu,\nu)\leq C_{p,q,d}D^{\infty}(\mu,\nu)^{1-\frac{p}{q}}.

$\Box$

3.2 Bounding the $K$ – $S$ -distance by the $L^{1}$ -Wasserstein distance

Let us denote by $\|u\|_{\infty}=\max_{i=1,\ldots,d}|u^{i}|$ the $\ell^{\infty}$ -norm and let us define, for every $A\subset{\mathbb{R}}^{d}$ and $x\!\in{\mathbb{R}}^{d}$ , $d_{\infty}(x,A)=\inf_{a\in A}|x-a|_{\infty}$ . The key property of this section is the Monge-Kantorovich representation of the $L^{1}$ - Wasserstein distance, namely

{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)=\sup\bigg\{\int fd\mu-\int fd\nu,f\!\in{\rm Lip}({\mathbb{R}}^{d},{\mathbb{R}}),\,\mbox{ with }[f]_{\rm Lip}\leq 1\bigg\},

(3.21)

where $[f]_{\rm Lip}:=\sup_{x,y\in{\mathbb{R}}^{d}}\frac{|f(x)-f(y)|}{|x-y|_{{}_{\infty}}}$ .

Having in mind that the topology induced by the $K$ – $S$ distance is finer than that induced by ${\cal W}_{1}$ , as emphasized by the counterexample (see (1.1)), we need an additional assumption on one of the two probability measures under consideration to bound the first distance by the second one. Thus, we will assume in the proposition below that at least one of the two measures is absolutely continuous with respect to the Lebesgue measure.

Theorem 3.4 (Bounding star discrepancy discrepancy by $L^{1}$ -Wasserstein distance).

Let $\nu$ be an absolutely continuous distribution on ${\mathbb{R}}^{d}$ with density $g\!\in{\cal L}^{\frac{r}{r-1}}({\mathbb{R}}^{d},\lambda_{d})$ for some $r\!\in(1,+\infty]$ and finite first moment. Then, for every probability distribution $\mu$ on ${\mathbb{R}}^{d}$ with finite first moment,

D^{\star}(\mu,\nu)\leq C_{r,d}{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)^{\frac{d}{r+d}}\big\|g\big\|^{\frac{r}{r+d}}_{{\cal L}^{\frac{r}{r-1}}(\lambda_{d})}.

(3.22)

with $C_{r,d}=\begin{pmatrix}r+d\\ r\end{pmatrix}^{-\frac{1}{r+d}}\bigg(\Big(\frac{d}{r}\Big)^{\frac{r}{r+d}}+\Big(\frac{r}{d}\Big)^{\frac{d}{r+d}}\bigg)$ for $r\geq 1$ . If $g$ is bounded, one has:

D^{\star}(\mu,\nu)\leq C_{1,d}{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)^{\frac{d}{d+1}}\big\|g\big\|^{\frac{1}{d+1}}_{\infty}.

Remark. Note the case of a bounded density corresponds to $r=1$ and is consistent with the general formula for $r>1$ . Also note that this constant goes to $1$ as $d\to\infty$ .

Proof.

Let $x\!\in[0,1]^{d}$ , let $f_{x}=\mbox{\bf 1}_{]\!]-\infty,x]\!]}$ and, for every $\varepsilon>0$ , $f_{x,\varepsilon}=\Big(1-\frac{d_{\infty}(\cdot,]\!]-\infty,x]\!])}{\varepsilon}\Big)^{+}$ and $\tilde{f}_{x,\varepsilon}=\Big(1-\frac{d_{\infty}(\cdot,]\!]-\infty,x-\varepsilon\mathbf{1}]\!])}{\varepsilon}\Big)^{+}$ (with the convention on boxes). The functions $f_{x,\varepsilon}$ and $\tilde{f}_{x,\varepsilon}$ are clearly $\frac{1}{\varepsilon}$ -Lipschitz for the $\ell^{\infty}$ -norm. It is clear that $\tilde{f}_{x,\varepsilon}\leq f_{x}\leq f_{x,\varepsilon}$ .

Let us compute $d_{\infty}(u,]\!]-\infty,x]\!])$ for every $u\!\in{\mathbb{R}}^{d}\setminus]\!]-\infty,x]\!]$ . First, note that he continuous convex function $\varphi_{u}:y\mapsto|u-y|_{\infty}$ attains its minimum on the boundary of the box $]\!]-\infty,x]\!]$ namely

\partial]\!]-\infty,x]\!]=\bigcup_{1\leq i\leq d}\prod_{1\leq j\leq i-1}\{x^{j}\}\times(-\infty,x^{i}]\times\prod_{i+1\leq j\leq d}\{x^{j}\}.

First note that $\inf_{y\in]\!]-\infty,x]\!]}\varphi_{i}(y)=\min_{y\in B_{\ell^{\infty}}(x,2|u-x]_{{}_{\infty}})}|u-y|_{{}_{\infty}}$ hence ${\rm argmin}\,\varphi_{u}$ is nonempty. If not included in $\partial]\!]-\infty,x]\!$ , let $y^{*}\in{\rm argmin}\,\varphi_{u}\cap]\!]-\infty,x[\![$ and let $g(t)=\varphi_{u}(tu+(1-t)y^{*}$ ), $t\in[0,1]$ . The function $g$ is nonnegative, continuous and convex and there exists $\eta>0$ such that $u+(1-t)y^{*}\!\in]\!]-\infty,x[\![$ for $t\!\in(0,\eta]$ . Hence the right derivative $g^{\prime}_{r}(0)\geq 0$ by definition of $y^{*}$ . As $g$ is convex, it is also non-decreasing. Noting that $g(1)=0$ implies that $g$ is identically $0$ . Then $g(0)=0$ so that $u=y^{*}$ which is impossible since $u$ does not belong to $]\!]-\infty,x]\!]$ . Hence, one easily checks that

d_{\infty}(u,]\!]-\infty,x]\!])=\min_{i=1,\ldots,d}(x^{i}-u^{i})^{+}.

Then

	$\displaystyle\mu(]\!]-\infty,x]\!])-\nu(]\!]-\infty,x]\!])$	$\displaystyle=\int\underbrace{(f_{x}-f_{x,\varepsilon})}_{\leq 0}d\mu+\int f_{x,\^{E}\varepsilon}d\mu-\int f_{x,\^{E}\varepsilon}d\nu+\int(f_{x,\varepsilon}-f_{x})d\nu$
		$\displaystyle\leq\frac{1}{\varepsilon}{\cal W}_{1}^{\ell_{\infty}}(\mu,\nu)+\int(f_{x,\varepsilon}-f_{x})gd\lambda_{d}$		(3.23)

owing to (3.21). Now it follows from the expression for $d_{\infty}(u,]\!]-\infty,x]\!])$ that, for every $u\!\in[0,1]^{d}$ ,

	$\displaystyle 0\leq f_{x,\varepsilon}(u)-f_{x}(u)$	$\displaystyle=\bigg(1-\frac{d_{\infty}(u,]\!]-\infty,x]\!])}{\varepsilon}\bigg)^{+}\mbox{\bf 1}_{]\!]-\infty,x]\!]^{c}}(u)$
		$\displaystyle=\bigg(1-\frac{d_{\infty}(u,]\!]-\infty,x]\!])}{\varepsilon}\bigg)\mbox{\bf 1}_{[\![x,x+\varepsilon\mathbf{1}]\!]^{c}}(u)$
		$\displaystyle\leq\bigg(1-\frac{\max_{i=1,\ldots,d}(u^{i}-x^{i})}{\varepsilon}\bigg)\mbox{\bf 1}_{x^{i}\leq u^{i}\leq x^{i}+\varepsilon,i=1\ldots d}.$

Assume $r\!\in(1,+\infty)$ . It follows from Hölder inequality that

\int(f_{x,\varepsilon}-f_{x})d\nu\leq\bigg(\int_{\prod_{i}[x^{i},x^{i}+\varepsilon]}\bigg[\Big(1-\frac{\max_{i=1,\ldots,d}(u^{i}-x^{i})}{\varepsilon}\Big)\bigg]^{r}du\bigg)^{\frac{1}{r}}\big\|g\big\|_{{\cal L}^{\frac{r}{r-1}}(\lambda_{d})}.

(3.24)

Now

	$\displaystyle\int_{[0,1]^{d}\cap\prod_{i}[x^{i},x^{i}+\varepsilon]}\bigg[\Big(1-\frac{\max_{i=1,\ldots,d}(u^{i}-x^{i})}{\varepsilon}\Big)\bigg]^{r}du$	$\displaystyle\leq\int_{\prod_{i}[x^{i},x^{i}+\varepsilon]}\bigg[\Big(1-\frac{\max_{i=1,\ldots,d}(u^{i}-x^{i})}{\varepsilon}\Big)\bigg]^{r}du$
		$\displaystyle=\varepsilon^{d}\int_{[0,1]^{d}}\bigg[\Big(1-\max_{i=1,\ldots,d}v^{i}\Big)\bigg]^{r}dv$
		$\displaystyle=\varepsilon^{d}\int_{[0,1]^{d}}(\min_{i=1,\ldots,d}w^{i})^{r}dw$
		$\displaystyle=\varepsilon^{d}d!\int_{0<w^{1}<\cdots<w^{d}<1}(w^{1})^{r}dw$
		$\displaystyle=\varepsilon^{d}d!\frac{r!}{(r+d)!}=\varepsilon^{d}\begin{pmatrix}d+r\\ r\end{pmatrix}^{-1}.$

Inserting this in (3.24) and then in (3.23) yields

\mu(]\!]-\infty,x]\!])-\nu(]\!]-\infty,x]\!])\leq\frac{1}{\varepsilon}{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)+\varepsilon^{\frac{d}{r}}\begin{pmatrix}d+r\\ r\end{pmatrix}^{-\frac{1}{r}}\big\|g\big\|_{{\cal L}^{\frac{r}{r-1}}(\lambda_{d})}.

one shows likewise using $\tilde{f}_{x,\varepsilon}$ that $\nu(]\!]-\infty,x]\!])-\mu(]\!]-\infty,x]\!])$ satisfies the same inequality since $\tilde{f}_{x,\varepsilon}-f_{x}\leq 0$ . Consequently, for every $\varepsilon>0$ ,

D^{\star}(\mu,\nu)\leq\frac{1}{\varepsilon}{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)+\varepsilon^{\frac{d}{r}}C_{r,d}\big\|g\big\|_{{\cal L}^{\frac{r}{r-1}}(\lambda_{d})}.

with $C_{r,d}=\begin{pmatrix}d+r\\ r\end{pmatrix}^{-\frac{1}{r}}$ . One concludes by setting $\displaystyle\varepsilon=\Big(\frac{{\cal W}^{\ell^{\infty}}_{1}(\mu,\nu)}{\|g\|_{{\cal L}^{\frac{r}{r-1}}(\lambda_{d})}}\frac{r}{dC_{r,d}}\Big)^{\frac{r}{d+r}}$ at which the above function of $\varepsilon$ attains its minimum. The case $r=1$ follows likewise. ∎

Remarks. $\bullet$ Assume $d\geq 2$ . Based on (3.17) and (3.22) with $\nu=g\cdot\lambda_{d}$ , with $g\!\in{\cal L}^{\frac{r}{r-1}}(\lambda_{d})$ for some $r\geq 1$ , one easily deduces that for $q>\frac{d}{d-1}$ and every $\varepsilon>0$ small enough

\Big(M_{\frac{\mu+\nu}{2}}(q)\vee 1\Big)^{-1}{\cal W}_{1}(\mu,\nu)\preceq D^{\star}(\mu,\nu)^{\frac{1}{d}}\preceq\big\|g\big\|^{\frac{r}{d(r+d)}}_{{\cal L}^{\frac{r}{r-1}}(\lambda_{d})}{\cal W}_{1}(\mu,\nu)^{\frac{1}{r+d}},

where $\preceq$ stands for “lower up to a constant” (possibly depending on $r$ , $q$ , $d$ ). This suggests that this upper-bound is not sharp, having in mind that if $\mu_{n}=\frac{1}{n}\sum_{k=1}^{n}\delta_{\frac{2k-1}{2n}}$ and $\nu={\cal U}([0,1])$ , then, for every $n\geq 1$ ,

{\cal W}_{1}(\mu_{n},\nu)=D^{\star}(\mu_{n},\nu)=\frac{1}{2n}.

$\bullet$ In [GL23], a similar upper bound is established for more general “smooth Wasserstein” distances $d_{m}$ defined by $d_{m}(\mu,\nu)=\sup_{f\in{\cal H}_{m}}|\mu(f)-\nu(f)|$ where ${\cal H}_{m}$ is the space of $m-1$ differentiable functions with $1$ -Lipschitz partial derivatives or order $m-1$ in the case where the distribution has a bounded density. The above appears as an extension of the setting $m=r=1$ to $m=1$ and $r\!\in[1,+\infty)$ .

Fundings. The first author benefited for this research of the support of the “Chaire Risques Financiers”, Fondation du Risque. The second author thanks the Henri Lebesgue Center (ANR-11-LABX-0020-01) and the ANR project RAWABRANCH (ANR-23-CE40-0008).

References

[BL94] Nicolas Bouleau and Dominique Lépingle. Numerical methods for stochastic processes. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Inc., New York, 1994. A Wiley-Interscience Publication.
[Chu49] Kai-Lai Chung. An estimate concerning the Kolmogoroff limit distribution. Trans. Amer. Math. Soc., 67:36–50, 1949.
[DSS13] Steffen Dereich, Michael Scheutzow, and Reik Schottstedt. Constructive quantization: approximation by empirical measures. Ann. Inst. Henri Poincaré Probab. Stat., 49(4):1183–1203, 2013.
[FG15] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Relat. Fields, 162(3-4):707–738, 2015.
[GL23] Robert E. Gaunt and Siqi Li. Bounding kolmogorov distances through wasserstein and related integral probability metrics. Journal of Mathematical Analysis and Applications, 522(1):126985, 2023.
[Kie61] Jack C. Kiefer. On large deviations of the empiric D. F. of vector chance variables and a law of the iterated logarithm. Pacific J. Math., 11:649–660, 1961.
[KN74] Lauwerens Kuipers and Harald Niederreiter. Uniform distribution of sequences. Pure and Applied Mathematics. Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974.
[LP23] Harald Luschgy and Gilles Pagès. Marginal and functional quantization of stochastic processes, volume 105 of Probability Theory and Stochastic Modelling. Springer, Cham, 2023.
[LR21] E. L. Lehmann and Joseph P. Romano. Testing statistical hypotheses. Springer Texts in Statistics. Springer, Cham, fourth edition, [2021] ©2021.
[Nie92] Harald Niederreiter. Random number generation and quasi-Monte Carlo methods, volume 63 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992.
[Pag26] Gilles Pagès. Numerical probability. An introduction with applications to finance. Universitext. Cham: Springer, 2nd edition edition, 2026.
[Pro88] Petko D. Proïnov. Discrepancy and integration of continuous functions. J. Approx. Theory, 52(2):121–131, 1988.
[Vil03] Cédric Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003.
[Vil09] Cédric Villani. Optimal transport, volume 338 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 2009. Old and new.

Appendix A Proof of Lemma 2.1.

$(a)$ Let $x$ , $y\!\in[0,1]^{d}$ , $x\preceq y$ and let $x_{n}\to x$ such that $x^{i}<x^{i}_{n}$ and $x^{i}_{n}\downarrow x^{i}$ for every $i=1,\ldots,d$ such that $x^{i}<1$ (if $x^{i}=1$ for some $i$ then $y^{i}=1$ so that $\mu(]\!]x,y]\!])=\nu(]\!]x,y]\!])=0$ ). We set $\tilde{x}^{i}_{n}=x^{i}_{n}\wedge y^{i}$ . It is clear that $[\![\tilde{x}_{n},y]\!]\uparrow\,]\!]x,y]\!]$ for the inclusion so that $\mu\big([\![\tilde{x}_{n},y]\!]\big)\uparrow\mu(]\!]x,y]\!])$ . Idem for $\nu$ . Hence

|\mu(]\!]x,y]\!])-\nu(]\!]x,y]\!])|=\lim_{n}|\mu([\![\tilde{x}_{n},y]\!])-\nu([\![\tilde{x}_{n},y]\!])|\leq D^{\infty}(\mu,\nu)

from which we derive the announced statement.

$(b)$ Let $x$ , $y\!\in[0,1]^{d}$ , $x\preceq y$ and let $x_{n}\to x$ so that $x^{i}_{n}<x^{i}$ and $x^{i}_{n}\uparrow x^{i}$ for every, $i=1,\ldots,d$ such that $x^{i}\neq 0$ and $x_{n}^{i}=0$ if $x^{i}=0$ . Then

]\!]x_{n},y]\!]\,\downarrow\,K_{x,y}\mbox{ such that }K_{x,y}\cap(0,1]^{d}=[\![x,y]\!]\cap(0,1]^{d}.

Then $\mu\big(]\!]x_{n},y]\!]\big)\downarrow\mu(K_{x,y})=\mu\big(K_{x,y}\cap(0,1]^{d}\big)=\mu\big([\![x,y]\!]\big)$ . The same for $\nu$ . Consequently

|\mu([\![x,y]\!])-\nu([\![x,y]\!])|=\lim_{n}|\mu(]\!]x_{n},y]\!])-\nu(]\!]x_{n},y]\!])|\leq\sup_{x,\,y\in[0,1]^{d}}\big|\mu\big(]\!]x,y]\!]\big)-\nu\big(]\!]x,y]\!]\big)\big|.

Combined with Claim $(a)$ this completes the proof.

(c) With the notations of $(b)$ , one checks that the sequence $(]\![x_{n},y]\!])_{n}$ decreases to $[\![x,y]\!]$ so that, with the same monotone convergence argument as in $(b)$ , one obtains that

D^{\infty}(\mu,\nu)\leq\sup_{x,\,y\in[0,1]^{d},x\preceq y}\big|\mu\big(]\![x,y]\!]\big)-\nu\big(]\![x,y]\!]\big)\big|,

For the reverse inequality, we adapt $(a)$ by assuming that $x_{n}^{i}=0$ when $x^{i}=0$ . In this case, the sequence $[\![\tilde{x}_{n},y]\!]\uparrow\,]\![x,y]\!]$ and the sequel is identical to $(a)$ . $\Box$

Kolmogorov-Smirnov distance and discrepancies versus Wasserstein distances

Abstract

1 Introduction

2 Discrepancies for [0,1]d[0,1]^{d}-supported distributions

2.1 Definitions, notation and a technical lemma

Lemma 2.1.

2.2 Bounding Wasserstein distances by the uniform discrepancy

Proposition 2.2 (Existing upper-bound and a variant).

Proof.

Theorem 2.3 (Bounding Wasserstein distance by the uniform discrepancy).

Proof.

Proposition 2.4 (One dimensional setting for 𝒲1{\cal W}_{1}).

Proof.

Corollary 2.5.

2.3 A refinement when p=1p=1 and d>1d>1

Theorem 2.6.

Remark 2.1.

Proof.

2.4 Connections with QMC & MC methods

Proposition 2.7 (Proïnov Theorem (1984)).

Remark 2.2.

2.5 Bounding the star discrepancy by the L1L^{1}-Wasserstein distance

3 Kolmogorov-Smirnov distance vs pp-Wasserstein distance on 𝒫p​(ℝd){\cal P}_{p}({\mathbb{R}}^{d})

3.1 Bounding the pp-Wasserstein distance by the KK–SS distance

Definition 3.1.

Proposition 3.1.

Theorem 3.2.

Lemma 3.3.

Proof.

3.2 Bounding the KK–SS-distance by the L1L^{1}-Wasserstein distance

Theorem 3.4 (Bounding star discrepancy discrepancy by L1L^{1}-Wasserstein distance).

Proof.

References

Appendix A Proof of Lemma 2.1.

2 Discrepancies for $[0,1]^{d}$ -supported distributions

Proposition 2.4 (One dimensional setting for ${\cal W}_{1}$ ).

2.3 A refinement when $p=1$ and $d>1$

2.5 Bounding the star discrepancy by the $L^{1}$ -Wasserstein distance

3 Kolmogorov-Smirnov distance vs $p$ -Wasserstein distance on ${\cal P}_{p}({\mathbb{R}}^{d})$

3.1 Bounding the $p$ -Wasserstein distance by the $K$ – $S$ distance

3.2 Bounding the $K$ – $S$ -distance by the $L^{1}$ -Wasserstein distance

Theorem 3.4 (Bounding star discrepancy discrepancy by $L^{1}$ -Wasserstein distance).