# Dobrushin and Steif metrics are equal

J. Armstrong-Goodall and R.S.MacKay  Mathematics Institute, University of
Warwick, Coventry CV4 7AL, UK<EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
###### Abstract.

It is proved that two useful and apparently different metrics on the set of
Borel probabilities on countable products of Polish spaces of bounded
diameters are equal. This paves the way for advances in their computation.

##  1\. Introduction

It is well-known that standard metrics on spaces of multivariate probability
distributions with many or countably infinite number of variables are of
limited use. For example, Liggett [L] laments on p.70 that “total variation
convergence essentially never occurs for particle systems”. Examples of other
metrics that fail similarly are given in [M1, M2].

To rectify this, one of us [M1] introduced a metric on multivariate
probability distributions that does give convergence for many systems (the
examples treated there were weakly dependent probabilistic cellular automata,
but the same applies to particle systems). It was based on ingredients from
Dobrushin [D] (following [Va]), which give a type of weak convergence for such
systems, but it appears that Dobrushin did not take the final step of
metrising the weak topology (perhaps because it requires an assumption of
bounded diameters).

It turned out, however, that Steif had proposed a metric that achieves the
same goal many years before [S]. Its definition extends one of Ornstein [OW]
from the case of translation-invariant probabilities on $A^{\mathbb{Z}}$ for a
finite set $A$ to general Borel probabilities on $A^{\mathbb{Z}}$. [M1] had
dismissed extension of Ornstein’s metric but had missed Steif’s way of
achieving it.

Superficially, the two metrics look different. Yet in the Appendix to [M2] it
was shown that for finite spaces they are not only equivalent but equal. This
led to the conjecture that they are always equal.

Dobrushin metric was defined on any countable product of Polish (complete
separable metric) spaces with bounded diameters. Steif’s metric can easily be
generalised to the same context. In this paper it is proved that they are
equal.

This result is significant because they are useful for proving and quantifying
convergence of interacting particle systems and parameter-dependence of the
stationary probabilities. Their computation for explicit multivariate
probabilities, however, is not easy (though see [DM] for some successes). It
is helpful to have two alternative formulations of the same metric.

Before closing the introduction, a comment is appropriate on [FH]. It extends
the weak convergence proof of [Va] to allow a global component of interaction.
In our opinion, this is, however, already covered by the results of [Va, D],
because the dependency matrix of [Va, D] gains a contribution $\varepsilon/N$
in each of the $N$ components, which still sums to only $\varepsilon$.
Furthermore, the metric of [FH] requires an artificial enumeration and
weighting of the components, and they use the oscillation of a function rather
than its Lipschitz constant.

##  2\. Statement of result

Let $S$ be a countable set. For each $s\in S$, let $(X_{s},d_{s})$ be a Polish
(complete separable metric) space. Suppose $\sup_{s\in
S}\mbox{diam}(X_{s})<\infty$. Let $X=\prod_{s\in S}X_{s}$ with product
topology. Let $\mathcal{P}$ be the set of Borel probabilities on $X$. For
$\mu\in\mathcal{P}$ (or a signed Borel measure) and measurable
$f:X\to\mathbb{R}$, denote the integral of $f$ with respect to $\mu$ by
$\mu(f)$. For $x\in X$ denote the component in $X_{s}$ by $x_{s}$. Extend
$d_{s}:X_{s}\times X_{s}\to\mathbb{R}$ to a semi-metric $d_{s}:X\times
X\to\mathbb{R}$ (denoted by the same symbol) defined by
$d_{s}(x,y)=d_{s}(x_{s},y_{s})$ for all $x,y\in X$.

For $f:X\to\mathbb{R}$ and $s\in S$ define the partial Lipschitz constant

$\Delta_{s}(f)=\sup\frac{f(x)-f(y)}{d_{s}(x,y)}$

over pairs $x\neq y\in X$ agreeing off $s$. Let the Dobrushin semi-norm

$\|f\|=\sum_{s}\Delta_{s}(f)\in\mathbb{R}_{+}\cup\\{\infty\\}.$

