exact-kantorovich

Exact Kantorovich distance between finite probability measures.

This small package allows to compute the exact Kantorovich distance between two finite probability measures. This assumes that the probability masses are rational numbers and that the distance function takes rational values only.

---

Let's say you have the two probability measures with masses $(1/7, 2/7, 4/7)$ and $(1/4, 1/4, 1/2)$, both distributed on the set ${1, 2, 3}$, and you want to get the Kantorovich distance between them when this set is endowed with the distance function $d(i, j) = |i - j|$. To get it with this package, you will use the kantorovich function. It has four arguments. The first two ones are the two random variables corresponding these probability measures, and a random variable is defined as a map from its states set to the rational numbers; this map assigns to each element its probability mass:

import Data.Map.Strict ( fromList )
import Data.Ratio ( (%) )
mu, nu :: RandomVariable Int
mu = fromList $ zip [1, 2, 3] [1%7, 2%7, 4%7]
nu = fromList $ zip [1, 2, 3] [1%4, 1%4, 1%2]

The third one is the distance function; it must return a positive rational number:

dist :: (Int, Int) -> Rational
dist (i, j) = toRational $ abs (i - j)

And the fourth one is a Boolean value that you set to True if you want to print to the stdout stream some details of the simplex algorithm performed by the kantorovich function:

import Math.Optimization.Kantorovich
result <- kantorovich mu nu dist False

The output of the kantorovich function has type IO (Maybe (KantorovichResult a b)) where here a = b = Int and the type KantorovichResult a b is the pair of types (Rational, RandomVariable (a, b)). The first element of an object of a KantorovichResult object represents the value of the Kantorovich distance and the second element represents a solution of the underlying linear programming problem, that is to say a joining of the two probability measures that achieves the Kantorovich distance.

Here is the value of the Kantorovich distance for our example:

import Data.Maybe ( fromJust )
fst $ fromJust result
-- 5 % 28

You can display the solution in the style of a matrix with the help of the prettyKantorovichSolution function:

putStrLn $ prettyKantorovichSolution result

This prints:

┌                      ┐
│  1 % 7  0 % 1  0 % 1 │
│ 3 % 28 5 % 28  0 % 1 │
│  0 % 1 1 % 14  1 % 2 │
└                      ┘

That's all. There is no other function exported by this package.