# exact-kantorovich: Exact Kantorovich distance between finite probability measures.

[ bsd3, library, math, optimization ] [ Propose Tags ]

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.

## Modules

[Index] [Quick Jump]

#### Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

• No Candidates
Versions [RSS] 0.1.0.0 CHANGELOG.md base (>=4.7 && <5), containers (>=0.6.5.1 && <0.7), extra (>=1.7 && <1.8), matrix (>=0.3.6.0 && <0.4), monad-logger (>=0.3.40 && <0.4), simplex-method (>=0.2.0.0 && <0.3) [details] BSD-3-Clause 2024 Stéphane Laurent Stéphane Laurent laurent_step@outlook.fr Math, Optimization https://github.com/stla/exact-kantorovich#readme head: git clone https://github.com/stla/exact-kantorovich by stla at 2024-05-08T06:40:23Z NixOS:0.1.0.0 22 total (3 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2024-05-08

[back to package description]

# 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.