Let the Dobrushin smooth functions $\mathcal{F}$ be the set of
$f:X\to\mathbb{R}$ with $\|f\|<\infty$, and $\mathcal{C}$ be the constant
functions $X\to\mathbb{R}$. From these ingredients, [M1] made the following
Definition: The Dobrushin distance between $\mu$ and $\nu\in\mathcal{P}$ is

(1)
$D(\mu,\nu)=\sup_{f\in\mathcal{F}\setminus\mathcal{C}}\frac{\mu(f)-\nu(f)}{\|f\|}.$

For $\mu,\nu\in\mathcal{P}$ let $M$ be the set of joinings of $\mu$ to $\nu$
(often called couplings), i.e. the set of Borel probabilities $m$ on $X\times
X$ whose marginals on the first and second factors are $\mu,\nu$,
respectively. Extending [S] from the case where each $X_{s}$ was finite with
discrete metric, define Definition: The Steif distance between $\mu$ and
$\nu\in\mathcal{P}$ is

(2) $\bar{d}(\mu,\nu)=\inf_{m\in M}\sup_{s\in S}m(d_{s}).$

It is not difficult to check (see [M1] for $D$) that both $D$ and $\bar{d}$
are metrics on $\mathcal{P}$ and $\mathcal{P}$ is complete with respect to
each. Theorem: $D=\bar{d}$

##  3\. Proof

Proof: Firstly, by homogeneity of degree one,

$D(\mu,\nu)=\sup_{f\in\mathcal{F}:\|f\|\leq 1}(\mu-\nu)(f).$

Let $E=\\{e=(e_{s})_{s\in S}\in\mathbb{R}_{+}^{S}:\sum_{s\in S}e_{s}\leq
1\\}$. For $e\in E$, let

$c_{e}(x,y)=\sum_{s\in S}e_{s}d_{s}(x,y)$

and

$F_{e}=\\{f:X\to\mathbb{R}:\forall x,y\in X,f(x)-f(y)\leq c_{e}(x,y)\\}.$

Then $f\in\cup_{e\in E}F_{e}$ implies $\|f\|\leq 1$ because if $f\in F_{e}$
then for all $s\in S$ and $x,y\in X$ agreeing on $s$, $f(x)-f(y)\leq
e_{s}d_{s}(x,y)$. So $\Delta_{s}(f)\leq e_{s}$, thus summing over $s\in S$,
$\|f\|\leq 1$. Conversely, $\|f\|\leq 1$ implies $f\in\cup_{e\in E}F_{e}$
because choose an enumeration of $S$ and change sequentially the components of
$x$ to those of $y$ to obtain $f(x)-f(y)\leq\sum_{s\in
S}\Delta_{s}(f)d_{s}(x,y)$. But $\sum_{s\in S}\Delta_{s}(f)=\|f\|\leq 1$ and
$\Delta_{s}(f)\geq 0$, so $\Delta(f)\in E$, thus $f\in F_{\Delta(f)}$. The
supremum over $f\in\cup_{e\in E}F_{e}$ is the same as the supremum over $e\in
E$ of the supremum over $f\in F_{e}$. Thus,

(3) $D(\mu,\nu)=\sup_{e\in E}\sup_{f\in F_{e}}(\mu-\nu)(f).$

Secondly, $\sup_{s\in S}m(d_{s})=\sup_{e\in E}\sum_{s\in S}e_{s}m(d_{s})$,
because denote the lefthand side by $u$ and let $\varepsilon>0$ then $\exists
s^{\prime}\in S$ with $m(d_{s^{\prime}})\geq u-\varepsilon$, so choose
$e_{s^{\prime}}=1$ and the rest of $e_{s}=0$ to get the righthand side at
least $u-\varepsilon$; conversely, $\sum_{s\in S}m(d_{s})\leq\sum_{s\in
S}e_{s}u\leq u$. So

$\bar{d}(\mu,\nu)=\inf_{m\in M}\sup_{e\in E}\sum_{s\in S}e_{s}m(d_{s}).$

