38  Integral Probablity Metrics

Author

Affiliation

Aditya Mahajan

McGill University

Keywords

IPM

[TODO: Add introduction]

38.1 Definition of Integral Probability Metrics

Notation

1. Let $(\mathcal{X},d)$ be a complete separable metric space, i.e., a Polish space.

2. Let $w:\mathcal{X}\to [1,\infty )$ be a measurable function and define the weighted norm of any function $f:\mathcal{X}\to \mathbb{R}$ as $${\Vert \phantom{(}f\Vert }_w=\underset{x\in \mathcal{X}}{sup}\frac{f(x)}{w(x)}.$$

3. Let $\mathcal{M}(\mathcal{X})$ denote the set of all measurable real-valued functions on $\mathcal{X}$ and let ${\mathcal{M}}_w(\mathcal{X})$ denote the subset with bounded $w$-norm, i.e., $${\mathcal{M}}_w(\mathcal{X})=\{f\in \mathcal{M}(\mathcal{X}):{\Vert \phantom{(}f\Vert }_w<\infty \}$$

4. Let $\mathfrak{X}$ denote the Borel $\sigma$-algebra of $\mathcal{X}$.

5. Let $\mathcal{P}(\mathcal{X})$ denote the set of all probaility measures on $(\mathcal{X},\mathfrak{X})$ and ${\mathcal{P}}_w(\mathcal{X})=\{\mu \in \mathcal{P}(\mathcal{X}):\int wd\mu <\infty \}$.

$$ Integral probability metrics (IPMs) are pseudo-metrics on ${\mathcal{P}}_w(\mathcal{X})$ defined as follows.

Definition 38.1 The integral probability metric $d_{\mathfrak{F}}$ is a pseudo-metric on ${\mathcal{P}}_w(\mathcal{X})$ generated by the function class $\mathfrak{F}\subset {\mathcal{M}}_w(\mathcal{X})$ is defined as $$d_{\mathfrak{F}}({\mu }_1,{\mu }_2)=\underset{f\in \mathfrak{F}}{sup}|\int fd{\mu }_1-\int fd{\mu }_2|,\mathrm{\forall }{\mu }_1,{\mu }_2\in {\mathcal{P}}_w(\mathcal{X}).$$ The function $f$ is called the witness function and the function class $\mathfrak{F}$ is called the generator.

An IPM is a pseudo-metric, i.e., it satisfies the following properties: for all ${\mu }_1,{\mu }_2,{\mu }_3\in {\mathcal{P}}_w(\mathcal{X})$

1. $d_{\mathfrak{F}}({\mu }_1,{\mu }_1)=0$
2. Symmetry. $d_{\mathfrak{F}}({\mu }_1,{\mu }_2)=d_{\mathfrak{F}}({\mu }_2,{\mu }_1)$
3. Triangle inequality. $d_{\mathfrak{F}}({\mu }_1,{\mu }_3)\le d_{\mathfrak{F}}({\mu }_1,{\mu }_2)+d_{\mathfrak{F}}({\mu }_2,{\mu }_3)$.

IPM is a metric when $d({\mu }_1,{\mu }_2)=0⟹{\mu }_1={\mu }_2$.

Examples

1. The Kolmogorov-Smirnov metric. The Kolmogorov-Smirnov metric on $\mathbb{R}$ is defined as $$\text{KS}(\mu ,\nu )=\underset{t\in \mathbb{R}}{sup}|\phantom{(}M(t)-N(t)|$$ where $M$ and $N$ are CDFs corresponding to $\mu$ and $\nu$, respectively. It has the following properties:

   • $\text{KS}(\mu ,\nu )\in [0,1]$
   • $\text{KS}(\mu ,\nu )=0$ iff $\mu =\nu$
   • $\text{KS}(\mu ,\nu )=1$ iff the two distributions have disjoint support, i.e., there exists a $s\in \mathbb{R}$ such that $\mu ((-\infty ,s])=1$ and $\nu ((-\infty ,s])=0$
   • $\text{KS}$ is a metric

   The Kolmogorov-Smirnov metric is an IPM with $\mathfrak{F}=\{{\mathbb{1}}_{[t,\infty )}:t\in \mathbb{R}\}$.

2. Total variation metric Let $(\mathcal{S},\mathfrak{S})$ be a probability space. The total variation metric between two probability measures $\mu$ and $\nu$ on $(\mathcal{S},\mathfrak{S})$ is defined as $$\text{TV}(\mu ,\nu )=\underset{B\in \mathfrak{S}}{sup}|\phantom{(}\mu (B)-\nu (B)|.$$ It has the following properties:

   • $\text{TV}(\mu ,\nu )\in [0,1]$
   • $\text{TV}(\mu ,\nu )=0$ iff $\mu =\nu$
   • $\text{TV}(\mu ,\nu )=1$ iff there exists an event $B\in \mathfrak{S}$ such that $\mu (B)=1$ and $\mu (B)=0$.
   • $\text{TV}$ is a metric

   When $\mathcal{S}={\mathbb{R}}^k$ the measures $\mu$ and $\nu$ have densities $f$ and $g$ with respect to a measure $\lambda$, then

   • $\text{TV}(\mu ,\nu )=\frac{1}{2}\int |\phantom{(}f(x)-g(x)|\lambda (dx)$.
   • $\text{TV}(\mu ,\nu )=1-\int min\{f(x),g(x)\}\lambda (dx)$.
   • $\text{TV}(\mu ,\nu )=\mu (B)-\nu (B)$, where $B=\{x:f(x)\ge g(x)\}$.

   One may view the total variation metric as the total variation norm of the signed measure $\mu -\nu$. An implication of the first property is that total variation can be expressed as an IPM with the generator $$\mathfrak{F}=\{f:{\Vert \phantom{(}f\Vert }_{\infty }\le 1\}.$$

   See Adell and Jodrá (2006) for exact TV distance between some common distributions.

3. Kantorovich-Rubinstein metric or Wasserstein distance. Let $(\mathcal{S},\mathfrak{S})$ be a probability space and $d_{\mathcal{S}}$ be a metric on $\mathcal{S}$. Let $p\in [1,+\mathrm{\infty }]$. Then the Wasserstein $p$-distance between two measures $\mu$ and $\nu$ on $(\mathcal{S},\mathfrak{S})$ is defined as $${\text{Was}}_p(\mu ,\nu )={(\underset{\gamma \in \mathrm{\Gamma }(\mu ,\nu )}{inf}{\int }_{\mathcal{S}\times \mathcal{S}}{d}_{\mathcal{S}}(x,y)d\gamma (x,y))}^{1/p}$$ where $\mathrm{\Gamma }(\mu ,\nu )$ are all couplings (i.e., joint measures on $(\mathcal{S}\times \mathcal{S},\mathfrak{S}\otimes \mathfrak{S})$ with marginals $\mu$ and $\nu$. An compact way to write this is $${\text{Was}}_p(\mu ,\nu )={(\underset{\gamma \in \mathrm{\Gamma }(\mu ,\nu )}{inf}{\mathbb{E}}_{(X,Y)\sim \gamma }[d_{\mathcal{S}}(X,Y{)}^p])}^{1/p}$$

   In this section, we focus on ${\text{Was}}_1$ distance (i.e., $p=1$), and will drop the subscript $1$ for convenience and write $$\text{Was}(\mu ,\nu )=\underset{\gamma \in \mathrm{\Gamma }(\mu ,\nu )}{inf}{\mathbb{E}}_{(X,Y)\sim \gamma }[d_{\mathcal{S}}(X,Y)].$$

   Theorem 38.1 (Kantorovich Rubinstein duality) The Wasserstein distance is equivalent to the following: $$\text{Was}(\mu ,\nu )=\underset{f:\parallel f{\parallel }_L\le 1}{sup}|{\mathbb{E}}_{X\sim \mu }[f(X)]-{\mathbb{E}}_{Y\sim \nu }[f(Y)]|$$

   Proof

   The orignal definition is an (infinite dimensional) linear program: ${\mathbb{E}}_{(X,Y)\sim \gamma }[d_{\mathcal{S}}(X,Y)]$ is a linear function of $\gamma$ and the of all couplings $\mathrm{\Gamma }(\mu ,\nu )$ is a convex polytope. Taking its dual, we get $$\text{Was}(\mu ,\nu )=\underset{f,g:\mathcal{S}\to \mathbb{R}}{sup}[{\mathbb{E}}_{X\sim \mu }[f(X)]+{\mathbb{E}}_{Y\sim \nu }[g(Y)]]\text{such that}f(x)+g(y)\le d(x,y).$$

   Similar in spirit to Legendre transform define the $d_{\mathcal{S}}$-dual of the function $g$ as $$g^{\ast }(x)=\underset{u\in \mathcal{S}}{inf}[d(x,u)-g(u)]$$ Observe that for any $u$ $$g^{\ast }(x)\le d(x,u)-g(u)\le d(x,y)+d(y,u)-g(u).$$ Therefore, $$g^{\ast }(x)\le d(x,y)+\underset{u\in \mathcal{S}}{min}[d(y,u)-g(u)]=d(x,y)+g^{\ast }(y).$$ Thus, $g^{\ast }(x)-g^{\ast }(y)\le d_{\mathcal{S}}(x,y)$. Interchanging the role of $x$ and $y$, we get $$|g^{\ast }(x)-g^{\ast }(y)|\le d_{\mathcal{S}}(x,y).$$ Thus, $\parallel g^{\ast }{\parallel }_L\le 1$.

   Now consider any $f$ and $g$ that satisfies the constraint $f(x)+g(y)\le d(x,y)$ for all $x,y$. For any $x$, let $u^{\ast }$ be the value of $u$ that achieves the minimum in the definition of $g^{\ast }(x)$, i.e., $$g^{\ast }(x)=d(x,u^{\ast })-g(u^{\ast })\ge f(x).$$ Moreover, $$g^{\ast }(x)\le d(x,x)-g(x)=-g(x).$$ Thus, for any $f$ and $g$ that satisfy the constraint, we have $$\begin{array}{rl}\text{Was}(\mu ,\nu )& =\underset{f,g:f(x)+g(y)\le d_{\mathcal{S}}(x,y)}{sup}[{\mathbb{E}}_{X\sim \mu }[f(X)]+{\mathbb{E}}_{Y\sim \nu }[g(Y)]]\\ & \le \underset{g^{\ast }}{sup}[{\mathbb{E}}_{X\sim \mu }[g^{\ast }(X)]-{\mathbb{E}}_{Y\sim \nu }[g^{\ast }(Y)]]\\ \text{(1)}& & \le \underset{f:\parallel f{\parallel }_L\le 1}{sup}[{\mathbb{E}}_{X\sim \mu }[f(X)]-{\mathbb{E}}_{Y\sim \nu }[f(Y)]]\end{array}$$ where the last inequality follows because we have shown that $\parallel g^{\ast }{\parallel }_L\le 1$.

   Now observe that for any $f$ such that $\parallel f{\parallel }_L\le 1$, we have $f(x)-f(y)\le d(x,y)$. Hence, for any coupling $\gamma \in \mathrm{\Gamma }(\mu ,\nu )$, we have $${\mathbb{E}}_{(X,Y)\sim \gamma }[d(X,Y)]\ge {\mathbb{E}}_{(X,Y)\sim \gamma }[f(X)-f(Y)]={\mathbb{E}}_{X\sim \mu }[f(X)]-{\mathbb{E}}_{Y\sim \nu }[f(Y)].$$ Thus, for any function $f$ such that $\parallel f{\parallel }_L\le 1$, we have $${\mathbb{E}}_{X\sim \mu }[f(X)]-{\mathbb{E}}_{Y\sim \nu }[f(Y)]\le \underset{\gamma \in \mathrm{\Gamma }(\mu ,\nu )}{inf}{\mathbb{E}}_{(X,Y)\sim \gamma }[d(X,Y)]=\text{Was}(\mu ,\nu ).$$ Consequently, $$\begin{array}{}\text{(2)}& \underset{f:\parallel f{\parallel }_L\le 1}{sup}[{\mathbb{E}}_{X\sim \mu }[f(X)]-{\mathbb{E}}_{Y\sim \nu }[f(Y)]]\le \text{Was}(\mu ,\nu ).\end{array}$$

   The result then follows from $\text{(1)}$ and $\text{(2)}$.

   Remark about absolute value

   Note that in the proof, we have shown that $$\text{Was}(\mu ,\nu )=\underset{f:\parallel f{\parallel }_L\le 1}{sup}{\mathbb{E}}_{X\sim \mu }[f(X)]-{\mathbb{E}}_{Y\sim \nu }[f(Y)]$$ but in Theorem 38.1, we use absolute value in the right hand side. This is because (using a slightly terse notation) $$|\int fd\mu -\int fd\nu |\text{ is either}\int fd\mu -\int fd\nu \text{ or }\int (-f)d\mu -\int (-f)d\nu$$ and both $f$ and $-f$ have the same Lipschitz constant. So $$\underset{f:\parallel f{\parallel }_L\le 1}{sup}[\int fd\mu -\int fd\nu ]=\underset{f:\parallel f{\parallel }_L\le 1}{sup}|\int fd\mu -\int fd\nu |$$

   Theorem 38.1 implies that Wasserstein distance can be expressed as an IPM with the generator $$\mathfrak{F}=\{f:\parallel f{\parallel }_L\le 1\}.$$

4. Maximum-mean discrepency.

   TBW

5. Weighted total variation.

   TBW

38.2 Maximal generators

So far, we haven’t imposed any restriction on the generator $\mathfrak{F}$. We now present a canonical representation of a generator.

Definition 38.2 For a function class $\mathfrak{F}\in {\mathcal{M}}_w(\mathcal{X})$, define the maximal generator ${\mathcal{G}}_{\mathfrak{F}}$ as $${\mathcal{G}}_{\mathfrak{F}}=\{f\in {\mathcal{M}}_w(\mathcal{X}):|\int fd{\mu }_1-\int fd{\mu }_2|\le d_{\mathfrak{F}}({\mu }_1,{\mu }_2),\text{for all }{\mu }_1,{\mu }_2\in {\mathcal{P}}_w(\mathcal{X})\}.$$

Maximal generators have the following properties.

Proposition 38.1 Let $\mathfrak{F}\subset {\mathcal{M}}_w(\mathcal{X})$ be an arbitary generator. Then:

1. ${\mathcal{G}}_{\mathfrak{F}}$ contains the convex hull of $\mathfrak{F}$.
2. If $f\in {\mathcal{G}}_{\mathfrak{F}}$, then $\alpha f+\beta \in {\mathcal{G}}_{\mathfrak{F}}$ for all $|\alpha |\le 1$ and $\beta \in \mathbb{R}$.
3. If the sequence $\{f_n{\}}_{n\ge 1}\in {\mathcal{G}}_{\mathfrak{F}}$ converges uniformly to $f$, then $f\in {\mathcal{G}}_{\mathfrak{F}}$.

Maximal generators also allow us to compare IPMs with different generators.

Balanced set

A set $\mathcal{S}$ is said to be balanced if for all scalars $a$ satisfying $|a|\le 1$, we have $a\mathcal{S}\subset \mathcal{S}$.

Proposition 38.2 Let $\mathfrak{F}\subset \mathfrak{D}\subset {\mathcal{M}}_w(\mathcal{X})$ and ${\mu }_1,{\mu }_2\in {\mathcal{P}}_w(\mathcal{X})$. Then

1. $d_{\mathfrak{F}}({\mu }_1,{\mu }_2)\le d_{\mathfrak{D}}({\mu }_1,{\mu }_2)$.
2. ${\mathcal{G}}_{\mathfrak{F}}\subset {\mathcal{G}}_{\mathfrak{D}}$.
3. If $\mathfrak{D}\subset {\mathcal{G}}_{\mathfrak{F}}$ then $d_{\mathfrak{F}}$ and $d_{\mathfrak{D}}$ are identical.
4. If $\mathfrak{F}\subset \mathfrak{D}\subset {\mathcal{G}}_{\mathfrak{F}}$ and $\mathfrak{D}$ is convex and balanced, contains the constant functions, and is closed with respect to pointwise convergence, then $\mathfrak{D}={\mathcal{G}}_{\mathfrak{F}}$.

Examples

1. Kolmogorov-Smirnov metric. The maximal generator of Kolmogorov-Smirnov metric is $${\mathcal{G}}_{\mathfrak{F}}=\{f:V(f)\le 1\}$$ where $V(f)$ denotes the variation of function $f$, which is defined as $$V(f)=\underset{P}{sup}\sum _{k=1}^n|\phantom{(}f(x_k)-f(x_{k-1})|.$$ where the suprimum is over all partitions $P=\{x_0,\dots ,x_n\}$ of $\mathbb{R}$.

2. Total-variation metric. The maximal generator of total-variation metric is $${\mathcal{G}}_{\mathfrak{F}}=\{f:\frac{1}{2}\mathrm{sp}(f)\le 1\}$$

3. Kantorovich-Rubinstein metric or Wasserstein distance.

   The generator of Wasserstein distance given above is actually a maximal generator. Thus, $${\mathcal{G}}_{\mathfrak{F}}=\{f:\parallel f{\parallel }_L\le 1\}$$

4. Maximum-mean discrepency.

5. Weighted total variation.

38.3 Minkowski functional or gauge of an IPM

We will assume that the generator $\mathfrak{F}$ is the maximal generator. In particular, this means that $0\in \mathfrak{F}$ is an interior point. Define $(0,\infty )\mathfrak{F}:={\cup }_{0<r<\infty }r\mathfrak{F}$, which is a subset of ${\mathcal{M}}_w(\mathcal{X})$.

For any function $f\in {\mathcal{M}}_w(\mathcal{X})$ define the Minkowski functional (or gauge) as follows: $${\rho }_{\mathfrak{F}}(f)=inf\{\rho >0:f/\rho \in \mathfrak{F}\}.$$ where the infimum of an empty set is defined as infinity. Therefore, ${\rho }_{\mathfrak{F}}(f)<\infty$ if $f\in (0,\infty )\mathfrak{F}$; otherwise ${\rho }_{\mathfrak{F}}(f)=\infty$.

In all the above examples, the Minkowski functional is a semi-norm, which is a general property.

Proposition 38.3 The Minkowski functional is a semi-norm, i.e., it satisfies the following properties:

1. Non-negativity. $\rho (f)\ge 0$.
2. Absolute homogeneity ${\rho }_{\mathfrak{F}}(af)=|a|{\rho }_{\mathfrak{F}}(f)$ for all scalars $a$.
3. Subadditivity. ${\rho }_{\mathfrak{F}}(f_1+f_2)\le {\rho }_{\mathfrak{F}}(f_1)+{\rho }_{\mathfrak{F}}(f_2)$.

Proof

Non-negativity holds by definition. Absolute homogeneity holds because $\mathfrak{F}$ is balanced, in particular $\mathfrak{F}=-\mathfrak{F}$. Note that absolute homogeneity implies ${\rho }_{\mathfrak{F}}(0)=0$.

To see why subadditivity holds, let ${\rho }_1={\rho }_{\mathfrak{F}}(f_1)$ and ${\rho }_2={\rho }_{\mathfrak{F}}(f_2)$. Then, since $\mathfrak{F}$ is convex, we have for any $\lambda \in [0,1]$, $$\lambda \frac{f_1}{{\rho }_1}+(1-\lambda )\frac{f_2}{{\rho }_2}\in \mathfrak{F}.$$ Take $\lambda ={\rho }_1/({\rho }_1+{\rho }_2)$, which implies $(f_1+f_2)/({\rho }_1+{\rho }_2)\in \mathfrak{F}$. Thus, ${\rho }_{\mathfrak{F}}(f_1+f_2)\le {\rho }_1+{\rho }_2$.

Proposition 38.4 For any $f\in (0,\infty )\mathfrak{F}$ such that ${\rho }_{\mathfrak{F}}(f)\ne 0$ and any ${\mu }_1,{\mu }_2\in {\mathcal{P}}_w(\mathcal{X})$, we have $$|\int fd{\mu }_1-\int fd{\mu }_2|\le {\rho }_{\mathfrak{F}}(f)d_{\mathfrak{F}}({\mu }_1,{\mu }_2).$$

Proof

By the assumptions imposed on $f$, we know that ${\rho }_{\mathfrak{F}}(\rho )\in (0,\infty )$. Define $f^{\prime }=f/{\rho }_{\mathfrak{F}}(f)\in \mathfrak{F}$. Then, $$|\int fd{\mu }_1-\int fd{\mu }_2|={\rho }_{\mathfrak{F}}(f)|\int f^{\prime }d{\mu }_1-\int f^{\prime }d{\mu }_2|\le {\rho }_{\mathfrak{F}}(f)d_{\mathfrak{F}}({\mu }_1,{\mu }_2)$$ where the last inequality uses the fact that $f^{\prime }\in \mathfrak{F}$.

Why care about maximal generators

Proposition 38.2 implies that the maximal generator of $\mathfrak{F}$ is the smallest superset of $\mathfrak{F}$ that is convex and balanced, contains the constant functions, and is closed with respect to pointwise convergence. The IPM distance wrt a generator and its maximal generator are the same but the Minkowski functionals are not! In particular if $\mathfrak{F}\subset \mathfrak{D}$, then ${\rho }_{\mathfrak{F}}(f)\ge {\rho }_{\mathfrak{D}}(f)$. So, working with the maximal generators gives us the tightest version of the bound in Proposition 38.4.

For example, we know that $\{f:{\Vert \phantom{(}f\Vert }_{\infty }\le 1\}$ is a generator for total-variation distance. Using this, the result of Proposition 38.4 implies that $$\begin{array}{}\text{(3)}& |\int fd{\mu }_1-\int fd{\mu }_2|\le {\Vert \phantom{(}f\Vert }_{\infty }\text{TV}({\mu }_1,{\mu }_2).\end{array}$$ Note that the left hand side is invariant to addition by a constant, but the right hand side is not. Therefore, this bound cannot be tight.

Now consider the maximal generator for total-variation distance is $\{f:\frac{1}{2}\mathrm{sp}f\le 1\}$. Using this, the result of Proposition 38.4 implies that $$\begin{array}{}\text{(4)}& |\int fd{\mu }_1-\int fd{\mu }_2|\le \frac{1}{2}\mathrm{sp}(f)\text{TV}({\mu }_1,{\mu }_2).\end{array}$$ In this case, the right hand side is invariant to additional by a constant. Moreover, ${\Vert \phantom{(}f\Vert }_{\infty }\le \frac{1}{2}\mathrm{sp}(f)$ (see Exercise 38.1). Therefore, the bound of $\text{(4)}$ is tighter than that of $\text{(3)}$.

Examples

1. Kolmogorov-Smirnov metric. The Minkowski functional of a function $f$ for Kolmogorov-Smirnov metric is its total variation $V(f)$. Thus, for any function with bounded total variation: $$|\int fd\mu -\int fd\nu |\le \text{KS}(\mu ,v)V(f).$$

2. Total variation metric. The Minkowski functional of a function $f$ for total variation metric is $\frac{1}{2}\mathrm{sp}(f)$. Thus, for any function with bounded span: $$|\int fd\mu -\int fd\nu |\le \text{TV}(\mu ,v)\frac{1}{2}\mathrm{sp}(f).$$

3. Kantorovich-Rubinstein metric or Wasserstein distance. The Minkowski functional of a function $f$ for Wasserstein distance is $\parallel f{\parallel }_L$. Thus, for any function with bounded Lipschitz constant, we have $$|\int fd\mu -\int fd\nu |\le \text{Was}(\mu ,v)\parallel f{\parallel }_L.$$

4. Maximum-mean discrepency.

5. Weighted total variation.

38.4 Properties of IPMs

Definition 38.3 Let $(\mathcal{S},d)$ be a metric vector space, $w:\mathcal{S}\to [1,\infty )$ a weight function, and $d_{\mathfrak{F}}$ any semi-metric on ${\mathcal{P}}_w$. Then, $d_{\mathfrak{F}}$ is said to have

• Property (R) if $d_{\mathfrak{F}}({\delta }_a,{\delta }_b)=d(a,b)$.
• Property (M) if $d_{\mathfrak{F}}(aX,aY)=a{d}_{\mathfrak{F}}(X,Y)$.
• Property (C) if $d_{\mathfrak{F}}(P_1\ast Q,P_2\ast Q)\le d_{\mathfrak{F}}(P_1,P_2)$ for all probability measures $Q$.

The next result is from Müller (1997), Theorem~4.7.

Suppose $d_{\mathfrak{F}}$ is an IPM with a maximal generator ${\mathcal{G}}_{\mathfrak{F}}$. Then

1. Property (R) holds if and only if $$\underset{f\in \mathcal{F}}{sup}\frac{|\phantom{(}f(x)-f(y)|}{d(x,y)}=1,\text{for all }x,y\in \mathcal{S},x\ne y.$$
2. Property (C) holds if any only if ${\mathcal{G}}_{\mathfrak{F}}$ is invariant under translations.

Exercises

Exercise 38.1 Show that for any function $f$: $$\frac{1}{2}\mathrm{sp}(f)\le {\Vert \phantom{(}f\Vert }_{\infty }.$$

Hint: Suppose $f$ is such that $max(f)=-min(f)$, i.e., the function is centered at $0$. Then, the inequality holds with equality. What can you say when the function is not centered at $0$?

Exercise 38.2 (Convexity of IPMs) Show that IPM is convex, i.e., for any probability measures ${\mu }_1$, ${\mu }_2$, and $\nu$ and any constant $\lambda \in [0,1]$, we have $$d_{\mathfrak{F}}(\lambda {\mu }_1+(1-\lambda ){\mu }_2,\nu )\le \lambda d_{\mathfrak{F}}({\mu }_1,\nu )+(1-\lambda )d_{\mathfrak{F}}({\mu }_2,\nu ).$$

Hint: Use triangle inequality.

Notes

IPMs were first defined by Zolotarev (1984), where they were called probability metrics with $\zeta$-structure. They are studied in detail in Rachev (1991). The term IPM was coined by Müller (1997). The discussion here is mostly borrowed from Müller (1997).

Adell, J.A. and Jodrá, P. 2006. Exact kolmogorov and total variation distances between some familiar discrete distributions. Journal of Inequalities and Applications 2006, 1–8. DOI: 10.1155/jia/2006/64307.

Müller, A. 1997. Integral probability metrics and their generating classes of functions. Advances in Applied Probability 29, 2, 429–443. DOI: 10.2307/1428011.

Rachev, S.T. 1991. Probability metrics and the stability of stochastic models. Wiley, New York.

Zolotarev, V.M. 1984. Probability metrics. Theory of Probability & Its Applications 28, 2, 278–302. DOI: 10.1137/1128025.