Probabilistic Bisimulation - Semantics of Probabilistic Processes: An Operational Approach - page 32

The original transportation problem, formulated by the French mathematician G.
Monge in 1781 [ 32 ], consists of finding an optimal way of shovelling a pile of sand
into a hole of the same volume; see Fig. 3.2 . In the 1940s, the Russian mathematician
and economist L. V. Kantorovich, who was awarded a Nobel prize in economics in
1975 for the theory of optimal allocation of resources, gave a relaxed formulation of
the problem and proposed a variational principle for solving it [ 25 ]. Unfortunately,
Kantorovich's work went unrecognised for a long time. The later-known Kantorovich
metric has appeared in the literature under different names, because it has been
rediscovered historically several times from different perspectives. Many metrics
known in measure theory, ergodic theory, functional analysis, statistics etc. are
special cases of the general definition of the Kantorovich metric [ 33 ]. The elegance
of the formulation, the fundamental character of the optimality criterion as well as the
wealth of applications that keep arising place the Kantorovich metric in a prominent
position among the mathematical works of the twentieth century. In addition, this
formulation can be computed in polynomial time [ 34 ], which is an appealing feature
for its use in solving applied problems. For example, it is widely used to solve a variety
of problems in business and economy such as market distribution, plant location,
scheduling problems etc. In recent years the metric attracted the attention of computer
scientists [ 35 ]: it has been used in various different areas in computer science such
as probabilistic concurrency, image retrieval, data mining, bioinformatics etc.
Roughly speaking, the Kantorovich metric provides a way of measuring the dis-
tance between two distributions. Of course, this requires first a notion of distance
between the basic elements that are aggregated into the distributions, which is often
referred to as the ground distance . In other words, the Kantorovich metric defines
a “lifted” distance between two distributions of mass in a space that is itself en-
dowed with a ground distance. There is a host of metrics available in the literature
(see e.g. [ 36 ]) to quantify the distance between probability measures; see [ 37 ] for
a comprehensive review of metrics in the space of probability measures. The Kan-
torovich metric has an elegant formulation and a natural interpretation in terms of
the transportation problem.
We now recall the mathematical definition of the Kantorovich metric. Let ( X , m )
be a separable metric space. (This condition will be used by Theorem 3.2 below.)

Definition 3.3 Given any two Borel probability measures ʔ and ʘ on X , the
Kantorovich distance between ʔ and ʘ is defined by

sup

fdʘ | |

fdʔ

1 . K ( ʔ , ʘ ) = − f || ≤

sup x = y | f ( x ) − f ( y ) | where ||·|| is the Lipschitz seminorm defined by || f || = for a

m ( x , y )

function f : X .

The Kantorovich metric has an alternative characterisation. We denote by P ( X )
the set of all Borel probability measures on X such that for all z

ₒ R

∈ ∈

X ,if ʔ P ( X )

then X m ( x , z ) ʔ ( x ) <

∞

. We write M ( ʔ , ʘ ) for the set of all Borel probability
measures on the product space X

× X with marginal measures ʔ and ʘ , i.e. if

ʓ ∈ M ( ʔ , ʘ ) then y ∈ X dʓ ( x , y ) = dʔ ( x ) and x ∈ X dʓ ( x , y )

= dʘ ( y ) hold.