This is at least $\sup_{e\in E}\inf_{m\in M}\sum_{s\in S}e_{s}m(d_{s})$
because for any $e^{\prime}\in E,m\in M$,

$\sup_{e\in E}\sum_{s\in S}e_{s}m(d_{s})\geq\sum_{s\in
S}e^{\prime}_{s}m(d_{s}).$

Taking the infimum over $m\in M$, $\inf_{m\in M}\sup_{e\in E}\sum_{s\in
S}e_{s}m(d_{s})\geq\inf_{m\in M}\sum_{s\in S}e^{\prime}_{s}m(d_{s})$. Taking
the supremum over $e^{\prime}\in E$,

$\inf_{m\in M}\sup_{e\in E}\sum_{s\in S}e_{s}m(d_{s})\geq\sup_{e^{\prime}\in
E}\inf_{m\in M}\sum_{s\in S}e^{\prime}_{s}m(d_{s}).$

$\bar{d}(\mu,\nu)$ is also at most $\sup_{e\in E}\inf_{m\in M}\sum_{s\in
S}e_{s}m(d_{s})$ because for all $\varepsilon>0$, $e\in E$, there exists
$m^{\prime}_{e,\varepsilon}\in M$ such that

$\inf_{m\in M}\sum_{s\in S}e_{s}m(d_{s})+\varepsilon\geq\sum_{s\in
S}e_{s}m^{\prime}_{e,\varepsilon}(d_{s}).$

So for all $\varepsilon>0$,

$\sup_{e\in E}\inf_{m\in M}\sum_{s\in
S}e_{s}m(d_{s})+\varepsilon\geq\sup_{e\in E}\sum_{s\in
S}e_{s}m^{\prime}_{e,\varepsilon}(d_{s})\geq\inf_{m\in M}\sup_{e\in
E}\sum_{s\in S}e_{s}m(d_{s}).$

This holds for all $\varepsilon>0$ so the result
$\bar{d}(\mu,\nu)\leq\sup_{e\in E}\inf_{m\in M}\sum_{s\in S}e_{s}m(d_{s})$
follows. Combining the above two results,

$\bar{d}(\mu,\nu)=\sup_{e\in E}\inf_{m\in M}\sum_{s\in S}e_{s}m(d_{s}).$

Thus, using linearity of integration and the definition of $c_{e}$,

(4) $\bar{d}(\mu,\nu)=\sup_{e\in E}\inf_{m\in M}m(c_{e}).$

Thirdly, for all $e\in E$, $c_{e}$ is a semi-metric on $X$, so by Kantorovich-
Rubinstein duality, e.g. Theorem 5.10(i) of [Vi],

(5) $\sup_{f\in F_{e}}(\mu-\nu)(f)=\inf_{m\in M}m(c_{e}).$

Taking the supremum over $e\in E$ and using equations (3,4) yields the desired
result:

$D(\mu,\nu)=\bar{d}(\mu,\nu).$

∎

## Acknowledgements

We are grateful to Jeff Steif for bringing his metric to our attention and for
correspondence on the topic.

## Appendix: Clarification of Appendix of [M2]

We take the opportunity to clarify the Appendix to [M2]. For $c_{e}=\sum_{s\in
S}e_{s}d_{s}$ and $\mu,\nu\in\mathcal{P}$, it addressed maximising
$\mu(f)+\nu(g)$ over pairs of functions $f,g:X\to\mathbb{R}$ subject to
$f(x)+g(y)\leq c_{e}(x,y)$ for all $x,y\in X$. To use linear programming
results, the discussion there was restricted to the case of $X$ finite, but
the analysis to follow here applies in full generality if maximum is replaced
by supremum.

It was stated that “For fixed $e$, the maximum is attained by $g=-f$, by the
Kantorovich-Rubinstein theorem applied to cost function $\sum_{s\in
S}e_{s}d_{s}(x_{s},y_{s})$.” What was intended to be cited is the third
inequality in Theorem 5.10(i) of [Vi], combined with the statement there that
one can impose $\psi$ to be $c$-convex, and an extension of the Particular
Case 5.4 of [Vi] to semi-metrics. The extension was sketched in parentheses at
the end of Particular Case 5.4 of [Vi], but we believe is missing a
hypothesis, so we spell it out here.

Say $c:X\times X\to\mathbb{R}$ is a semi-metric if $\forall x,y,z\in
X,c(x,z)\leq c(x,y)+c(y,z)$ and $c(x,x)=0$. Note that we do not require
symmetry, nor non-negativity. A function $\psi:X\to\mathbb{R}$ is called
$c$-convex if there exists a function $\zeta:X\to\mathbb{R}$ such that
$\psi(x)=\sup_{y}(\zeta(y)-c(x,y))$. $\psi:X\to\mathbb{R}$ is called
1-Lipschitz (with respect to $c$) if for all $x,x^{\prime}\in X$,
$\psi(x)-\psi(x^{\prime})\leq c(x^{\prime},x)$ (note that by reversing the
roles of $x,x^{\prime}$, it also implies
$\psi(x)-\psi(x^{\prime})\geq-c(x,x^{\prime})$). The $c$-transform of a
function $\psi:X\to\mathbb{R}$ is the function
$\psi^{c}(x)=\inf_{y}(\psi(y)+c(y,x))$.

Proposition 1: If $c$ is a semi-metric on $X$ and $\psi:X\to\mathbb{R}$, then
the following are equivalent:

  1. (1)

$\psi$ is $c$-convex;

  2. (2)

$\psi$ is 1-Lipschitz;

  3. (3)

$\psi^{c}=\psi$.

Proof: Suppose $\psi$ is $c$-convex. Then for all $\varepsilon>0$ and $x\in X$
there exists $y\in X$ such that $\psi(x)\leq\zeta(y)-c(x,y)+\varepsilon$.
Also, for all $x^{\prime}\in X$,
$\psi(x^{\prime})\geq\zeta(y)-c(x^{\prime},y)$, so
$\psi(x)-\psi(x^{\prime})\leq c(x^{\prime},y)-c(x,y)+\varepsilon\leq
c(x^{\prime},x)+\varepsilon$ by the triangle inequality. So for all
$x,x^{\prime}\in X$, $\psi(x)-\psi(x^{\prime})\leq c(x^{\prime},x)$, which is
the definition of $\psi$ being 1-Lipschitz.

In the other direction, if $\psi$ is 1-Lipschitz, then for all $x,y\in X$,
$\psi(y)-c(x,y)\leq\psi(x)$ so $\sup_{y}(\psi(y)-c(x,y))\leq\psi(x)$. But if
$y=x$ then $\psi(y)-c(x,y)=\psi(x)$, using $c(x,x)=0$. Thus
$\sup_{y}(\psi(y)-c(x,y))=\psi(x)$, showing that $\psi$ is $c$-convex with
$\zeta=\psi$.

Next, suppose $\psi$ is 1-Lipschitz. Then for all $x,y\in X$,
$\psi(x)\leq\psi(y)+c(y,x)$. So $\psi(x)\leq\inf_{y}(\psi(y)+c(y,x))$. The
right hand side is the definition of $\psi^{c}(x)$. Inserting $y=x$ and using
$c(x,x)=0$ we see also that $\psi(x)\geq\psi^{c}(x)$. So $\psi^{c}=\psi$.

Conversely, if $\psi=\psi^{c}$ then for all $x\in X$,
$\psi(x)=\inf_{y}(\psi(y)+c(y,x))$. Thus for all $\varepsilon>0$ and $x\in X$,
there exists $y$ with $\psi(y)+c(y,x)\leq\psi(x)+\varepsilon$. Also, for all
$x^{\prime}\in X$, $\psi(x^{\prime})\leq\psi(y)+c(y,x^{\prime})$. So
$\psi(x^{\prime})-\psi(x)\leq c(y,x^{\prime})-c(y,x)+\varepsilon\leq
c(x,x^{\prime})+\varepsilon$ by the triangle inequality. Hence
$\psi(x^{\prime})-\psi(x)\leq c(x,x^{\prime})$, so $\psi$ is 1-Lipschitz. ∎

Then the third inequality of Theorem 5.10(i) of [Vi] allows one to replace $g$
by $(-f)^{c}$ (the correspondence with his notation is $\phi=g,\psi=-f$). His
statement there that one can impose that $\psi$ be $c$-convex and the above
proposition allow one to replace $(-f)^{c}$ by $-f$. Hence one can take
$g=-f$, as claimed.

Note that Prop.5.8 of [Vi] gives yet another equivalence to $c$-convexity:
$\psi$ is $c$-convex iff $\psi^{cc}=\psi$.

We now give a simple proof that does not refer to the Kantorovich-Rubinstein
theorem, using only the above Proposition 1. Proposition 2: Given
$\mu,\nu\in\mathcal{P}$ and semi-metric $c$ on $X$, the supremum of
$\mu(f)+\nu(g)$ over pairs of functions $f,g:X\to\mathbb{R}$ subject to
$f(x)+g(y)\leq c(x,y)$ for all $x,y\in X$ is equal to the supremum over cases
with $g=-f$. Proof: Firstly, the constraint $f(x)+g(y)\leq c(x,y)$ implies
that for all $y$, $g(y)\leq\inf_{x}(c(x,y)-f(x))$, which is the definition of
$(-f)^{c}(y)$. So $\nu(g)\leq\nu((-f)^{c})$ and for all $x,y\in X$,
$f(x)+(-f)^{c}(y)\leq c(x,y)$. Thus replacing $g$ by $(-f)^{c}$ satisfies the
constraint and does not decrease the objective function.

Secondly, by the same argument one can replace $f$ by $\tilde{f}=(-g)^{c}$.
But $-\tilde{f}$ is $c$-convex, because $(-g)^{c}(x)=\inf_{y}(-g(y)+c(y,x))$
iff $-(-g)^{c}(x)=\sup_{y}(g(y)-c(y,x))$. Hence, by Proposition 1,
$(-\tilde{f})^{c}=-\tilde{f}$. So one can restrict to $f$ satisfying
$(-f)^{c}=-f$.

Combining these, one can restrict $g$ to be $(-f)^{c}$ and we can restrict $f$
to be $(-(-f)^{c})^{c}=f^{c}$, so we can restrict to $g=-f$. ∎

Finally, we remark that the final sentence of the Appendix to [M2] perhaps
left too much to the reader to do, but is fleshed out in section 3.

## References

  * [DM] Diakonova M, MacKay RS, Mathematical examples of space-time phases, Int J Bif Chaos 21 (2011) 2297–304.
  * [D] Dobrushin RL, Prescribing a system of random variables by conditional distributions, Theory Prob. Appl. 15 (1970) 458–86.
  * [FH] Föllmer H, Horst U, Convergence of locally and globally interacting Markov chains, Stoch Proc Appln 96 (2001) 99–121.
  * [L] Liggett TM, Interacting particle systems (Springer, 1985).
  * [M1] MacKay RS, Robustness of Markov processes on large networks, J Diff Eq & Appl 17 (2011) 1155–67.
  * [M2] MacKay RS, Management of complex dynamical systems, Nonlinearity 31 (2018) R52–65.
  * [OW] Ornstein DS, Weiss B, Statistical properties of chaotic systems, Bull. Am. Math. Soc. 24 (1991) 11–116.
  * [S] Steif JE, Convergence to equilibrium and space-time Bernoullicity for spin systems in the $M<\varepsilon$ case, Ergod Th Dyn Sys 11 (1991) 547–575.
  * [Va] Vasershtein LN, Markov processes over denumerable product of spaces describing large systems of automata. Problemy Peredachi Informatsii 5 (1969) 64–72.
  * [Vi] Villani C, Optimal Transport (Springer, 2009).